izvestswsuИзвестия Юго-Западного государственного университетаProceedings of the Southwest State University2223-15602686-6757ЮЗГУ10.21869/2223-1560-2024-28-4-154-176izvestswsu-1379Research ArticleИнформатика, вычислительная техника и управлениеComputer science, computer engineering and IT managmentПоиск и взвешивание треппин-cетов в квазициклических кодах методом поднятия и проекции мультиграфаSearch and weighting for trapping sets in quasi-cyclic codes by multigraph lift and projection methodУсатюкВ. С.UsatjukV. S.

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

департамент исследований и разработок

107076; ул. Краснобогатырская, д. 44, стр. 1; Москва

Vasily S. Usatjuk,  Cand. of Sci. (Engineering), Head Engineer

R & D department

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

usatiuk@t8.ruКузнецовЮ. О.KuznetsovYu. O.

Юрий Олегович Кузнецов, кандидат физико-математических наук, ведущий инженер-разработчик

департамент исследований и разработок

107076; ул. Краснобогатырская, д. 44, стр. 1; Москва

Yuri O. Kuznetsov, Cand. of Sci. (Physico-Mathematical), Leading Engineer

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

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

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

кафедра вычислительной техники

305040; ул. 50 лет Октября, д. 94; Курск

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

305040; 50 Let Oktyabrya str. 94; Kursk

sie58@mail.ruООО «Т8»LLC "T8"Юго-Западный государственный университетSouthwest State University202407042025284154176Copyright © Усатюк В.С., Кузнецов Ю.О., Егоров С.И., 20252025Усатюк В.С., Кузнецов Ю.О., Егоров С.И.Usatjuk V.S., Kuznetsov Y.O., 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/1379

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

   Методы

   Методы. Предложенный метод поиска треппин-сетов использует алгебраические свойства квазициклических кодов на графах. Применение операций подъема и проекции графа переводит задачу поиска треппин-сетов в пространство большей размерности, где треппин-сеты более различимы. Предложенный метод оценки вероятности ошибок, основанный на выборке по значимости, в сравнении с предложенным ранее методом Коула, позволяет осуществить распараллеливание вычислений без необходимости дублирования таблиц. Такой подход кратно уменьшает объем требуемой памяти и позволяет осуществлять вычисления по разделенным индексам.

   Результаты

   Результаты. Предложенный метод поиска треппин-сетов удобен для аппаратной реализации, в частности на платах-ускорителях, использующих ПЛИС. Для его реализации достаточно менее половины чиплета SLR (super logic regions) ускорителя BittWare XUP-P3R (в конфигурации с 128 Гб DDR4 ОЗУ) или ускорителя AMD Alveo U200/VCU1525 (64 Гб DDR4 ОЗУ). Это в сочетание с уменьшенными требованиями к объему ОЗУ позволяет расположить на кристалле ПЛИС AMD Virtex UltraScale+ XCVU9P [51] 5 исполнительных блоков вместо 2x, необходимых для модифицированного метода Коула. При этом ускорение поиска для матрицы с размером циркулянта 128 составит 2.5 раза. Применение предложенного метода для оценки вероятности ошибок, вызванных треппин-сетами, обеспечивает ускорение в 5.3 раза в сравнении с методом Коула для квазициклического кода с размером циркулянта 2048. Предложенный метод позволяет оценивать помехоустойчивость кода во всем диапазоне отношения сигнал/шум.

   Заключение

   Заключение. Предложенный метод поиска треппин-сетов обладает высоким быстродействием и обеспечивает полноту поиска. Предложенный метод оценки вероятности ошибок, вызванных этими треппинсетами, также обладает высоким быстродействием.

   Purpose of research is to develop a new high-speed method for searching for trapping sets, and a new method for estimating the probability of errors caused by these trapping sets for quasi-cyclic codes with a circulant size that is not a prime number.

   Methods

   Methods. The proposed method for searching for trapping sets uses the algebraic properties of quasi-cyclic codes on graphs. Using the graph lifting and projection operations, the problem of searching for trapping sets is transferred to a higher-dimensional space, where trapping sets are more distinguishable. The proposed method for estimating the probability of errors based on selection by importance, in comparison with the previously proposed Cole method, allows parallelization of calculations without the need to duplicate tables. This approach reduces the amount of required memory many times and allows calculations to be performed using separated indices.

   Results

   Results. The proposed method of searching for trapping sets is convenient for hardware implementation, in particular, on accelerator boards using FPGAs. For its implementation, less than half of the SLR (super logic regions) chiplet of the BittWare XUP-P3R accelerator (in a configuration with 128 GB of DDR4 RAM) or the AMD Alveo U200/VCU1525 accelerator (64 GB of DDR4 RAM) is sufficient. This, combined with reduced requirements for RAM volume, allows placing 5 execution units on the AMD Virtex UltraScale+ XCVU9P FPGA [51] crystal instead of 2x, required for the modified Cole method. At the same time, the search acceleration for a matrix with a circulant size of 128 will be 2.5 times. The application of the proposed method for estimating the probability of errors caused by trapping sets provides a 5.3-fold acceleration compared to the Cole method for a quasi-cyclic code with a circulant size of 2048. The proposed method allows one to estimate the noise immunity of the code over the entire range of the signal-to-noise ratio.

   Conclusion

   Conclusion. The proposed method of searching for trapping sets has high performance and ensures completeness of the search. The proposed method of estimating the probability of errors caused by these trapping sets also has high performance.

