О декодере мягких решений двоичных кодов Рида-Маллера второго порядка
Автор: Деундяк Владимир Михайлович, Могилевская Надежда Сергеевна
Статья в выпуске: 2 т.9, 2020 года.
Бесплатный доступ
Построена общая модель помехоустойчивого двоичного канала передачи данных, предназначенная для использования с различными декодерами мягких решений. Линия связи, рассматриваемая в модели, является дискретной по входу и непрерывной по выходу. На ее вход поступают дискретные сигналы из мультипликативного двоичного алфавита, а в силу искажений, действующих в линии связи, на выходе после фильтрации формируются символы из мультипликативной группы поля вещественных чисел, которые затем подаются на вход декодера помехоустойчивого кода. Мягкие и вероятностные декодеры помехоустойчивых кодов позволяют исправлять большее количество ошибок в кодовых словах, чем гарантируется минимальным расстоянием используемого кода. В работе рассмотрен вероятностный декодер мягких решений Сидельникова-Першакова для кодов Рида-Маллера второго порядка в модификации, предложенной П. Лоидрю и Б. Саккуром. Ранее эффективность этих декодеров была подтверждена с помощью имитационных экспериментов, но теоретическое обоснование отсутствовало. В настоящей работе сформулировано требование к каналу связи, названное гладкостью канала, при выполнении которого теоретически доказана корректность этого декодера в случае, когда количество ошибок на каждое кодовое слово не превосходит половины кодового расстояния. В основе доказательства лежит использование теории квадратичных форм и методов дифференциального исчисления в кольце полиномов нескольких переменных над полями Галуа.
Коды рида-маллера, декодер, модель канала, доказательство корректности декодера
Короткий адрес: https://sciup.org/147234273
IDR: 147234273 | УДК: 519.876.5, | DOI: 10.14529/cmse200204
On soft solutions decoder for Reed-Muller binary codes of the second order
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.
Список литературы О декодере мягких решений двоичных кодов Рида-Маллера второго порядка
- 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. Р. 266271.
- 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.
- Деундяк В.М., Могилевская Н.С. Дифференцирование полиномов нескольких переменных над полями Галуа нечетной мощности и приложения к кодам Рида-Маллера // Вестник Донского государственного технического университета. 2018. Т. 18, № 3. С. 339-348. DOI: 10.23947/1992-5980-2018-18-3-339-348.
- Деундяк В.М., Могилевская Н.С. Модель троичного канала передачи данных с использованием декодера мягких решений кодов Рида—Маллера второго порядка // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Технические науки. 2015. № 1(182). С. 3-10. DOI: 10.17213/0321-2653-2015-1-3-10.
- Деундяк В.М., Могилевская Н.С. Об условиях корректности декодера мягких решений троичных кодов Рида—Маллера второго порядка // Владикавказский математический журнал. 2016. Т. 18, № 4. С. 23-33.
- Деундяк В.М., Могилевская Н.С. Схема разделенной передачи конфиденциальных данных на основе дифференцирования полиномов нескольких переменных над простыми полями Галуа // Вопросы кибербезопасности. 2017. Т. 5, № 24. С. 64-71. DOI: 10.21681/2311-3456-2017-5-64-71.
- Логачев О.А. Булевы функции в теории кодирования и криптологии. Москва: МЦНМО, 2004. 470 с.
- Могилевская Н.С., Скоробогат В.Р., Чудаков B.C. Экспериментальное исследование декодеров кодов Рида—Маллера второго порядка / / Вестник ДГТУ. 2008. Т. 8, № 3. С. 231-237.
- Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Москва: Техносфера, 2005. 320 с.
- Сидельников В.М., Першаков А.С. Декодирование кодов Рида—Маллера при большом числе ошибок / / Пробл. передачи информ. 1992. Т. 28, № 3. С. 80-94.
- Скляр Б. Цифровая связь. Теоретические основы и практическое применение, 2-е издание. Москва: Издательский дом «Вильямс», 2016. 1104 с.
- Хирш М. Дифференциальная топология. Москва: Мир, 1979. 280 с.
