+7 (495) 957-77-43

Article 8-6 2019

Извините, этот техт доступен только в “Американский Английский”. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.


Nikita Yu. Rumenko,  Moscow technical university of communication and informatics, Moscow, Russia 
Alexander V. Kostyuck,  Moscow technical university of communication and informatics, Moscow, Russia, tigran 201094@ mail.ru

Ever-increasing requirements for high-quality and high-speed communications lead to more and more sophisticated, noise-tolerant waveforms and communication protocols. Recent advances in power control, adaptive coding and modulation now makes it possible to transmit signal under much worse channel conditions than as far as twenty years ago. In cognitive radio systems, as well as in non-cooperative communication channels, the parameters of error-control code often are not known a priori at the receiver. Hence, the development of blind code recognition systems is essential for future cognitive communications. Among other known error-correcting codes one of the most important class is iteratively decodable codes, especially low-density parity check ones. Excellent error-correcting performance of LDPC made them part of several communicational standards, including Wi-Fi, DVB-S2(x) and DVB-T2. Accordingly, there exist a lot of works considering LDPC blind identification methods, all of which being in fact methods of solving systems of linear equations [1-5].  In this work, we will study one special case, namely, we will consider a code with relatively dense parity checks used in a good, but rather low-rate channel. Note that in this case exhaustive search techniques including «birthday» algorithms cannot be used due to high computational complexity, and information set decoding algorithms will not have enough codewords. To handle this problem we adapt information-set decoding to few-codewords scenario and show, that for good enough channels even parity checks of weight larger than 10 can be relatively easy to find. Although all the results of this paper are not limited to the binary case, we will mainly focus on systems of boolean equations, due to the fact that most of LDPC in modern communications are binary.

Keywords: identification, error-correcting codes, LDPC, systems of equations.


  1. Cluzeau M., Finiasz M. (2009). Recovering length and synchronization from a noisy intercepted bitstream.
  2. Chabot C. (2007). Recognition of a code in a noisy environment. In IEEE Conference, ISIT’07, pр. 2210-2215.
  3. Cluzeau M. (2006). Block code reconstruction using iterative decoding techniques. In IEEE Conference, ISIT’06, pр. 2269-2273, Seattle, USA. IEEE Press.
  4. Sicot G. and Houcke S. (2005). Blind detection of interleaver parameters. In ICCASP05.
  5. Valembois A. (2001). Detection and recognition of a binary linear code Discrete Applied Mathematics, 111(1-2):199-218, July 2001.
  6. May A., Meurer A. and Thomae E. (2011). Decoding Random Linear Codes in O(20.054n) In Asiacrypt 2011. Springer, 2011.
  7. Balakin G.V. (1997). Introduction to the theory of random systems of equations, (In Russian). Transactions in applied discrete mathematics. Vol. 1, рр. 1-18.

Information about authors:
Nikita Yu. Rumenko, Moscow technical university of communication and informatics, research engineer, Moscow, Russia
Alexander V. Kostyuck, Moscow technical university of communication and informatics, PhD, senior research engineer, Moscow, Russia