lfsr - Berlekamp-Massey 最小 LFSR 问题

Question

我在为我的序列(模式)获取正确的 LFSR 时遇到了一些问题，当我将它实现为 LFSR 和相应的抽头时，它不会生成序列，有什么建议吗？目标 patt 为 {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 被排除在外以及 Wang Laung-Terng、Wu Cheng-Wen 和 W. Xiaoqing，“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

相比Wikipedia pseudocode它旨在实现，问题的代码有两个明显的差异(至少第二个是致命的错误):

d=c[0]*patt[N]应该是 d=patt[N]匹配 d ← sN…

d=d ^ c[i]*patt[N-L]应该是 d=d ^ c[i]*patt[N-i]匹配 d ← sN ⊕ c1sN−1 ⊕ c2sN−2 ⊕ ... ⊕ cLsN−L

的其他项

顺便说一句，代码没有显示最终的 L ，这是流的最小 LFSR 的长度。但是那个 L也是最后一个 1的索引在输出中，所以我们可以避免这个遗漏。

通过这些更改，代码输出 c=1 0 1 0 1 1 0 0 0 0 0 0 0 ，这是一个带有 L 的 LFSR =5 位和循环 si ← si-2 ⊕ si-4 ⊕ si-5，或等效地 si+5 ← si+3 ⊕ si+1 ⊕ si。这确实符合顺序!应用于 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输出中的数字，除了最左边的，对应于 Fibonnaci LFSR 中 XOR 的项，从最近到最旧；

最左边的输出是 1并对应于计算出的下一项；

1阅读顺序中的数字对应于斐波那契多项式从 1 到 xL(此处为 1+x2+x4+x5)的项，或等效于从 xL 到 1 的伽罗瓦多项式项(此处为 x5+x3+x1+ 1)

斐波那契约定中的初始状态只是第一个 L给定 si 的项，即 patt[i]在问题的代码中。

这是代码的精简版，输出更少更清晰，细读 for澄清意图，坚持原始伪代码中的变量名称，与更多的 C 编译器兼容，尽可能使用 bool 运算符，远离浮点，并使用最小的结束条件进行循环。在我做的几个测试中，它似乎工作得很好。

// 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

我对维基百科伪代码及其代码转录有一个评论家:索引在分析中的序列中以相反的方向 si 和正在构造的多项式 ci；这似乎只会造成并发症。