Evaluation of Decoding Delay in the Perpetual Coding

Perpetual coding is a sparse coding method in which coefficients are used in a structured way for coding operations. It has been shown that this method reduces the computational complexity of the random linear network coding method. The purpose of this paper is to articulate a mathematical model to illustrate the performance of perpetual coding, and to show that in a perpetual coding with the presence of an erasure channel 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 coefficients present in each coded packet after a pivot element. Then, a mathematical analytical model for the number of transmitted packets is provided, which predicts the number of packets until the second round. Finally, we obtain the probability of the packet’s decoding in round  and validate it by simulation. The results show that for low error probability and small on the link, overhead value can even reach a number close to 70%. To reduce the transmitter overhead, the value must be selected correctly, and the correct choice of is highly dependent on the probability of channel error. Also, for , generation size  and low erasure probability on the link, a destination can receive up to 70% overhead on average. Moreover, by increasing the width, the overhead decreases and for it becomes negligible. We show that our mechanism reduces the delay by 37.44 percent.