Introduction
The Berlekamp-Massey algorithm is an efficient algorithm for determining the linear complexity of a finite binary sequence s<sub>n</sub>
of length n
. The algorithm takes n
iterations, with the N
th iteration computing the linear complexity of the subsequence s<sub>N</sub>
consisting of the first N
terms of s<sub>n</sub>
. Returned value (L
) is the length of the shortest linear feedback shift register sequence that generates all bits in sequence s<sub>n</sub>
.
(Used in NIST statistical test suite - "Linear Complexity Test".)
The Code
public static int BerlekampMassey(byte[] s)
{
int L, N, m, d;
int n=s.Length;
byte[] c=new byte[n];
byte[] b=new byte[n];
byte[] t=new byte[n];
b[0]=c[0]=1;
N=L=0;
m=-1;
while (N<n)
{
d=s[N];
for (int i=1; i<=L; i++)
d^=c[i]&s[N-i];
if (d==1)
{
Array.Copy(c, t, n);
for (int i=0; (i+N-m)<n; i++)
c[i+N-m]^=b[i];
if (L<=(N>>1))
{
L=N+1-L;
m=N;
Array.Copy(t, b, n);
}
}
N++;
}
return L;
}
}
Finally
Sorry, but this might only be useful to those freaks (like me:) that work on statistical tests and/or cryptanalysis. I just needed to put this on the Web because I couldn't find some useful implementation out there.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.