N.V. Shishkin1, A.V. Yurlov2, I.N. Molchanov3, V. O. Yudin4

1–4 The Academy of the Federal Guard Service of the Russian Federation (Orel, Russia)
1 shishkin_nv@mail.ru, 2 yurlov@bk.ru, 3 zorro_42@rambler.ru, 4 attitudehxc@gmail.com

Forward error correction (FEC) codes play a vital role in improving the error performance of digital communication systems by correcting the random errors due to noisy channel conditions. The message is encoded at the transmitter by channel encoder and decoded at the receiver knowing the parameters of code such as generator and parity check matrices. However, only limited knowledge about the FEC code parameters is available at the receiver sometimes. Specification recovery for communication systems from received signal, without any knowledge about the transmitter system is very complicated.

Reconstruction of channel coding parameters plays a significant role in applications such as cognitive radio, adaptive modulation and coding (AMC), etc. Therefore, it is essential to reconstruct the channel encoder by identifying the code parameters using the recieved sequences.

Low-density parity-check (LDPC) codes have recently emerged due to their excellent performance. Technically, LDPC belong to the class of linear block codes. Low-density parity-check codes are used in various applications such as Digital video broadcasting-satellite-second generation (DVB-S2) system, IEEE 802.11 Wi-Fi systems, etc.

In this paper, the algorithm of identification of parameters of the FEC code is proposed to obtain parity-check matrix of LDPC but limited to non-erroneous channel conditions. Here we study the problem of the blind identification of the parity check matrix of LDPC codes using a sample of a sufficient number of codewords.

The identification of parameters of LDPC codes requires obtaining a parity check matrix into an equivalent systematic form, which can be accomplished by Gaussian elimination.

Gaussian elimination requires large memory and heavy calculation. From a complexity theoretical point of view, the solution of an linear systems of equations (LSEs) is efficiently computable, i.e., using the well-known Gaussian elimination algorithm any LSEs can be solved in at most cubic time.

However, for the case in the process of identification of parameters of FEC code like LDPC its software implementation is unsatisfying in practice. This is due to the very large but sparse LSEs that must be solved to obtain a parity check matrix.

This paper reviews standard Gaussian elimination and presents a modified variant of the well-known Gaussian elimination for solving LSEs and its highly efficient implementation. In the paper proposed a fast recovery scheme based on the «Method of Four Russians» for matrix multiplication.

Shishkin N.V., Yurlov A.V., Molchanov I.N., Yudin V.O. Modified algebraic method of identification of a forward error correction code. Dynamics of complex systems. 2025. V. 19. № 3. P. 67−73. DOI: 10.18127/j19997493-202503-07 (in Russian).

1. Kir'yanov I.A. Sravnenie perspektivnyh tekhnik pomekhoustojchivogo kodirovaniya informacii. Elektromagnitnye volny i elektronnye sistemy. 2015, № 1, S. 26–34 (in Russian).
2. Karimian Y. Ziapour S., Ahmadian-Attari M. Parity Check Matrix Recognition from Noisy Codewords. Elektronnaya publikaciya v repozitorii arXiv.org, arXiv:1205.4641. 2012.
3. Valembois A. Detection and recognition of a binary linear code. Discrete Applied Mathematics 111(1–2). 2001.
4. Zacepina T.P. Analiz struktury cifrovyh potokov. CHast' 1. Gruppovye blochnye kody. M.: AFSB. 1999. 113 s. (in Russian).
5. Vinberg E.B. Kurs algebry. Izd. 2-e. M.: Faktorial Press. 2001. S. 43–90 (in Russian).
6. Gregory V. Bard. Accelerating cryptanalysis with the Method of Four Russians. Cryptology ePrint Archive. Report 2006/251. 2006. 20 с.
7. Martin R. Albrecht. Clément Pernet. Efficient Decomposition of Dense Matrices over GF(2). arXiv:1006.1744. 2010. 17 с.