Broadcast Erasure Channel with Feedback and Message Side Information, and Related Index Coding Results
Athanasios Papadopoulos, Leonidas G. Georgiadis · IEEE Transactions on Information Theory · 2017
We consider the N -receiver broadcast erasure channel with feedback and message side information at the receivers prior to beginning of transmission. Specifically, the transmitter must deliver different, independent messages to each of the receivers, and each receiver knows a function of these messages before transmission begins. This situation can arise in multi-hop wireless networks, where a receiver may overhear transmissions consisting of possibly encoded combinations of messages (e.g., encoded using a network coding technique) prior to beginning of transmission over a given broadcast channel. We provide an outer bound to the capacity region of this system. For the case, where each message consists of a number of symbols taking values in a finite field and each receiver knows linear combinations of these symbols, the outer bound is given in terms of ranks of matrices expressing the linear combinations. For the latter case and when N=2 , the outer bound is tight under mild conditions on the limiting behavior of the ranks of matrices expressing the side information. We provide a capacity achieving code for this case. The special case, where each receiver either knows the entire message of another receiver or has no information about it, constitutes a generalization of the index coding problem that incorporates channel erasures. For this instance, and when there are no channel errors, we show that the outer bound reduces to the known maximum weighted acyclic induced subgraph bound.