Berlekamp–Massey algorithm: Difference between revisions

Revision as of 13:38, 30 October 2016

Revision as of 18:14, 25 March 2017

Line 145:

#[[Assignment (computer science)|assign]] <math>L \leftarrow 0, m \leftarrow -1</math>.

#'''For''' <math>N = 0</math> '''step''' 1 '''while''' <math>N < n </math>:<!-- should be N <= n ??? -->

#*Let discrepancy <math>d</math> be <math>s_N +\oplus c_1s_{N-1} +\oplus c_2s_{N-2} +\oplus \cdots +\oplus c_Ls_{N-L}</math>.<!-- These are operations in the FIELD -->

#*'''if''' <math>d = 0</math>, '''then''' <math>c</math> is already a polynomial which annihilates the portion of the stream from <math>N-L</math> to <math>N</math>.

#*'''else''':

Line 152:

#** 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.

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 +\oplus c_{L-1}s_{a+1} +\oplus c_{L-2}s_{a+2} +\oplus \cdots = 0</math> for all <math>a</math>.<!-- this expression is in the FIELD -->

==See also==