Berlekamp–Massey algorithm: Difference between revisions

Revision as of 06:49, 5 September 2016

Revision as of 03:57, 6 September 2016

Line 141:

The following is the Berlekamp–Massey algorithm specialized for the typical 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_0S_0, s_1S_1, s_2S_2 \cdots s_S_{nN-1}</math> be the [[bit]]sS of the stream.

#Initialise two arrays <math>bB</math> and <math>cC</math> each of length <math>nN</math> to be zeroes, except <math>b_0B_0 \leftarrow 1, c_0C_0 \leftarrow 1</math>

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

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

#*Let <math>d</math> be <math>s_NS_n + c_1s_C_1S_{Nn-1} + c_2s_C_2s_{Nn-2} + \cdots + c_Ls_C_Ls_{Nn-L}</math>.<!-- These are operations in the FIELD -->

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

#*'''else''':

#** Let <math>tT</math> be a copy of <math>cC</math>.

#** Set <math>c_C_{Nn-m} \leftarrow c_C_{Nn-m} \oplus b_0B_0, c_C_{Nn-m+1} \leftarrow c_C_{Nn-m+1} \oplus b_1B_1, \dots </math> up to <math>c_C_{nN-1} \leftarrow c_C_{nN-1} \oplus b_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>bB \leftarrow tT</math>; otherwise leave <math>L</math>, <math>m</math> and <math>bB</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_aC_LS_a + c_C_{L-1}s_S_{a+1} + c_C_{L-2}s_S_{a+2} + \cdots = 0</math> for all <math>a</math>.<!-- this expression is in the FIELD -->

==Code sample for the binary field in Java==