Berlekamp-Massey минимальные проблемы LFSR

Question

У меня возникают некоторые проблемы с получением правильного LFSR для моей последовательности (паттерна), когда я реализую его как LFSR и соответствующие отводы, он не генерирует последовательность, какие-либо предложения?Патч цели: {1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1};

Мой код соответствует версии википедии для двоичного поля (https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm):

#include <stdio.h>

int main()
{
    int patt[]={1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1};
    int n=sizeof(patt)/sizeof(int);

    int N=0, L=0, m=-1, b[n], c[n], d=0, t[n], j;
    b[0]=1;
    c[0]=1;
    float val;

    for(int i=1; i<n; i++){
        b[i]=0;
        c[i]=0;
        //printf("b[%d]=%d, c[%d]=%d; ",i,b[i],i,c[i]);
    }


    while (N < n){

        printf("N=%d, ",N);
        d=c[0]*patt[N];//initializing the value of d

        for(int i=1; i<=L; i++){
            //printf("d = %d + %d*%d, ",d,c[i],patt[N-L]);
            d=d ^ c[i]*patt[N-L];
            //printf("d=%d \n",d);
        }

        printf("d=%d\n", d);

        if (d==0){
            printf("c=c\n\n");
        }
        else{
            for(int i=0; i<n; i++){
                t[i]=c[i];
            }

            j=0;
            while(N-m+j<=n-1){
                printf("c[%d-%d+%d]=c[%d-%d+%d]^b[%d]; c[%d]=c[%d]^b[%d], %d=%d^%d; ", N, m, j, N, m, j, j, N-m+j, N-m+j, j, c[N-m+j], c[N-m+j], b[j]);
                c[N-m+j]=c[N-m+j]^b[j];//XOR operator: ^
                printf("c=%d\n",c[N-m+j]);
                j++;
            }
            printf("\n");
            val=N;
            val=val/2;
            printf("L=%d, N=%d, N/2=%f \n",L, N, val);

            if(L<= val){
                printf("updating L, m & b\n\n");
                L=N+1-L;
                m=N;

                for(int i=0; i<n; i++){
                    b[i]=t[i];
                }
            }
        }
        N++;
    } 

    int CiSi=c[L]*patt[0];;

    for(int i=1; i<L; i++){
        CiSi=CiSi ^ c[L-i]*patt[i];//XORing
    }

    printf("CiSi = %d;", CiSi);

    printf("c=");

    for(int i=0; i<n; i++){
        printf("%d ",c[i]);
    }

    return 0;
}

Ответы за цикл:

N=0, d=1
c[0--1+0]=c[0--1+0]^b[0]; c[1]=c[1]^b[0], 0=0^1; c=1
c[0--1+1]=c[0--1+1]^b[1]; c[2]=c[2]^b[1], 0=0^0; c=0
c[0--1+2]=c[0--1+2]^b[2]; c[3]=c[3]^b[2], 0=0^0; c=0
c[0--1+3]=c[0--1+3]^b[3]; c[4]=c[4]^b[3], 0=0^0; c=0
c[0--1+4]=c[0--1+4]^b[4]; c[5]=c[5]^b[4], 0=0^0; c=0
c[0--1+5]=c[0--1+5]^b[5]; c[6]=c[6]^b[5], 0=0^0; c=0
c[0--1+6]=c[0--1+6]^b[6]; c[7]=c[7]^b[6], 0=0^0; c=0
c[0--1+7]=c[0--1+7]^b[7]; c[8]=c[8]^b[7], 0=0^0; c=0
c[0--1+8]=c[0--1+8]^b[8]; c[9]=c[9]^b[8], 0=0^0; c=0
c[0--1+9]=c[0--1+9]^b[9]; c[10]=c[10]^b[9], 0=0^0; c=0
c[0--1+10]=c[0--1+10]^b[10]; c[11]=c[11]^b[10], 0=0^0; c=0
c[0--1+11]=c[0--1+11]^b[11]; c[12]=c[12]^b[11], 0=0^0; c=0

L=0, N=0, N/2=0.000000 
updating L, m & b

N=1, d=0
c=c

