Berlekamp–Massey algorithm: Difference between revisions

Revision as of 01:55, 14 August 2018

Revision as of 04:02, 22 September 2018

Line 141:

The following is the Berlekamp–Massey algorithm specialized for the binary [[finite field]] F₂ (also written GF(2)). The field elements are '0' and '1'. The field operations '+' and '−' are identical and are equivalent to the 'exclusive or' operation, XOR. The multiplication operator '*' becomes the logical AND operation. The division operator reduces to the identity operation (i.e., field division is only defined for dividing by 1, and x/1 = x).

#Let <math>s_0, s_1, s_2 \cdots s_{nN-1}</math> be the [[bit]]s of the stream.

#Initialise two arrays <math>b</math> and <math>c</math> each of length <math>nN</math> to be zeroes, except <math>b_0 \leftarrow 1, c_0 \leftarrow 1</math>

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

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

#*Let discrepancy <math>d</math> be <math>s_Ns_n \oplus c_1s_{Nn-1} \oplus c_2s_{Nn-2} \oplus \cdots \oplus c_Ls_{Nn-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>Nn-L</math> to <math>Nn</math>.

#*'''else''':

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

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

#** If <math>L \le \frac{Nn}{2}</math>, set <math>L \leftarrow Nn+1-L</math>, set <math>m \leftarrow Nn</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 -->