CONSTRUCTION OF LDPC CODES GENERATING MATRIX
Article Sidebar
Main Article Content
Abstract
This paper presents a detailed analysis of the problem of constructing encoders for linear block codes, with a special emphasis on low-density parity-check (LDPC) codes. The aim of this paper is to provide a comprehensive description of the mathematical methods for the transition from the verification matrix to the efficient coding process. Both classical linear algebra approaches and specialized methods for sparse matrices. Results. The fundamental algebraic constructions underlying the duality between the generating and checking matrices over Galois fields, in particular GF (2), are considered. The classical Gaussian exclusion method for systematic coding is analyzed in detail and its shortcomings in the context of LDPC codes, related to the fill-in phenomenon and loss of sparsity, are revealed. The central place in the study is occupied by the Approximate Lower Triangulation method proposed by Richardson and Urbanky, which allows achieving linear coding complexity. The article contains a detailed description of matrix preprocessing algorithms, mathematical derivation of formulas for calculating parity bits, as well as an analysis of quasicyclic constructions used in modern telecommunications standards (5G, Wi-Fi). Full numerical examples of transformations for low-dimensional codes and a detailed analysis of the LDPC encoder architecture are given. Conclusion. The solution was to abandon the explicit use of the generating matrix in favor of approximate triangulation methods of the check matrix and the use of quasicyclic structures, which has become standard in 5G and Wi-Fi. The integration of algebraic-geometric methods opens up new prospects for creating codes with specified properties.
Article Details
References
Guruswami, V. (2006), Iterative Decoding of Low-Density Parity Check Codes - CMU School of Computer Science, University of Washington Seattle, WA 98195, 29 p., available at: https://www.cs.cmu.edu/~venkatg/pubs/papers/ldpc.pdf
Nozaki, T. (2016), “Parallel Encoding Algorithm for LDPC Codes Based on Block-Diagonalization”, 2015 IEEE International Symposium on Information Theory (ISIT), IEEE, China, doi: https://doi.org/10.1109/ISIT.2015.7282788
Zeng, Z., Feng, Y. and Sun, X. (2012), “An efficient LDPC encoder for CMMB using RU method”, Procedia Engineering, vol. 29, pp. 1851–1855, doi: https://doi.org/10.1016/j.proeng.2012.01.225
Kuchuk, N., Mozhaiev, M., Kalinin, Y., Mozhaev, O. and Kuchuk, H. (2022), “Calculation of Signal Information Delay in Intelligent Communication Networks”, 2022 IEEE 3rd KhPI Week on Advanced Technology, KhPI Week 2022 - Conference Proceedings, doi: https://doi.org/10.1109/KhPIWeek57572.2022.9916323
Khodaiemehr, H. and Kiani, D. (2017), “Construction and Encoding of QC-LDPC Codes Using Group Rings”, IEEE Transactions on Information Theory, vol. 63, is. 4, pp. 2039–2060, doi: https://doi.org/10.1109/TIT.2017.2655029
Nguyen, T. T. B., Nguyen Tan, T., and Lee, H. (2019), “Efficient QC-LDPC Encoder for 5G New Radio”, Electronics, vol. 8(6), 668, doi: https://doi.org/10.3390/electronics8060668
İbrahimov B.G., Hasanov A.H. and Hashimov E.G. (2024), “Research and analysis of efficiency indicators of critical infrastructures in the communication system”, Advanced Information Systems, vol. 8, no. 2, pp. 58–64, doi: https://doi.org/10.20998/2522-9052.2024.2.07
Yevseiev, S., Rzayev, K., Korol, O., and Imanova, Z. (2016), “Development of mceliece modified asymmetric crypto-code system on elliptic truncated codes”, Eastern-European Journal of Enterprise Technologies, vol. 4(9(82)), pp. 18–26, doi: https://doi.org/10.15587/1729-4061.2016.75250
Rezanov, B., and Kuchuk, H. (2023), “Model of elemental data flow distribution in the Internet of Things supporting Fog platform”, Innovative Technologies and Scientific Solutions for Industries, no. 3(25), pp. 88–97, doi: https://doi.org/10.30837/ITSSI.2023.25.088
Kuchuk, G., Kovalenko, A., Kharchenko, V. and Shamraev, A. (2017), “Resource-oriented approaches to implementation of traffic control technologies in safety-critical I&C systems”, Studies in Systems, Decision and Control, vol. 105, pp. 313–337, doi: https://doi.org/10.1007/978-3-319-55595-9_15
Yevseiev, S., Korol, O., and Kots, H. (2017), “Construction of hybrid security systems based on the crypto-code structures and flawed codes”, Eastern-European Journal of Enterprise Technologies, vol. 4(9 (88), pp. 4–21, doi: https://doi.org/10.15587/1729-4061.2017.108461
Kuchuk, G., Kharchenko, V., Kovalenko, A. and Ruchkov, E. (2016), “Approaches to selection of combinatorial algorithm for optimization in network traffic control of safety-critical systems”, Proceedings of 2016 IEEE East-West Design and Test Symposium, EWDTS 2016, 7807655, doi: https://doi.org/10.1109/EWDTS.2016.7807655
Zhang, T., Li, C., Wu, X. and Wu, Y. (2024), “Reconstruction of LDPC code sparse check matrix based on modified LBP decoding”, Tongxin Xuebao Journal on Communications, vol. 45(5), pp. 70–79, doi: https://doi.org/10.11959/j.issn.1000-436x.2024097
Pathak, R. and Awasthi, S.K. (2025), “Implementation of Low-Density Parity-Check (LDPC) Codes in Verilog HDL”, International Conference on Electronics AI and Computing Innovating for A Sustainable and Connected Future Eaic 2025, doi: https://doi.org/10.1109/EAIC66483.2025.11101329
Vladyslav, Y. and Kosenko, V. (2024), “Low-power coding method in data transmission systems”, Innovative technologies and scientific solutions for industries, no. 3 (29), pp. 121–129, doi: https://doi.org/10.30837/2522-9818.2024.3.121
Li, C., Zhang, T., Wu, Y. and Wu, X. (2025), “Reconstruction of QC-LDPC code sparse check matrix based on spatial compression”, Systems Engineering and Electronics, vol. 47(10), pp. 3504–3511, doi: https://doi.org/10.12305/j.issn.1001-506X.2025.10.33
Ruban, I., Kuchuk, H., Kovalenko, A., Lukova-Chuiko, N. and Martovytsky, V. (2021), “Method for Determining the Structural Reliability of a Network Based on a Hyperconverged Architecture”, Studies in Computational Intelligence, vol. 976, pp. 147–163, doi: https://doi.org/10.1007/978-3-030-74556-1_9
Balamurugan, K. and Janakiraman, N. (20250, “An Effective Non-linear Distortion Elimination and Data Transmission Using Hybrid BCH-LDPC Coding and 64-APSK Modulator Scheme in Satellite Forward Link”, Lecture Notes in Electrical Engineering, 1323 LNEE, pp. 453–464, doi: https://doi.org/10.1007/978-981-96-1587-2_35
Mozhaev, O., Kuchuk, H., Kuchuk, N., Mykhailo, M. and Lohvynenko, M. (2017), “Multiservice network security metric”, 2nd International Conference on Advanced Information and Communication Technologies, AICT 2017 – Proceedings, pp. 133–136, doi: https://doi.org/10.1109/AIACT.2017.8020083
Kharchenko, V., Andrashov, A., Sklyar, V., Kovalenko, A. and Siora, O. (2013), “Gap-and-IMECA-Based Assessment of I&C Systems Cyber Security”, Complex Systems and Dependability. Advances in Intelligent and Soft Computing, vol 170, Springer, Berlin, Heidelberg, https://doi.org/10.1007/978-3-642-30662-4_10
Korchenko, O. G., Tereikovskyi, I. A., Korystin, O. Y., Tereikovska, L. O. and Tereikovskyi, O.I. (2026), “A method for detecting financial phishing in instant messengers using an ensemble of dialogical intelligent assistants based on large language models”, Herald of Advanced of Information Technology, vol. 9, no. 1, pp. 71–84, doi: https://doi.org/10.15276/hait.09.2026.06
Yevseiev, S., Korol, O., and Kots, H. (2017), “Construction of hybrid security systems based on the crypto-code structures and flawed codes” Eastern-European Journal of Enterprise Technologies, vol. 4(9 (88), pp. 4–21, doi: https://doi.org/10.15587/1729-4061.2017.108461
Dmitrishin, D. V., Khamitov, V. M., Antoshchuk, S.G. and Boltеnkov, V. O. (2026), “A modified image encryption algorithm based on the chaotic Tent map”, Herald of Advanced of Information Technology, vol. 9, no. 1, pp. 9–19, doi: https://doi.org/10.15276/hait.09.2026.01
Kuchuk, N., Kashkevich, S., Radchenko, V., Andrusenko, Y. and Kuchuk, H. (2024), “Applying edge computing in the execution IoT operative transactions”, Advanced Information Systems, vol. 8, no. 4, pp. 49–59, doi: https://doi.org/10.20998/2522-9052.2024.4.07
Yevseiev, S., Tsyhanenko, O., Ivanchenko, S., Aleksiyev, V., Verheles, D., Volkov, S., Korolev, R., Kots, H., Milov, O., and Shmatko, O. (2018), “Practical implementation of the Niederreiter modified crypto¬code system on truncated elliptic codes”, Eastern-European Journal of Enterprise Technologies, vol. 6(4 (96), pp. 24–31, doi: https://doi.org/10.15587/1729-4061.2018.150903
Soloviova, D. V., Antoshchuk, S. G. and Boltenkov, V. O. (2026), “Research into the Possibilities of Improving Proof-of-Work Blockchain Technology”, Herald of Advanced of Information Technology, vol. 7, no. 2, pp. 131–146, doi: https://doi.org/10.15276/hait.07.2024.9
Lada, N. and Rudnytska, Y. (2022), “Implementation of a method for synthesizing groups of symmetric double-operand operations of cryptographic information coding for block encryption systems Innovative technologies and scientific solutions for industries, no. 2 (20), pp. 35–43, doi: https://doi.org/10.30837/ITSSI.2022.20.035
Kuchuk, H., Kalinin, Y., Dotsenko, N., Chumachenko, I. and Pakhomov, Y. (2024), “Decomposition of integrated high-density IoT data flow”, Advanced Information Systems, vol. 8, no. 3, pp. 77–84, doi: https://doi.org/10.20998/2522-9052.2024.3.09
Yevseiev, S., Tsyhanenko, O., Gavrilova, A., Guzhva, V., Milov, O., Moskalenko, V., Opirskyy, I., Roma, O., Tomashevsky, B., and Shmatko, O. (2019), “Development of Niederreiter hybrid crypto-code structure on flawed codes”, Eastern-European Journal of Enterprise Technologies, vol. 1(9 (97), pp. 27–38, doi: https://doi.org/10.15587/1729-4061.2019.156620
Rezanov, B. And Kuchuk, H. (2022), Fast Two-Factor Authentication Method in Systems With a Centralized User's Database, 2022 IEEE 4th KhPI Week on Advanced Technology, KhPI Week 2022 – Conference Proceedings, 03-07 October 2022, Code 183771, doi: https://doi.org/10.1109/KhPIWeek57572.2022.9916491
Kharchenko, V., Kovalenko, A., Andrashov, A. and Siora, A. (2012), “Cyber security of FPGA-based NPP I&C systems:challenges and solutions”, 8th International Conference Topical Meeting on Nuclear Plant Instrumentation, Control and Human Machine Interface Technologies, San Diego, California, Westin San Diego, available at: https://www.researchgate.net/publication/319292444_CYBER_SECURITY_OF_FPGA-BASED_NPP_IC_SYSTEMS_CHALLENGES_AND_SOLUTIONS
Petrović, V. L., El Mezeni, D. M., and Radošević, A. (2021), “Flexible 5G New Radio LDPC Encoder Optimized for High Hardware Usage Efficiency”, Electronics, vol. 10(9), article number: 1106, doi: https://doi.org/10.3390/electronics10091106
Yevseiev, S., Hryshchuk, R., Zakovorotnyi, O., Milov, O., Kuchuk, H. and Milevskyi, S. (2024), “Intelligent Control and Security Systems Models Synthesis Methodology for Critical Infrastructure Objects”, 2024 IEEE 5th International Conference on Advanced Trends in Information Theory, pp. 275–281, doi: https://doi.org/10.1109/ATIT64324.2024.11222460
Pohasii, S., Yevseiev, S., Zhuchenko, O., Milov, O., Lysechko, V., Kovalenko, O., Kostiak, M., Volkov, A., Lezik, A., and Susukailo, V. (2022), “Development of crypto-code constructs based on LDPC codes”, Eastern-European Journal of Enterprise Technologies, vol. 2(9 (116), pp. 44–59., doi: https://doi.org/10.15587/1729-4061.2022.254545
Milevskyi, S., Korol, O., Mykytyn, G., Lozova, I., Solnyshkova, S., Husarova, I., Hrebeniuk, A., Vlasov, A., Sukhoteplyi, V., and Balagura, D. (2024), “Development of the sociocyberphysical systems` multi-contour security methodology”, Eastern-European Journal of Enterprise Technologies, vol. 1(9 (127)), pp. 34–51, doi: https://doi.org/10.15587/1729-4061.2024.298844