N=2, d=1
c[2-0+0]=c[2-0+0]^b[0]; c[2]=c[2]^b[0], 0=0^1; c=1
c[2-0+1]=c[2-0+1]^b[1]; c[3]=c[3]^b[1], 0=0^0; c=0
c[2-0+2]=c[2-0+2]^b[2]; c[4]=c[4]^b[2], 0=0^0; c=0
c[2-0+3]=c[2-0+3]^b[3]; c[5]=c[5]^b[3], 0=0^0; c=0
c[2-0+4]=c[2-0+4]^b[4]; c[6]=c[6]^b[4], 0=0^0; c=0
c[2-0+5]=c[2-0+5]^b[5]; c[7]=c[7]^b[5], 0=0^0; c=0
c[2-0+6]=c[2-0+6]^b[6]; c[8]=c[8]^b[6], 0=0^0; c=0
c[2-0+7]=c[2-0+7]^b[7]; c[9]=c[9]^b[7], 0=0^0; c=0
c[2-0+8]=c[2-0+8]^b[8]; c[10]=c[10]^b[8], 0=0^0; c=0
c[2-0+9]=c[2-0+9]^b[9]; c[11]=c[11]^b[9], 0=0^0; c=0
c[2-0+10]=c[2-0+10]^b[10]; c[12]=c[12]^b[10], 0=0^0; c=0

L=1, N=2, N/2=1.000000 
updating L, m & b

N=3, d=0
c=c

N=4, d=0
c=c

N=5, d=0
c=c

N=6, d=1
c[6-2+0]=c[6-2+0]^b[0]; c[4]=c[4]^b[0], 0=0^1; c=1
c[6-2+1]=c[6-2+1]^b[1]; c[5]=c[5]^b[1], 0=0^1; c=1
c[6-2+2]=c[6-2+2]^b[2]; c[6]=c[6]^b[2], 0=0^0; c=0
c[6-2+3]=c[6-2+3]^b[3]; c[7]=c[7]^b[3], 0=0^0; c=0
c[6-2+4]=c[6-2+4]^b[4]; c[8]=c[8]^b[4], 0=0^0; c=0
c[6-2+5]=c[6-2+5]^b[5]; c[9]=c[9]^b[5], 0=0^0; c=0
c[6-2+6]=c[6-2+6]^b[6]; c[10]=c[10]^b[6], 0=0^0; c=0
c[6-2+7]=c[6-2+7]^b[7]; c[11]=c[11]^b[7], 0=0^0; c=0
c[6-2+8]=c[6-2+8]^b[8]; c[12]=c[12]^b[8], 0=0^0; c=0

L=2, N=6, N/2=3.000000 
updating L, m & b

N=7, d=0
c=c

N=8, d=1
c[8-6+0]=c[8-6+0]^b[0]; c[2]=c[2]^b[0], 1=1^1; c=0
c[8-6+1]=c[8-6+1]^b[1]; c[3]=c[3]^b[1], 0=0^1; c=1
c[8-6+2]=c[8-6+2]^b[2]; c[4]=c[4]^b[2], 1=1^1; c=0
c[8-6+3]=c[8-6+3]^b[3]; c[5]=c[5]^b[3], 1=1^0; c=1
c[8-6+4]=c[8-6+4]^b[4]; c[6]=c[6]^b[4], 0=0^0; c=0
c[8-6+5]=c[8-6+5]^b[5]; c[7]=c[7]^b[5], 0=0^0; c=0
c[8-6+6]=c[8-6+6]^b[6]; c[8]=c[8]^b[6], 0=0^0; c=0
c[8-6+7]=c[8-6+7]^b[7]; c[9]=c[9]^b[7], 0=0^0; c=0
c[8-6+8]=c[8-6+8]^b[8]; c[10]=c[10]^b[8], 0=0^0; c=0
c[8-6+9]=c[8-6+9]^b[9]; c[11]=c[11]^b[9], 0=0^0; c=0
c[8-6+10]=c[8-6+10]^b[10]; c[12]=c[12]^b[10], 0=0^0; c=0

L=5, N=8, N/2=4.000000 
N=9, d=0
c=c

N=10, d=0
c=c

N=11, d=0
c=c

N=12, d=1
c[12-6+0]=c[12-6+0]^b[0]; c[6]=c[6]^b[0], 0=0^1; c=1
c[12-6+1]=c[12-6+1]^b[1]; c[7]=c[7]^b[1], 0=0^1; c=1
c[12-6+2]=c[12-6+2]^b[2]; c[8]=c[8]^b[2], 0=0^1; c=1
c[12-6+3]=c[12-6+3]^b[3]; c[9]=c[9]^b[3], 0=0^0; c=0
c[12-6+4]=c[12-6+4]^b[4]; c[10]=c[10]^b[4], 0=0^0; c=0
c[12-6+5]=c[12-6+5]^b[5]; c[11]=c[11]^b[5], 0=0^0; c=0
c[12-6+6]=c[12-6+6]^b[6]; c[12]=c[12]^b[6], 0=0^0; c=0

