线性分组码编码的分析与实现

课程设计任务书20112012学年第一学期专业： 通信工程 学号： 姓名： 李琼 课程设计名称： 信息论与编码课程设计 设计题目： 线性分组码编码的分析与实现 完成期限：自 2011 年 12 月 19 日至 2011 年 12 月 25 日共 1 周一设计目的1、深刻理解信道编码的基本思想与目的；2、理解线性分组码的基本原理与编码过程；3、提高综合运用所学理论知识独立分析和解决问题的能力；4、使用MATLAB或其他语言进行编程。二设计内容 给定消息组M及生成矩阵G，编程求解其线性分组码码字。三设计要求编写的函数要有通用性。四设计条件计算机、MATLAB或其他语言环境五参考资料1曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007.2王慧琴.数字图像处理.北京：北京邮电大学出版社，2007.指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日摘要该系统是（6，3）线性分组码的编码的实现，它可以对输入的三位的信息码进行线性分组码编码。当接收到的六位码字中有一位发生错误时，可以纠正这一位错码；当接收到的码字有两位发生错误时，只能纠正一位错误，但同时能检测出另一位错误不能纠正。只有特定位有两位错误时，才能纠正两位错误。这样就译出正确的信息码组，整个过程是用MATLAB语言实现的。 关键词：编码；MATLAB；纠错目录1课程描述12 设计原理22.1 线性分组码的编码22.1.1 生成矩阵22.1.2 校验矩阵42.2 伴随式与译码52.2.1 码的距离及纠检错能力52.2.2 伴随式与译码53 设计过程63.1 编码过程63.2 仿真程序83.4 结果分析12总 结14致谢15参考文献16 课程设计说明书 1课程描述 线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术。对线性分组码的讨论都在有限域GF(2)上进行，域中元素为0,1,域中元素计算为模二加法和模二乘法。分组码是一组固定长度的码组，可表示为（n , k），通常它用于前向纠错。在分组码中，监督位被加到信息位之后，形成新的码。在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。对于长度为n的二进制线性分组码，它有种2n可能的码组，从2n种码组中，可以选择M=2k个码组（kn）组成一种码。这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=2k个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。要设计一个（6，3）线性分组码的编译码程序，最基本的是要具备对输入的信息码进行编码，让它具有抗干扰的能力。同时，还要让它具有对接收到的整个码组中提取信息码组的功能。但是，在实际的通信系统中，由于信道传输特性不理想以及加性噪声的影响，接收到的信息中不可避免地会发生错误，影响通信系统的传输可靠性，因而，本设计还要让该程序具有纠正错误的能力，当接收到的码组中有一位码，发生错误时可以检测到这一位错码，并且可以纠正这一位错码，并且让系统从纠正后的码组中提取正确的信息码组。针对给定的矩阵0 1 11 0 11 1 0Q=完成如下的工作：1 完成对任意信息序列的编码2 根据生成矩阵，形成监督矩阵；3 根据得到的监督矩阵，得到伴随式，并根据它进行译码；4 验证工作的正确性。2 设计原理2.1 线性分组码的编码2.1.1 生成矩阵线性分组码（n，k）中许用码字（组）为2k个。定义线性分组码的加法为模二加法，乘法为二进制乘法。即1+1=0、1+0=1、0+1=1、0+0=0；11=1、10=0、00=0、01=0。且码字与码字的运算在各个相应比特位上符合上述二进制加法运算规则。线性分组码具有如下性质（n，k）的性质：1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。对于码组长度为n、信息码元为k位、监督码元为rnk位的分组码，常记作（n，k）码，如果满足2r1n，则有可能构造出纠正一位或一位以上错误的线性码。下面我们通过（7，3）分组码的例子来说明如何具体构造这种线性码。设分组码（n，k）中，k = 3，为能纠正一位误码，要求r3。现取r4，则nkr7。该例子中，信息组为(c6c5c4),码字为(c6c5c4c3c2c1c0).当已知信息组时，按以下规则得到四个校验元，即 c3=c6+c4c2=c6+c5+c4 （2-1）c1=c6+c5c0=c5+c4 这组方程称为校验方程。 （7，3）线性分组码有23（8）个许用码字或合法码字，另有27-23个禁用码字。发送方发送的是许用码字，若接收方收到的是禁用码字，则说明传输中发生了错误。 为了深化对线性分组码的理论分析，可将其与线性空间联系起来。由于每个码字都是一个二进制的n重，及二进制n维线性空间Vn中的一个矢量，因此码字又称为码矢。线性分组码的一个重要参数是码率r=k/n,它说明在一个码字中信息位所占的比重，r越大，说明信息位所占比重越大，码的传输信息的有效性越高。由于(n,k)线性分组，线性分组码的2k个码字组成了n维线性空间Vn的一个K维子空间。因此这2k个码字完全可由k个线性无关的矢量所组成。 设此k个矢量为c1,c2,ck,有生成矩阵形式为c1c2ck G=（2-2）(n,k)码字中的任一码字ci,均可由这组基底的线性组合生成，即 ci=miG=mn-1 mn-2 mn-kG 式中，mi=mn-1 mn-2 mn-k 是k个信息元组成的信息组。表2-1 （7，3）线性分组码信息组码字000001010011100101110111对于表2-1给出的（7，3）线性分组码，可将写成矩阵形式 c6 c5 c4 c3 c2 c1 c0=c6 c5 c4故（7，3）码的生成矩阵为 G= 可以看到，从（7，3）码的8个码字中，挑选出k=3个线性无关的码字（）（），（）作为码的一组基底，用c=mG计算得码字。一个系统码的生成矩阵G，其左边k行k列应是一个k阶单位方阵Ik，因此生成矩阵G表示为 G=Ik P （2-3） 式中，P是一个k(n-k)阶矩阵。2.1.2 校验矩阵表2-1所示的（7，3）线性分组码的四个校验元由式（2-1）所示的线性方程组决定的。把（2-1）移相，有c6+c4+c3=0c6+c5+c4+c2=0c6+c1+c5=0 （2-4）c5+c4+c0=0上式的矩阵形式为 = 这里的四行七列矩阵称为（7，3）码的一致校验矩阵，用H表示，即 H= （2-5）由H矩阵得到(n,k)线性分组码的每一码字ci,(i=1,2,2k),都必须满足由H矩阵各行所确定的线性方程组，即 ciHT=0.（7，3）码的生成矩阵G中每一行及其线性组合都是（n,k）码的码字，所以有GHT =0。由G和H构成的行生成的空间互为零空间，即G和H彼此正交。H=PT Ir其右边r行r列组成一个单位方阵。2.2 伴随式与译码2.2.1 码的距离及纠检错能力 1码的距离两个码字之间，对应位取之不同的个数，称为汉明距离，用d表示。一个吗的最小距离dmin定义为dmin=mind(ci,cj),ij,ci,cj(n,k),两个码字之间的距离表示了它们之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个码字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。2. 线性码的纠检错能力 对于任一个（n,k）线性分组码，若要在码字内（1） 检测出e个错误，则要求码的最小距离de+1;(2) 纠正t个错误，则要求码的最小距离d2t+1;(3)纠正t个错误同时检测e(t)个错误，则要求 dt+e+1；2.2.2 伴随式与译码假设接收端收到的码字为B，那么它和原来发送端发送的码字A之间就有可能存在着误差。即在码组A=a6 a5 a4 a3 a2 a1 a0 中的任意一位就有可能出错。这样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要表达的意思。为了描述数据在传输信道中出现错误的情况，引入了错误图样E，在错误图样中，0代表对应位没有传错，1代表传输错误。实际上错误图样E就是收序列与发送序列的差。所以在译码中用接收到的码字B模尔加错误图样E就可以得到发送端的正确码字A。因此译码的过程就是要找到错误图样E。 定义：校正子SS = B * H= ( A + E ) * H = A * H+ E * H = E * H因为A是编得的正确码字。根据前面所叙述，它和监督矩阵的转置相乘为0。显然，S仅与错误图样有关，它们之间是一一对应的关系。找到了校正子S，也就可以找到E。而与发送的码字无关。若E=0，则S=0；因此根据S是否为0可进行码字的检错。如果接收码字B中只有一位码元发生错误，又设错误在第i位。即Ei-1=1,其他的Ei均为0。在后面的译码程序中，建立了一个校正子S与错误图样E对应的表。也就是收到一个B序列，就可以通过计算得到一个校正子，而每一个校正子都对应着一个错误图样E，再通过B模尔加上E，就可以得到正确的码字A。因为在不同的错误序列B中，同一位码元错误时对应的E是一样的，所以可以利用这个正确的码字让它每位依次错误，来求得它的八个校正子。而这时的矩阵B就是错误图样E。这样就算得了8个校正子S。而这时的错误序列B，就是错误图样E，所以有： E与S都已经得到，这时就可以建立一个表来将它们一一对应起来。 3 设计过程3.1 编码过程监督矩阵H与生成矩阵G的关系： (3-1)由H与G的分块表示的矩阵形式 (3-2)H =P In-k （3-1）G=Ik Q （3-2） (3-3)P=QT （3-3） 则有GHT=0 （3-4）或 HGT=0 （3-5）已知给出的（6，3）码的Q矩阵 0 1 11 0 11 1 0 Q= （3-6） 则可以根据G=Ik Q求出生成矩阵 1 0 0 0 1 10 1 0 1 0 10 0 1 1 1 0 G= （3-7）由P=QT 和H =P In-k 可求出监督矩阵H为0 1 1 1 0 01 0 1 0 1 01 1 0 0 0 1 H= 有了生成矩阵后则可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵，即MATLAB函数为： C=rem(I*G,2); （3-8）其中C为编码后的结果，I为信息矩阵，G为生成矩阵。则编码的所有情况为：编码序列：信息位 | 监督位0 0 0 0 0 00 0 1 1 1 00 1 0 1 0 10 1 1 0 1 11 0 0 0 1 11 0 1 1 0 11 1 0 1 1 01 1 1 0 0 0 C=（3-9）3.2 仿真程序% H 监督矩阵% G 生成矩阵 % C 编码矩阵% I 输入信息序列 % R 信道输出码 % A 纠错输出码序列 % E 错码矩阵% S 校验子矩阵% M 校验子的行的十进制序列%信道编码程序 clear all close all H=0 1 1 1 0 0; 1 0 1 0 1 0; 1 1 0 0 0 1; %监督矩阵H G=gen2par(H); %求H阵的生成矩阵G I=0 0 0;0 0 1;0 1 0;0 1 1;1 0 0;1 0 1;1 1 0;1 1 1; C=rem(I*G,2); %求码字C disp(所得的编码结果为:C=); %显示输出码字C disp(C); %信道译码程序 clear all; close all; H=0 1 1 1 0 0; 1 0 1 0 1 0; 1 1 0 0 0 1; %监督矩阵H B=input(请输入接收码组B:); a,b=size(B); %返回数组B的维数 E=0 0 0 0 0 0;0 0 0 0 0 1;0 0 0 0 1 0;0 0 0 1 0 0; 0 0 1 0 0 0;0 1 0 0 0 0;1 0 0 0 0 0;1 0 0 1 0 0; S=rem(B*H,2); %求校验子S i=1; for i=1:1:a M(i,1)=S(i,1).*4+S(i,2).*2+S(i,3); %求校验子所表示的十进制整数 end for i=1:1:a switch(M(i,1) case 0 A(i,:)=B(i,:)+E(1,:); case 1 A(i,:)=B(i,:)+E(2,:); case 2 A(i,:)=B(i,:)+E(3,:); case 3 A(i,:)=B(i,:)+E(4,:); case 4 A(i,:)=B(i,:)+E(5,:); case 5 A(i,:)=B(i,:)+E(6,:); case 6 A(i,:)=B(i,:)+E(7,:); case 7 A(i,:)=B(i,:)+E(8,:); end endfor i=1:1:a switch(M(i,1) case 0 disp(没有出现错误！); case 1 disp(注意：第1位出现一个错误！请纠正！); case 2 disp(注意：第2位出现一个错误！请纠正！); case 3 disp(注意：第3位出现一个错误！请纠正！); case 4 disp(注意：第4位出现一个错误！请纠正！); case 5 disp(注意：第5位出现一个错误！请纠正！); case 6 disp(注意：第6位出现一个错误！请纠正！); case 7 disp(注意：第6位和第3位出现两个错误！请纠正！); end endA=rem(A,2); %求出正确的编码 disp(检纠错后的码组A=); disp(A); %显示正确的编码 j=1; while j=3 %提取信息位 I(:,j)=A(:,j); j=j+1; end disp(译出的信息序列I=); disp(I); %显示原信息码 3.3 仿真结果图1输出编码结果及输入正确接收码的译码结果,根据仿真程序得出仿真结果如下图所示：图3-1 输出编码结果和正确输入时显示图2输入一位错误时的结果显示图图3-2 有一位错误输入时的显示图3输入两位特定位错误时的结果显示图3-3 有两位特定位错误输入时的显示图3.4 结果分析1输出编码结果及输入正确接收码的译码结果分析由图3-1 输出编码结果和正确输入时显示图所示的结果可以看出编码的结果的八种情况和在推导过程中运算的结果是一致的，可以见得程序的编码过程是正确的。对于译码过程而言，当界面显示“请输入接收码组B：” ，然后从提示符后输入：0 0 0 1 0 0，由于输入的接收码组与编码后的码字一致，它提取了每个码组的前四位，即信息位，由结果看出译码过程是正确的，并没有出现错译的情况，可见程序的译码片段是正确的。2输入一位错误时的结果分析对于纠错过程而言，当界面显示“请输入接收码组B：” 。然后从提示符后输入：1 1 1 1 1 0，由图3-2 有一位错误输入时的显示图所知，接收码组的第五位发生了错误，经程序纠检错误后改正了接收序列的错误，并且正确译出了信息位。可见程序的纠错功能也是可以实现的，以上结果进一步证实了，系统译码程序的正确性。3输入两位特定位错误时的结果分析由图3-3 有两位特定位错误输入时的显示图知，当输入B=1 0 0 1 0 0时，校正子是111，错误图样是，所以结果显示与理论相符。总 结通过对线性分组码中的线性分组码的编码编程实现，了解到线性分组码的构成方式是把信息序列分成每k个码元一段，并由这k个码元按一定规则产生r 个校验位，组成长度为n=k+r的码字，用(n，k)表示。信息码元与校验位之间为线性关系。并且知道了线性分组码的编码过程信息码元与校验位之间的线性关系实现起来是十分简单的.对于码组长度为n、信息码元为k位、监督码元为rnk位的分组码，如果满足2r1n，则有可能构造出纠正一位或一位以上错误的线性码。就像本设计的（6，3）分组码的（n，k）中，n=6，k = 3，r3能纠正一位误码，检测到两位误码。运用MATLAB语言进行编程，可以较明显的知道编码的过程和译码时出现的错误，码字的最小距离是3时，可以纠正一位错误，当输入特定的