Berlekamp–Massey algorithm: Difference between revisions

Revision as of 03:59, 6 September 2016

Revision as of 16:32, 11 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 < Nn </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==

Line 159:

<source lang="java">

public static voidint mainrunTest(Stringint[] argsarray) {

public class BerlekampMassey {

forfinal (int iN = 0; i < array.length(); i++) {

public static String findPolynomial(char[] S) {

final int[] Nb = S.lengthnew int[N];

charint[] Bc = new charint[N]; B[0] = 1;

charint[] Ct = new charint[N];
C b[0] = 1;

charc[0] T = new char[N]1;

int Ll = 0, m = -1;

}int elsem {= -1;

for (int n = 0; n < N; n++) {

int d = S[n]0;

for (int i = 10; i <= Ll; i++) {
d ^= (Cc[i] &* Sarray[n - i]);

}

if (d == 1) {

System.arraycopy(Cc, 0, Tt, 0, N);

for (int i = 0, jN_M = n - m; j < N; i++, j++) C[j] ^= B[i];

iffor (Lint j <= n0; j < N - /N_M; 2j++) {

L = nc[N_M + 1j] -^= Lb[j];

}

if (args.lengthl <= n >/ 02) {

l = n + 1 - l;

m = n;

System.arraycopy(Tt, 0, Bb, 0, N);

}

}

}

return stringify(C, L)l;

}

public static String findPolynomial(String array) {

char[] charArray = array.toCharArray();

for (int i = 0; i < array.length(); i++) {

charArray[i] -= '0';

}

return findPolynomial(charArray);

}

public static String stringify(char[] array, int length) {

// convert `length` chars of array to string, and reverse it

char[] output = new char[length];

for (int i = 0, j = length; i < length; i++, j--) {

output[i] = (char)(array[j] + '0');

}

return String.valueOf(output);

}

public static void main(String[] args) {

if (args.length > 0) {

System.out.println(findPolynomial(args[0]));

} else {

System.err.println("Example: java BerlekampMassey 100110101111000");

}

}

}

</source>