L=5, N=12, N/2=6.000000 
updating L, m & b

CiSi = 0; 

CiSi = 0; проверка значений, упомянутых в результате алгоритма, выглядит корректно, поскольку равна нулю, но

c=1 1 0 1 0 1 1 1 1; excluding the last 4 zeros due to their values as zeros

c = 1 1 0 1 0 1 1 1 1, это коэффициенты полинома, начинающиеся слева направо: C0, ..., Ck: 1 + x ^ 2 + x ^ 4+ x ^ 5 + x ^ 6 + x ^ 7

Когда я применяю эти значения, результаты НЕ ПРАВЫ *

Реализация LFSR с отводами в соответствующих положениях, x0 исключается согласноhttps://en.wikipedia.org/wiki/Linear-feedback_shift_register, а также Ван Лаунг-Тернг, Ву Ченг-Вэнь и В. Сяоцин, «Принципы и архитектура тестирования VLSI - Дизайн для тестирования», 2006:

%Matlab source code
clear all;
seed=[1 1 0 0 0 0 1 0];
seed_sz=size(seed);
%Loop to initialize a array
for i=1:50
    A{i}=1:seed_sz(1,2);
    A{i}(1,1:end)=0;
end

filename='LFSR rightshift no x0 c program.xlsx';

for i=1:50
    A{i}=seed;
    xlswrite(filename,A{i},'1',['A',int2str(i)]);
    XOR_output=xor(seed(1,8),seed(1,7));
    XOR_output=xor(XOR_output,seed(1,6));
    XOR_output=xor(XOR_output,seed(1,5));
    XOR_output=xor(XOR_output,seed(1,3));
    XOR_output=xor(XOR_output,seed(1,1));

    %Right shift the seed
    seed=circshift(seed,1);

    seed(1,1)=XOR_output;
end

Блок-схемаалгоритм адаптирован из Википедии

Answer 1

Дополнение к ответу Фриу.Код для Фибоначчи и Галуа LFSR, показывающий как левый, так и правый алгоритмы сдвига.Это создаст исходную строку плюс еще 2 бита (0 1), что является 15-битным повторяющимся шаблоном.Начальные значения LFSR различаются для того, чтобы выходной шаблон соответствовал исходному строковому шаблону.

    // Fibonacci LFSR right shift
    printf("fr=");
    d = 0x03;
    do {
        printf(" %1x", d & 1);
        m = ((d>>3)^(d>>1)^(d>>0))&1;
        d  = (d >> 1)|(m << 4);
    } while (d != 0x3);
    printf("\n");

    // Fibonacci LFSR left shift
    printf("fl=");
    d = 0x18;
    do {
        printf(" %1x", d >> 4);
        m = ((d>>4)^(d>>3)^(d>>1)) & 1;
        d = ((d << 1)&0x1e) | m;
    } while (d != 0x18);
    printf("\n");

    //  Galios LFSR right shift
    printf("gr=");
    d = 0x1f;
    do {
        printf(" %1x", d & 1);
        m = d & 1;
        d >>= 1;
        if (m)
            d ^= 0x1a;
    } while (d != 0x1f);
    printf("\n");

    //  Galios LFSR left shift
    printf("gl=");
    d = 0x1f;
    do {
        printf(" %1x", d >> 4);
        d <<= 1;
        if (d & 0x20)
            d ^= 0x2b;
    } while (d != 0x1f);
    printf("\n");

output:

fr= 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1
fl= 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1
gr= 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1
gl= 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1

Answer 2

По сравнению с псевдокодом Википедии , который он стремится реализовать, код вопроса имеет два явных несоответствия (по крайней мере, второе является фатальной ошибкой):

• d=c[0]*patt[N]должно быть d=patt[N], чтобы соответствовать d ← s _N …
• d=d ^ c[i]*patt[N-L] должно быть d=d ^ c[i]*patt[N-i], чтобы соответствовать другим условиям d ← s _N ⊕ c ₁ с _{N − 1} ⊕ c ₂ s _{N − 2} ⊕… ⊕ c _L s _N-L

Кроме того, код не показывает окончательный L, то есть длинаминимальная LFSR для потока .Но это L также является индексом последнего 1 в выходных данных, поэтому мы можем избежать этого упущения.

С этими изменениями код выводит c=1 0 1 0 1 1 0 0 0 0 0 0 0, то есть LFSR с L = 5 бит и повторение s _i ← s _i-2 ⊕ s _i-4 ⊕ s _i-5 или эквивалентно с _{i + 5} ← s _{i + 3} ⊕ s _{i + 1} ⊕ s _i .Это действительно соответствует последовательности!Применительно к 5 первым заданным терминам вычисляются следующие 8:

