izvestswsuИзвестия Юго-Западного государственного университетаProceedings of the Southwest State University2223-15602686-6757ЮЗГУ10.21869/2223-1560-2023-27-4-79-97izvestswsu-1204Research ArticleИнформатика, вычислительная техника и управлениеComputer science, computer engineering and IT managmentПоиск треппин-cетов методом смешанного целочисленного линейного программирования с использованием априорного списка кодовых вершинTrapping Sets Search Using the Method of Mixed Integer Linear Programming with a Priori List of Variable NodesУсатюкВ. С.UsatjukV S.

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

д. 44, стр. 1, г. Москва 107076

Vasily S. Usatjuk, Cand. of Sci. (Engineering), Head Engineer, R&D department

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

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

sie58@mail.ruООО «Т8»LLC "T8"Юго-Западный государственный университетSouthwest State University2023010320242747997Copyright © Усатюк В.С., Егоров С.И., 20242024Усатюк В.С., Егоров С.И.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/1204

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

Методы

Методы. Существует два подхода к поиску треппин-сетов. Первый на основе метода Монте-Карло со смещенной оценкой вероятности при помощи выборки по значимости (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 использованием априорного списка кодовых вершин. Метод обладает высоким быстродействием и обеспечивает полноту поиска.

Purpose of research is to develop a new high-speed method for searching trappin sets in graph codes, ensuring the completeness of the search.

Methods

Methods. There are two approaches to finding trappin sets. The first, based on the Monte Carlo method with a biased probability estimation using Importance Sampling, involves the use of a decoder. The advantage of this approach is its high performance. The disadvantages are the dependence on decoder parameters and channel characteristics and the finite probability of missing trappin sets. The second approach is based on the use of linear programming methods. The advantage of this approach is the completeness of the resulting list of trappin sets, due to its independence from the decoder parameters and channel characteristics. The disadvantage of this approach is its high computational complexity. In the article, within the framework of the second approach, a new method for searching trappin sets with less computational complexity is proposed. The method involves solving a mixed integer linear programming problem using an a priori list of code vertices participating in the shortest cycles in the code graph.

Results

Results. Using the proposed method, a search for trappin sets was performed for several low-density codes. For this purpose, the mathematical linear programming package IBM CPLEX version 12.8 was used, which was run on 32 threads of a 16-core AMD Ryzen 3950X processor with 32GB of RAM (DDR4). In the Margulis code (2640, 1320), using the proposed method, the trappin set TS(6,6) was found in a time of 0.53 s. The speedup provided by the method proposed in the paper compared to the Velazquez-Subramani method is 8252.415 times. Thanks to the high speed and completeness of the search, trappin sets were found for the first time TS(62,16) and TS(52,14) in the Margulis code (4896, 2474 ).

Conclusion

Conclusion. The paper proposes a new method for searching trapping sets by solving a mixed integer linear programming problem with an a priori list of code. The method is fast and provides completeness of the search.

Коды на графахLDPC-кодытреппин-сетыметоды cмешанного целочисленного программированияIBM CPLEXgraph codesLDPC codestrapping setsmixed integer programming methodIBM CPLEXReferencesDjordjevic I. B. Quantum Communication, Quantum Networks, and Quantum Sensing / Elsevier/Academic Press, 2022. 608 p.Djordjevic I. B. Quantum Communication, Quantum Networks, and Quantum Sensing. / Elsevier/Academic Press, 2022, 608 p.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.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.Panteleev P., Kalachev G. Degenerate Quantum LDPC Codes with Good Finite Length Performance // Quantum. 2021. Vol 5, p. 585.Panteleev P., Kalachev G. Degenerate Quantum LDPC Codes with Good Finite Length Performance. Quantum, 2021, vol. 5, 585 p.Mézard M., Montanari A. Information, Physics, and Computation. Oxford Graduate Texts / Oxford University Press. 2009. 569 p.Mézard M., Montanari A. Information, Physics, and Computation. Oxford Graduate Texts / Oxford University Press, 2009, 569 p.Richardson T., Urbanke R. Modern Coding Theory / Cambridge University Press. 2008. 590 p.Richardson T., Urbanke R. Modern Coding Theory. Cambridge University Press. 2008, 590 p.Ryan W., Shu Lin Channel Codes: Classical and Modern / Cambridge University Press. 2009. 710 p.Ryan W., Shu Lin. Channel Codes: Classical and Modern. Cambridge University Press, 2009, 710 p.Djordjevic I. B. Advanced Optical and Wireless Communications Systems, 2nd Edition / Springer Nature Switzerland AG. 2022. 992 p.Djordjevic I. B. Advanced Optical and Wireless Communications Systems, 2nd Edition. Springer Nature Switzerland AG, 2022, 992 p.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.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.Richardson T. J. Error floors of LDPC codes// in 41st Annual Allerton Conference on Comm., Control and Computing, Oct. 2003. P. 1426–1435.Richardson T. J. Error floors of LDPC codes. In 41st Annual Allerton Conference on Comm., Control and Computing, Oct. 2003, pp. 1426–1435.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.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.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.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.Cole C. A. Error floor analysis for an ensemble of easily implementable irregular (2048, 1024) LDPC codes// MILCOM - 2008, pp. 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).Butler B. K., Siegel P. H. Error Floor Approximation for LDPC Codes in the AWGN Channel // ITIT. 2014. Vol. 60. № 12. Pp. 7416-7441.Butler B. K., Siegel P. H. Error Floor Approximation for LDPC Codes in the AWGN Channel. ITIT, 2014, vol. 60, no. 12, pp. 7416-7441.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.Karimi M., Banihashemi A. H. Efficient Algorithm for Finding Dominant Trapping Sets of LDPC Codes. IEEE Transactions on Information Theory, 2012, vol. 58, no. 11, pp. 6942-6958.Усатюк В.С., Егоров С.И. Построение LDPC-кодов с использованием модифицированного метода выборки по значимости Коула // Известия Юго-Западного государственного университета. 2023; 27(1): 92-110. https://doi.org/10.21869/2223-15602023-27-1-92-110.Usatjuk V. S., Egorov S. I. Construction of LDPC Codes Using Cole's Modified Importance Sampling Method. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta = Proceedings of the Southwest State University. 2023; 27(1): 92-110 (In Russ.). https://doi.org/10.21869/2223-1560-2023-27-1-92-110.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.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.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.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 Lect. Notes in Comp. Science, 2018. V. 10856., pp. 402–415.Vasić B., et al Trapping set ontology // 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2009. Pp. 1-7.Vasić B., et al Trapping set ontology. 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2009, pp. 1-7.Improved min-sum decoding algorithms for irregular LDPC codes / J. Chen, R. M. Tanner, C. Jones, Y. Li // ISIT., 2005. Pp. 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. Pp. 180-182.Zhang J., Fossorier M., Gu D., Zhang J. Two-dimensional correction for min-sum decoding of irregular LDPC codes. in 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). Pp. 3566-3575.Zhang S., Schlegel C. Controlling the Error Floor in LDPC Decoding. In IEEE Transactions on Comm., 2013, vol. 61(9), pp. 3566-3575.Tian T., et al Selective avoidance of cycles in irregular LDPC code construction // IEEE Trans. on Comm. 2004. Vol. 52. № 8. Pp. 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.Усатюк В.С., Егоров С.И. Построение квазициклических недвоичных низкоплотностных кодов на основе совместной оценки их дистантных свойств и спектров связности //Телекоммуникации. 2016. №8. C. 32-40.Usatjuk V. S., Egorov S. I. Postroenie kvazitsiklicheskikh nedvoichnykh nizkoplotnostnykh kodov na osnove sovmestnoi otsenki ikh distantnykh svoistv i spektrov svyaznosti [Quasi-Cyclic Non-binary LDPC Codes Construction based on joint optimization the code distance properties and ACE=EMD Spectrum code’s graph properties]. Telekommunikatsii = Telecommunications, 2016, no 8, pp. 32-40.Усатюк В.С., Егоров С.И. Устройство для оценки кодового расстояния линейного блочного кода методом геометрии чисел // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2017. № 4 (25). С. 24-33.Usatjuk V. S., Egorov S. I. [An Apparatus for Estimation of Linear Block Codes Minimum Distance Based on Number Geometry Method]. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: 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 (In Russ.).Margulis G. A. Explicit Constructions of Graphs Without Short Cycles and Low Density Codes // Combinatorica. 1982. Vol. 2. № 1. Pp. 71-78.Margulis G. A. Explicit Constructions of Graphs Without Short Cycles and Low Density Codes. Combinatorica, 1982, vol. 2, no. 1, pp. 71-78.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.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.IBM CPLEX function documentation. URL: https://www.ibm.com/docs/en/icos/12.9.0?topic=functions-cplexmilpIBM CPLEX function documentation https://www.ibm.com/docs/en/icos/12.9.0?topic=functions-cplexmilpGilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem". Operations Research. 9 (6), (1961): 849–859.Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem". Operations Research. 1961. 9 (6): 849–859.Chvatal V. Edmonds polytopes and a hierarchy of combinatorial problems // Discrete Math. 1973. № 4. Pp. 305–337.Chvatal V. Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math, 1973, no. 4, pp. 305–337.Usatyuk V.S. Support material for Mixed Linear Programming Method for Trapping Sets Search. URL: https://github.com/Lcrypto/trapping-sets-enumeration/tree/master/LPUsatyuk V.S. Support material for Mixed Linear Programming Method for Trapping Sets Search. Available at: https://github.com/Lcrypto/trapping-sets-enumeration/tree/master/LP

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