Evaluation of Decoding Delay in the Perpetual Coding

Document Type : Original Article

Authors

Department of Computer Science and Information Technology/ IASBS University

Abstract

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.

Keywords

References

[1] Luby, “Lt codes”, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 271 – 280.
[2] Shokrollahi, “Raptor codes”, IEEE Transactions on Information Theory, Vol.52, NO.6, June 2006, pp. 2551–2567.
[3] Ahlswede, N.Cai, S.Y.Li, R.W Yeung, “Network information flow”, IEEE Transactions on Information Theory, Vol. 46, NO. 4, Jul 2000, pp. 1204 – 1216.
[4] Y.R.Li, R.W.Yeung, N.Cai, “Linear network coding”, IEEE Transactions on Information Theory
Vol.52, NO.2, Feb 2003, pp. 371–381.
[5] Katti, H.Rahul, W.Hu, D.Katabi, M.Médard, J.Crowcroft. “XORs in the air: Practical wireless network coding”. In ACM
SIGCOMM computer communication review, volume 36, ACM, 2006, pages 243–254.
[6] Janus, M.V.Pedersen, F.Fitzek, M.Medard,, “A perpetual code for network coding”, 2014
IEEE 79th Vehicular Technology Conference (VTC Spring), May 2014, pp. 1– 6.
[7] P.Pahlevani, S.Crisóstomo, D.E. “An analytical
model for perpetual network codes in packet erasure channels”. In International Workshop on Multiple Access Communications, Springer, 2016, pages 126–135.
[8] Pedersen, J.Heide, F.H.Fitzek, “KODO: An open and research oriented network coding library”, Springer, 2011, pp. 145–152.
[9] Sehat, P.Pahlevani, “On the probability of partial decoding in sparse network coding”, arXiv preprint arXiv:1907.12051, 2019
Danilo, W.Zeng, F.Kschischang, “Sparse network coding with overlapping classes”, workshop on network coding,Theory, and Applications,2009, pp. 74-79
Janus, M.V.Pedersen, F.Fitzek, M.Medard, “On code parameters and coding vector representation for practical rlnc”. In: 2011 IEEE nternational Conference on Communications (ICC), 2011, pp 1-5
Zarei, P. Pahlevani and M. Davoodi, “On the Partial Decoding Delay of Sparse Network Coding”, IEEE Communications Letters, vol. 22, no. 8, 2018, pp. 1668-1671.
Feizi, DE. Lucani, M.Medard “Tunable sparse network coding” ,22th International Zurich Seminar on Communications (IZS), Eidgen Eidgenossische Technische Hochschule Zurich, 2012
Karzand, D. Leith, J.Cloud, “Design of FEC for low delay in 5G”, IEEE Journal on Selected Areas in Communications, 2017, pp.1783-1793
Gabriel, S. Wunderlich, S. Pandi, F. H. P. Fitzek and M. Reisslein, “Caterpillar RLNC With Feedback (CRLNC-FB): Reducing Delay in Selective Repeat ARQ Through Coding”, IEEE Access, vol. 6 2018, pp. 44787-44802.
Nguyen, E. Tasdemir, G. T. Nguyen, D. E. Lucani, F. H. P. Fitzek and M. Reisslein, "DSEP Fulcrum: Dynamic Sparsity and Expansion Packets for Fulcrum Network Coding," in IEEE Access, vol. 8, 2020, pp. 78293-78314.
Advanced Signal Processing
Volume 4, Issue 1 - Serial Number 5
August 2020
Pages 111-119

Files

Share

How to cite

Statistics