TY - GEN

T1 - Broadcasting with side information

AU - Gummadi, Ramakrishna

AU - Shokrollahi, Amin

AU - Sreenivas, Ramavarapu

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77954826882&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954826882&partnerID=8YFLogxK

U2 - 10.1109/ITWKSPS.2010.5503175

DO - 10.1109/ITWKSPS.2010.5503175

M3 - Conference contribution

AN - SCOPUS:77954826882

SN - 9781424463725

T3 - IEEE Information Theory Workshop 2010, ITW 2010

BT - IEEE Information Theory Workshop 2010, ITW 2010

T2 - IEEE Information Theory Workshop 2010, ITW 2010

Y2 - 6 January 2010 through 8 January 2010

ER -