Построение LDPC-кодов с использованием модифицированного метода выборки по значимости Коула

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

1. Cole C. A., et al. Regular {4, 8} LDPC Codes and Their Low error Floors // MILCOM. 2006. Р. 1-7

2. Cole C. A., et al. Analysis and Design of Moderate Length Regular LDPC Codes with Low Error Floors // 40th CISS. 2006. Р. 823-828.

3. Cole C. A. Error floor analysis for an ensemble of easily implementable irregular (2048, 1024) LDPC codes // MILCOM. 2008. Р. 1-5.

4. 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)

5. 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–415

6. Усатюк В.С., Егоров С.И. Устройство для оценки кодового расстояния линейного блочного кода методом геометрии чисел // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2017. № 4 (25). С. 24-33.

7. Richardson T. J. Error floors of LDPC codes // in 41st Annual Allerton Conference on Comm., Control and Computing. Oct. 2003. Р. 1426–1435.

8. Improved min-sum decoding algorithms for irregular LDPC codes / J. Chen, R. M. Tanner, C. Jones, Y. Li // ISIT. 2005. Р. 449-453.

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

10. Zhang S., Schlegel C. Controlling the Error Floor in LDPC Decoding // in IEEE Transactions on Comm. 2013. Vol. 61(9). Р. 3566-3575.

11. Tian T., et al Selective avoidance of cycles in irregular LDPC code construction// in IEEE Trans. on Comm. 2004. Vol. 52. № 8. Р. 1242-1247.

12. Vasić B., et al Trapping set ontology // 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2009. Р. 1-7.

13. McGregor A., Milenkovic O. On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes // IEEE ITW. 2007. Р. 248-253.

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

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

16. Компьютерное моделирование / В.М. Градов, Г.В. Овечкин, П.В. Овечкин, И. В. Рудаков. М.: КУРС: Инфра-М, 2020. 264 с.

17. 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-341

18. Tanner R. M., Fuja T. E., Sridhara D. A Class of Group Structured LDPC Codes // Proceedings 6th ISCTA, Ambleside, England, July 2001. Р.365-370.

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

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

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

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

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