On a simple algorithm for decoding BCH codes, Reed-Solomon codes, and Goppa codes
Abstract
Gao obtained a simple and efficient algorithm for decoding Reed-Solomon codes. In this paper we describe the use of this algorithm for decoding generalized Reed-Solomon codes, Goppa codes, Bose-Chaudhuri-Hocquenghem codes, and Reed-Solomon codes with errors and erasures.
About the Authors
S. M. Ratseev
Ульяновский государственный университет
Russian Federation
Russian Federation
O. I. Cherevatenko
Ульяновский государственный педагогический университет имени Н. И. Ульянова
Russian Federation
Russian Federation
References
1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. Перевод с англ.: И. И. Грушко, В. М. Блиновский. Под редакцией К.Ш. Зигангирова. М.: Мир, 1986. 576 с.
2. W. Cary Huffman, Vera Pless. Fundamentals of Error-Correcting Codes. Cambridge University Press, 2003. 646 p.
3. Gao S. A new algorithm for decoding Reed-Solomon codes // Communications, Information and Network Security / V. Bhargava, H. V. Poor, V. Tarokh, and S. Yoon, Eds. Norwell, MA: Kluwer, 2003. V. 712. P. 55-68.
4. Shiozaki A. Decoding of redundant residue polynomial codes using Euclid’s algorithm // IEEE Transactions on Information Theory. Sep. 1988. V. IT-34, № 5. P. 1351-1354.
5. 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.
6. Федоренко С. В. Простой алгоритм декодирования алгебраических кодов // Информационно-управляющие системы. 2008. № 3. С. 23-27.
7. Althaus H., Leake R Inverse of a finite-field Vandermonde matrix (Corresp.) // IEEE Transactions on Information Theory. 1969. V. 15, № 1. P. 173.
8. Клейбанов С. Б., Норкин К. Б., Привальский В. Б. Обращение матрицы Вандермонда // Автоматика и телемеханика. 1977. № 4. С. 176-177.
9. Bjorck A, Pereyra V Solution of Vandermonde systems of equations // Mathematics of Computation. 1970. V. 24, № 112. P. 893-903.
10. Gohberg I., Olshevsky V. The fast generalized Parker-Traub algorithm for inversion of Vandermonde and related matrices // Journal of Complexity. 1997. Vol. 13, № 2. P. 208-234.
11. Parker F. D. Inverses of Vandermonde matrices // The American Mathematical Monthly. 1964. V. 71, №4. P. 410-411.
12. Traub J. F. Associated polynomials and uniform methods for the solution of linear problems // Siam Review. 1966. V. 8, № 3. P. 277-301.
13. 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.
14. Гоппа В. Д.Новый класс линейных корректирующих кодов // Пробл. передачи информ. 1970. Т. 6, № 3. С. 24-30.
15. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: пер. с англ. М: Связь, 1979. 744 с.
Review
For citations:
Ratseev S.M., Cherevatenko O.I. On a simple algorithm for decoding BCH codes, Reed-Solomon codes, and Goppa codes. The Herald of the Siberian State University of Telecommunications and Information Science. 2020;(3):3-14. (In Russ.)
Views:
1248
Email this article 
