Дослідження побудови регулярних LDPC-кодів з випадковою структурою на основі алгоритмів прогресивного зростання ребер і видалення коротких циклів

Автор(и)

DOI:

https://doi.org/10.15587/1729-4061.2021.225852

Ключові слова:

LDPC, мала щільність перевірок на парність, PEG, прогресивне зростання ребер, канальне кодування, графи Таннера

Анотація

У даній статті досліджується побудова LDPC-кодів (з малою щільністю перевірок на парність) з випадковою структурою з використанням алгоритму прогресивного зростання ребер (PEG) і двох запропонованих алгоритмів видалення коротких циклів (алгоритм CB1 і CB2; CB означає Cycle Break (Розрив циклів)).

Progressive Edge-Growth (Прогресивне зростання ребер) – це алгоритм комп'ютерного проектування LDPC-кодів з випадковою структурою, який полягає у створенні графа Таннера (дводольного графа, що представляє матрицю перевірки на парність коригуючого коду каналу) з якомога меншою кількістю коротких циклів. Короткі цикли, особливо найкоротші з довжиною 4 ребра, в графах Таннера LDPC-кодів здатні погіршити продуктивність алгоритму декодування, оскільки після певного числа ітерацій декодування інформація, передана через його ребра, перестає бути незалежною.

Основним внеском статті є унікальний підхід до процесу видалення коротких циклів у вигляді алгоритму CB2, який видаляє ребра з матриці перевірки на парність коду без зменшення мінімальної відстані Хеммінга коду. Два алгоритми видалення циклів можуть бути використані для поліпшення коригуючої ефективності PEG-генерованих (або будь-яких інших) LDPC-кодів, представляються досягнуті результати. Всі ці алгоритми були використані для створення PEG LDPC-коду, який конкурує з найбільш відомим PEG-генерованим LDPC-кодом з аналогічними параметрами, наданим одним із засновників LDPC-кодів.

Описані методи генерації згаданих коригуючих кодів, а також моделювання, в якому порівнюється коригуюча ефективність вихідних кодів, згенерованих алгоритмом PEG, PEG-кодів, оброблених алгоритмом CB1 або CB2, а також зовнішнього PEG-коду, опублікованого одним із засновників LDPC-кодів.

Спонсор дослідження

  • This paper was written as a part of following scientific projects: Slovak Research and Development Agency APVV-17-0631 (Co-existence of photonics sensor systems and networks in the framework of internet of things.)

Біографії авторів

Viktor Durcek, University of Zilina

PhD

Department of Multimedia and Information-Communication Technologies

Michal Kuba, University of Zilina

PhD

Department of Multimedia and Information-Communication Technologies

Milan Dado, University of Zilina

Professor, PhD

Department of Multimedia and Information-Communication Technologies

