On Design and Efficient Decoding of Sparse Random Linear Network Codes

While random linear network coding is known to improve network reliability and throughput, its high costs for delivering coding coefficients and decoding represent an obstacle where nodes have limited power to transmit and decode packets. In this paper, we propose sparse network codes for scenarios where low coding vector weights and low decoding cost are crucial. We consider generation-based network codes where source packets are grouped into overlapping subsets called generations, and coding is performed only on packets within the same generation in order to achieve sparseness and low complexity. A sparse code is proposed that is comprised of a precode and random overlapping generations. The code is shown to be much sparser than existing codes that enjoy similar code overhead. To efficiently decode the proposed code, a novel low-complexity overhead-optimized decoder is proposed where code sparsity is exploited through local processing and multiple rounds of pivoting. Through extensive simulation comparison with existing schemes, we show that short transmissions of the order of 10² -10³ source packets, a denomination convenient for many applications of interest, can be efficiently decoded by the proposed decoder.