Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Рацеев С. М., Череватенко О. И. Об алгоритмах декодирования кодов Гоппы на случай ошибок и стираний // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2022. Т. 22, вып. 1. С. 28-47. DOI: 10.18500/1816-9791-2022-22-1-28-47, EDN: SKXHVX

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
31.03.2022
Полный текст:
(downloads: 2152)
Язык публикации: 
русский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
519.725
EDN: 
SKXHVX

Об алгоритмах декодирования кодов Гоппы на случай ошибок и стираний

Авторы: 
Рацеев Сергей Михайлович, Ульяновский государственный университет
Череватенко Ольга Ивановна, Ульяновский государственный педагогический университет имени И. Н. Ульянова
Аннотация: 

В 1978 г. Мак-Элис построил первую кодовую криптосистему с открытым ключом, которая основана на применении помехоустойчивых кодов. Данная криптосистема именно на основе кодов Гоппы считается перспективной и криптостойкой с учетом квантовых вычислений. При этом эффективные атаки на секретные ключи этой криптосистемы до сих пор не найдены. В работе исследуются алгоритмы декодирования кодов Гоппы на случай ошибок и стираний. Приводятся четыре алгоритма декодирования на основе алгоритмов для кодов Рида–Соломона, предложенных Гао, Берлекэмпом и Месси, Сугиямой и др. Первые два алгоритма строятся на основе алгоритма Гао и относятся к алгоритмам бессиндромного декодирования, остальные — к алгоритмам синдромного декодирования. При этом любой из этих алгоритмов применим и для случая канала связи только с ошибками. Также приводятся примеры декодирования сепарабельных кодов Гоппы с использованием данных алгоритмов.

Список источников: 
  1. Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process. National Institute of Standards and Technology. Internal Report 8240. January, 2019. 27 p. https://doi.org/10.6028/NIST.IR.8240
  2. Гоппа В. Д. Новый класс линейных корректирующих кодов // Проблемы передачи информации. 1970. Т. 6, № 3. С. 24–30.
  3. Мак-Вильямc Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки : пер. с англ. Москва : Связь, 1979. 744 с.
  4. Блейхут Р. Теория и практика кодов, контролирующих ошибки / пер. с англ. И. И. Грушко, В. М. Блиновский ; под ред. К. Ш. Зигангирова. Москва : Мир, 1986. 576 с.
  5. Gao S. A new algorithm for decoding Reed–Solomon codes // Communications, Information and Network Security / eds.: V. Bhargava, H. V. Poor, V. Tarokh, S. Yoon. Norwell, MA : Kluwer, 2003. Vol. 712. P. 55–68.
  6. Huffman W. C., Pless V. Fundamentals of Error-Correcting Codes. New York ; Cambridge : Cambridge University Press, 2003. 646 p.
  7. Рацеев С. М. Элементы высшей алгебры и теории кодирования : учеб. пособие для вузов. Санкт-Петербург : Лань, 2022. 656 с.
  8. Федоренко С. В. Простой алгоритм декодирования алгебраических кодов // Информационно-управляющие системы. 2008. № 3. С. 23–27.
  9. Gohberg I., Olshevsky V. The fast generalized Parker–Traub algorithm for inversion of Vandermonde and related matrices // Journal of Complexity. 1997. Vol. 13, iss. 2. P. 208–234. https://doi.org/10.1006/jcom.1997.0442
  10. Yan S., Yang A. Explicit algorithm to the inverse of Vandermonde matrix // 2009 International Conference on Test and Measurement. Hong Kong, 2009. P. 176–179. https://doi.org/10.1109/ICTM.2009.5413083
  11. Rawashdeh E. A. A simple method for finding the inverse matrix of Vandermonde matrix // MATEMATICKI VESNIK. 2019. Vol. 71, № 3. P. 207–213.
  12. Рацеев С. М., Череватенко О. И. Об алгоритмах декодирования обобщенных кодов Рида–Соломона на случай ошибок и стираний // Вестник Самарского университета. Естественнонаучная серия. 2021. Т. 26, № 3. С. 17–29. http://doi.org/10.18287/2541-7525-2020-26-3-17-29
Поступила в редакцию: 
25.08.2021
Принята к публикации: 
28.09.2021
Опубликована: 
31.03.2022