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

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

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

   Результаты. Предложенный метод поиска треппин-сетов удобен для аппаратной реализации, в частности на платах-ускорителях, использующих ПЛИС. Для его реализации достаточно менее половины чиплета 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. Предложенный метод позволяет оценивать помехоустойчивость кода во всем диапазоне отношения сигнал/шум.

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

1. Forney G. D. Codes on graphs: normal realizations // IEEE Transactions on Information Theory. 2001. Vol. 47, no. 2. P. 520-548.

2. Huang B., Jebara T. Approximating the permanent with belief propagation. URL: arxiv.org/abs/0908.1769. (accessed: 15. 06. 2024).

3. Vontobel P. O. A factor-graph approach to Lagrangian and Hamiltonian dynamics // IEEE International Symposium on Information Theory. 2011. P. 2183-2187.

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

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

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

7. Welling M., Hinton G. E. A new learning algorithm for mean field boltzmann machines // Int. Conf. on Artificial Neural Networks, 2002. Р. 351–357.

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

9. Dinh L., Krueger D., Bengio Y. NICE: Non-linear independent components estimation. URL: arxiv.org/abs/1410.8516. (accessed: 15. 06. 2024).

10. Sohl-Dickstein J., et al. Deep unsupervised learning using nonequilibrium thermodynamics // Int. Conf. on Machine Learning, 2015. Р. 2256–2265.

11. Gao R., et al. Learning generative convnets via multi-grid modeling and sampling // IEEE Conference on Computer Vision and Pattern Recognition, 2018. Р. 9155–9164.

12. Bose A. J., Ling H., Cao Y. Adversarial contrastive estimation // The 56^-th Annual Meeting of the Association for Comput. Linguistics, 2018. Vol. 1. Р. 1021–1032.

13. Ceylan C., Gutmann M. U. Conditional noise-contrastive estimation of unnormalised models // International Conference on Machine Learning, 2018. Р. 726–734.

14. Dai B., et al. Exponential family estimation via adversarial dynamics embedding // 33^rd International Conference on Neural Information Processing Systems, 2019. Р. 10979–10990.

15. Polyanskii N., Usatyuk V., Vorobyev I. Floor Scale Modulo Lifting for QC-LDPC codes. URL: arxiv.org/abs/1701.07521. (accessed: 15. 06. 2024).

16. Price A., Hall J. A Survey on Trapping Sets and Stopping Sets. URL: arxiv.org/abs/1705.05996. (accessed: 15. 06. 2024).

17. Myung S., Yang K. Extension of quasi-cyclic LDPC codes by lifting // IEEE International Symposium on Information Theory, 2005. Р. 2305-2309.

18. Myung S., Yang K., Kim Y. Lifting methods for quasi-cyclic LDPC codes // IEEE Comm. Lett. 2006. Vol. 10, no. 6. Р. 489-491.

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

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

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

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

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

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

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

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

27. Smarandache R. Pseudocodewords from Bethe permanents // IEEE International Symposium on Information Theory. 2013. Р. 2059-2063.

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

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

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

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

32. MacWilliams F., Sloane N. The Theory of Error-Correcting Codes. North-holland Publishing Company, 1977. 778 p.

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

34. Richardson T. Error floors of LDPC codes // The 41st Annu. Allerton Conf., Alleton, USA. 2003. Р. 1426-1435.

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

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