Computing Reviews

The Berlekamp-Massey algorithm revisited
Atti N., Diaz–Toca G., Lombardi H. Applicable Algebra in Engineering, Communication and Computing17(1):75-82,2006.Type:Article
Date Reviewed: 01/22/08

The authors of this paper “propose a slight modification of the Berlekamp-Massey algorithm for obtaining the minimal polynomial of a given linearly recurrent sequence.”

After reading the paper several times, I was only able to discover two differences between algorithm one, which is the usual Berlekamp-Massey algorithm, and algorithm two, which is the new one. The first difference is the occurrence of the local variable m, which gets an initial value and does not vary. The second is that the extended Euclidean algorithm is performed, in the first case, for the polynomials x2n and P(x), and in the second case for x2n and x° PP(1/x), where the coefficients of P(x) are members of a linear recursive sequence.

The authors state that both algorithms find the minimal polynomial of the sequence, but I am not convinced that their proof is complete.

Reviewer:  A. Pethö Review #: CR135132 (0811-1095)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy