迭代译码

迭代译码实验设计报告SUN一、实验目的1.掌握采用简单的迭代算法求解错误位置多项式；2.熟悉Berlekamp迭代译码算法的实现步骤。二、实验原理1.根据牛顿公式：，。如果伴随式si已知，错误个数t已知，则由前t个方程可解出t个错误位置多项式系数σ1,σ2,…,σt，以后t个方程作校验方程;2.如果恰好有t个错误，则σ(x)满足后t个校验方程，σ(x)即为错误位置多项；3.在实际问题中，错误个数e是未知的，如果et，牛顿公式仍有解，但解不唯一，无法确定哪个解是错误位置多项式σ(x)的系数。三、实验内容1.建立有限域与阿尔法幂次的关系对应表，并求出伴随式系数；代码如下：for(i=0;i15;i++){r[i]=(r1i)&1;}//升序存储a[0]=1;for(i=0;i3;i++){a[i+1]=a[i]1;}for(i=0;i11;i++){a[4+i]=a[1+i]^a[i];//域生成多项式f(x)=4x+x+1}for(i=0;i15;i++){c[a[i]]=i;//向量与幂次互换//b[i]=15;}for(i=1;i=2*t;i++){for(j=0;j15;j++){s[i]=s[i]^(a[(i*j)%15]*r[j]);//伴随式系数：s[i]=r(a[i])}}printf(伴随式系数：\n);for(i=1;i=2*t;i++){if((c[s[i]]==0)&&(s[i]!=0)){printf(S%d=1,i);continue;}if(s[i]==0){printf(S%d=0,i);continue;}printf(S%d=a^%d,i,c[s[i]]);}printf(\n);2.设定迭代初始值：j=-1σ(j)(x)=1D(j)=0j-D(j)=-1dj=1j=0σ(j)(x)=1D(j)=0j-D(j)=0dj=s1代码如下：//迭代初始值n=0;j=2*t+1;b[j][0]=1;D[j]=2*t+2;d[j]=1;//相当于j=-1j=0;b[j][0]=1;D[j]=0;d[j]=s[1];//b[j][次数];数组b[j][]为错位多项式系数3.求错误多项式。若dj=0，则：σ(j+1)(x)=σ(j)(x)，D(j+1)=D(j)，若dj≠0，则：σ(j+1)(x)=σ(j)(x)+djdi-1x(j-i)σ(i)(x)，D(j+1)=Deg[σ(j+1)(x)]。其中：ij,dj≠0,且i-D(i)最大。如果j=2t-1，迭代结束，σ(x)=σ(2t)(x)。否则：令j=j+1，计算：dj=sj+1+sjσ1(j)+…+sj+1-D(j)σD(j)(j)重复直到结束迭代。代码如下：if((2*t+1-D[2*t+1])=max)//j=-1时{max=2*t+1-D[2*t+1];//max=-1temp=2*t+1;//相当于i=-1}for(j=0;j2*t;){if(d[j]==0){D[j+1]=D[j];for(m=0;m=D[j+1];m++){b[j+1][m]=b[j][m];}}if(d[j]!=0){for(i=0;ij;i++){if(((i-D[i])=max)&&(d[i]!=0)){max=i-D[i];temp=i;}//temp相当于公式要找的i}i=temp;if(i==(2*t+1)){b[1][0]=1;b[1][1]=s[1];//i=-1时}else{for(k=0;k=(D[i]);k++){f[k+j-i]=a[(c[b[i][k]]+c[d[j]]+15-c[d[i]])%15];//b[j][D[j]]}for(k=0;k=(D[i]+j-i);k++){b[j+1][k]=b[j][k]^f[k];//b[j][D[j]]}}if(i==7)D[j+1]=D[j]+1;for(k=0;k=j-i;k++){if(b[j+1][D[j]+k]!=0)D[j+1]=D[j]+k;}}if(j==(2*t-1))break;else{j=j+1;for(m=1,d[j]=s[j+1];m=D[j];m++){if((s[j+1-m]!=0)&&(b[j][m]!=0))d[j]=d[j]^a[(c[s[j+1-m]]+c[b[j][m]])%15];//求d[j]}}}for(i=0,n=1;i=14;i++){for(k=1,m=1;k=D[2*t-1];k++){if(b[2*t-1][k]!=0)m=m^a[(c[b[2*t-1][k]]+c[a[i]]*k)%15];}if(m==0){h[n]=a[i];//求错误多项式的根n++;}}4.求出对应的e(x)，找出正确码字：for(i=1;i=n-1;i++){if(h[i]!=0)x[i]=15-c[h[i]];//错误多项式的次数}for(i=1;i=n-1;i++){for(j=1,y=0;j=2*t;j++){if(s[j]==0)y++;}if(y==2*t)break;e[x[i]%15]=1;}//令相应的x的次数为1for(i=0;i15;i++){v[i]=r[14-i]^e[14-i];}//降幂存储四、实验框图开始建立有限域的向量表示关系求出伴随式系数设定迭代初始值求出错误多项式遍历求出其根v(x)=r(x)+e(x)结束五、实验总结1.迭代译码编程序过程对迭代过程更加熟悉，对操作步骤更加明确；2.迭代过程中，对j=-1和有限域中0的表示，对实验内容要求比较艰难，在此过程也遇到各种错误的出现；3.通过实验，对VC的单步调试和断点调试更熟悉，为以后的实验奠定了坚实基础。4,实验部分结果截图如下：