Алгоритмы для мажоритарного декодирования групповых кодов
https://doi.org/10.18255/1818-1015-2015-4-464-482
Аннотация
Решается задача конструктивного описания и обоснования алгоритмов, необходимых при практической реализации мажоритарного декодера для групповых кодов, заданных как левые идеалы групповых алгебр. Кроме алгоритмов, необходимых для реализации классического декодера Дж. Мэсси, построено обобщение классического декодера для кодов с неравной защитой символов, который в ряде случаев может быть лучше классического. Для применения как классического декодера Дж. Мэсси, так и его обобщения к групповым кодам разработан алгоритм построения декодирующих деревьев, которые лежат в основе этих алгоритмов мажоритарного декодирования. В силу того, что групповые коды определяются как левые идеалы групповых алгебр, алгоритм построения декодирующих деревьев позволяет по одному дереву построить все декодирующие деревья. На основе обобщенного алгоритма декодирования разработан алгоритм декодирования групповых кодов, индуцированных кодами на подгруппе. Применение разработанных декодеров проиллюстрировано на примере кодов Рида–Маллера–Бермана и индуцированных ими групповых кодах на неабелевой группе аффинных преобразований. В частности, для кода Рида–Маллера–Бермана приводится описание и обоснование алгоритма построения одного декодирующего дерева, по которому с использованием алгоритма построения всех декодирующих деревьев строится мажоритарный декодер кода Рида–Маллера–Бермана и индуцированных им кодов.
Об авторах
В. М. Деундяк
ФГНУ НИИ "Спецвузавтоматика"
Россия
Россия
канд. физ.-мат. наук, доцент
пер. Газетный, 51, г. Ростов-на-Дону, 344002, Россия
Ю. В. Косолапов
Южный Федеральный Университет
Россия
Россия
канд. техн. наук
ул. Большая Садовая, 105/42, г. Ростов-на-Дону, 344006, Россия
Список литературы
1. Федоренко С.В., Методы быстрого декодирования линейных кодов, ГУАП, СПб., 2008, 199 с.; [Fedorenko S. V., Metody bystrogo dekodirovaniya lineynykh kodov, GUAP, SPb., 2008, 199 pp., (in Russian).]
2. Massey J. L., Threshold Decoding, MIT Press, Cambridge, 1963.
3. Clark G. C. Jr., Cain J. B., Error-Correction Coding for Digital Communications, Springer, 1981., 432 pp.
4. Сидельников В.М., “Открытое шифрование на основе двоичных кодов Рида–
5. Маллера”, Дискретная математика, 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. Берман С. Д., “К теории групповых кодов”, Кибернетика, 3:17 (1967), 31–39; [English transl.: Berman S. D., “On the theory of group codes”, Kibernetika, 3:1 (1967), 31–39]
7. Грушко И.И., “О мажоритарном декодировании обобщенных кодов Рида–Маллера”, Пробл. передачи информ., 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]
8. Логачев О.А., Ященко В.В., “Коды типа Рида–Маллера на конечной абелевой группе”, Пробл. передачи информ., 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]
9. Циммерман К.-Х., Методы теории модулярных представлений в алгебраической теории кодирования, МЦНМО, М., 2011, 246 с.; (Tsimmerman K.-Kh., Metody teorii modulyarnykh predstavleniy v algebraicheskoy teorii kodirovaniya, MTsNMO, M., 2011, 246 pp., [in Russian].)
10. Деундяк В.М., Косолапов Ю.В., “О стойкости кодового зашумления к статистическому анализу наблюдаемых данных многократного повторения”, Моделирование и анализ информационных систем, 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].)
11. Косолапов Ю.В., “Коды для обобщенной модели канала с подслушиванием”, Проблемы передачи информации, 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]
12. Деундяк В.М., Мкртичян В.В., “Исследование границ применения схемы защиты информации, основанной на РС-кодах”, Дискретный анализ и исследование операций, 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].)
13. Сидельников В.М., Теория кодирования, ФИЗМАТЛИТ, 2011, 323 с.; (Sidel’nikov V. M., Teoriya kodirovaniya, FIZMATLIT, 2011, 323 pp., [in Russian].)
14. Деундяк В.М., Дружинина М.А., Косолапов Ю.В., “Модификация криптоаналитического алгоритма Сидельникова–Шестакова для обобщенных кодов Рида–Соломона и ее программная реализация”, Известия высших учебных заведений. Северо-Кавказский регион, Технические науки, 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].)
15. Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, Eurocrypt 2007 of Lecture Notes in Computer Science, 4515 (2007), 347—360.
16. Зиновьев В.А., Зяблов В.В., “Коды с неравной защитой информационных символов”, Проблемы передачи информ., 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]
17. Curtis C. W., Reiner I., Representation Theory of Finite Groups and Associative Algebras, Intersclence Publishers, New York, 1962.
18. Логачев О.А., Сальников А.Ю., Ященко В.В., Булевы функции в теории кодирования и криптологии, МЦМНО, М., 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.
Рецензия
Для цитирования:
Деундяк В.М., Косолапов Ю.В. Алгоритмы для мажоритарного декодирования групповых кодов. Моделирование и анализ информационных систем. 2015;22(4):464-482. https://doi.org/10.18255/1818-1015-2015-4-464-482
For citation:
Deundyak V.M., Kosolapov Y.V. Algorithms for Majority Decoding of Group Codes. Modeling and Analysis of Information Systems. 2015;22(4):464-482. (In Russ.) https://doi.org/10.18255/1818-1015-2015-4-464-482
Просмотров:
1641
Послать статью по эл. почте 