Berlekamp–Massey algorithm: Difference between revisions

Revision as of 16:32, 11 September 2016

Revision as of 20:27, 12 September 2016

Line 153:

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} + \cdots = 0</math> for all <math>a</math>.<!-- this expression is in the FIELD -->

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

The following code sample is for a binary field.

<source lang="java">

public static int runTest(int[] array) {

final int N = array.length;

int[] b = new int[N];

int[] c = new int[N];

int[] t = new int[N];

b[0] = 1;

c[0] = 1;

int l = 0;

int m = -1;

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

int d = 0;

for (int i = 0; i <= l; i++) {

d ^= c[i] * array[n - i];

}

if (d == 1) {

System.arraycopy(c, 0, t, 0, N);

int N_M = n - m;

for (int j = 0; j < N - N_M; j++) {

c[N_M + j] ^= b[j];

}

if (l <= n / 2) {

l = n + 1 - l;

m = n;

System.arraycopy(t, 0, b, 0, N);

}

}

}

return l;

}

</source>

==See also==