实验四 纠错编码基本实验一、实验目的1、通过实验理解线性分组码的基本原理；2、练习根据理论分析自行设计实验方法的能力。
二、实验内容1、已知一(10,4)线性分组码的生成矩阵为1001110111111000111001101101011101111001G ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦试用Matlab 求出该码的全部码字和最小汉明距离。
2、用Matlab 求x 15+1的所有因子，构造(15,4)循环码的所有可能的生成多项式；选择其中一个作为(15,4)循环码的生成多项式，求出所有的许用码字，并计算最小汉明距离。
三、实验原理1、线性生成码的原理线性分组码的构成方式是把信息序列分成每k 个码元一段，并由这k 个码元按一定规则产生r 个校验位，组成长度为n = k + r 的码字，用(n, k) 表示信息码元与校验位之间为线性关系。
一个[n ,k ]线性分组码，是把从信源输出的以k 个码元为一组的信息组m ，通过信道编码器后，变成长度为n ≥k 的码组（码字）c 作为[n ,k ]线性分组码的一个码字。
设GF(q )是一个含有q 个元素的有限数域，若每位码元的取值有q 种（取自GF(q )），则信息组m 共有k q 种不同的状态，因此，需要k q 个码字c 。
而长为n 的数组共有nq 个，二进制时(q =2)共有n 2个。
显然，n q 个n 维向量组成有限域GF(q )上的一个n 维线性空间V ，编码就是要在这个n 维线性空间中选出k q 个向量作为合法码字，其余的n q -k q 个向量为禁用码字。
如果选出的k q 个作为合法码字的向量的集合构成了V 的一个k 维线性子空间，则称它是一个q 进制[n ,k ]线性分组码。
如果值取自GF(q )上的[n ,k ]分组码的k q 个码字的集合C ，便构成了有限域GF(q )上的n 维线性空间V 的一个k 维线性子空间，则称C 是一个q 进制[n ,k ]线性分组码。
2、循环码的编码原理在编码时，首先需要根据给定循环码的参数确定生成多项式g (x )，也就是从的因子中选一个 （n-k ）次多项式作为g (x )；然后，利用循环码的编码特点，即所有循环码多项式A (x )都可以被g (x )整除， 来定义生成多项式g (x )。
根据上述原理可以得到一个较简单的系统循环码编码方法：设要产生（n,k ）循环码，m (x )表示信息多 项式，则其次数必小于k ，而·m (x )的次数必小于n ，用·m (x )除以g (x )，可得余数r (x )，r (x )的次 数必小于（n-k ），将r (x )加到信息位后作监督位，就得到了系统循环码。
下面就将以上各步处理加以解释：（1）用乘m (x )。
这一运算实际上是把信息码后附加上（n-k ）个“0”。
例如，信息码为110，它相当于m(x)＝+x。
当n-k＝7-3＝4时，·m（x）＝+，它相当于1100000。
而希望的到得系统循环码多项式应当是A(x) = ·m(x) + r(x)。
（2）求r(x)。
由于循环码多项式A(x)都可以被g(x)整除，也就是：因此，用·m(x)除以g(x)，就得到商Q(x)和余式r(x)，即这样就得到了r(x)。
（3）编码输出系统循环码多项式A(x)为：例如，对于（7，3）循环码，若选用，信息码110时，则这时的编码输出为：1100101。
四、具体实验方法1、对于问题一，已知线性分组码的生成矩阵G，因为要产生系统码，而给定的生成矩阵不是典型生成矩阵，因此首先要将G通过一系列初等行变换，变为典型生成矩阵。
然后利用码组矩阵A等于信息矩阵C与典型生成矩阵G的乘积，将所得的矩阵A按照异或运算的规则进行相应的处理，即可求得所有的生成码字矩阵A（A中每一行为一个生成码字），将生成码字矩阵A的每一行与其他行进行比较，如果对应值相同则为0，不同则为1，将比较所得的结果保留在一个与A矩阵列数相同的矩阵M中，再对M中的所有行求和，则得到任意两个码字的汉明距离S，对所得结果S求最小值，即得到最小汉明距离。
2、对于问题二，首先利用函数cyclpoly函数来产生(15,4)循环码的所有可能的生成多项式，然后在所有可能的生成多项式中任选一个作为(15,4)循环码的生成多项式g，任选一个信息码元m1求其对应的循环码字，具体过程如下：1)将信息码元m1*x^11，即将信息码元左移11位，并将其由多项式形式转化为矩阵形式m22)用g 除m2得到余数R,由于在求解余数时是按照一般的算术运算计算的，而实际要求的为模2运算，所以要经过适当的转化，转化为模2运算，得到符合要求的R3)将m2与R 相加，即得到对应于信息码为m1的码字T4)将得到的码字T 进行循环移位运算，即得到所有码字5)利用与问题一同样的方法即可得到最小汉明距离五、实验源代码、仿真结果及分析1、已知一(10,4)线性分组码的生成矩阵为1001110111111000111001101101011101111001G ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦试用Matlab 求出该码的全部码字和最小汉明距离。
（1）源代码G=[1 0 0 1 1 1 0 1 1 1;1 1 1 0 0 0 1 1 1 0;0 1 1 0 1 1 0 1 0 1;1 1 0 1 1 1 1 0 0 1]%生成矩阵%将生成矩阵标准化，化为典型生成矩阵B1=G(2,:),G(2,:)=G(3,:),G(3,:)=B1; %交换第2、3行的位置G(3,:)=(~G(3,:) & G(2,:))|(G(3,:) & (~G(2,:))); %将第2行的数据与第3行的数据进行异或运算作新的第3行的值G(4,:)=(~G(4,:) & G(2,:))|(G(4,:) & (~G(2,:))); %将第2行的数据与第4行的数据进行异或运算作为新的第4行的值G(1,:)=(~G(1,:) & G(3,:))|(G(1,:) & (~G(3,:))); %将第3行的数据与第1行的数据进行异或运算作为新的第1行的值G(4,:)=(~G(4,:) & G(3,:))|(G(4,:) & (~G(3,:))); %将第3行的数据与第4行的数据进行异或运算作为新的第4行的值B2=G(1,:),G(1,:)=G(3,:),G(3,:)=B2; %交换第1、3行的位置G(2,:)=(~G(2,:) & G(4,:))|(G(2,:) & (~G(4,:))); %将第4行的数据与第2行的数据进行异或运算作为新的第2行的值G(2,:)=(~G(2,:) & G(3,:))|(G(2,:) & (~G(3,:))); %将第3行的数据与第2行的数据进行异或运算作为新的第2行的值G(4,:)=(~G(4,:) & G(3,:))|(G(4,:) & (~G(3,:))); %将第3行的数据与第4行的数据进行异或运算作为新的第4行的值B3=G(3,:),G(3,:)=G(4,:),G(4,:)=B3; %交换第3、4行的位置%信息位码元矩阵为CC=[0 0 0 0;0 0 0 1;0 0 1 0;0 0 1 1;0 1 0 0;0 1 0 1;0 1 1 0;0 1 1 1;1 0 0 0;1 0 0 1;1 0 1 0;1 0 1 1;1 1 0 0;1 1 0 1;1 1 1 0;1 1 1 1]%生成的含有全部码字的矩阵AA=C*Gfor i=1:16for j=1:10if (A(i,j)==2) |(A(i,j)==4)A(i,j)=0;endif A(i,j)==3A(i,j)=1;endendend %由于进行乘法运算中各数是进行加和，必须改为异或运算，即使生成矩阵中只含有0和1，以上即是运用异或运算的规则进行转化%求最小汉明距离t=1;for i=1:15for j=i+1:16M(t,:)=(A(i,:)~=A(j,:));t=t+1;endend %分别比较两行中不同的元素S=(sum(M,2))'%将M矩阵的每一行求和，得出任意两个码字之间的距离d=min(S) %最小汉明距离（2）仿真结果以及仿真分析1) 将生成矩阵进行标准化，化为典型生成矩阵如下：分析及说明：通过一系列的初等行变换将最开始的一般生成矩阵转换为典型生成矩阵，由以上矩阵G可知，为一个标准矩阵。
2)全部码字如下：说明以及分析：矩阵A的每一行表示(10,4)线性分组码的一个码字，每一个码字由10位构成，包括四位信息位和六位监督位。
可知，(10,4)线性分组码总共有16个许用码字。
3)任意两个码字之间的汉明距离如下：4)最小汉明距离为d=22、用Matlab求x15+1的所有因子，构造(15,4)循环码的所有可能的生成多项式；选择其中一个作为(15,4)循环码的生成多项式，求出所有的许用码字，并计算最小汉明距离。
（1）源代码syms xG=cyclpoly(15, 4,'all') %求出所有的生成多项式g=G(2,:) %选择任意一个作为(15,4)循环码的生成多项式r=15-4 %监督位数m1=x^3+x^2+1 %信息码元m11=expand(x^r*m1) %用x^r乘以m1，相当于对m1进行左移r位的操作m2=sym2poly(m11) %将多项式转化为矩阵表示形式[Q,R] = DECONV(m2,g) %求m2除以g所得的余数R=abs(R)for i=1:length(R)if R(i)==2R(i)=0endend %由于在求解余数时是按照一般的算术运算计算的，而实际要求的为模2运算，转化为模2运算T=R+m2 %T为生成的一个循环码字T2(1,:)=Tfor i=1:14T2(i+1,:)=circshift(T2(i,:),[0,1])end %T2为将得到的第一个循环码字进行循环，得到其他的码字Y=[zeros(1,15);T2] %Y矩阵为生成的全部码字%求最小汉明距离t=1;for i=1:15for j=i+1:16M(t,:)=(Y(i,:)~=Y(j,:));t=t+1;endend %分别比较两行中不同的元素S=(sum(M,2))' %将M矩阵的每一行求和，得出任意两个码字之间的距离d=min(S) %最小汉明距离(2)仿真结果1)构造出(15,4)循环码的所有可能的生成多项式如下：说明以及分析：矩阵G的每一行为一个生成多项式的矩阵表示形式，g1、g2、g3为(15,4)循环码的所有生成多项式，可知总共有三个生成多项式的。