квазициклические LDPC-кодытреппин-сетыметоды выборки по значимостиподъем мультиграфаquasi-cyclic LDPC codestrapping setsimportance sampling methodsmultigraph liftingReferencesForney G. D. Codes on graphs: normal realizations // IEEE Transactions on Information Theory. 2001. Vol. 47, no. 2. P. 520-548.Forney G. D. Codes on graphs: normal realizations. IEEE Transactions on Information Theory. 2001; 47(2): 520-548.Huang B., Jebara T. Approximating the permanent with belief propagation. URL: arxiv.org/abs/0908.1769. (accessed: 15. 06. 2024).Huang B., Jebara T. Approximating the permanent with belief propagation. Available at: arxiv.org/abs/0908.1769. (accessed: 15. 06. 2024).Vontobel P. O. A factor-graph approach to Lagrangian and Hamiltonian dynamics // IEEE International Symposium on Information Theory. 2011. P. 2183-2187.Vontobel P. O. A factor-graph approach to Lagrangian and Hamiltonian dynamics. IEEE International Symposium on Information Theory. 2011. P. 2183-2187.Glasser I., Pancotti N., Cirac J. I. From Probabilistic Graphical Models to Generalized Tensor Networks for Supervised Learning // IEEE Access. 2020. Vol. 8. Р. 68169-68182.Glasser I., Pancotti N., Cirac J. I. From Probabilistic Graphical Models to Generalized Tensor Networks for Supervised Learning. IEEE Access. 2020; 8: 68169-68182.Ikeda S., Tanaka T., Amari S. Information geometry of turbo and low-density parity–check codes // IEEE Transactions on Information Theory. 2004. Vol. 50, no. 6. Р. 1097-1114.Ikeda S., Tanaka T., Amari S. Information geometry of turbo and low-density parity–check codes. IEEE Transactions on Information Theory. 2004; 50(6): pp. 1097-1114.Usatyuk V., Sapozhnikov D., Egorov S. Topology-Aware Exploration of Energy-Based Models Equilibrium: Toric QC-LDPC Codes and Hyperbolic MET QC-LDPC Codes. URL: arxiv.org/abs/2401.14749. (accessed: 15. 06. 2024).Usatyuk V., Sapozhnikov D., Egorov S. Topology-Aware Exploration of Energy-Based Models Equilibrium: Toric QC-LDPC Codes and Hyperbolic MET QC-LDPC Codes. Available at: arxiv.org/abs/2401.14749. (accessed: 15. 06. 2024).Welling M., Hinton G. E. A new learning algorithm for mean field boltzmann machines // Int. Conf. on Artificial Neural Networks, 2002. Р. 351–357.Welling M., Hinton G. E. A new learning algorithm for mean field boltzmann machines. Int. Conf. on Artificial Neural Networks, 2002. P. 351–357.Fischer A., Igel Empirical analysis of the divergence of gibbs sampling based learning algorithms for restricted boltzmann machines // Int. Conf. on Artificial Neural Networks, 2010. Р. 208–217.Fischer A., Igel Empirical analysis of the divergence of gibbs sampling based learning algorithms for restricted boltzmann machines. Int. Conf. on Artificial Neural Networks, 2010. P. 208–217.Dinh L., Krueger D., Bengio Y. NICE: Non-linear independent components estimation. URL: arxiv.org/abs/1410.8516. (accessed: 15. 06. 2024).Dinh L., Krueger D., Bengio Y. NICE: Non-linear independent components estimation. Available at: arxiv.org/abs/1410.8516. (accessed: 15. 06. 2024).Sohl-Dickstein J., et al. Deep unsupervised learning using nonequilibrium thermodynamics // Int. Conf. on Machine Learning, 2015. Р. 2256–2265.Sohl-Dickstein J., et al. Deep unsupervised learning using nonequilibrium thermodynamics. Int. Conf. on Machine Learning, 2015. P. 2256–2265.Gao R., et al. Learning generative convnets via multi-grid modeling and sampling // IEEE Conference on Computer Vision and Pattern Recognition, 2018. Р. 9155–9164.Gao R., et al. Learning generative convnets via multi-grid modeling and sampling. IEEE Conference on Computer Vision and Pattern Recognition, 2018. P. 9155–9164.Bose A. J., Ling H., Cao Y. Adversarial contrastive estimation // The 56<sup>-th</sup> Annual Meeting of the Association for Comput. Linguistics, 2018. Vol. 1. Р. 1021–1032.Bose A. J., Ling H., Cao Y. Adversarial contrastive estimation. The 56<sup>-th</sup> Annual Meeting of the Association for Comput. Linguistics. 2018; 1: 1021–1032.Ceylan C., Gutmann M. U. Conditional noise-contrastive estimation of unnormalised models // International Conference on Machine Learning, 2018. Р. 726–734.Ceylan C., Gutmann M. U. Conditional noise-contrastive estimation of unnormalised models. International Conference on Machine Learning, 2018. P. 726–734.Dai B., et al. Exponential family estimation via adversarial dynamics embedding // 33<sup>rd</sup> International Conference on Neural Information Processing Systems, 2019. Р. 10979–10990.Dai B., et al. Exponential family estimation via adversarial dynamics embedding. 33<sup>rd</sup> International Conference on Neural Information Processing Systems, 2019. P.10979–10990.Polyanskii N., Usatyuk V., Vorobyev I. Floor Scale Modulo Lifting for QC-LDPC codes. URL: arxiv.org/abs/1701.07521. (accessed: 15. 06. 2024).Polyanskii N., Usatyuk V., Vorobyev I. Floor Scale Modulo Lifting for QC-LDPC codes. Available at: arxiv.org/abs/1701.07521. (accessed: 15. 06. 2024).Price A., Hall J. A Survey on Trapping Sets and Stopping Sets. URL: arxiv.org/abs/1705.05996. (accessed: 15. 06. 2024).Price A., Hall J. A Survey on Trapping Sets and Stopping Sets. Available at: arxiv.org/abs/1705.05996. (accessed: 15. 06. 2024).Myung S., Yang K. Extension of quasi-cyclic LDPC codes by lifting // IEEE International Symposium on Information Theory, 2005. Р. 2305-2309.Myung S., Yang K. Extension of quasi-cyclic LDPC codes by lifting. IEEE International Symposium on Information Theory, 2005. P. 2305-2309.Myung S., Yang K., Kim Y. Lifting methods for quasi-cyclic LDPC codes // IEEE Comm. Lett. 2006. Vol. 10, no. 6. Р. 489-491.Myung S., Yang K., Kim Y. Lifting methods for quasi-cyclic LDPC codes. IEEE Comm. Lett. 2006; 10(6): 489-491.Characterizations of pseudo-codewords of (low-density) parity-check codes / R. Koetter, W.-C. W. Li, P. O. Vontobel, J. L. Walker // Advances in Mathematics. 2007. Vol. 213, is. 1. Р. 205-229.Koetter R., Li W.-C. W., Vontobel P. O., Walker J. L. Characterizations of pseudo-codewords of (low-density) parity-check codes. Advances in Mathematics. 2007; 213 (1): 205-229.On Deriving Good LDPC Convolutional Codes from QC LDPC Block Codes / A. E. Pusane, R. Smarandache, P. O. Vontobel, D. J. Costello // IEEE International Symposium on Information Theory, Nice, France, 2007. Р. 1221-1225.Pusane A. E., Smarandache R., Vontobel P. O., Costello D. J. On Deriving Good LDPC Convolutional Codes from QC LDPC Block Codes. IEEE International Symposium on Information Theory, Nice, France, 2007. P. 1221-1225.Deriving Good LDPC Convolutional Codes from LDPC Block Codes / A. E. Pusane, R. Smarandache, P. O. Vontobel, D. J. Costello // IEEE Transactions on Information Theory. 2011. Vol. 57, no. 2. Р. 835-857.Pusane A. E., Smarandache R., Vontobel P. O., Costello D. J. Deriving Good LDPC Convolutional Codes from LDPC Block Codes. IEEE Transactions on Information Theory. 2011; 57 (2): 835-857.LDPC block and convolutional codes based on circulant matrices / R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, D. J. Costello // IEEE Transactions on Information Theory. 2004. Vol. 50, no. 12. Р. 2966-2984.Tanner R. M., Sridhara D., Sridharan A., Fuja T. E., Costello D. J. LDPC block and convolutional codes based on circulant matrices. IEEE Transactions on Information Theory. 2004; 50 (12): 2966-2984.MacKay D. J., Davey M. C. Evaluation of Gallager codes for short block length and high rate applications // The IMA Workshop on Codes, System and Graphical Models. 2001. Р. 113–130.MacKay D. J., Davey M. C. Evaluation of Gallager codes for short block length and high rate applications. The IMA Workshop on Codes, System and Graphical Models, 2001. P. 113–130.Smarandache R., Vontobel P. O. Quasi-cyclic LDPC codes: Influence of proto- and Tanner-graph structure on minimum Hamming distance upper bounds // IEEE Transactions on Information Theory. 2012. Vol. 58, no. 2. Р. 585-607.Smarandache R., Vontobel P. O. Quasi-cyclic LDPC codes: Influence of proto- and Tanner-graph structure on minimum Hamming distance upper bounds. IEEE Transactions on Information Theory. 2012; 58(2): 585-607.Butler B. K., Siegel P. H. Bounds on the Minimum Distance of Punctured Quasi-Cyclic LDPC Codes // IEEE Transactions on Information Theory. 2013. Vol. 59, no. 7. Р. 4584-4597.Butler B. K., Siegel P. H. Bounds on the Minimum Distance of Punctured Quasi-Cyclic LDPC Codes. IEEE Transactions on Information Theory. 2013; 59(7): 4584-4597.Huang Y., Vontobel P. O. Bounding the Permanent of a Non-negative Matrix via its Degree- M Bethe and Sinkhorn Permanents // IEEE International Symposium on Information Theory. 2023. Р. 2774-2779.Huang Y., Vontobel P. O. Bounding the Permanent of a Non-negative Matrix via its Degree- M Bethe and Sinkhorn Permanents. IEEE International Symposium on Information Theory, 2023/ P. 2774-2779.Smarandache R. Pseudocodewords from Bethe permanents // IEEE International Symposium on Information Theory. 2013. Р. 2059-2063.Smarandache R. Pseudocodewords from Bethe permanents. IEEE International Symposium on Information Theory, 2013. P. 2059-2063.Vontobel P. O. Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function // IEEE Transactions on Information Theory. 2013. Vol. 59, no. 9. Р. 6018-6048.Vontobel P. O. Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function. IEEE Transactions on Information Theory. 2013; 59(9): 6018-6048.Dehghan A., Banihashemi A. H. On the Tanner Graph Cycle Distribution of Random LDPC, Random Protograph-Based LDPC, and Random Quasi-Cyclic LDPC Code Ensembles // IEEE Transactions on Information Theory. 2018. Vol. 64, no. 6. Р. 4438-4451.Dehghan A., Banihashemi A. H. On the Tanner Graph Cycle Distribution of Random LDPC, Random Protograph-Based LDPC, and Random Quasi-Cyclic LDPC Code Ensembles. IEEE Transactions on Information Theory. 2018; 64(6): 4438-4451.Усатюк В.С., Егоров С.И. Построение LDPC-кодов с использованием модифицированного метода выборки по значимости Коула // Известия Юго-Западного государственного университета. 2023; 27(1): 92-110. doi: 10.21869/2223-1560-2023-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.). doi: 10.21869/2223-1560-2023-27-1-92-110.XILINX SDAccel Development Environment Release Notes, Installation, and Licensing Guide UG1238 (v2019.1) July 26, 2019. Р. 7-9. URL: https://download.amd.com/docnav/documents/aem/xilinx2019_1-ug1238-sdx-rnil.pdf. (accessed: 15. 06. 2024).XILINX SDAccel Development Environment Release Notes, Installation, and Licensing Guide UG1238 (v2019.1) July 26, 2019, p. 7-9. Available at: https://down-load.amd.com/docnav/documents/aem/xilinx2019_1-ug1238-sdx-rnil.pdf. (accessed: 15. 06. 2024).MacWilliams F., Sloane N. The Theory of Error-Correcting Codes. North-holland Publishing Company, 1977. 778 p.MacWilliams F., Sloane N. The Theory of Error-Correcting Codes. North-holland Publishing Company, 1977. 778 p.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. (accessed: 15. 06. 2024).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: 15. 06. 2024).Richardson T. Error floors of LDPC codes // The 41st Annu. Allerton Conf., Alleton, USA. 2003. Р. 1426-1435.Richardson T. Error floors of LDPC codes. The 41st Annu. Allerton Conf., Alleton, USA, 2003. P. 1426-1435.Fossorier M., et al. Reduced complexity iterative decoding of low density parity check codes based on belief propagation // IEEE Transactions on Communications. 1999. Vol. 47, no. 5. Р. 673-680.Fossorier M., et al. Reduced complexity iterative decoding of low density parity check codes based on belief propagation. IEEE Transactions on Communications. 1999; 47(5): 673-680.Chen J., Fossorier M. Near optimum universal belief propagation based decoding of low-density parity check codes // IEEE Transactions on Communications. 2002. Vol. 50, no. 3. Р. 406-414.Chen J., Fossorier M. Near optimum universal belief propagation based decoding of low-density parity check codes. IEEE Transactions on Communications. 2002. 50(3). 406-414.

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