VPF::LFSR и линейная сложность - Форум программистов

Vandalko

Дата 11.1.2009, 01:44 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 7.5.2007

Репутация: нет
Всего: нет

И так, есть реализация алгоритма 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!!! smile

chaos

Дата 11.1.2009, 08:37 (ссылка)

(нет голосов)

Загрузка ...

Серийный программист

Профиль
Группа: Завсегдатай
Сообщений: 2979
Регистрация: 7.7.2004
Где: Екатеринбург

Репутация: 6
Всего: 44

про данные алгоритмы ничего не знаю, но код походу на C#

MrCellophane

Дата 28.9.2013, 00:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 28.9.2013

Репутация: нет
Всего: нет

ошибка в реализации Берлэкампа-Мэсси. Вот ссылка. Там есть нормальная реализация на java

http://en.wikipedia.org/wiki/Berlekamp%E2%...assey_algorithm

А тут ты как минимум нахомутал с регистрами.

akizelokro

Дата 30.9.2013, 21:42 (ссылка)

(нет голосов)

Загрузка ...

Крокодил

Профиль
Группа: Участник
Сообщений: 761
Регистрация: 30.7.2007

Репутация: 1
Всего: 5

Энто что, когда не справляются с проблемами на других языках, пошла мода озадачивать программеров на С++? (Я ещё VB, JavaScript, PHP чутка знаю, а до того ещё когда-то на С#, фортране, Паскале и Perl что-то писал). smile

--------------------

a = a + b; b = a - b; a = a - b;

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »