Geodesic
On decoding algorithms for generalized Reed — Solomon codes with errors and erasures
Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, Tome 26 (2020) no. 3, pp. 17-29 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The article is devoted to the decoding algorithms for generalized Reed — Solomon codes with errors and erasures. These algorithms are based on Gao algorithm, Sugiyama algorithm, Berlekamp — Massey algorithm (Peterson — Gorenstein — Zierler algorithm). 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 post-quantum 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.
Keywords: error-correcting codes, Reed — Solomon codes, code decoding.
Mots-clés : Goppa codes 
@article{VSGU_2020_26_3_a1,
     author = {S. M. Ratseev and O. I. Cherevatenko},
     title = {On decoding algorithms for generalized {Reed~{\textemdash}} {Solomon} codes with errors and erasures},
     journal = {Vestnik Samarskogo universiteta. Estestvennonau\v{c}na\^a seri\^a},
     pages = {17--29},
     year = {2020},
     volume = {26},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSGU_2020_26_3_a1/}
}
TY  - JOUR
AU  - S. M. Ratseev
AU  - O. I. Cherevatenko
TI  - On decoding algorithms for generalized Reed — Solomon codes with errors and erasures
JO  - Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
PY  - 2020
SP  - 17
EP  - 29
VL  - 26
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VSGU_2020_26_3_a1/
LA  - ru
ID  - VSGU_2020_26_3_a1
ER  - 
%0 Journal Article
%A S. M. Ratseev
%A O. I. Cherevatenko
%T On decoding algorithms for generalized Reed — Solomon codes with errors and erasures
%J Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
%D 2020
%P 17-29
%V 26
%N 3
%U http://geodesic.mathdoc.fr/item/VSGU_2020_26_3_a1/
%G ru
%F VSGU_2020_26_3_a1
S. M. Ratseev; O. I. Cherevatenko. On decoding algorithms for generalized Reed — Solomon codes with errors and erasures. Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, Tome 26 (2020) no. 3, pp. 17-29. http://geodesic.mathdoc.fr/item/VSGU_2020_26_3_a1/

[1] R. E. Blahut, Theory and practice of error control codes, Translation from English, Mir, M., 1986, 576 pp. (In Russ.)

[2] S. Gao, “A new algorithm for decoding Reed-Solomon codes”, Communications, Information, Network Security, The Springer International Series in Engineering and Computer Science (Communications and Information Theory), 712, eds. Bhargava V.K., Poor H.V., Tarokh V., Yoon S., Springer, Boston | DOI | Zbl

[3] W. C. Huffman, V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003, 646 pp. | DOI | Zbl

[4] S. M. Ratseev, “On decoding algorithms for Goppa codes”, Chelyabinsk Physical and Mathematical Journal, 5:3 (2020), 327–341 (In Russ.) | DOI | Zbl

[5] S. M. Ratseev, O. I. Cherevatenko, “On a simple algorithm for decoding BCH codes, Reed Solomon codes, and Goppa codes”, Vestnik SibGUTI, 2020, no. 3 (51), 3–14 (In Russ.)

[6] S. M. Ratseev, O. I. Cherevatenko, “On decoding algorithms for generalized Reed Solomon codes”, Systems and Means of Informatics, 30:4 (2020), 83–94 (In Russ.) | DOI

[7] N. J. Patterson, “The algebraic decoding of Goppa codes”, IEEE Transactions on Information Theory, 21:2 (1975), 203–207 | DOI | Zbl

[8] R. J. McEliece, “A Public-Key Cryptosystem Based On Algebraic Coding Theory”, DSN Progress Report, 42–44 (1978), 114–116

[9] Marek Repka, Pavol Zaj, “Overview of the Mceliece Cryptosystem and its Security”, Tatra Mountains Mathematical Publications, 60 (2014), 57–83 | DOI | Zbl

[10] Bernstein Daniel J., “List decoding for binary Goppa codes”, Coding and Cryptology, IWCC 2011, Lecture Notes in Computer Science, 6639, eds. Chee Y.M. et al., Springer, Berlin–Heidelberg | DOI

[11] Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process, Internal Report 8240, National Institute of Standards and Technology, January 2019, 27 pp. | DOI

[12] S. V. Fedorenko, “A simple algorithm for decoding algebraic codes”, Information and Control Systems, 2008, no. 3, 23–27 (In Russ.)