Посилання

  1. Ryan, W. E., Lin, S. (2009). Channel Codes: Classical and Modern. Cambridge University Press. doi: https://doi.org/10.1017/cbo9780511803253
  2. Vandendriessche, P. (2009). Some low-density parity-check codes derived from finite geometries. Designs, Codes and Cryptography, 54 (3), 287–297. doi: https://doi.org/10.1007/s10623-009-9324-9
  3. Gallager, R. (1962). Low-density parity-check codes. IEEE Transactions on Information Theory, 8 (1), 21–28. doi: https://doi.org/10.1109/tit.1962.1057683
  4. MacKay, D. J. C., Neal, R. M. (1996). Near Shannon limit performance of low density parity check codes. Electronics Letters, 32 (18), 1645. doi: https://doi.org/10.1049/el:19961141
  5. MacKay, D. J. C. (1997). Good error-correcting codes based on very sparse matrices. Proceedings of IEEE International Symposium on Information Theory. doi: https://doi.org/10.1109/isit.1997.613028
  6. Arora, K., Singh, J., Randhawa, Y. S. (2019). A survey on channel coding techniques for 5G wireless networks. Telecommunication Systems, 73 (4), 637–663. doi: https://doi.org/10.1007/s11235-019-00630-3
  7. Richardson, T., Urbanke, R. (2008). Modern Coding Theory. Cambridge University Press. doi: https://doi.org/10.1017/cbo9780511791338
  8. Blahut, R. E. (2003). Algebraic Codes for Data Transmission. Cambridge University Press. doi: https://doi.org/10.1017/cbo9780511800467
  9. Fan, J., Xiao, Y., Kim, K. (2008). Design LDPC Codes without Cycles of Length 4 and 6. Research Letters in Communications, 2008, 1–5. doi: https://doi.org/10.1155/2008/354137
  10. Liu, X., Zhang, W., Fan, Z. (2009). Construction of Quasi-Cyclic LDPC Codes and the Performance on the PR4-Equalized MRC Channel. IEEE Transactions on Magnetics, 45 (10), 3699–3702. doi: https://doi.org/10.1109/tmag.2009.2023422
  11. Jiang, X.-Q., Lee, M. H., Wang, H.-M., Li, J., Wen, M. (2016). Modified PEG algorithm for large girth Quasi-cyclic protograph LDPC codes. 2016 International Conference on Computing, Networking and Communications (ICNC). doi: https://doi.org/10.1109/iccnc.2016.7440704
  12. Hailes, P., Xu, L., Maunder, R. G., Al-Hashimi, B. M., Hanzo, L. (2016). A Survey of FPGA-Based LDPC Decoders. IEEE Communications Surveys & Tutorials, 18 (2), 1098–1122. doi: https://doi.org/10.1109/comst.2015.2510381
  13. Prompakdee, P., Phakphisut, W., Supnithi, P. (2011). Quasi Cyclic-LDPC codes based on PEG algorithm with maximized girth property. 2011 International Symposium on Intelligent Signal Processing and Communications Systems (ISPACS). doi: https://doi.org/10.1109/ispacs.2011.6146165
  14. Huang, Y., Cheng, Y., Zhang, Y., Han, H. (2010). Construction of non-binary quasi-cyclic LDPC codes based on PEG algorithm. 2010 IEEE 12th International Conference on Communication Technology. doi: https://doi.org/10.1109/icct.2010.5689251
  15. Uchoa, A. G. D., Healy, C., de Lamare, R. C., Souza, R. D. (2012). Generalised Quasi-Cyclic LDPC codes based on Progressive Edge Growth Techniques for block fading channels. 2012 International Symposium on Wireless Communication Systems (ISWCS). doi: https://doi.org/10.1109/iswcs.2012.6328513
  16. Zongwang Li, Vijaya Kumar, B. V. K. (2004). A class of good quasi-cyclic low-density parity check codes based on progressive edge growth graph. Conference Record of the Thirty-Eighth Asilomar Conference on Signals, Systems and Computers. doi: https://doi.org/10.1109/acssc.2004.1399513
  17. Lei, Y., Dong, M. (2017). An Efficient Construction Method for Quasi-Cyclic Low Density Parity Check Codes. IEEE Access, 5, 4606–4610. doi: https://doi.org/10.1109/access.2017.2678515
  18. Jiang, X.-Q., Hai, H., Wang, H.-M., Lee, M. H. (2017). Constructing Large Girth QC Protograph LDPC Codes Based on PSD-PEG Algorithm. IEEE Access, 5, 13489–13500. doi: https://doi.org/10.1109/access.2017.2688701
  19. McGowan, J. A., Williamson, R. C. (2003). Loop removal from LDPC codes. Proceedings 2003 IEEE Information Theory Workshop (Cat. No.03EX674). doi: https://doi.org/10.1109/itw.2003.1216737
  20. Li, B., Wang, G., Yang, H. (2009). A new method of detecting cycles in Tanner graph of LDPC codes. 2009 International Conference on Wireless Communications & Signal Processing. doi: https://doi.org/10.1109/wcsp.2009.5371660
  21. Hu, P., Zhao, H. (2010). Improved method for detecting the short cycles of LDPC codes. 2010 IEEE International Conference on Information Theory and Information Security. doi: https://doi.org/10.1109/icitis.2010.5689706
  22. Karimi, M., Banihashemi, A. H. (2013). Message-Passing Algorithms for Counting Short Cycles in a Graph. IEEE Transactions on Communications, 61 (2), 485–495. doi: https://doi.org/10.1109/tcomm.2012.100912.120503
  23. Li, J., Lin, S., Abdel-Ghaffar, K. (2015). Improved message-passing algorithm for counting short cycles in bipartite graphs. 2015 IEEE International Symposium on Information Theory (ISIT). doi: https://doi.org/10.1109/isit.2015.7282488
  24. Cho, S., Cheun, K., Yang, K. (2018). A Message-Passing Algorithm for Counting Short Cycles in Nonbinary LDPC Codes. 2018 IEEE International Symposium on Information Theory (ISIT). doi: https://doi.org/10.1109/isit.2018.8437844
  25. Karimi, M., Banihashemi, A. H. (2012). Counting Short Cycles of Quasi Cyclic Protograph LDPC Codes. IEEE Communications Letters, 16 (3), 400–403. doi: https://doi.org/10.1109/lcomm.2012.020212.112311
  26. Su, Z., Qiu, Q., Zhou, H. (2016). Analysis and elimination of short cycles in LDPC convolutional codes. 2016 2nd IEEE International Conference on Computer and Communications (ICCC). doi: https://doi.org/10.1109/compcomm.2016.7924880
  27. Hu, X.-Y., Eleftheriou, E., Arnold, D.-M. (2001). Progressive edge-growth Tanner graphs. GLOBECOM’01. IEEE Global Telecommunications Conference (Cat. No.01CH37270). doi: https://doi.org/10.1109/glocom.2001.965567
  28. MacKay, D. J. C. The Inference Group. Available at: http://www.inference.org.uk/is/

##submission.downloads##

Опубліковано

2021-08-31

Як цитувати

Durcek, V., Kuba, M., & Dado, M. (2021). Дослідження побудови регулярних LDPC-кодів з випадковою структурою на основі алгоритмів прогресивного зростання ребер і видалення коротких циклів. Eastern-European Journal of Enterprise Technologies, 4(9(112), 46–53. https://doi.org/10.15587/1729-4061.2021.225852

Номер

Том 4 № 9(112) (2021): Інформаційно-керуючі системи

Розділ

Інформаційно-керуючі системи

Ліцензія

Авторське право (c) 2021 Viktor Durcek, Michal Kuba, Milan Dado

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.