On The Analysis of Decoding Delay of LT and Sparse Network Codes

Sparse Network Coding (SNC) is introduced as a mechanism to alleviate the decoding and encoding computational complexity of Random Linear Network Coding (RLNC) by selecting a large fraction of zero-valued coding coefficients in the encoding matrix. One of other advantages of a SNC is the possibility to carry out partial decoding, i.e., decoding some source packets prior to receiving all the required coded packets to recover the whole coded data. In this paper, by taking advantage of the SNC’s partial decoding, we study SNC as a technique for reducing the Average Decoding Delay (ADD) per packet in real-time multimedia and delay critical applications. We focus on characterizing the ADD per packet for SNC considering the effects of the finite field size and compare the SNC with LT codes in terms of the ADD per packet. We validate our model using simulations and show that for different finite field, sparsity level and generation sizes the SNC scheme outperforms the LT codes with regard to the imposed ADD per packet to recover a generation