Форум Микро-Чип
Поиск и заказ электронных компонентов
 

Вернуться   Форум Микро-Чип > Вопросы начинающих

Вопросы начинающих Прежде чем задать вопрос, стоит воспользоваться поиском

Ответ
 
Опции темы Опции просмотра
Старый 11.01.2009, 14:38   #1
Vidocq
Junior Member
 
Регистрация: 21.09.2008
Возраст: 28
Сообщений: 3
Вес репутации: 100/0
Vidocq will become famous soon enoughVidocq will become famous soon enough
Exclamation LFSR и линейная сложность

И так, есть реализация алгоритма 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 < Math.pow(2,n)-1; j++) { // выводит все возможные значения из периода 2^n-1

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!!!
Vidocq вне форума   Ответить с цитированием
Ответ

Метки
lfsr, теорвер


Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
 
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход


Часовой пояс GMT +3, время: 16:49.


Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd. Перевод: zCarot