maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2015-4-464-482mais-266Research ArticleОригинальные статьиArticlesАлгоритмы для мажоритарного декодирования групповых кодовAlgorithms for Majority Decoding of Group CodesДеундякВ. М.DeundyakV. M.

канд. физ.-мат. наук, доцент

пер. Газетный, 51, г. Ростов-на-Дону, 344002, Россия

PhD

51 Gazetniy lane, Rostov-on-Don, 344002, Russia

 

vlade@math.rsu.ruКосолаповЮ. В.KosolapovY. V.

канд. техн. наук

ул. Большая Садовая, 105/42, г. Ростов-на-Дону, 344006, Россия

PhD

105/42 Bolshaya Sadovaya Str., Rostov-on-Don, 344006, Russia

itaim@mail.ruФГНУ НИИ "Спецвузавтоматика"РоссияFGNU NII "Specvuzavtomatika"Russian FederationЮжный Федеральный УниверситетРоссияSouth Federal UniversityRussian Federation201520082015224464482Copyright © Деундяк В.М., Косолапов Ю.В., 20152015Деундяк В.М., Косолапов Ю.В.Deundyak V.M., Kosolapov Y.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/266

Решается задача конструктивного описания и обоснования алгоритмов, необходимых при практической реализации мажоритарного декодера для групповых кодов, заданных как левые идеалы групповых алгебр. Кроме алгоритмов, необходимых для реализации классического декодера Дж. Мэсси, построено обобщение классического декодера для кодов с неравной защитой символов, который в ряде случаев может быть лучше классического. Для применения как классического декодера Дж. Мэсси, так и его обобщения к групповым кодам разработан алгоритм построения декодирующих деревьев, которые лежат в основе этих алгоритмов мажоритарного декодирования. В силу того, что групповые коды определяются как левые идеалы групповых алгебр, алгоритм построения декодирующих деревьев позволяет по одному дереву построить все декодирующие деревья. На основе обобщенного алгоритма декодирования разработан алгоритм декодирования групповых кодов, индуцированных кодами на подгруппе. Применение разработанных декодеров проиллюстрировано на примере кодов Рида–Маллера–Бермана и индуцированных ими групповых кодах на неабелевой группе аффинных преобразований. В частности, для кода Рида–Маллера–Бермана приводится описание и обоснование алгоритма построения одного декодирующего дерева, по которому с использованием алгоритма построения всех декодирующих деревьев строится мажоритарный декодер кода Рида–Маллера–Бермана и индуцированных им кодов.

We consider a problem of constructive description and justification of the algorithms necessary for a practical implementation of the majority decoder for group codes specified as left ideals of groupalgebras. In addition to the algorithms needed to implement a classical decoder of J. Massey, it is built a generalization of the classical decoder for codes with unequal protection of characters, which in some cases could be better than the classic one. For use as a classical decoder of J. Massey and its generalization to group codes it was developed an algorithm for constructing decoding trees that lie at the core of these algorithms for majority decoding. Because group codes are defined as left ideals of group algebras, the decoding algorithm for constructing decoding trees allows to build all decoding trees from one tree. On the basis of the generalized decoding algorithm it was developed an algorithm for decoding group codes induced on the subgroup. Application of the developed decoders was illustrated by an example of Reed-Muller-Berman codes and group codes induced by them on a non-Abelian group of affine transformations. In particular, for Reed–Muller–Berman code description and justification of the algorithm for constructing one decoding tree are provided. This three is used for constructing all decoding trees and then it is a built decoder for Reed-Muller-Berman codes and codes induced by them.

