Systems and Means of Informatics
2020, Volume 30, Issue 4, pp 83-94
ON DECODING ALGORITHMS FOR GENERALIZED REED-SOLOMON CODES
- S. M. Ratseev
- O. I. Cherevatenko
Abstract
The paper is devoted to decoding algorithms for generalized Reed- Solomon codes that are based on algorithms for Reed-Solomon codes. The Gao, Sugiyama, and Berlekamp-Massey algorithms (Peterson-Gorenstein-Zierler algorithm) are given. The first of these algorithms belongs to syndrome-free decoding algorithms, the others - to syndrome decoding algorithms. The relevance of these algorithms is that they are applicable for decoding Goppa codes which are the basis of some promising postquantum cryptosystems. These algorithms are applicable for Goppa codes over an arbitrary field as opposed to the well-known Patterson decoding algorithm for binary Goppa codes.
[+] References (9)
- Shiozaki, A. 1988. Decoding of redundant residue polynomial codes using Euclid's algorithm. IEEE T. Inform. Theory IT-34(5): 1351-1354.
- Gao, S. 2002. A new algorithm for decoding Reed-Solomon codes. Communications, information and network security. Eds. V. Bhargava, H.V. Poor, V. Tarokh, and
S. Yoon. Norwell, MA: Kluwer. 712:55-68.
- Blahut, R. E. 1983. Theory and practice of error control codes. Addison-Wesley Pub. Co. 500 p.
- Elia, M., E. Viterbo, and G. Bertinetti. 1999. Decoding of binary separable Goppa codes using Berlekamp-Massey algorithm. Electron. Lett. 35(20): 1720-1721.
- Huffman, W. C., and V. Pless. 2003. Fundamentals of error-correcting codes. Cambridge University Press. 646 p.
- Wang, Yongge. 2017. Decoding generalized Reed-Solomon codes and its application to RLCE encryption scheme. arXiv.org. Available at: https://arxiv.org/abs/1702.07737 (accessed October 13, 2020).
- NISTIR 8240. 2019. Status report on the first round of the NIST post-quantum cryptography standardization process. National Institute of Standards and Technology. 27 p. doi: 10.6028/NIST.IR.8240.
- Fedorenko, S. V. 2008. Prostoy algoritm dekodirovaniya algebraicheskikhkodov [A simple algorithm for decoding algebraic codes]. Informatsionno-upravlyayushchie sistemy [Information and Control Systems] 3:23-27.
- Ratseev, S. M. 2020. Ob algoritmakh dekodirovaniya kodov Goppy [On decoding algorithms for Goppa codes]. Chelyab. fiz.-matem. zh. [Chelyabinsk Physical and Mathematical J.] 5(3):327-341.
[+] About this article
Title
ON DECODING ALGORITHMS FOR GENERALIZED REED-SOLOMON CODES
Journal
Systems and Means of Informatics
Volume 30, Issue 4, pp 83-94
Cover Date
2020-12-10
DOI
10.14357/08696527200408
Print ISSN
0869-6527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
error-correcting codes; Reed-Solomon codes; Goppa codes; code decoding
Authors
S. M. Ratseev  and O. I. Cherevatenko 
Author Affiliations
Ulyanovsk State University, 42 Lev Tolstoy Str., Ulyanovsk 432017, Russian Federation
Ilya Ulyanov State Pedagogical University, 4/5 Lenina Sq., Ulyanovsk 432071, Russian Federation
|