Berlekamp–Massey algorithm

From Wikipedia, the free encyclopedia

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 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 code.

[edit] 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

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.