Encoding Methods for Random Low-Density Parity-Check Codes
DOI: 10.21293/1818-0442-2026-29-2-64-73
Abstract: Relevance. The development and investigation of encoding methods for random low-density parity-check (LDPC) codes is an important task in the design of high-speed communication systems, since different codeword generation algorithms differ significantly in computational cost and implementation requirements. Purpose of the study. Comparative analysis of encoding methods for LDPC-codes defined by random sparse parity-check matrices, with an assessment of their computational complexity and practical performance. Methods. The study employs methods of linear algebra, analytical estimation of computational complexity, simulation modeling, and the Monte Carlo method. The encoding approaches under study include Neal's method, algorithms based on LU and LUP-decompositions, transformation of the parity-check matrix to row-echelon form, as well as lower and approximate lower triangulation methods. Scientific novelty. A comparative study of encoding methods for random LDPC codes was carried out, including a joint assessment of their analytical computational complexity and software implementation time under identical initial conditions. Results. Differences in the growth patterns of computational costs among the considered methods as the size of the parity-check matrix increases were identified. It was shown that Neal's method, LU decomposition, and the method based on transformation to row-echelon form require fewer arithmetic operations, whereas the results of software simulations depend significantly on the implementation approach and the optimization capabilities for matrix operations in MatLab. Practical significance. The obtained results can be used to select encoding algorithms for random LDPC-codes and developing software and hardware encoders for high-speed communication systems.
Keywords: LDPC, low-density parity-check codes, random matrices, error-correcting coding, computational complexity
For citation:
Kravchenko A. N., Pokamestov D. A. Encoding Methods for Random Low-Density Parity-Check Codes. Doklady Tomskogo gosudarstvennogo universiteta sistem upravleniya i radioelektroniki, 2026, vol. 29, no. 2, pp. 64–73. DOI: 10.21293/1818-0442-2026-29-2-64-73
Authors and copyright holders:
- Kravchenko A. N. , Ubiso GmbH
- Pokamestov D. A. , Tomsk State University of Control Systems and Radioelectronics
- 1. Pokamestov D.A., Kryukov Y.V., Abenov R.R., Rogozhnikov E.V., Brovkin A.A., Shinkevich A.S., Shalin G.N. 6G communication systems: concept, trends, physical level technologies. Radio Engineering and Electronics, 2024, vol. 69, no. 1, pp. 3–33.
- 2. Gallager R.G. Low-density parity-check codes. IRE Transactions on Information Theory, 1962, vol. 8, no. 1, pp. 21–28.
- 3. Rowshan M., Qiu M., Xie Y., Gu X., Yuan J. Channel Coding Toward 6G: Technical Overview and Outlook. IEEE Open Journal of the Communications Society, 2024, vol. 5, рр. 2585–2685.
- 4. Trifonov P.V. Osnovy pomekhoustoichivogo kodiro- vaniya: uchebnoe posobie [Fundamentals of error-correcting coding: textbook]. Saint-Petersburg, ITMO University Publ., 2022, 231 p. (in Russ.).
- 5. Lin S. Structured Low-Density Parity-Check Codes: Algebraic Constructions. IEEE 802.3an Task Force Meeting, IEEE, Portland, OR, July 13–15, 2004.
- 6. Donovan D., Price A., Rao A., Üsküplü E., Yazıcı E.Ş. High-rate LDPC codes from partially balanced incomplete block designs. Journal of Algebraic Combinatorics, 2022, vol. 55, pp. 259–275.
- 7. MacKay D.J.C. Good error-correcting codes based on very sparse matrices. IEEE Transactions on Information The- ory, 1999, vol. 45, no. 2, pp. 399–431.
- 8. Kravchenko A.N. [Reduced-complexity decoding (in Russ.).
- 9. Subhi M.I., Al-Doori Q., Alani O. Enhancing data com- munication performance: a comprehensive review and evalua- tion of LDPC decoder architectures. Ingénierie des Systèmes d'Information, 2023, vol. 28, no. 5, pp. 1113–1125.
- 10. MacKay D.J.C. Encyclopedia of Sparse Graph Codes. Available at: http://www.inference.org.uk/mackay/codes/ data.html (accessed: 19 August 2026).
- 11. Neal R.M. Sparse matrix methods and probabilistic in- ference algorithms. IMA Program on Codes, Systems and Graphical Models, 1999, pp. 1–16.
- 12. Strang G. Introduction to Linear Algebra. 6th ed. Wellesley, MA, USA: Wellesley-Cambridge Press, 2023, 537 p.
- 13. Verzhbitskii V.M. Vychislitelnaya lineinaya algebra [Computational linear algebra]. Moscow, Vysshaya shkola Publ., 2009, 352 p. (in Russ.).
- 14. LUP-razlozhenie kvadratnykh matrits [LUP decompo- sition of square matrices]. Available at: https://study.sfu- kras.ru/DATA/docs/ProgramTheory/recurs/lup_expn.htm (ac- cessed: 19 August 2026).
- 15. Harris S.L., Harris D. Digital design and computer ar- chitecture: RISC-V edition. Elsevier, Morgan Kaufmann, 2021, 592 p.
- 16. Lee D.-U., Luk W., Wang C., Jones C., Smith M., Vil- lasenor J. A flexible hardware encoder for low-density parity- check codes. Proc. 12th Annual IEEE Symposium on Field-Pro- grammable Custom Computing Machines, 2004, pp. 101–111.
- 17. Liao X., Guo J., Luo Z., Xu Y., Chu Y. Research and implementation of high-efficiency and low-complexity LDPC coding algorithm. Electronics, 2023, vol. 12, no. 17, pp. 1–20.
- 18. Richardson T.J., Urbanke R.L. Efficient encoding of low-density parity-check codes. IEEE Transactions on Infor- mation Theory, 2001, vol. 47, no. 2, pp. 638–656.
- 19. Watkins D.S. Osnovy matrichnykh vychislenii [Funda- mentals of matrix computations]. Moscow, BINOM. Labora- toriya znanii Publ., 2006, 664 p. (in Russ.).
- 20. Partitioned matrices and the Schur complement. Avail- able at: https://quickfem.com/wp-content/uploads/IFEM. AppP_.pdf (accessed: 19 August 2026).
- 21. Golub G.H., Van Loan C.F. Matrix computations. 4th ed. Baltimore, Johns Hopkins University Press, 2013, 756 p.
- 22. Tian Y., Bai Y., Liu D. Low-latency QC-LDPC en- coder design for 5G NR. Sensors, 2021, vol. 21, no. 18, pp. 6266.
- 23. Petrović V.L., Mezeni D.M., Radošević A. Flexible 5G New Radio LDPC encoder optimized for high hardware usage efficiency. Electronics, 2021, vol. 10, no. 9, pp. 1106.
Last issue
Editorial office address
Executive Secretary of the Editor’s Office
Editor’s Office: 40 Lenina Prospect, Tomsk, 634050, Russia
Phone / Fax: + 7 (3822) 701-582
Executive Secretary of the Editor’s Office
Editor’s Office: 40 Lenina Prospect, Tomsk, 634050, Russia
Phone / Fax: + 7 (3822) 51-21-21 / 51-43-02
Subscription for updates
