On the Berlekamp — Massey algorithm and its application for decoding algorithms

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.