Berlekamp–Massey algorithm: Difference between revisions

Revision as of 19:34, 12 June 2008

Revision as of 19:37, 12 June 2008

Line 1:

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 [[Recurrence relation|linearly recurrent sequence]].

Do not confuse it with [[Berlekamp's Algorithmalgorithm]] 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]].

Line 21:

Increment N and continue

At the end of the algorithm, L is the length of the minimal LFSR for the stream, and we have c[L]s[a] + c[L-1]s[a+1] + c[L-2]s[a+2] ... = 0 for all a.

==How does it work?==