Berlekamp–Massey algorithm: Difference between revisions

Revision as of 15:18, 4 August 2008

Revision as of 15:28, 4 August 2008

Line 7:

==The algorithm==

#Let the stream be <math>s_0, s_1, s_2 ... s_n</math> be the [[bit]]s of the stream.

#Initialise three arrays <math>b</math>, <math>c</math> and <math>t</math> ofeach theof length of the stream<math>n</math> to be zeroes, except <math>b_0 \leftarrow 1, c_0 \leftarrow 1</math>; initialise[[Assignment (computer science)|assign]] <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:

#** letLet <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 <math>c_Ls_a + c_{L-1}s_{a+1} + c_{L-2}s_{a+2} ... = 0</math> for all <math>a</math>.

==External links==