lfsr - Berlekamp-Massey 最小 LFSR 问题
问题描述
我在为我的序列（模式）获取正确的 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
当我实现这个值时，结果不正确
根据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
改编自维基百科的算法流程图
解决方案
推荐阅读
- flutter - 调整图像大小与图像包冲突
- sql - SQL 查询 - 将一行中的值添加到所有记录
- c# - 拖放在 Chrome 驱动程序版本 76.0.3809.100 中不起作用
- python - For 循环在达到条件之前结束
- typescript - Typescript 与 C# 类似的构造函数
- uart - 在 PIC24F Curiosity 上将 Printf 重定向到 UART
- c - WINAPI - WM_COMMAND 与 WM_MENUCOMMAND 用于固定菜单和动态子菜单
- postgresql - 使用二进制字段的 postgres 复制命令
- javascript - 从另一个指令中动态添加 VueJS 指令
- python - Tensorflow 模型，随机森林 AUC - 如何使用 Session 计算？