Construction of LDPC Codes Using Cole's Modified Importance Sampling Method
https://doi.org/10.21869/2223-1560-2023-27-1-92-110
Abstract
Purpose of research is a modification of Cole's importance sampling method for finding trapping sets in an LDPC code to speed up their search.
Methods. Cole proposed a method for searching for trapping sets in an LDPC code by using a Monte Carlo method that causes the decoding algorithm to fail at nodes potentially contained in trapping sets. His method makes it possible to accelerate the study of the efficiency of medium-length LDPC codes in the region of large SNRs. The modified method uses the properties of automorphisms of Tanner graphs, which make it possible to exclude a significant number of symbolic nodes from the enumeration. The modified method also provides for an ordered enumeration over subgraphs containing cycles.
Results. The proposed method made it possible to speed up the search for trapping sets in Mackay's PEG(1008, 504) LDPC code by 5027 times compared to the Velasquez-Subramani method, and 43 times faster compared to the original Cole method. In the case of (2640, 1320) LDPC Margulis code, the proposed method is 28 times faster than the Velasquez-Subramani quasi-cyclic method and 134 times faster than the original Cole method.
Conclusion. The result of experimental studies showed the possibility of using the developed method to improve the connectivity spectrum, increase the code distance of QC-LDPC codes. This made it possible to reduce the probability of a bit error at the decoder output by orders of magnitude at high signal-to-noise ratios in the AWGN channel.
About the Authors
V. S. Usatjuk
Company T8
Russian Federation
Russian Federation
Vasily S. Usatjuk, Head Engineer, R&D department
44, Krasnobogatyrskaya str., p. 1, Moscow 107076, Russian Federation
S. I. Egorov
Southwest State University
Russian Federation
Russian Federation
Sergey I. Egorov, Dr. of Sci. (Engineering), Associate Professor
50 Let Oktyabrya str. 94, Kursk 305040, Russian Federation
References
1. Cole C. A., et al. Regular {4, 8} LDPC Codes and Their Low error Floors. MILCOM, 2006, pp. 1-7.
2. Cole C. A., et al. Analysis and Design of Moderate Length Regular LDPC Codes with Low Error Floors. 40th CISS, 2006, pp. 823-828.
3. Cole C. A. Error floor analysis for an ensemble of easily implementable irregular (2048, 1024) LDPC codes. MILCOM, 2008, pp. 1-5.
4. 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)
5. 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, 2018, vol. 10856, pp. 402–415.
6. Usatyuk V.S., Egorov S.I. Ustroistvo dlya otsenki kodovogo rasstoyaniya lineinogo blochnogo koda metodom geometrii chisel [A device for estimating the code distance of a linear block code by the geometry of numbers method]. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. 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.
7. Richardson T. J. Error floors of LDPC codes. 41st Annual Allerton Conference on Comm., Control and Computing, Oct. 2003, pp. 1426–1435.
8. Chen J., Tanner R. M., Jones C., Li Y. Improved min-sum decoding algorithms for irregular LDPC codes. ISIT, 2005, pp. 449-453.
9. Zhang J., Fossorier M., Gu D., Zhang J. Two-dimensional correction for min-sum decoding of irregular LDPC codes. IEEE Communications Letters, March 2006, vol. 10, no. 3, pp. 180-182.
10. Zhang S., Schlegel C. Controlling the Error Floor in LDPC Decoding. IEEE Transactions on Comm., 2013, vol. 61(9), pp. 3566-3575.
11. 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.
12. Vasić B., et al Trapping set ontology. 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2009, pp. 1-7.
13. McGregor A., Milenkovic O. On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes. IEEE ITW, 2007, pp. 248-253.
14. Jeruchim M. Techniques for estimating the bit error rate in the simulation of digital communication systems. IEEE Journal on selected areas in communications, 1984, vol. 2, no. 1, pp. 153–170.
15. Smith P. J., Shafi M., Gao H. Quick simulation: A review of importance sampling techniques in communication systems. IEEE J.Select.Areas Commun, 1984, vol. 15, pp. 597–613.
16. Gradov V.M., Ovechkin G.V., Ovechkin P.V., Rudakov I. V. Komp'yuternoe modelirovanie [Computer simulation]. Moscow, Infra-M Publ., 2020, 264 p.
17. Vasić B., Chilappagari S.K., Nguyen D. V. Chapter 6 - Failures and Error Floors of Iterative Decoders, Editor(s): Declerq D., Fossorier M., Biglieri E., Academic Press Library in Mobile and Wireless Comm., 2014, pp. 299-341
18. Tanner R. M., Fuja T. E., Sridhara D. A Class of Group Structured LDPC Codes. Proceedings 6th ISCTA. Ambleside, England, July 2001, pp.365-370.
19. Fossorier M. P. C. Quasi-cyclic low-density parity-check codes fromcirculant permutation matrices. IEEE Trans. Inf. Theory, Aug. 2004, vol. 50, no. 8, pp. 1788–1793.
20. Halford T. R., Chugg K. M. An algorithm for counting short cycles in bipartite graphs. IEEE Trans. on Inform. Theory, 2006, vol. 52(1), pp. 287-292.
21. Usatyuk V., Vorobyev I. Simulated Annealing Method for Construction of HighGirth QC-LDPC Codes. 41st International Conference on Telecommunications and Signal Processing (TSP). Athens, Greece, 2018.
22. Usatyuk V., Egorov S., Svistunov G. Construction of Length and Rate Adaptive MET QC-LDPC Codes by Cyclic Group Decomposition. IEEE East-West Design & Test Symposium (EWDTS). Batumi, Georgia, 2019.
23. Schlegel C., Zhang S., "On the Dynamics of the Error Floor Behavior in (Regular) LDPC Codes. IEEE Transactions on Information Theory, 2010, vol. 56, no. 7, pp. 3248-3264.
Review
For citations:
Usatjuk V.S., Egorov S.I. Construction of LDPC Codes Using Cole's Modified Importance Sampling Method. 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
Views:
810
Email the author 
Post a Comment 
