Successive Segmentation-Based Coding for Broadcasting over Erasure Channels

Motivated by error correction coding in multimedia applications, we study the problem of broadcasting a single common source to multiple receivers over heterogeneous erasure channels. Each receiver is required to partially reconstruct the source sequence by decoding a certain fraction of the source symbols. We propose a coding scheme that requires only off-the-shelf erasure codes and can be easily adapted as users join and leave the network. Our scheme involves splitting the source sequence into multiple segments and applying a systematic erasure code to each such segment. We formulate the problem of minimizing the transmission latency at the server as a linear programming problem and explicitly characterize an optimal choice for the code rates and segment sizes. Through numerical comparisons, we demonstrate that our proposed scheme outperforms both separation-based coding schemes and degree-optimized rateless codes and performs close to a natural outer (lower) bound in certain cases. We further study individual user decoding delays for various orderings of segments in our scheme. We provide closed-form expressions for each individual user's excess latency when parity checks are successively transmitted in both increasing order and decreasing order of their segment's coded rate and also qualitatively discuss the merits of each order.