ارزیابی تأخیر کدگشایی در روش کدگذاری پرپچوال

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشکده علوم رایانه و فناوری اطلاعات، دانشگاه علوم پایه زنجان

2 دانشکده علوم رایانه و فناوری اطلاعات/دانشگاه علوم پایه زنجان

چکیده

کدگذاری پرپچوال روش کدگذاری تنک است که ضرایب به صورت ساختار یافته برای عملیات کدگذاری استفاده می­شود. نشان داده شده است که این روش پیچیدگی محاسباتی روش کدگذای خطی تصادفی را کاهش می­دهد. هدف از این مقاله بیان یک مدل ریاضی برای نشان دادن عملکرد کدگذاری پرپچوال است و  نشان دادن این مطلب که در کدگذاری پرپچوال در کانال­های دارای خطا بسته­های وابسته­ی خطی ارسالی به  شدت به پارامتر عرض  بستگی دارد. پارامتر عرض به تعداد ضرایب غیر صفر پشت سر هم که در هر بسته­ی کد شده بعد از عنصر محور می­آید گفته می­شود. سپس یک مدل تحلیلی ریاضی برای تعداد بسته­های ارسال شده ارائه می­شود که مدل ارائه شده تعداد بسته­ها را تا دور دوم پیشبینی می­کند. در نهایت یک توزیع احتمال کدگشایی بسته‌ها در دور  ام‌ را بدست می‌آوریم و آنرا از طریق شبیه سازی اعتبار سنجی می‌کنیم. نتایج نشان می­دهند که برای احتمال خطای کوچک و  کم، مقدار سربار حتی می­تواند به عددی نزدیک 70% برسد. برای کاهش سربار فرستنده باید مقدار  به صورت درست انتخاب شود و انتخاب درست به شدت به احتمال خطای کانال وابسته است. همچنین برای  و اندازه­ی نسل برابر با  و احتمال پایین خطا در کانال ارتباطی، گره مقصد به طور میانگین 70%  بسته­ی اضافی دریافت می­کند. با افزایش ، سربار کمتر می­شود و برای  این مقدار قابل چشم پوشی است. همچنین نشان دادیم که روش ارائه­ شده به دلیل کاهش 44/37 درصدی میانگین تأخیر کدگشایی، بهبود مناسبی در کارایی سیستم­ ایجاد می­کند.

کلیدواژه‌ها

عنوان مقاله [English]

Evaluation of Decoding Delay in the Perpetual Coding

نویسندگان [English]

  • Sanaz Mohammadi 1
  • Peyman Pahlevani 2
1 Department of Computer Science and Information Technology/ IASBS University
2 Department of Computer Science and Information Technology/ IASBS University
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Network
  • Channel Coding
  • RLNC
  • Perpetual
  • Decoding

مراجع

[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.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار