И так, есть реализация алгоритма Berlekamp-Massey:
| Код |
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];
//Initialization
b[0]=c[0]=1;
N=L=0;
m=-1;
//Algorithm core
while (N<n)
{
d=s[N];
for (int i=1; i<=L; i++)
d^=c[i]&s[N-i]; //(d+=c[i]*s[N-i] mod 2)
if (d==1)
{
Array.Copy(c, t, n); //T(D)<-C(D)
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); //B(D)<-T(D)
}
}
N++;
}
return L;
}
}
|
И еще реализация LFSR:
| Код |
public static void main(final String[] args) {
boolean[] B = { true, false, true, false, false};
int len = 5;
byte[] A = new byte[len];
for (int i = 0; i < len; i++) {
A[i] = (byte) Math.rint(Math.random());
}
byte temp = 0;
byte out = 0;
for (int j = 0; j < 100; j++) {
temp = A[len - 1];
out = A[len - 1]; // - сюда поступает выход(результат)
for (int i = len - 1; i > 0; i--) {
A[i] = A[i - 1];
if (B[i]) {
temp ^=A[i];
// A[i] = (byte) (A[i - 1] ^ temp);
} else {
// A[i] = A[i - 1];
}
}
A[0] = temp;
}
}
|
Так вот, све прекрасно, кроме последовательности: {1,1,1,1,1,0,0,0,0,0} - результат выповления метода BerlekampMassey: линейная сложность = 5, но вот проблема - LFSR такой длины никогда не выдает такую последовательность, максимум {1,1,1,1,1,0,0,0,0}, а уже 6-битовый регистр может генерировать последовательность с 5мя нулями, тоесть нужный нам результат....
Возможно я гдето ошибаюсь в реализации самого LFSR, но и проверка "на листике" так же не дала нужный результат... тогда напрашивается мысль об ошибке в реализации алгоритма Berlekamp-Massey, но это очень врятли... Вобщем, я застрял... Help!!!   |
