Berlekamp–Massey algorithm: Difference between revisions

Revision as of 02:39, 2 July 2008

Revision as of 15:18, 4 August 2008

Line 5:

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

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.

#Let the stream be s[0]<math>s_0, s[1]s_1, s[2]s_2 ... s[n]s_n</math>

#Initialise three arrays <math>b</math>, <math>c</math> and <math>t</math> of the length of the stream to be zeroes, except b[0]<math>b_0 =\leftarrow c[0]1, c_0 =\leftarrow 1</math>; initialise <math>N= \leftarrow 0, L= \leftarrow 0, m= \leftarrow -1</math>

#While <math>N</math> is less than <math>n</math>:

#*Let <math>d</math> be <math>s_N + c_1s_{N-1} + c_2s_{N-2} + ... + c_Ls_{N-L}</math>

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

#*If <math>d</math> is 1, then:

#** let <math>t</math> be a copy of <math>c</math>

#** Set <math>c_{N-m} \leftarrow c_{N-m} \oplus b_0, c_{N-m+1} \leftarrow c_{N-m+1} \oplus b_1, ... </math> up to <math>c_{n-1} \leftarrow c_{n-1} \oplus b_{n-N+m-1}</math> (where <math>\oplus</math> is the [[Exclusive or]] operator)

#** If <math>L \le \frac{N}{2}</math>, set <math>L \leftarrow N+1-L</math>, set <math>m \leftarrow N</math>, and let <math>b \leftarrow t</math>; otherwise leave <math>L</math>, <math>m</math> and <math>b</math> alone

#**Increment <math>N</math> and continue

#At the end of the algorithm, <math>L</math> is the length of the minimal LFSR for the stream, and we have c[L]s[a]<math>c_Ls_a + c[c_{L-1]s[}s_{a+1]} + c[c_{L-2]s[}s_{a+2]} ... = 0</math> for all <math>a</math>.

==External links==