Design of network coding for wireless broadcast and multicast with optimal decoders

This paper considers the design of network coding schemes for reliable wireless broadcast and multicast transmissions, in which the same packet is broadcast to a group of receivers. Network coding across multiple broadcasted packets is employed to generate redundant packets for the broadcast retransmissions so that the lost packets can be recovered. It is assumed that optimal decoders are employed at the receivers and the focus is on the design of short block codes with small numbers of redundant bits. To this end, use if first made of the residual graph representation to calculate the error probability of the optimal decoder. Then two code design schemes are proposed to minimize the error probability, including a low-complexity deterministic greedy code design algorithm as well as a stochastic code construction algorithm inspired by the simulated annealing technique. Extensive simulation studies have been carried out to assess the performance of the proposed schemes. It is seen that for a given number of retransmissions, the proposed network coding schemes can considerably increase the average number of recovered packages per user at the receivers and thereby improve the spectral efficiency over traditional coding methods.