XOR-Based Encoding With Instantaneous Decoding for the Broadcast Erasure Channel With Feedback: The Three-User Case

Abstract

We study the case of a three-user broadcast erasure channel with multiple unicast traffic sessions, where feedback from the users is fed back to the transmitter in the form of positive acknowledgment (ACK)/negative acknowledgment (NACK) messages. The capacity region of this system has been recently derived and two capacity-achieving coding algorithms employing intersession linear network coding have been proposed. Since these algorithms suffer from large computational complexity and decoding delay, our aim, in this paper, is to design a coding algorithm with reduced computational complexity and a low decoding delay that achieves a comparable rate region to the former algorithms. We exclusively consider algorithms that require no knowledge of channel statistics, only perform XOR operations among the packets, and allow for instantaneous decoding by any receiver that successfully receives a packet. We present such an algorithm, named IXOR, which operates on a specially constructed network of virtual queues and, through intelligent packet combining, achieves the capacity under a general condition, which is satisfied in the following settings: 1) spatially independent identically distributed erasure channels with arbitrary values of erasure probability, and 2) spatially independent erasure channels where the maximum erasure probability does not exceed 8/9.