s[ 0] :=                                     1
s[ 1] :=                                     1
s[ 2] :=                                     0
s[ 3] :=                                     0
s[ 4] :=                                     0
s[ 5] := s[ 3] ^ s[ 1] ^ s[ 0] = 0 ^ 1 ^ 1 = 0
s[ 6] := s[ 4] ^ s[ 2] ^ s[ 1] = 0 ^ 0 ^ 1 = 1
s[ 7] := s[ 5] ^ s[ 3] ^ s[ 2] = 0 ^ 0 ^ 0 = 0
s[ 8] := s[ 6] ^ s[ 4] ^ s[ 3] = 1 ^ 0 ^ 0 = 1
s[ 9] := s[ 7] ^ s[ 5] ^ s[ 4] = 0 ^ 0 ^ 0 = 0
s[10] := s[ 8] ^ s[ 6] ^ s[ 5] = 1 ^ 1 ^ 0 = 0
s[11] := s[ 9] ^ s[ 7] ^ s[ 6] = 0 ^ 0 ^ 1 = 1
s[12] := s[10] ^ s[ 8] ^ s[ 7] = 0 ^ 1 ^ 0 = 1

Интерпретация выходных данных программы:

• крайний правый 1 в выводе говорит о ширинеLFSR, а остальные следует игнорировать;
• цифры 1 в выходных данных, кроме крайнего левого, соответствуют терминам XOR в Fibonnaci LFSR , от самых последних досамый старый;
• самый левый вывод равен 1 и соответствует следующему вычисленному члену;
• 1 цифры в порядке чтения соответствуют условиям полинома Фибоначчи от 1 до x ^L (здесь 1 + x ² + x ⁴ + x ⁵ ) или эквивалентно полиному Галуа от x ^L до 1 (здесь x ⁵ + x ³ + x ¹ + 1 )

Начальное состояние в соглашении Фибоначчи - это просто первые L членыданного с _i , то есть patt[i] в коде вопроса.

Вот упрощенная версия кода с меньшим и более четким выводом, просматривающая for для уточнения намерения, придерживающаяся имен переменных в исходном псевдокоде, совместимаяс большим количеством компиляторов C _{^{с использованием булевых операторов, когда это возможно, вдали от плавающей запятой и созданием циклов с минимальными конечными условиями}} .Похоже, что он отлично работает в тех немногих тестах, которые я сделал.

// Berlekamp-Massey algorithm per https://en.wikipedia.org/w/index.php?title=Berlekamp%E2%80%93Massey_algorithm&oldid=808089047#The_algorithm_for_the_binary_field
#include <stdio.h>
int main(void) {
    int s[]={1,1,0,0,0,0,1,0,1,0,0,1,1}; // bits of the stream to analyse
    #define n (sizeof(s)/sizeof(*s))     // how many bits there are
    int b[n], c[n], t[n], d, j, N, L=0, m=-1;
    for(j=n; --j>0;)
        b[j]=c[j]=0;
    b[0]=c[0]=1;
    for(N=0; N<n; ++N) {                 // For N=0 step 1 while N<n
        d=s[N];                          // first term  of discrepancy
        for(j=L; j>0; --j)               // other terms of discrepancy
            d ^= c[j]&s[N-j];
        if (d!=0) {                      // non-zero discrepancy
            for(j=n; --j>=0;)            // copy c to t
                t[j]=c[j];
            for(j=n-N+m; --j>=0;)        // XOR b (reversed) into c
                c[N-m+j] ^= b[j];
            if(L+L<=N) {                 // if L<=N/2
                L=N+1-L;
                m=N;
                for(j=n; --j>=0;)        // copy t to b
                    b[j]=t[j];
            }
        }
    }
    printf("s =");                       // show input
    for(j=0; j<n; j++)
        printf(" %d",s[j]);
    printf("\nc ="); 
    for(j=0; j<=L; j++)                  // show result
        printf(" %d",c[j]);
    printf("\nL = %d\n",L);              // show degree of polynomial
    return 0;
}

//  The above code outputs the following:
//  s = 1 1 0 0 0 0 1 0 1 0 0 1 1
//  c = 1 0 1 0 1 1
//  L = 5

У меня есть критик по псевдокоду Википедии и его транскрипции в код: индексы идут в обратном направлении в анализируемой последовательности s _i и строящийся полином c _i ;это, кажется, только создает осложнения.