izvestswsuИзвестия Юго-Западного государственного университетаProceedings of the Southwest State University2223-15602686-6757ЮЗГУ10.21869/2223-1560-2023-27-1-92-110izvestswsu-1092Research ArticleИнформатика, вычислительная техника и управлениеComputer science, computer engineering and IT managmentПостроение LDPC-кодов с использованием модифицированного метода выборки по значимости КоулаConstruction of LDPC Codes Using Cole's Modified Importance Sampling MethodУсатюкВ. С.UsatjukV. S.

Усатюк Василий Станиславович, кандидат технических наук, главный инженер департамента исследований и разработок 

 ул. Краснобогатырская, д. 44, стр. 1, г. Москва 107076, Российская Федерация 

Vasily S. Usatjuk, Head Engineer, R&D department

44, Krasnobogatyrskaya str., p. 1, Moscow 107076, Russian Federation 

usatiuk@t8.ruhttps://orcid.org/0000-0001-5859-1024ЕгоровС. И.EgorovS. I.

Егоров Сергей Иванович, доктор технических наук, доцент, профессор кафедры вычислительной техники

 ул. 50 лет Октября, д. 94, г. Курск 305040, Российская Федерация 

Sergey I. Egorov, Dr. of Sci. (Engineering), Associate Professor

50 Let Oktyabrya str. 94, Kursk 305040, Russian Federation 

sie58@mail.ruООО «Т8»Company T8Юго-Западный государственный университетSouthwest State University20231404202327192110Copyright © Усатюк В.С., Егоров С.И., 20232023Усатюк В.С., Егоров С.И.Usatjuk V.S., Egorov S.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://izvestswsu.elpub.ru/jour/article/view/1092

Целью исследования является модификация метода выборки по значимости Коула для поиска треппинсетов (Trapping Sets) в LDPC-коде, позволяющая ускорить их поиск.Методы. Коул предложил метод поиска треппин-сетов в LDPC-коде путем использования метода выборки по значимости - метода Монте-Карло со смещенной оценкой, провоцирующего отказ алгоритма декодирования в узлах, потенциально содержащихся в треппин-сетах. Его метод позволяет ускорить исследование эффективности LDPC-кодов средней длины в области больших SNR. Модифицированный метод использует свойства автоморфизмов графов Таннера, позволяющие исключить из перебора значительное число символьных узлов. Также модифицированный метод предусматривает упорядоченный перебор по подграфам, содержащим циклы.Результаты. Предложенный метод позволил ускорить поиск треппин-сетов в PEG(1008, 504) LDPC-коде Маккея в 5027 раз по сравнению с методом Веласкеса-Субрамани, в 43 раза быстрее по сравнению с оригинальным методом Коула. В случае (2640, 1320) LDPC-кода Маргулиса предложенный метод в 28 раз быстрее квазициклического метода Веласкеса-Субрамани и в 134 раза быстрее, чем оригинальный метод Коула. Заключение. Результат экспериментальных исследований показал возможность при помощи разработанного метода улучшить спектр связности, увеличить кодовое расстояние QC-LDPC кодов. Это позволило уменьшить вероятность ошибки на бит на выходе декодера на порядки при высоких отношениях сигнал/шум в АБГШ-канале.

Purpose of research is a modification of Cole's importance sampling method for finding trapping sets in an LDPC code to speed up their search.Methods. Cole proposed a method for searching for trapping sets in an LDPC code by using a Monte Carlo method that causes the decoding algorithm to fail at nodes potentially contained in trapping sets. His method makes it possible to accelerate the study of the efficiency of medium-length LDPC codes in the region of large SNRs. The modified method uses the properties of automorphisms of Tanner graphs, which make it possible to exclude a significant number of symbolic nodes from the enumeration. The modified method also provides for an ordered enumeration over subgraphs containing cycles.Results. The proposed method made it possible to speed up the search for trapping sets in Mackay's PEG(1008, 504) LDPC code by 5027 times compared to the Velasquez-Subramani method, and 43 times faster compared to the original Cole method. In the case of (2640, 1320) LDPC Margulis code, the proposed method is 28 times faster than the Velasquez-Subramani quasi-cyclic method and 134 times faster than the original Cole method.Conclusion. The result of experimental studies showed the possibility of using the developed method to improve the connectivity spectrum, increase the code distance of QC-LDPC codes. This made it possible to reduce the probability of a bit error at the decoder output by orders of magnitude at high signal-to-noise ratios in the AWGN channel.

