Search and weighting for trapping sets in quasi-cyclic codes by multigraph lift and projection method

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

1. Forney G. D. Codes on graphs: normal realizations. IEEE Transactions on Information Theory. 2001; 47(2): 520-548.

2. Huang B., Jebara T. Approximating the permanent with belief propagation. Available at: 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; 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; 50(6): pp. 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. Available at: 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. P. 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. P. 208–217.

9. Dinh L., Krueger D., Bengio Y. NICE: Non-linear independent components estimation. Available at: 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. P. 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. P. 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; 1: 1021–1032.

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

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

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

16. Price A., Hall J. A Survey on Trapping Sets and Stopping Sets. Available at: 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. P. 2305-2309.

18. Myung S., Yang K., Kim Y. Lifting methods for quasi-cyclic LDPC codes. IEEE Comm. Lett. 2006; 10(6): 489-491.

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

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

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

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

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. P. 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; 58(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; 59(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/ P. 2774-2779.

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

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

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; 64(6): 4438-4451.

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

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

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. Available at: 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. P. 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; 47(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. 50(3). 406-414.