Bipartite Index Coding Protocol

Abstract—In literature, the capacity of the Broadcast Packet Erasure Channel (BPEC) with feedback was derived and proto-cols were proposed. Out of these protocols, only few can be put in practice, because of their limitations. Mainly, these techniques impose impractical feedback assumption, which requests the feedback to be at the end of each time-slot. In this work, a novel protocol for reliable unicast trans-missions over lossy broadcast links is proposed. Our approach represents a variation on the index coding theme, with bursty feedback. A satellite scenario, with the user-downlinks modelled as BPEC, is considered. Each user is downloading a different file composed of a set of distinct packets. Resulting from the channel broadcast nature, unintended users may overhear their neighbours packets. Using the side information and a bipartite graph, to model the problem at hand, allow us to build only instantly-decodable linear combinations, which are decoded by bit-wise XOR operations. These retransmissions occur at the end of every transmission round instead of every time-slot, which is a very realistic assumption in terrestrial wireless, cellular or satellite networks. Our protocol can easily serve an arbitrary number of users. Numerical results show that using our proposed scheme, rates very close to the capacity of the BPEC with feedback can be achieved. I