On Soft Solutions Decoder for Reed–Muller Binary Codes of the Second Order
DOI:
https://doi.org/10.14529/cmse200204Keywords:
Reed–Muller codes, decoder, model of channel, proof of decoder correctnessAbstract
A general model of a noise-resistant binary data channel is constructed, intended for use with various soft decision decoders. The communication line considered in the model is discrete in input and continuous in output. Discrete signals from the multiplicative binary alphabet are received at its input, and due to distortions acting in the communication line, symbols from the multiplicative group of the field of real numbers are formed at the output after filtering, which are then fed to the input of the error-correcting code decoder. Soft and probabilistic decoders of error-correcting codes allow correcting more errors in code words than is guaranteed by the minimum distance of the code used. The paper considers a probabilistic Sidelnikov–Pershakov decoder of soft solutions for Reed–Muller codes of the second order in the modification proposed by P. Loidreau and B. Sakkour. Earlier, the effectiveness of these decoders was confirmed by simulation experiments, but there was no theoretical justification. In this paper, the requirement to the communication channel, called the smoothness of the channel, is formulated, in which the correctness of this decoder is theoretically proved in the case when the number of errors per code word does not exceed half the code distance. The proof is based on the use of the theory of quadratic forms and methods of differential calculus in the polynomial ring of several variables over Galois fields.
References
Loidreau P., Sakkour B. Modified version of Sidel'nikov–Pershakov decoding algorithm for binary second order Reed–Muller codes. Ninth International Workshop on Algebraic and Combinatorial Coding theory (ACCT’2004) (Kranevo, Bulgaria, 2004). 2004. Р. 266–271.
Pellikaan R., Wu X.-W. List decoding of q-ary Reed–Muller Codes. IEEE Trans. On Information Theory. 2004. Vol. 50, no. 3. P. 679–682. DOI: 10.1109/tit.2004.825043.
Deundyak V.М., Mogilevskaya N.S. Differentiation of polynomials in several variables over Galois fields of odd cardinality and applications to Reed–Muller codes. Vestnik of Don State Technical University. 2018. Vol. 18, no. 3. P. 339–348. (in Russian) DOI: 10.23947/1992-5980-2018-18-3-339-348.
Deundyak V.M., Mogilevskaya N.S. The model of the ternary communication channel with using the decoder of soft decision for Reed–Muller codes of the second order. University news. North-Caucasian region. Technical sciences series. 2015. Vol. 1, no. 182. P. 3–10. (in Russian) DOI: 10.17213/0321-2653-2015-1-3-10.
Deundyak V.M., Mogilevskaya N.S. On Correctness Conditions of a Soft-Decisions Decoder for Ternary Reed–Muller Codes of Second Order. Vladikavkaz Mathematical Journal. 2016. Vol. 18, no. 4. P. 23–33. (in Russian)
Deundyak V.M., Mogilevskaya N.S. The confidential data divided transmission scheme based on differential calculus of polynomials in several variables over prime Galois fields Voprosy kiberbezopasnosti. 2017. Vol. 5, no. 24. P. 64–71. (in Russian) DOI: 10.21681/2311-3456-2017-5-64-71.
Logachev O.A., Salnikov A.A., Iashchenko V.V. Boolean functions in coding theory and cryptology. MCCME, 2004. 470 p. (in Russian)
Mogilevskaya N.S., Skorobogat V.R., Chudakov V.S. Experimental research of second order Reed–Muller codes. Vestnik of Don State Technical University. 2008. Vol. 8, no. 3. P. 231–237. (in Russian)
Morelos-Saragosa R. The art of noiseless coding. Methods, Algorithms, Application. Tekhnosfera, 2005. 320 p. (in Russian)
Sidelnikov V.M., Pershakov A.S. Decoding of Reed–Muller codes with a large number of errors. Problems of Information Transmission. 1992. Vol. 28, no. 3. P. 80–94. (in Russian)
Skliar B. Digital communication. Theoretical foundations and practical application. Viliams Press, 2016. 1104 p. (in Russian)
Hirsch M. Differential topology. Mir Press, 1979. 280 p. (in Russian)
