This page belongs to Andi Loeliger's home page.

On Berlekamp-Massey, the Euclidean Algorithm, and Partial Inverses

This note is about the following papers:

Jiun-Hung Yu and H.-A. L.,
Partial inverses mod m(x) and reverse Berlekamp-Massey decoding,
IEEE Trans. Inform. Theory, vol. 62, pp. 6737-6756, Dec. 2016.
IEEE Xplore / Preprint
Jiun-Hung Yu and H.-A. L.,
The partial-inverse approach to linearized polynomials and Gabidulin codes with applications to network coding,
IEEE Trans. Inform. Theory, vol. 69, pp. 3759-3774, June 2023.
IEEE Xplore

Background: Reed-Solomon codes are classical error correcting codes, and the Euclidean algorithm (Sugiyama 1975) and the Berlekamp-Massey algorithm are two classical decoding algorithms for such codes (and some related codes). These two algorithms have long been known to be related, but in a complicated way.

The first paper introduces the partial-inverse problem and shows that both the Euclidean algorithm and (a version of) the Berlekamp-Massey algorithm are obtained as very easy specializations of a new algorithm that solves the partial-inverse problem. However, the proof of this (new) partial-inverse algorithm is too complicated (despite all our efforts).

The second paper is about a generalization where this approach turns out to work as well, but the original proof of the partial-inverse algorithm does not apply. In this context, Jiun-Hung Yu finally found a simpler proof (which also works in the original setting) that is not more complicated than the standard proofs of Euclidean algorithm and the Berlekamp-Massey algorithm.

In consequence, the partial-inverse approach is an attractive way to prove and to teach the Euclidean algorithm and the Berlekamp-Massey algorithm simultaneously.

Last modified: March 28, 2026