Berlekamp–Massey algorithm: Difference between revisions

Revision as of 15:28, 4 August 2008

Revision as of 19:43, 11 September 2008

Line 1:

{{distinguish|Berlekamp's algorithm}}

The '''Berlekamp–Massey algorithm''' is an [[algorithm]] for finding the shortest [[linear feedback shift register]] (LFSR) for a given output sequence. Equivalently, it is an algorithm for finding the [[minimal polynomial]] of a linearly [[Recurrence relation|linearly recurrent sequence]].

Do not confuse it with [[Berlekamp's algorithm]] for factoring polynomials over finite fields.

The algorithm was invented by [[Elwyn Berlekamp]] in 1968. Its connection to linear codes was observed by [[James Massey]] the following year. It became the key to practical application of the now ubiquitous [[Reed–Solomon error correction|Reed–Solomon code]].