信道编码第二次试验实验报告.doc

信道编码第二次试验实验报告一、实验目的1、实现F2（x）多项式的加法、乘法以及除法运算；求多项式的周期；2、编写同余类域的生成、加法计算、乘法运算、除法运算、幂运算、元素求阶以及求解极小多项式的程序；二、实验原理1、多项式运算：加、乘多项式相加：同次项系数按照二元域中的加法相加；多项式相乘：按普通多项式的乘法相乘，计算系数按二元域上的加法和乘法运算。2、多项式的除法：给定任意两个多项式f(x)、g(x)，一定存在唯一的多项式q(x)和r(x),使：f(x)=q(x)g(x)+r(x) (r(x)(g(x) r(x)称为f(x)模g(x)的余式3、多项式的周期：定义：设f(x)为二元域上次数不为0的多项式，且f(0)0，则f(x)|(xn+1)的最小正整数n称为多项式f(x)的周期,(n=(f(x)实现方法：方法一：长除法求多项式周期用多项式f(x)按升幂排列去除1，当所得余式是单项xn时，f(x)的周期即为n。方法二：利用欧拉-费尔马定理4、GF(2)的扩域GF(2n)扩域GF(2n)：设p(x)为GF(2)上的n次既约多项式，模p(x)的所有2n个余式在模p(x)加法和乘法下构成2n元域，称为GF(2)的扩域(也称为模p(x)的剩余类域)，记为GF(2n)。 5、幂运算：元素累乘6、元素求阶： 具有性质an=e的最小正整数n称为a的阶7、求解元素的极小多项式： 最小多项式：以扩域GF(2m)上的非零元素为根的最低次多项式称为的最小多项式，记为M (x)求解方法：待定系数法三、实验结果 我在我的函数中规定：代表多项式的向量，从左到右为多项式高次到低次 1、多项式的加、乘运算： 在进行多项式的加法、乘法运算的编程时，思路来自于老蒋蒋凌云。加法：二元域上的多项式加法遵从模2加的运算规则。在编程时，输入的两个向量必须维度一致，MATLAB才能对其进行处理和运算。因此，先将输入的两个多项式向量维度设定一致，再运用mod函数求出最终结果。function zc = zsadd( x,y )lx=length(x);ly=length(y);lm=max(lx,ly);x=zeros(1,lm-lx),x;y=zeros(1,lm-ly),y;zc=mod(x+y,2);end乘法：乘法运算也存在着与加法运算相同的问题，即向量维度要保持一致。在进行本次试验编程之前，我曾经向教员询问过实验该如何做。教员就拿乘法当做例子为我进行了讲解。我选择了教员提供的方法中较为简单的一种，即对输入向量进行卷积运算，再对其卷积结果进行mod 2运算，得到最终结果。lx=length(x);ly=length(y);lm=max(lx,ly);x=zeros(1,lm-lx),x;y=zeros(1,lm-ly),y;zc=conv(x,y);zc=mod(zc,2);但在运用上面的思想编出了乘法函数之后，在实验第二项同余类域的运算中，结果出现了一些问题，仍与向量的维度有关，我不得不考虑，若是输入向量次数低于向量维度即类似【 0 0 1 1 0 1】的这种情况，我后面所进行的编程要求将其前几位的0消去，得到的最终结果也要求最高次为1。于是我添加了a=find(x=1,1,first);b=length(x);x=x(a:b);a1=find(y=1,1,first);b1=length(y);y=y(a1:b1);来消去0.2、多项式的除法：我认为多项式的除法运算是本次试验的最难也是最重要的一项函数，在进行后面编程时除法出现问题又对其重新进行修改，我一共修改了五次。我的编程思想是：选择那些原理并不高深、出现问题我能及时理解情况的方法。因此我选择了两个具体的多项式进行手动计算，将运算一步一步地实现，最终连贯到一起，就得出了除法函数。一开始，我以两个输入向量的次数为标准进行判断，这种方法同样遇到了维度的问题，在进行了第一次修改之后成功了，但在进行周期函数的编程时，出现了问题，即被除数次数小于除数次数的情况，我添加了判断次数大小的语句，分成两种情况来进行判断，但在进行判断输入多项式是否为既约多项式的编程中，又出现了除数次数与被除数次数相同的情况，我在原本的除法程序上添加了第二种判断语句，这样就将除法运算分成了三种情况，但此次修改中除法函数无法再正常地进行运算，各个判断条件无法兼容，后来我听取了老蒋的建议，将除数与被除数进行二进制到十进制转化，以十进制的大小为判断标准，重新编了除法，这样就只分成了两种情况，即大于等于和小于，大于等于进行正常运算，被除数小于除数就输出商为0，余数为被除数。后来又进行了一次适应后续函数的修改，终于将除法函数定型。function zc,r = zcchu2( x,y )a=find(x=1,1,first);b=length(x);c=b-a; % x多项式的最高次数d=find(y=1,1,first);e=length(y);f=e-d;% y多项式的最高次数g=c-f;% x，y的次数之差zc=zeros(1,g+1);x=x(a:b);x1=x;q=bi2de(x,left-msb);%十进制转换y1=bi2de(y,left-msb);flag=0;while(flag=0) a1=find(x=1,1,first); b1=length(x); x=x(a1:b1); c1=1,zeros(1,b1-a1+1-e); d1=conv(c1,y); x=zsadd(d1,x); c2=zeros(1,g+1-length(c1),c1; zc=zc+c2; r=x; q1=bi2de(x,left-msb); if(q1y1) flag=1; endendif(qy1) zc=0; r=x1;endend3、多项式的周期：周期的方法与除法方法一样，我选择了长除法一步一步的实现，后来我又从薛丽莎那里得到了另一种方法，即利用多项式周期的定义，我将两种方法都实现了之后，进行了比较，发现定义法在输入多项式次数较高时，运算速度明显变慢，而长除法速度较快，这可能与我实现的方法有关。长除法：function zq = zhouqi( x )y=1;flag=0;while(flag=0)ly=length(y);a=find(y=1,1,last);a=ly-a;b=1,zeros(1,a);c=conv(b,x);y=zsadd(y,c);d=find(y=1,3,last); if(d=1) zq=length(y)-1; flag=1; endend定义法：function e = zhouqi2( x )lx=length(x); ,r = zcchu2( x,1,0 );if (find(r=1) a=1; c=lx; endwhile(find(a=1) b=1,zeros(1,c-1),1; ,a=zcchu2(b,x); c=c+1;ende=c-1;end至于欧拉函数法，虽然我们在现实计算中只使用这种方法，但MATLAB编程实现十分困难，而且在这当中我的除法函数出现了问题，使得我抛弃了原有的方法，不得不使去用一种新的方法，于是我只进行了既约多项式的判断的编程实现。既约多项式的判断：function e = jiyue( x )y=1;d=0;flag=0;while(flag=0) zc,r = zcchu2( x,y ); a=bi2de(y,left-msb); b=a+1; y=de2bi(b,left-msb); if(r=0) d=d+1; end if(find(zc=1) flag=0; else flag=1; endendif(d=2) e=1; disp(既约);else e=0; disp(可约)endend4、同余类域GF(2n)的生成： 在进行同余类域的生成中，我没有选择运用数学方法实现，而是选择直接实现的方法，即根据同余类域的性质，直接生成一个大矩阵。我使用了十进制转换的方法，用循环的方式形成了结果。这也使得其与之后的几种运算割裂开来，成了一个没什么意义的函数。function a = tongyu( x )x1=bi2de(x,left-msb);i=0;flag=0;while(flag=0) if(2ix1) flag=1; a1=i-1; endenda=zeros(2(a1),a1);flag=0;i=0;i1=1;while(flag=0) a(i1,:)=zeros(1,a1-length(de2bi(i,left-msb),de2bi(i,left-msb); if(i1)=2a1) flag=1; end i=i+1; i1=i+1;end5、同余类域的加法、乘法、除法运算： 这几种运算在多项式运算的基础上很容易就实现了，函数语句都只有两行。6、同余类域的幂运算： 我使用的方法简单粗暴一些，就是将输入的向量进行累乘，累乘一次就模p一次，将得到的余数继续进行累乘，最终得到幂运算的最终结果。老蒋提供了另一种方法，设一个同余类域的生成元，用生成元的幂表示同余类域中所有的元素，这样，先将输入的多项式化为相应的生成元的幂，再对生成元的幂进行幂运算，这样就将幂运算转化成了普通乘法运算，消除了超过生成元阶数的次数后，得到对应的同余类域中的元素，即最终结果。但由于我的同余类域的生成并没有使用生成元，就没法使用这种方法。 function a = miyunsuan( x,m,p )a1=1;a3=x;i=m-2;if(m=1) a=a3;else if(m=0) a=a1; elseflag=0;y=x;while(flag=0) y=zsmul(y,x); ,r=zcchu2(y,p); y=r; if(2(length(p)-1)=bi2de(y,left-msb)&bi2de(y,left-msb)bi2de(p,left-msb) y=zsadd(y,p); end if(i=0) flag=1; end i=i-1;enda2=y;a=a2; endend6、元素求阶： 我使用了元素阶数的定义，即使an=e的最小值n为元素的阶数。我调用了之前编的幂运算函数，循环得到n值。 function a = qiujie( x,p )flag=0;i=0;while(flag=0) i=i+1; b = miyunsuan( x,i,p ); if(bi2de(b,left-msb)=1) flag=1; endenda=i;end7、求解元素的极小多项式： 由于我在之前并没有使用生成元来构造函数，使得我在进行求解极小多项式的函数构造中使用了以下的步骤：【1】 计算输入向量所对应的生成元的幂【2】 求出极小多项式的最高次数【3】 构造出生成元的所有幂值对应的同余类域中的元素，并按幂值大小排列成一个矩阵求解极小多项式的准备都完成了，下面使用待定系数法求解极小多项式。我设立了一个向量，用其中的元素来代指极小多项式的系数，然后一种可能一种可能的去试，最后得到结果，为此我在一个循环内又设立了第二个循环。function a = jixiaoduoxiangshi( x,p )x1=bi2de(x,left-msb);a1=0 0;a2=1 1;b=zeros(1,(length(p)-1);flag=0;i=-1;if(x1=0) a=a1;else if(x1=1) a=a2; elsewhile(flag=0) i=i+1; b=miyunsuan(1 0,i,p); if(bi2de(x,left-msb)=bi2de(b,left-msb) flag=1; endend%计算输入x所对应的a的次数c=b;flag=0;i=0;while(flag=0) i=i+1; n=2i; b=miyunsuan(c,n,p); if(bi2de(c,left-msb)=bi2de(b,left-msb) flag=1; endend%求出了极小多项式的次数d=zeros(i-1,i+1);b=zeros(1,i+1);flag=0;j=0;while(flag=0) j=j+1; b=miyunsuan(x,j,p); b1=find(b=1,1,first); b=zeros(1,i+1-length(b(b1:end),b(b1:end); d(j,:)=b; if(j=i-1) flag=1; endend%求出极小多项式中的一系列a方幂b1=miyunsuan(x,i,p);b2=1;b3=zeros(1,i-1);flag=0;b4=0;while(flag=0) f=zsadd(b1,b2); flg=0; l=0; b4=b4+1; b3=de2bi(b4,left-msb); b3=zeros(1,i-1-length(b3),b3; while(flg=0) l=l+1; e=b3(l)*d(l,:);%b3从左到右，对应的幂依次增大 f=zsadd(e,f); if(l=i-1) flg=1; end end if(bi2de(f,left-msb)=0) flag=1; endendz=fliplr(b3);a3=1,z,1; a=a3; endendend四、实验心得这是我第一个独自完成的实验项目，从头到尾所有的项目文件都是我自己编写的。之前做过的所有的编程实验，基本上都有学长或者别人的辛勤劳动在里面。这次我决定自己真