Geodesic
On the Berlekamp — Massey algorithm and its application for decoding algorithms
Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, Tome 27 (2021) no. 1, pp. 44-61 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper is devoted to the Berlekamp — Masssey algorithm and its equivalent version based on the extended Euclidean algorithm. An optimized Berlekamp — Massey algorithm is also given for the case of a field of characteristic 2. The Berlekamp — Massey algorithm has a quadratic complexity and is used, for example, to solve systems of linear equations in which the matrix of the system is the Toeplitz matrix. In particular, such systems of equations appear in algorithms for the syndrome decoding of BCH codes, Reed — Solomon codes, generalized Reed — Solomon codes, and Goppa codes. Algorithms for decoding the listed codes based on the Berlekamp — Massey algorithm are given.
Keywords: Berlekamp — Massey algorithm, extended Euclidean algorithm, Reed — Solomon codes, code decoding. 
@article{VSGU_2021_27_1_a3,
     author = {S. M. Ratseev and A. D. Lavrinenko and E. A. Stepanova},
     title = {On the {Berlekamp~{\textemdash}} {Massey} algorithm and its application for decoding algorithms},
     journal = {Vestnik Samarskogo universiteta. Estestvennonau\v{c}na\^a seri\^a},
     pages = {44--61},
     year = {2021},
     volume = {27},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSGU_2021_27_1_a3/}
}
TY  - JOUR
AU  - S. M. Ratseev
AU  - A. D. Lavrinenko
AU  - E. A. Stepanova
TI  - On the Berlekamp — Massey algorithm and its application for decoding algorithms
JO  - Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
PY  - 2021
SP  - 44
EP  - 61
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VSGU_2021_27_1_a3/
LA  - ru
ID  - VSGU_2021_27_1_a3
ER  - 
%0 Journal Article
%A S. M. Ratseev
%A A. D. Lavrinenko
%A E. A. Stepanova
%T On the Berlekamp — Massey algorithm and its application for decoding algorithms
%J Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
%D 2021
%P 44-61
%V 27
%N 1
%U http://geodesic.mathdoc.fr/item/VSGU_2021_27_1_a3/
%G ru
%F VSGU_2021_27_1_a3
S. M. Ratseev; A. D. Lavrinenko; E. A. Stepanova. On the Berlekamp — Massey algorithm and its application for decoding algorithms. Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, Tome 27 (2021) no. 1, pp. 44-61. http://geodesic.mathdoc.fr/item/VSGU_2021_27_1_a3/

[1] Blahut Richard E., Theory and practice of error control codes, Translation from English, Mir, M., 1986, 576 pp. (In Russ.) https://scask.ru/h_book_tpc.php

[2] Huffman W. Cary, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003, 646 pp. | DOI | MR | Zbl

[3] Gao S., “A new algorithm for decoding Reed–Solomon codes”, Communications, Information and 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, MA, 55–68 | DOI | Zbl

[4] Massey J. L., “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory, IT 15:1 (1969), 122–127 | DOI | MR | Zbl

[5] Sugiyama Y. et al., “A method for solving key equation for decoding Goppa codes”, Information and Control, 27:1 (1975), 87–99 | DOI | MR | Zbl

[6] Dornstetter J. L., “On the equivalence Between Berlekamp's and Euclid's Algorithm”, IEEE Trans. Inform. Theory, IT-33:3 (1987), 428–431 | DOI | MR | Zbl

[7] Ratseev S. M., Cherevatenko O. I., “On decoding algorithms for generalized Reed-Solomon codes with errors and erasures”, Vestnik of Samara University. Natural Science Series, 26:3 (2020), 17–29 (In Russ.) | DOI | MR | Zbl

[8] Ratseev S. M., Cherevatenko O. I., “On decoding algorithms for generalized Reed-Solomon codes with errors and erasures. II”, Vestnik of Samara University. Natural Science Series, 27:2 (2021) (in Russ.) | MR

[9] Mac Williams F. J., Sloane N. J.A., The theory of error correcting codes, Svyaz', M., 1979, 744 pp. (In Russ.)