Vestnik of Don State Technical UniversityVestnik of Don State Technical UniversityВестник Донского государственного технического университета1992-5980531310.12737/10395Информатика, вычислительная техника и управлениеINFORMATION TECHNOLOGY, COMPUTER SCIENCE AND MANAGEMENTИнформатика, вычислительная техника и управлениеCorrecting capacity of soft-decision decoder of ternary Reed – Muller second-order codes with a large number of errors Корректирующая способность декодера мягких решений троичных кодов Рида - Маллера второго порядка при большом числе ошибокМогилевская Надежда СергеевнаMogilevskaya Nadezhda Сергеевнаbroshka@nm.ru3103201531032015151121130https://zh-szf.ru/en/nauka/article/5313/view
Цель работы состоит в изучении корректирующей способности нового мягкого декодера кодов Рида — Маллера. Метод достижения цели заключается в экспериментальном исследовании декодера с использованием специально построенной имитационной модели помехоустойчивого канала передачи данных. Источник и приемник сообщений модели оперируют цифровыми данными, заданными полем F3. Линия связи построенной модели в зависимости от настроек выдает цифровые или непрерывные сигналы. В случае непрерывных сигналов рассматриваются два варианта базовых искажений сигнала и их комбинации. Помехоустойчивость моделируемых каналов связи обеспечивается применением кодов Рида — Маллера второго порядка, заданных над полем F3, и нового декодера мягких решений для этих кодов. Результаты проведенных имитационных экспериментов показали, что исследуемый декодер как в цифровых, так и в полунепрерывных каналах позволяет исправлять ошибок больше, чем гарантируется минимальным кодовым расстоянием. Наибольшую эффективность декодер показал при использовании его в полунепрерывных каналах связи. Корректирующая способность декодера значительно зависит от типа линии связи и вида искажений, поражающих сигналы, и не чувствительна к местоположению ошибок внутри кодового слова. Сделаны выводы о возможности использования нового декодера в каналах связи низкого качества для обеспечения помехоустойчивости, а также в ряде криптографических приложений.
The research objective is to study the correcting capacity of a new soft decoder of Reed-Muller codes. The technique of achieving the goal is an experimental study of the decoder using a specially built simulation model of the antinoise data transfer channel. The model message source and receiver handle the numeric data identified in F3 field. The communication line of the constructed model produces digital or continuous signals depending on the settings. In the case of continuous signals, two variants of the basic signal distortion and their combinations are considered. Noise immunity of the simulated communication link is provided by using Reed-Muller second-order codes identified over F3 field, and the new soft-decision decoder for these codes. The results of the simulation experiments show that the decoder under study in both digital and semicontinuous channel allows correcting more errors than it is guaranteed by the minimum code distance. The decoder has proved the most effective in the semicontinuous communication channels. The decoder’s correcting capacity depends heavily on the communication line type and on the signal distortion mode; it is not sensitive to the error location within the codeword. Conclusions are made on the use of the new decoder in the low-rated communication channels to provide noise immunity, and in a number of the cryptographic applications.
троичный канал связитроичные коды Рида — Маллерадекодер мягких решенийматематическая модель канала связиэкспериментальное исследование корректирующей способности кодаисправление ошибок за границей половины минимального расстояния кодаternary channelternary Reed-Muller codessoft-decision decod-ermathematical model of communication channelexperimental research of the code correcting capabilityerror control out of the half minimum code distance
Введение. В разнообразных системах передачи и хранения информации для ее защиты от искажений используются алгебраические помехоустойчивые коды [1–3]. Одной из актуальных задач в настоящее время является разработка для известных кодов новых декодеров, которые обладают какими-либо преимуществами по сравнению с известными декодерами. К таким преимуществам может относиться, например, увеличение скорости работы декодера или повышение корректирующей способности кодека. Так, в последние годы для обеспечения помехоустойчивости актуально применение декодеров мягких решений (ДМР), особенность которых состоит в том, что принятые из канала данные вводятся в декодер, минуя демодулятор [1]. Обычно использование ДМР дает лучшие результаты по сравнению с декодированием жестких решений, когда на вход декодера поступают значения с выхода демодулятора, преобразующего данные из канала в слова над фиксированным конечным алфавитом. Эффективность ДМР основана на том, что в отсутствие демодулятора не накапливаются ошибки квантования, однако обычно декодеры с технологией ДМР обладают большей сложностью — например, [2].
Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / Р. Морелос-Сарагоса. - Москва : Техносфера, 2005. - 320 с.Morelos-Zaragoza, R. Iskusstvo pomekhoustoychivogo kodirovaniya. Metody, algoritmy, primenenie. [The Art of Error Correcting Coding. Methods, algorithms, application.] Moscow: Tekhnosfera, 2005, 320 p. (in Russian).Прокис, Дж. Цифровая связь / Дж. Прокис. - Москва : Радио и связь, 2000. - 800 с.Proakis, J. Tsifrovaya svyaz´. [Digital Communications.] Moscow: Radio i svyaz´, 2000, 800 p. (in Russian).Деундяк, В. М. Имитационная модель цифрового канала передачи данных и алгебраические методы поме-хоустойчивого кодирования / В. М. Деундяк, Н. С. Могилевская // Вестник Дон. гос. техн. ун-та. - 2001. - Т. 1, № 1. - С. 98-104.Deundyak, V.М., Mogilevskaya, N.S. Imitatsionnaya model´ tsifrovogo kanala peredachi dannykh i algebraiches-kie metody pomekhoustoychivogo kodirovaniya. [Simulation model of digital data transmission channel and algebraic methods for error-correcting coding.] Vestnik of DSTU, 2001, vol. 1, no. 1, pp. 98-104 (in Russian).Деундяк, В. М. Модель троичного канала передачи данных с использованием декодера мягких решений кодов Рида - Маллера второго порядка / В. М. Деундяк, Н. С. Могилевская // Известия вузов. Северо-Кавказский ре-гион. Технические науки. - 2015. - № 1. - С. 16-23.Deundyak, V.М., Mogilevskaya, N.S. Model´ troichnogo kanala peredachi dannykh s ispol´zovaniem dekodera myagkikh resheniy kodov Rida - Mallera vtorogo poryadka. [Ternary data channel model using the soft-decision decoder of Reed - Muller second-order codes.] Izvestiya vuzov. Severo-Kavkazskiy region. Technical Sciences. 2015, no. 1, pp. 16-23 (in Russian).Сидельников, В. М. Декодирование кодов Рида - Маллера при большом числе ошибок / В. М. Сидельников, А. С. Першаков // Проблемы передачи информации. - 1992. - Т. 28, № 3. - С. 80-94.Sidelnikov, V.М., Pershakov, A.S. Dekodirovanie kodov Rida - Mallera pri bol´shom chisle oshibok. [Decoding of Reed - Muller Codes with a Large Number of Errors.] Problems of Information Transmission, 1992, vol. 28, no. 3, pp. 80-94 (in Russian).Loidreau, P. Modified version of Sidel´nikov-Pershakov decoding algorithm for binary second order Reed-Muller codes / P. Loidreau, B. Sakkour // Proc. Ninth International Workshop on Algebraic and Combinatorial Coding theory, ACCT-9. - Kranevo, 2004. - Р. 266-271.Loidreau, P., Sakkour, B. Modified version of Sidel´nikov-Pershakov decoding algorithm for binary second order Reed-Muller codes. Proc. Ninth International Workshop on Algebraic and Combinatorial Coding theory, ACCT-9. Kranevo, 2004, pp. 266-271.Могилевская, Н. С. Экспериментальное исследование декодеров кодов Рида - Маллера второго порядка / Н. С. Могилевская, В. Р. Скоробогат, В. С. Чудаков // Вестник Дон. гос. техн. ун-та. - 2008. - Т. 8, № 3. - С. 231-237.Mogilevskaya, N.S., Skorobogat, V.R., Chudakov, V.S. Eksperimental´noe issledovanie dekoderov kodov Rida - Mallera vtorogo poryadka. [Experimental study of second-order Reed-Muller codes.] Vestnik of DSTU, 2008, vol. 8, no. 3, pp. 231-237 (in Russian).Pellikaan, R. List decoding of q-ary Reed-Muller Codes / R. Pellikaan, X.-W. Wu // IEEE Transactions on Infor-mation Theory. - 2004. - Vol. 50 (1). - P. 679-682.Pellikaan, R., Wu, X.-W. List decoding of q-ary Reed-Muller Codes. IEEE Transactions on Information Theory, 2004, vol. 50 (1), pp. 679-682.Информационная система «Канал» : св-во о гос. регистрации программ для ЭВМ № 2008614602 / Н. С. Могилевская, К. А. Чугунный ; заявл. 31.07.08 ; зарегистрир. 24.09.08. - 17 с.Mogilevskaya, N.S., Chugunny, K.A. Informatsionnaya sistema «Kanal» : sv-vo o gos. registratsii programm dlya EVM № 2008614602. [Information system Channel: Certificate of Software State Registration no. 2008614602, 2008.] (in Russian).Деундяк, В. М. Математическое моделирование источников ошибок цифровых каналов передачи данных: учеб. пособие / В. М. Деундяк, Н. С. Могилевская. - Ростов-на-Дону : Издательский центр ДГТУ, 2006. - 70 с.Deundyak, V.М., Mogilevskaya, N.S. Matematicheskoe modelirovanie istochnikov oshibok tsifrovykh kanalov peredachi dannykh: ucheb. posobie. [Mathematical modeling of error sources of digital data channels: study guide.] Rostov-on-Don: DSTU Publ. Centre, 2006, 70 p. (in Russian).Могилевская, Н. С. Введение в теорию информации: учеб. пособие / Н. С. Могилевская. - Ростов-на-Дону : Издательский центр ДГТУ, 2013. - 125 с.Mogilevskaya, N.S. Vvedenie v teoriyu informatsii: ucheb. posobie. [Introduction to the theory of information: study guide.] Rostov-on-Don: DSTU Publ. Centre, 2013, 125 p. (in Russian).Деундяк, В. М. О стойкости кодового зашумления к статистическому анализу наблюдаемых данных мно-гократного повторения / В. М. Деундяк, Ю. В. Косолапов // Моделирование и анализ информационных систем. - 2012. - Т. 19, № 4. - С. 110-127.Deundyak, V.М., Kosolapov, Y.V. O stoykosti kodovogo zashumleniya k statisticheskomu analizu nablyudae-mykh dannykh mnogokratnogo povtoreniya. [On the Firmness Code Noising to the Statistical Analysis of the Observable Da-ta of Repeated Repetition.] Modelirovanie i analiz informatsionnykh system, 2012, vol. 19, no. 4, pp. 110-127 (in Russian).