LDPC-кодметод выборки по значимостиспектр связностикодовое расстояниеметод КоулаLDPC codeImportance sampling methodApproximated Cycle Extrinsic Message Degreecode distanceCole methodError-floorReferencesCole C. A., et al. Regular {4, 8} LDPC Codes and Their Low error Floors // MILCOM. 2006. Р. 1-7Cole C. A., et al. Regular {4, 8} LDPC Codes and Their Low error Floors. MILCOM, 2006, pp. 1-7.Cole C. A., et al. Analysis and Design of Moderate Length Regular LDPC Codes with Low Error Floors // 40th CISS. 2006. Р. 823-828.Cole C. A., et al. Analysis and Design of Moderate Length Regular LDPC Codes with Low Error Floors. 40th CISS, 2006, pp. 823-828.Cole C. A. Error floor analysis for an ensemble of easily implementable irregular (2048, 1024) LDPC codes // MILCOM. 2008. Р. 1-5.Cole C. A. Error floor analysis for an ensemble of easily implementable irregular (2048, 1024) LDPC codes. MILCOM, 2008, pp. 1-5.Cole S. A., Wilson E. H., Giallorenzi T. A general method for finding low error rates of LDPC codes. URL: arxiv.org/abs/cs/0605051. (date of treatment: 14.04.2022)Cole S. A., Wilson E. H., Giallorenzi T. A general method for finding low error rates of LDPC codes. Available at: arxiv.org/abs/cs/0605051. (accessed: 14.04.2022)Velasquez A., et al. Finding Minimum Stopping and Trapping Sets: An Integer Linear Programming Approach // In: Lee J., Rinaldi G., Mahjoub A. (eds) Comb. Optim. ISCO 2018. Lect. Notes in Comp. Science. Vol. 10856. Р.. 402–415Velasquez A., et al. Finding Minimum Stopping and Trapping Sets: An Integer Linear Programming Approach. In: Lee J., Rinaldi G., Mahjoub A. (eds). Comb. Optim. ISCO 2018. Lect. Notes in Comp. Science, 2018, vol. 10856, pp. 402–415.Усатюк В.С., Егоров С.И. Устройство для оценки кодового расстояния линейного блочного кода методом геометрии чисел // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2017. № 4 (25). С. 24-33.Usatyuk V.S., Egorov S.I. Ustroistvo dlya otsenki kodovogo rasstoyaniya lineinogo blochnogo koda metodom geometrii chisel [A device for estimating the code distance of a linear block code by the geometry of numbers method]. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie = Proceedings of the Southwest State University. Series: Control, Computing Engineering, Information Science. Medical Instruments Engineering, 2017, no. 4 (25), pp. 24-33.Richardson T. J. Error floors of LDPC codes // in 41st Annual Allerton Conference on Comm., Control and Computing. Oct. 2003. Р. 1426–1435.Richardson T. J. Error floors of LDPC codes. 41st Annual Allerton Conference on Comm., Control and Computing, Oct. 2003, pp. 1426–1435.Improved min-sum decoding algorithms for irregular LDPC codes / J. Chen, R. M. Tanner, C. Jones, Y. Li // ISIT. 2005. Р. 449-453.Chen J., Tanner R. M., Jones C., Li Y. Improved min-sum decoding algorithms for irregular LDPC codes. ISIT, 2005, pp. 449-453.Two-dimensional correction for min-sum decoding of irregular LDPC codes / J. Zhang, M. Fossorier, D. Gu, J. Zhang // in IEEE Communications Letters. March 2006. Vol. 10. № 3. Р. 180-182.Zhang J., Fossorier M., Gu D., Zhang J. Two-dimensional correction for min-sum decoding of irregular LDPC codes. IEEE Communications Letters, March 2006, vol. 10, no. 3, pp. 180-182.Zhang S., Schlegel C. Controlling the Error Floor in LDPC Decoding // in IEEE Transactions on Comm. 2013. Vol. 61(9). Р. 3566-3575.Zhang S., Schlegel C. Controlling the Error Floor in LDPC Decoding. IEEE Transactions on Comm., 2013, vol. 61(9), pp. 3566-3575.Tian T., et al Selective avoidance of cycles in irregular LDPC code construction// in IEEE Trans. on Comm. 2004. Vol. 52. № 8. Р. 1242-1247.Tian T., et al Selective avoidance of cycles in irregular LDPC code construction. IEEE Trans. on Comm., 2004, vol. 52, no. 8, pp. 1242-1247.Vasić B., et al Trapping set ontology // 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2009. Р. 1-7.Vasić B., et al Trapping set ontology. 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2009, pp. 1-7.McGregor A., Milenkovic O. On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes // IEEE ITW. 2007. Р. 248-253.McGregor A., Milenkovic O. On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes. IEEE ITW, 2007, pp. 248-253.Jeruchim M. Techniques for estimating the bit error rate in the simulation of digital communication systems // IEEE Journal on selected areas in communications. 1984. Vol. 2. № 1. Р. 153–170.Jeruchim M. Techniques for estimating the bit error rate in the simulation of digital communication systems. IEEE Journal on selected areas in communications, 1984, vol. 2, no. 1, pp. 153–170.Smith P. J., Shafi M., Gao H. Quick simulation: A review of importance sampling techniques in communication systems, // IEEE J.Select.Areas Commun. 1997. Vol. 15. Р. 597–613.Smith P. J., Shafi M., Gao H. Quick simulation: A review of importance sampling techniques in communication systems. IEEE J.Select.Areas Commun, 1984, vol. 15, pp. 597–613.Компьютерное моделирование / В.М. Градов, Г.В. Овечкин, П.В. Овечкин, И. В. Рудаков. М.: КУРС: Инфра-М, 2020. 264 с.Gradov V.M., Ovechkin G.V., Ovechkin P.V., Rudakov I. V. Komp'yuternoe modelirovanie [Computer simulation]. Moscow, Infra-M Publ., 2020, 264 p.Vasić B., Chilappagari S.K., Nguyen D. V. Chapter 6 - Failures and Error Floors of Iterative Decoders, Editor(s): Declerq D., Fossorier M., Biglieri E., Academic Press Library in Mobile and Wireless Comm. 2014. Р. 299-341Vasić B., Chilappagari S.K., Nguyen D. V. Chapter 6 - Failures and Error Floors of Iterative Decoders, Editor(s): Declerq D., Fossorier M., Biglieri E., Academic Press Library in Mobile and Wireless Comm., 2014, pp. 299-341Tanner R. M., Fuja T. E., Sridhara D. A Class of Group Structured LDPC Codes // Proceedings 6th ISCTA, Ambleside, England, July 2001. Р.365-370.Tanner R. M., Fuja T. E., Sridhara D. A Class of Group Structured LDPC Codes. Proceedings 6th ISCTA. Ambleside, England, July 2001, pp.365-370.Fossorier M. P. C. Quasi-cyclic low-density parity-check codes fromcirculant permutation matrices// IEEE Trans. Inf. Theory. Aug. 2004. Vol. 50. № 8. Р. 1788–1793.Fossorier M. P. C. Quasi-cyclic low-density parity-check codes fromcirculant permutation matrices. IEEE Trans. Inf. Theory, Aug. 2004, vol. 50, no. 8, pp. 1788–1793.Halford T. R., Chugg K. M. An algorithm for counting short cycles in bipartite graphs // in IEEE Trans. on Inform. Theory. 2006. Vol. 52(1). Р. 287-292.Halford T. R., Chugg K. M. An algorithm for counting short cycles in bipartite graphs. IEEE Trans. on Inform. Theory, 2006, vol. 52(1), pp. 287-292.Usatyuk V., Vorobyev I. Simulated Annealing Method for Construction of HighGirth QC-LDPC Codes // 41st International Conference on Telecommunications and Signal Processing (TSP). Athens, Greece, 2018.Usatyuk V., Vorobyev I. Simulated Annealing Method for Construction of HighGirth QC-LDPC Codes. 41st International Conference on Telecommunications and Signal Processing (TSP). Athens, Greece, 2018.Usatyuk V., Egorov S., Svistunov G. Construction of Length and Rate Adaptive MET QC-LDPC Codes by Cyclic Group Decomposition // IEEE East-West Design & Test Symposium (EWDTS). Batumi, Georgia, 2019.Usatyuk V., Egorov S., Svistunov G. Construction of Length and Rate Adaptive MET QC-LDPC Codes by Cyclic Group Decomposition. IEEE East-West Design & Test Symposium (EWDTS). Batumi, Georgia, 2019.Schlegel C., Zhang S. On the Dynamics of the Error Floor Behavior in (Regular) LDPC Codes // IEEE Transactions on Information Theory. 2010. Vol. 56. № 7. Р. 3248-3264.Schlegel C., Zhang S., "On the Dynamics of the Error Floor Behavior in (Regular) LDPC Codes. IEEE Transactions on Information Theory, 2010, vol. 56, no. 7, pp. 3248-3264.

The authors declare that there are no conflicts of interest present.