Broadcasting with side information

Ramakrishna Gummadi, Amin Shokrollahi, Ramavarapu Sreenivas

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the problem of multicasting data from a source to receivers that possess arbitrary subsets of the data apriori as side information. Fountain codes, which are an ideal solution to the standard multicasting problem without any side information, have also been proposed as a potential approach for the side information problem in multiple independent studies recently. Relevant to such a context, we formulate and study an optimization problem over degree distributions to minimize the overhead necessary for complete decoding, and prove that: (i) Degree distributions converging to the standard soliton distribution cannot exploit side information in terms of the overhead necessary for complete decoding. (ii) An asymptotic shifted soliton distribution achieves an overhead which is within a constant factor (< 2) of the optimal overhead (iii) There exist no degree distributions which achieve asymptotically optimal overhead for any non trivial constant fraction of the data as side information. While (iii) is discouraging, this limitation can be sidestepped by using systematic versions, where intermediate symbols are generated from the source symbols, to which the fountain code is then applied. One important implication of this is that the systematic versions are in a sense indispensable to achieve asymptotic rate optimality for the side information problem.

Original languageEnglish (US)
Title of host publicationIEEE Information Theory Workshop 2010, ITW 2010
StatePublished - 2010
EventIEEE Information Theory Workshop 2010, ITW 2010 - Cairo, Egypt
Duration: Jan 6 2010Jan 8 2010

Publication series

NameIEEE Information Theory Workshop 2010, ITW 2010


OtherIEEE Information Theory Workshop 2010, ITW 2010

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science


Dive into the research topics of 'Broadcasting with side information'. Together they form a unique fingerprint.

Cite this