Berlekamp–Massey algorithm: Difference between revisions

Revision as of 16:03, 5 June 2008

Revision as of 19:34, 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 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]].

==The algorithm itself==

Let the stream be s[0], s[1], s[2] ... s[n]

Initialise three arrays b, c and t of the length of the stream to be zeroes, except b[0] = c[0] = 1; initialise N=0, L=0, m=-1

While N is less than n, let d be s[N] + c[1]*s[N-1] + c[2]*s[N-2] + ... + c[L]*s[N-L]

If d is zero, then c is already a polynomial which annihilates the portion of the stream from N-L to N; increase N by 1 and continue.

If d is 1, then:

* let t be a copy of c

* Set c[N-m] = c[N-m] xor b[0], c[N-m+1] = c[N-m+1] xor b[1], ... up to c[n-1] = c[n-1] xor b[n-N+m-1]

* If L is less than or equal to N/2, set L = N+1-L, set m=N, and let b=t; otherwise leave L, m and b alone

Increment N and continue

==How does it work?==

==External links==