мажоритарный декодергрупповые алгебрыгрупповые кодыкоды Рида– Маллера–Берманаmajority decodergroup algebragroup codesReed–Muller–Berman CodesReferencesФедоренко С.В., Методы быстрого декодирования линейных кодов, ГУАП, СПб., 2008, 199 с.; [Fedorenko S. V., Metody bystrogo dekodirovaniya lineynykh kodov, GUAP, SPb., 2008, 199 pp., (in Russian).]Федоренко С.В., Методы быстрого декодирования линейных кодов, ГУАП, СПб., 2008, 199 с.; [Fedorenko S. V., Metody bystrogo dekodirovaniya lineynykh kodov, GUAP, SPb., 2008, 199 pp., (in Russian).]Massey J. L., Threshold Decoding, MIT Press, Cambridge, 1963.Massey J. L., Threshold Decoding, MIT Press, Cambridge, 1963.Clark G. C. Jr., Cain J. B., Error-Correction Coding for Digital Communications, Springer, 1981., 432 pp.Clark G. C. Jr., Cain J. B., Error-Correction Coding for Digital Communications, Springer, 1981., 432 pp.Сидельников В.М., “Открытое шифрование на основе двоичных кодов Рида–Сидельников В.М., “Открытое шифрование на основе двоичных кодов Рида–Маллера”, Дискретная математика, 6:2 (1994), 3–20; [English transl.: Sidelnikov V. M., “Open coding based on Reed–Muller binary codes”, Diskr. Mat., 6:2 (1994), 3–20]Маллера”, Дискретная математика, 6:2 (1994), 3–20; [English transl.: Sidelnikov V. M., “Open coding based on Reed–Muller binary codes”, Diskr. Mat., 6:2 (1994), 3–20]Берман С. Д., “К теории групповых кодов”, Кибернетика, 3:17 (1967), 31–39; [English transl.: Berman S. D., “On the theory of group codes”, Kibernetika, 3:1 (1967), 31–39]Берман С. Д., “К теории групповых кодов”, Кибернетика, 3:17 (1967), 31–39; [English transl.: Berman S. D., “On the theory of group codes”, Kibernetika, 3:1 (1967), 31–39]Грушко И.И., “О мажоритарном декодировании обобщенных кодов Рида–Маллера”, Пробл. передачи информ., 26:3 (1990), 12–20; [English transl.: Grushko I. I., “Majority-logic decoding of generalized Reed-Muller codes”, Probl. Inf. Transm., 26:3 (1990), 189–196]Грушко И.И., “О мажоритарном декодировании обобщенных кодов Рида–Маллера”, Пробл. передачи информ., 26:3 (1990), 12–20; [English transl.: Grushko I. I., “Majority-logic decoding of generalized Reed-Muller codes”, Probl. Inf. Transm., 26:3 (1990), 189–196]Логачев О.А., Ященко В.В., “Коды типа Рида–Маллера на конечной абелевой группе”, Пробл. передачи информ., 34:2 (1998), 32–46; [English transl.: Logachev O. A., Yashchenko V. V., “Codes of the Reed-Muller type on a finite abelian group”, Probl. Inf. Transm., 34:2 (1998), 121–133]Логачев О.А., Ященко В.В., “Коды типа Рида–Маллера на конечной абелевой группе”, Пробл. передачи информ., 34:2 (1998), 32–46; [English transl.: Logachev O. A., Yashchenko V. V., “Codes of the Reed-Muller type on a finite abelian group”, Probl. Inf. Transm., 34:2 (1998), 121–133]Циммерман К.-Х., Методы теории модулярных представлений в алгебраической теории кодирования, МЦНМО, М., 2011, 246 с.; (Tsimmerman K.-Kh., Metody teorii modulyarnykh predstavleniy v algebraicheskoy teorii kodirovaniya, MTsNMO, M., 2011, 246 pp., [in Russian].)Циммерман К.-Х., Методы теории модулярных представлений в алгебраической теории кодирования, МЦНМО, М., 2011, 246 с.; (Tsimmerman K.-Kh., Metody teorii modulyarnykh predstavleniy v algebraicheskoy teorii kodirovaniya, MTsNMO, M., 2011, 246 pp., [in Russian].)Деундяк В.М., Косолапов Ю.В., “О стойкости кодового зашумления к статистическому анализу наблюдаемых данных многократного повторения”, Моделирование и анализ информационных систем, 19:4 (2012), 1100127; (Deundyak V.M., Kosolapov Yu. V., “On the Firmness Code Noising to the Statistical Analysis of the Observable Data of Repeated Repetition”, Modeling and Analysis of Information Systems, 19:4 (2012), 110—127, [in Russian].)Деундяк В.М., Косолапов Ю.В., “О стойкости кодового зашумления к статистическому анализу наблюдаемых данных многократного повторения”, Моделирование и анализ информационных систем, 19:4 (2012), 1100127; (Deundyak V.M., Kosolapov Yu. V., “On the Firmness Code Noising to the Statistical Analysis of the Observable Data of Repeated Repetition”, Modeling and Analysis of Information Systems, 19:4 (2012), 110—127, [in Russian].)Косолапов Ю.В., “Коды для обобщенной модели канала с подслушиванием”, Проблемы передачи информации, 51:1 (2015), 23328; [English transl.: Kosolapov Yu. V., “Codes for a Generalized Wire-Tap Channel Model”, Problems of Information Transmission, 51:1 (2015), 20024]Косолапов Ю.В., “Коды для обобщенной модели канала с подслушиванием”, Проблемы передачи информации, 51:1 (2015), 23328; [English transl.: Kosolapov Yu. V., “Codes for a Generalized Wire-Tap Channel Model”, Problems of Information Transmission, 51:1 (2015), 20024]Деундяк В.М., Мкртичян В.В., “Исследование границ применения схемы защиты информации, основанной на РС-кодах”, Дискретный анализ и исследование операций, 18:3 (2011), 21138; (Deundyak V. M., Mkrtichyan V. V., “Issledovanie granits primeneniya skhemy zashchity informatsii, osnovannoy na RS-kodakh”, Diskretnyy analiz i issledovanie operatsiy, 18:3 (2011), 21—38, [in Russian].)Деундяк В.М., Мкртичян В.В., “Исследование границ применения схемы защиты информации, основанной на РС-кодах”, Дискретный анализ и исследование операций, 18:3 (2011), 21138; (Deundyak V. M., Mkrtichyan V. V., “Issledovanie granits primeneniya skhemy zashchity informatsii, osnovannoy na RS-kodakh”, Diskretnyy analiz i issledovanie operatsiy, 18:3 (2011), 21—38, [in Russian].)Сидельников В.М., Теория кодирования, ФИЗМАТЛИТ, 2011, 323 с.; (Sidel’nikov V. M., Teoriya kodirovaniya, FIZMATLIT, 2011, 323 pp., [in Russian].)Сидельников В.М., Теория кодирования, ФИЗМАТЛИТ, 2011, 323 с.; (Sidel’nikov V. M., Teoriya kodirovaniya, FIZMATLIT, 2011, 323 pp., [in Russian].)Деундяк В.М., Дружинина М.А., Косолапов Ю.В., “Модификация криптоаналитического алгоритма Сидельникова–Шестакова для обобщенных кодов Рида–Соломона и ее программная реализация”, Известия высших учебных заведений. Северо-Кавказский регион, Технические науки, 2006, 15–20; (Deundyak V. M., Druzhinina M. A., Kosolapov Yu. V., “Modifikatsiya kriptoanaliticheskogo algoritma Sidel’nikova–Shestakova dlya obobshchennykh kodov Rida–Solomona i ee programmnaya realizatsiya”, Izvestiya vysshikh uchebnykh zavedeniy. Severo-Kavkazskiy region, Tekhnicheskie nauki, 2006, 15–20, [in Russian].)Деундяк В.М., Дружинина М.А., Косолапов Ю.В., “Модификация криптоаналитического алгоритма Сидельникова–Шестакова для обобщенных кодов Рида–Соломона и ее программная реализация”, Известия высших учебных заведений. Северо-Кавказский регион, Технические науки, 2006, 15–20; (Deundyak V. M., Druzhinina M. A., Kosolapov Yu. V., “Modifikatsiya kriptoanaliticheskogo algoritma Sidel’nikova–Shestakova dlya obobshchennykh kodov Rida–Solomona i ee programmnaya realizatsiya”, Izvestiya vysshikh uchebnykh zavedeniy. Severo-Kavkazskiy region, Tekhnicheskie nauki, 2006, 15–20, [in Russian].)Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, Eurocrypt 2007 of Lecture Notes in Computer Science, 4515 (2007), 347—360.Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, Eurocrypt 2007 of Lecture Notes in Computer Science, 4515 (2007), 347—360.Зиновьев В.А., Зяблов В.В., “Коды с неравной защитой информационных символов”, Проблемы передачи информ., 15:3 (1979), 50–60; [English transl.: Zinovev, V. A., Zyablov V. V., “Codes with unequal protection of information symbols”, Probl. Inf. Transm., 15:15 (1979), 197–205]Зиновьев В.А., Зяблов В.В., “Коды с неравной защитой информационных символов”, Проблемы передачи информ., 15:3 (1979), 50–60; [English transl.: Zinovev, V. A., Zyablov V. V., “Codes with unequal protection of information symbols”, Probl. Inf. Transm., 15:15 (1979), 197–205]Curtis C. W., Reiner I., Representation Theory of Finite Groups and Associative Algebras, Intersclence Publishers, New York, 1962.Curtis C. W., Reiner I., Representation Theory of Finite Groups and Associative Algebras, Intersclence Publishers, New York, 1962.Логачев О.А., Сальников А.Ю., Ященко В.В., Булевы функции в теории кодирования и криптологии, МЦМНО, М., 2004, 470 с.; [English transl.: Logachev O. A., Salnikov A. A., Yashchenko V. V., Boolean Functions in Coding Theory and Cryptography, AMS. Translations of Mathematical Monographs, 2012, 334 pp.Логачев О.А., Сальников А.Ю., Ященко В.В., Булевы функции в теории кодирования и криптологии, МЦМНО, М., 2004, 470 с.; [English transl.: Logachev O. A., Salnikov A. A., Yashchenko V. V., Boolean Functions in Coding Theory and Cryptography, AMS. Translations of Mathematical Monographs, 2012, 334 pp.

The authors declare that there are no conflicts of interest present.