О декодере мягких решений двоичных кодов Рида—Маллера второго порядка
Аннотация
Построена общая модель помехоустойчивого двоичного канала передачи данных, предназначенная для использования с различными декодерами мягких решений. Линия связи, рассматриваемая в модели, является дискретной по входу и непрерывной по выходу. На ее вход поступают дискретные сигналы из мультипликативного двоичного алфавита, а в силу искажений, действующих в линии связи, на выходе после фильтрации формируются символы из мультипликативной группы поля вещественных чисел, которые затем подаются на вход декодера помехоустойчивого кода. Мягкие и вероятностные декодеры помехоустойчивых кодов позволяют исправлять большее количество ошибок в кодовых словах, чем гарантируется минимальным расстоянием используемого кода. В работе рассмотрен вероятностный декодер мягких решений Сидельникова—Першакова для кодов Рида—Маллера второго порядка в модификации, предложенной П. Лоидрю и Б. Саккуром. Ранее эффективность этих декодеров была подтверждена с помощью имитационных экспериментов, но теоретическое обоснование отсутствовало. В настоящей работе сформулировано требование к каналу связи, названное гладкостью канала, при выполнении которого теоретически доказана корректность этого декодера в случае, когда количество ошибок на каждое кодовое слово не превосходит половины кодового расстояния. В основе доказательства лежит использование теории квадратичных форм и методов дифференциального исчисления в кольце полиномов нескольких переменных над полями Галуа.
Ключевые слова
Полный текст:
PDFЛитература
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)
DOI: http://dx.doi.org/10.14529/cmse200204