线性分组码教材.doc

线性分组码一、原理：监督矩阵：线性分组码中许用码组为个。定义线性分组码的加法为模二加法，乘法为二进制乘法。即、；、。且码组与码组的运算在各个相应比特位上符合上述二进制加法运算规则。线性分组码具有如下性质的性质：1. 封闭性。任意两个码组的和还是许用的码组。2. 码的最小距离等于非零码的最小码重。对于码组长度为、信息码元为位、监督码元为位的分组码，常记作码，如果满足，则有可能构造出纠正一位或一位以上错误的线性码。下面我们通过（7，4）分组码的例子来说明如何具体构造这种线性码。设分组码中，为能纠正一位误码，要求。取，则。该例子中，信息组为,码字为。用，的值与错码位置的对应关系可以规定为如表1所列。由表中规定可知，当已知信息组时，按以下规则得到三个校验元，即：（式1.1）表1 错码位置示意表。错码位置错码位置001101010110100111011000无错在发送端编码时，信息位，和的值决定于输入信号，因此它们是随机的。监督位，和应根据信息位的取值按监督关系来确定，即监督位应使上三式中，和的值为零（表示编成的码组中应无错码）。由上式经移项运算，解出监督位：（式1.2）给出信息位后，可直接按上式算出监督位，其结果见表2。接收端收到每个码组后先按式(1.1)计算出，和，再按表1判断错码情况。表2 （7，4）线性分组码（海明码）信息组码组信息组码组00000000000100010001110001000101110011001100001000101011010101001000110011110101110110010100010011011001100001010101011011101110111001100110011111011101000111011100011111111111给出（7,4）线性分组码有即16个许用码字或合法码字，另有个禁用码字。发送方发送的是许用码字，若接收方收到的是禁用码字，则说明传输中发生了错误。按上述方法构造的码称为海明码。表2所列的(7,4)海明码的最小码距，因此，这种码能纠正一个错码或检测两个错码。海明码的编码效率等于（式1.3）当n很大时，则编码效率接近1。可见，海明码是一种高效码。现在再来讨论线性分组码的一般原理。上面已经提到，线性码是指信息位和监督位满足一组线性方程的码，式(1.1)就是这样一组线性方程的例子。现在将它改写成：（式1.4）式（1.4）可以表示成如下矩阵形式： （模2）（式1.5）上式还可以简记为：或 （式1.6）其中右上标“T”表示将矩阵转置。将称为监督矩阵，编码时只要监督矩阵给定，编码时监督位和信息位的关系就完全确定。由式（1.4）、式（1.5）都可看出，的行数就是监督关系式的数目，它等于监督位的数目。的每行中的“1”的位置表示相应码元之间存在的监督关系。式（1.5）中的矩阵可以分为两部分： （式1.7）式中，为阶矩阵，为阶单位方阵，将具有形式的矩阵称为典型监督矩阵。由代数理论可知，矩阵的各行应该是线性无关的，否则将得不到个线性无关的监督关系式，从而也得不到个独立的监督位。若一行矩阵能写成典型的矩阵形式，则其各行一定是线性无关的。因为容易验证的各行是线性无关的，故也是线性无关的。生成矩阵：类似于式（1.4）改变成式（1.5）中矩阵形式那样，式（1.5）也可以改写成： （式:1.8）或者（式1.9）式中，为一个阶矩阵，即它为的转置，即 （式1.10）式（1.9）表明，信息位给定后，用信息位的行距乘矩阵就产生出监督位。将的左边加上一阶单位方阵就构成一矩阵，即（式1.11）称为生成矩阵，因为由它可以产生整个码组，即有（式1.12）或者（式1.13）因此，如果找到了码的生成矩阵，则编码的方法就完全确定。具有形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组中，信息位不变，监督位附加于其后，这种码称为系统码。与矩阵相似，也要求矩阵的各行是线性无关的。因为由式（1.13）可以看出，任一码组都是的各行的线性组合。共有行，若它们线性无关，则可组合出种不同的码组，它恰是有为信息位的全部码组；若的各行有线性相关的，则不可能由生成种不同码组了。实际上，的各行本身就是一个码组。因此，如果已有个线性无关的码组，则可以用其作为生成矩阵，并由它生成其余的码组。码的距离两个码字之间，对应位取之不同的个数，称为汉明距离，用表示。一个码的最小距离定义为，两个码字之间的距离表示了它们之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个码字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。线性分组码的纠检错能力对于任一个线性分组码，（1）若要在一个码字内检测出e个错误，则要求码的最小距离；（2）纠正个错误，则要求码的最小距离；（3）纠正个错误同时检测个错误，则要求。伴随式与译码一般说来，式（1.13）中为一列的行矩阵。此矩阵的个元素就是码组中的个码元，所以发送的码组就是。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与不一定相同。若设接收码组为一列的行矩阵，即（式1.14）则发送码组和接收码组之差为：（模2）（式1.15）它就是传输中产生的错码行矩阵，其中（式1.16）其中因此，若，表示该位接收码元无错；若，则表示该位接收码元有错。式（1.15）也可以改写成：（式1.17）接收端译码时，可将接收码组代入式（1.6）中计算。若接收码组中无错码，即，则，把它代入式（1.6）后，该式仍成立，则有（式1.18）当接收码组有错时，将代入式（1.15）后，该式不一定成立。在错码较多，已超过这种编码的检错能力时，变为另一许用码组则式（1.18）仍能成立。这样的错码错码是不可检测的。在未超过检错能力时，上式不成立，即其右端不等于零。假设这时式（1.18）的右端为，即（式1.19）将代入式（1.19）中可得由式（1.6）知，所以（式1.20）式中，称为伴随式或校正子。它与式（1.1）中的相似，有可能利用它来指示错码位置，这一点可以直接从式（1.20）中看出，式中只与有关，而与无关，这就意味着与错码之间有确定的线性变换关系。若和之间一一对应，则将能代表错码的位置。二、编解码流程：由与的分块表示的矩阵形式 （式2.1） （式2.2） （式2.3） （式2.4）则有 或 （式2.5）已知生成矩阵根据以上几式可求出监督矩阵最后可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵。即 （式2.6）所有的编码情况如表1所示。错误正确开 始提示输入要编码的信息码组的个数提示输入信息码组M输入正确？将码组赋给二维数组，码组的个数作为行数，码组的位数作为数组的列数返回提示输入错误并重新输入信息组的数组与生成矩阵数组相乘编码输出c把生成矩阵赋给一个二维数组G三、核心程序块：（7,4）码编译器整体程序：#include#includevoid main()/*G：生成矩阵 H：监督矩阵 HT：监督矩阵对应的转置矩阵*/*M：输入信息序列 C：编码输出序列 Input：输入接收码序列 B：译码输出序列 S：伴随式*/int Q,N;/*定义开始*/int i,j,s,r,k,t,p,u,m; int G47=1,0,0,0,1,1,1,0,1,0,0,1,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,1;int IR33=1,0,0,0,1,0,0,0,1;int H37, C107,M104,B207,Input100,HT73,P10,S1003;/*定义结束*/printf(n您好！欢迎使用线性分组码编译器！n);printf(nn本编译器针对（7，4）码，所采用的生成矩阵G=n);for(i=0;i4;i+)for(j=0;j7;j+)printf( %d,Gij);printf(n);printf(编译码过程都是针对二进制码组，除了系统要求选择功能，其他情况下禁止输入除0，1以外的数。请在使用的过程中严格按照编译器要求的格式输入数据。nn);printf(现在请输入您所选择的编译器所对应的序号,按回车键继续:n);printf(n1.编码器 2.译码器 3.退出n);printf(n我选择：);scanf(%d,&Q);if(Q=0)Q+=4;while(Q)if(Q=1|Q=2|Q=3)break;elseprintf(对不起，您输入有误，请重新输入);scanf(%d,&Q);while(Q=1|Q=2|Q=3)if(Q=1)/*编码程序*/printf(n请输入您需要编码的信息组数);scanf(%d,&N);printf(nn请输入您需要编码的%d组四位二进制信息组,码组间用空格分开，按回车键确认。n,N);/*输入信息码*/printf(n信息组m=);for(i=0;iN;i+)scanf(%1d%1d%1d%1d,&Mi3,&Mi2,&Mi1,&Mi0);/*求监督码*/for(i=0;iN;i+)Ci2=Mi3Mi2Mi1;Ci1=Mi3Mi2Mi0;Ci0=Mi3Mi1Mi0;for(j=0;j2;i-)/*输出编码结果*/Cji=Mji-3;printf(n您所输入的信息组编码结果c=);for(j=0;j=0;i-)printf(%d,Cji);printf(nn);printf(n接下来您想：nn);/*选择功能*/printf(1.用编码器 2.用译码器 3.退出nn);printf(我想：);scanf(%d,&Q);else if(Q=2)/*译码程序*/for(i=0;i3;i+)/*求监督矩阵*/for(j=0;j4;j+)Hij=Gji+4;for(j=4;j7;j+)Hij=IRij-4;printf(n监督矩阵H=n);/*输出监督矩阵*/for(i=0;i3;i+)for(j=0;j7;j+)printf( %d,Hij);printf(n);t=1;while(t!=2)/*输入接收码组*/p=1;printf(n请输入总位数为7的倍数的接收码组,每位用空格隔开，每组位数为7的倍数,以十进制2作为结束标志!按回车键确认n);while(p)for(i=0;i+)scanf(%d,&Inputi);if(Inputi=2)break;k=i%7;if(k=0)p=0;t=2;elsep=1;k=-k+7;printf(您接收到的码组丢失了%d位,系统不能判断丢失位的具体位置，请重新输入n,k);u=i/7;i=0;for(r=0;r=0;j-,i+)Brj=Inputi;printf(n将接收码组每七位分为一个码组，如下：n); for(i=0;iu;i+)for(j=0;j7;j+)printf( %1d,Bi6-j);printf(n);for(i=0;i3;i+)/*求监督矩阵H的转置矩阵*/for(j=0;j7;j+)HTji=Hij;for(i=0;iu;i+)for(m=0;m3;m+)for(j=0;j7;j+)s+=(Bi6-j*HTjm);if (s%2=1)s=1;else s=0;Si2-m=s;s=0;printf(nn伴随式S=n);/*输出伴随式*/for(j=0;j=0;i-)printf( %1d,Sji);printf(n);printf(n);for(i=0;i=0;j-)printf(%1d,Bij);printf(请您再次确认！);printf(译出的信息序列为：);for(j=6;j2;j-)printf(%d,Bij);break;case 2:Bi0=1Bi0;printf(nn您接收的第%d个码组有错误，正确的码组应为：,+i);i-;for(j=6;j=0;j-)printf(%1d,Bij);printf(译出的信息序列为：);for(j=6;j2;j-)printf(%d,Bij);break;case 3:Bi1=1Bi1;printf(nn您接收的第%d个码组有错误，正确的码组应为：,+i);i-;for(j=6;j=0;j-)printf(%1d,Bij);printf(译出的信息序列为：);for(j=6;j2;j-)printf(%d,Bij);break;case 4:Bi3=1Bi3;printf(nn您接收的第%d个码组有错误，正确的码组应为：,+i);i-;for(j=6;j=0;j-)printf(%1d,Bij);printf(译出的信息序列为：);for(j=6;j2;j-)printf(%d,Bij);break;case 5:Bi2=1Bi2;printf(nn您接收的第%d个码组有错误，正确的码组应为：,+i);i-;for(j=6;j=0;j-)printf(%1d,Bij);printf(译出的信息序列为：);for(j=6;j2;j-)printf(%d,Bij);break;case 6:Bi4=1Bi4;printf(nn您接收的第%d个码组有错误，正确的码组应为：,+i);i-;for(j=6;j=0;j-)printf(%1d,