Поиск треппин-cетов методом смешанного целочисленного линейного программирования с использованием априорного списка кодовых вершин

Целью исследования является разработка нового быстродействующего метода поиска треппин-сетов в кодах на графах, обеспечивающего полноту поиска.

Методы. Существует два подхода к поиску треппин-сетов. Первый на основе метода Монте-Карло со смещенной оценкой вероятности при помощи выборки по значимости (Importance Sampling) предусматривает использование декодера. Достоинством этого подхода является высокое быстродействие. Недостатками – зависимость от параметров декодера и характеристик канала и конечная вероятность пропуска треппинсетов. Второй подход основан на применении методов линейного программирования. Достоинством этого подхода является полнота полученного списка треппин-сетов, обусловленная его независимостью от параметров декодера и характеристик канала. Недостаток подхода заключается в его большой вычислительной сложности. В статье в рамках второго подхода предложен новый метод поиска треппин-сетов с меньшей вычислительной сложностью. Метод предусматривает решение задачи смешанного целочисленного линейного программирования с использованием априорного списка кодовых вершин, участвующих в кратчайших (коротких) циклах в графе кода. 

Результаты. С использованием предложенного метода был выполнен поиск треппин-сетов в нескольких низкоплотностных кодах. При этом применялся математический пакет линейного программирования IBM CPLEX версии 12.8, который запускался на 32 потоках 16-ядерного процессора AMD Ryzen 3950X с 32GB ОЗУ (DDR4). В коде Маргулиса (2640, 1320) с помощью предложенного метода был найден треппин-сет TS(6,6) за время 0.53 c. Ускорение, обеспечиваемое предложенным в статье методом, по сравнению с методом Веласкеса-Субрамани составляет 8252.415 раза. Благодаря высокому быстродействию и полноте поиска впервые были найдены треппин-сеты TS(62,16) и TS(52,14) в коде Маргулиса (4896, 2474). 

Заключение. В статье предложен метод поиска треппин-сетов на основе смешанного целочисленного линейного программирования c использованием априорного списка кодовых вершин. Метод обладает высоким быстродействием и обеспечивает полноту поиска.

1. Djordjevic I. B. Quantum Communication, Quantum Networks, and Quantum Sensing / Elsevier/Academic Press, 2022. 608 p.

2. Milicevic M., Feng C., Zhang L.M. et al. Quasi-cyclic multi-edge LDPC codes for long-distance quantum cryptography // Quantum Inf. 2018. Vol.4. 21 p.

3. Panteleev P., Kalachev G. Degenerate Quantum LDPC Codes with Good Finite Length Performance // Quantum. 2021. Vol 5, p. 585.

4. Mézard M., Montanari A. Information, Physics, and Computation. Oxford Graduate Texts / Oxford University Press. 2009. 569 p.

5. Richardson T., Urbanke R. Modern Coding Theory / Cambridge University Press. 2008. 590 p.

6. Ryan W., Shu Lin Channel Codes: Classical and Modern / Cambridge University Press. 2009. 710 p.

7. Djordjevic I. B. Advanced Optical and Wireless Communications Systems, 2nd Edition / Springer Nature Switzerland AG. 2022. 992 p.

8. Rosnes E., Ytrehus O. An Algorithm to Find All Small-Size Stopping Sets of LowDensity Parity-Check Matrices // IEEE International Symposium on Information Theory, Nice, France. 2007. Pp. 2936-2940.

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

10. Rosnes E. "On the Effects of Pseudo-Codewords on Independent Rayleigh FlatFading Channels," IEEE Inform. Theory Workshop on Information Theory for Wireless Networks, Bergen, Norway. 2007. Pp. 1-5.

11. Velasquez A., Subramani K., Wojciechowski P. On the complexity of and solutions to the minimum stopping and trapping set problems // Theor. Comput. Sci. 2022. Vol. 915. Pp. 26-44.

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

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

14. Butler B. K., Siegel P. H. Error Floor Approximation for LDPC Codes in the AWGN Channel // ITIT. 2014. Vol. 60. № 12. Pp. 7416-7441.

15. Karimi M., Banihashemi A. H. Efficient Algorithm for Finding Dominant Trapping Sets of LDPC Codes // IEEE Transactions on Information Theory, 2012. Vol. 58. № 11. Pp. 6942-6958.

16. Усатюк В.С., Егоров С.И. Построение LDPC-кодов с использованием модифицированного метода выборки по значимости Коула // Известия Юго-Западного государственного университета. 2023; 27(1): 92-110. https://doi.org/10.21869/2223-15602023-27-1-92-110.

17. Sarıduman A., Pusane A.E., Taşkın Z.C. An integer programming based trapping set search technique // 2012 20th Signal Processing and Communications Applications Conference, Mugla, Turkey. 2012. Pp. 1-4.

18. 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, V. 10856. Pp. 402–415.

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

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

21. 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. Pp. 180-182.

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

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

24. Усатюк В.С., Егоров С.И. Построение квазициклических недвоичных низкоплотностных кодов на основе совместной оценки их дистантных свойств и спектров связности //Телекоммуникации. 2016. №8. C. 32-40.

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

26. Margulis G. A. Explicit Constructions of Graphs Without Short Cycles and Low Density Codes // Combinatorica. 1982. Vol. 2. № 1. Pp. 71-78.

27. Rosenthal J., Vontobel P. O. Constructions of regular and irregular LDPC codes using Ramanujan graphs and ideas from Margulis // Proceedings 2001 IEEE International Symposium on Information Theory. 2001. Pp. 4.

28. IBM CPLEX function documentation. URL: https://www.ibm.com/docs/en/icos/12.9.0?topic=functions-cplexmilp

29. Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem". Operations Research. 9 (6), (1961): 849–859.

30. Chvatal V. Edmonds polytopes and a hierarchy of combinatorial problems // Discrete Math. 1973. № 4. Pp. 305–337.

31. Usatyuk V.S. Support material for Mixed Linear Programming Method for Trapping Sets Search. URL: https://github.com/Lcrypto/trapping-sets-enumeration/tree/master/LP