Sparse Network Coding (SNC) has been a promising network coding scheme as an improvement for Random Linear Network Coding (RLNC) in terms of the computational complexity. However, in this literature, there has been no analytical expressions for the probability of decoding a fraction of source messages after transmission of some coded packets. In this work, we looked into the problem of the probability of decoding a fraction of source messages, i.e., partial decoding, in the decoder for a system which uses SNC. We exploited the Principle of Inclusion and Exclusion to derive expressions of partial decoding probability. The presented model predicts the probability of partial decoding with an average deviation of 6 . Our results show that SNC has a great potential for recovering a fraction of the source message, especially in higher sparsity and lower Galois Field size. Moreover, to achieve a better probability of partial decoding throughout transmissions, we define a sparsity tuning scheme that significantly increases the probability of partial decoding. Our results show that this tuning scheme achieves a 16 improvement in terms of probability of decoding a fraction of source packets with respect to traditional SNC.
Perpetual codes provide a sparse, but structured coding for fast encoding and decoding. In this work, we illustrate that perpetual codes introduce linear dependent packet transmissions in the presence of an erasure channel. We demonstrate that the number of linear dependent packet transmissions is highly dependent on a parameter called the width ( ( )), which represents the number of consecutive non-zero coding coefficient present in each coded packet after a pivot element. We provide a mathematical analysis based on the width of the coding vector for the number of transmitted packets and validate it with simulation results. The simulations show that for ( = 5 ), generation size (g = 256 ), and low erasure probability on the link, a destination can receive up to (70 ) overhead in average. Moreover, increasing the width, the overhead contracts, and for ( 60 ) it becomes negligible. Random Linear Network Coding (RLNC) provides a theoretically efficient method for coding. The drawbacks associated with it are the complexity of the decoding and the overhead resulting from the coding vector. This adds to the overall energy consumption and is problematic for computational limited and battery driven platforms. In this work we present an approach to RLNC where the code is sparse and non-uniform. The sparsity allow for fast encoding and decoding, and the non- uniform protection of symbols enables recoding where the produced symbols are indistinguishable from those encoded at the source. The results show that the approach presented here provides a better trade- off between coding throughput and code overhead. In particular it can provide a coding overhead identical to RLNC but at significantly reduced computational complexity. It also allow for easy adjustment of this trade-off, which make it suitable for a broad range of platforms and applications. Finally it is easy to perform recoding and coding vectors can be efficiently represented.