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

吉林建筑大学电气与电子信息工程学院信息理论与编码课程设计报告设计题目：线性分组码编码的分析与实现专业班级： 电子信息工程 111 学生姓名： 学 号： 指导教师： 设计时间： 2014.11.242014.12.5 教师评语：成绩 评阅教师 日期 第1章 概述1.1设计的作用、目的1、通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想。2、加深对理论知识的理解，提高实践技能，培养独立分析问题及解决问题的能力。3、掌握编码的基本原理与编码过程，增强逻辑思维能力。 4、使用MATLABH或其他语言进行编程及实现。1.2设计任务及要求设计一个（7,3）线性分组码的编译码程序，完成对任意序列的编码，根据生成矩阵形成监督矩阵，得到伴随式下，并根据其进行译码，同时验证工作的正确性，最基本的是要具备对输入的信息码进行编码，让它具有抗干扰的能力。1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编 码过程 4. 能够使用MATLAB或其他语言进行编程，编写的函数要有通用性。1.3设计内容已知一个（7,3）线性分组码的校验元与信息元有如下限定关系。设码字为(c1,c2, c3, c4, c5, c6,c7) 求出标准校验矩阵、Q矩阵、标准生成矩阵，完成对任意信息序列（23个许用码字）的编码。当接收码字分别为(), (), (), (), (), (), (), (), ()时，写出其伴随式S，以表格形式写出伴随式与错误图样E的对应关系，纠错并正确译码，当有两位错码时，假定为c5位和c2位发生错误。第2章 线性分组码编码分析与实现2.1设计原理1. 线性分组码的生成矩阵和校验矩阵（1）（n，k）线性分组码的性质1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。对于长度为n的二进制线性分组码，它有种2n可能的码组，从2n种码组中，可以选择M=2k个码组（kn）组成一种码。这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=2k个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。对于码组长度为n、信息码元为k位、监督码元为rnk位的分组码，常记作（n，k）码，如果满足2r1n，则有可能构造出纠正一位或一位以上错误的线性码。（2）生成矩阵和校验矩阵 线性分组码码空间是由个线性无关的基底，张成的维重子空间，码空间的所有元素(即码字)都可以写成个基底的线性组合，即 这种线性组合特性正是线性分组码名称的来历。显然，研究线性分组的关键是研究基底、子空间和映射规则，可把子空间和映射关系画成如图一所示的图形。k维k重信组空间mn维n重空间 n-k维n重对偶空间Dk维k重码空间cGH 图2.1 码空间与映射用表示第个基底并写成矩阵形式再将个基底排列成行列的矩阵，得： 由于个基底即的个行矢量线性无关，矩阵的秩一定等于，当信息元确定后，码字仅由矩阵决定，因此称这矩阵为该线性分组码的生成矩阵。基底不是唯一的，生成矩阵也就不是唯一的。事实上，将个基底线性组合后产生另一组个矢量，只要满足线性无关的条件，依然可以作为基底张成一个码空间。不同的基地有可能生成同一个码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。基底的线性组合等效于生成矩阵的行运算，可以产生一组新的基底。利用这点可使生成矩阵具有如下的“系统形式”： 这里是矩阵；是单位矩阵，从而保证了矩阵的秩是。与任何一个分组线性码的码空间相对应，一定存在一个对偶空间。事实上，码空间基底数只是维重空间全部个基底的一部分，若能找出另外个基底，也就找到了对偶空间。既然用个基底能产生一个分组线性码，那么也就能用个基底产生包含个码字的分组线性码，称码是码的对偶码。将空间的个基底排列起来可构成一个矩阵，将这个矩阵称为码空间的校验矩阵，而它正是对偶码的生成矩阵，它的每一行是对偶码的一个码字。和的对偶是互相的，是的生成矩阵又是的校验矩阵，而是的生成矩阵，又是的校验矩阵。由于的基底和的基底正交，空间和空间也正交，它们互为零空间。因此，线性码的任意码字一定正交于其对偶码的任意一个码字，也必定正交于校验矩阵的任意一个行矢量，即。由于生成矩阵的每个行矢量都是一个码字，因此必有。对于生成矩阵符合“系统形式”的系统码，其校验矩阵也是规则的，必为： 上式中的负号在二进制码情况下可以省略，因为模2减法和模2加法是等同的。（3）信息码元及对应码字的关系（n，k）码字中的任一码字，均可以由这组基底的线性组合生成，即 式中的是个信息元组的信息组，因此其信息码元及对应码字的关系如表一所示：表2.1 信息码元及对应码字关系信息组码字0000010100111001011101112. 线性分组码的伴随式与译码 （1）码的距离及检错能力两个码字之间，对应位取之不同的个数，称为汉明距离，用d表示。一个码的最小距离定义为,两个码字之间的距离表示了它们之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个码字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。任何最小距离的线性分组码，其检错能力为纠错能力t为 最小距离表明码集中各码字差异的程度，差异越大越容易区分，抗干扰能力自然越强，因此成了衡量分组码性能最重要的指标之一。估算最小距离是纠错码设计的必要步骤，最原始的方法是逐一计算两两码字间距离，找到其中最小者。含个码字的码集需计算个距离后才能找出，费时太多，实用中还有一些更好更快的方法。线性分组码的最小距离等于码集中时非零码字的最小重量，即 式中，符号 表示 重量（1的个数）。这里利用了群的封闭性，由于分组码是群码，任意两码字之和仍是码字，即。因此任意两码字间的汉明距离其实必是另一码字的重量，表示为成下面公式形式。于是可将最小距离问题转化为寻找最轻码字问题，含个码字的码集仅需计算次。码的检错能力取决于码的最小距离，但还需说明的另一点是码的总体检错能力不仅仅与有关。检错能力只是说明距离的差错一定能纠，并非说距离大于的差错一定不能纠。事实上，如果有个码子，就存在 个距离，这并非相等的。比如最小距离 ，检错力 ，是由码的距离决定，只要 朝 方向偏差大于1就会出现译码差错；然而若朝方向偏差3，译码时仍可正确地判断为而非。可见，总体的、平均的纠错能力不但与最小距离有关，而且与其余码距离或者说与码子的重量分布特性有关，把码距（码重）的分布特性称为距离（重量）谱，其中最小的重量就是。正如信息论各符号等概时熵最大一样，从概念上可以想象到:当所有码距相等时是（重量谱为线谱）码的性能应该最好；或者退一步说，当各码距相当不大时（重量谱为窄谱）性能应该叫好。事实证明确实如此，在同样的条件下，窄谱的码一般比宽谱的码更优。纠错重量谱的研究具有理论与现实意义，不仅仅是计算各种译码差错概率的主要依据，也是研究码的结构、改善码集内部关系从而发现新的好码的重要工具。但目前除了少数几类码如汉明码、极长码等的重量分布已知外，还有很多码的重量分布并不知道，距离分布与性能之间确切的定量关系对于大部分码而言尚在进一步研究当中，特别当 和 较大时，要得出码重分布是非常困难的。 重量谱可以如下多项式来表示，称为重量算子，即 式中的含义：在码长的码集里，包括重量为0的码子个（线性码一定包含一个重量为0的全0码），码重为1的码字个，重量为n的码字个。（2）伴随式与译码 码字在传输过程中受到各种干扰，接收端收码已不一定等于发码，两者间的差异就是差错，差错是多样化的，我们定义差错的式样为差错图样,即 对于二进制码，模2减等同模2加，因此有 利用码字与校验矩阵的正交性，可检验收码是否错误,即 定义运算结果为伴随式,即 可见，虽然本身与发码有关，但乘以后的伴随式 仅与差错图有关，只反映信道对码字造成怎样的干扰而与发什么码无关了。于是可以先利用收码和已知的算出的伴随式；再利用算出差错图样。这种思路下的编译码过程如图所示。在此过程中，和的计算都是确定性的，而从计算却带有随机性。这是因为伴随式是一个重失量，二进制时只有种肯那个的组合，而差错图样是重失量，有种可能的组合，因此与不存在一一对应关系。假设接收端收到的码字为，那么它和原来发送端发送的码字之间就有可能存在着误差。即在码组中的任意一位就有可能出错。这样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要表达的意思。为了描述数据在传输信道中出现错误的情况，引入了错误图样，在错误图样中，0代表对应位没有传错，1代表传输错误。实际上错误图样就是收序列与发送序列的差。所以在译码中用接收到的码字模尔加错误图样就可以得到发送端的正确码字。因此译码的过程就是要找到错误图样E。 定义：校正子 因为是编得的正确码字。根据前面所叙述，它和监督矩阵的转置相乘为0。显然，仅与错误图样有关，它们之间是一一对应的关系。找到了校正子，也就可以找到。而与发送的码字无关。若，则；因此根据是否为0可进行码字的检错。如果接收码字中只有一位码元发生错误，又设错误在第位。即,其他的均为0。在后面的译码程序中，建立了一个校正子与错误图样对应的表。也就是收到一个序列，就可以通过计算得到一个校正子，而每一个校正子都对应着一个错误图样，再通过模尔加上，就可以得到正确的码字。因为在不同的错误序列中，同一位码元错误时对应的是一样的，所以可以利用这个正确的码字让它每位依次错误，来求得它的八个校正子。而这时的矩阵就是错误图样。2.2设计步骤1. 编码过程根据已知检验元与信息的关系，设码字为(c1,c2, c3, c4, c5, c6,c7) 在由监督矩阵和生成矩阵的关系如下： 由与的分块的矩阵形式，,。可以求出生成矩阵和监督矩阵。 有了生成矩阵后可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵，即MATLAB函数为：其中为编码后的结果，为信息矩阵，为生成矩阵。则编码所有情况为：编码序列： 信息位 | 监督位 2. 译码过程对于译码过程来说，由上面可知道监督矩阵：矩阵与码的任何一个许用码字进行相乘的结果必等于0，即若是任一码字，则必有。若不属于许用码字，或有传输差错，且差错位数在码纠错能力内，则运算结果将为非0值，此时，可以纠错或检错重发。 设接收的码字(c1,c2,c3,c4,c5,c6,c7)，c1为第七位，c7为第一位，则：(1)当接收码字为（）时：所以此时接收编码无错误。（2） 当接收码字为（）时：所以，此时接收编码第一位发生错误，纠错后的正确译码为（）。 （3）当接收码字为（）时：所以，此时接收编码第二位发生错误，纠错后的正确译码为（）。（4）当接收码字为（）时：所以，此时接收编码第三位发生错误，纠错后的正确译码为（）。（5）当接收码字为（）时：所以，此时接收编码第四位发生错误，纠错后的正确译码为（）。（6）当接收码字为（）时： 所以，此时接收编码第五位发生错误，纠错后的正确译码为（）。（7）当接收码字为（）时：所以，此时接收编码第六位发生错误，纠错后的正确译码为（）。（8）当接收码字为（）时：所以，此时接收编码c5位和c2位发生错误，纠错后的正确译码（）。当编码矩阵与生成矩阵的转置矩阵相乘时，若当其中的一位编码或两位出现差错时会有八种情况，则这些情况列出错码矩阵如下表二：表2.2 伴随式与错误图样的对应关系校正子 差错图样 000000010010010010001101011111100011第3章 仿真程序及结果分析3.1 仿真程序% H 监督矩阵% G 生成矩阵 % C 编码矩阵% I 输入信息序列 % B 信道输出码 % A 纠错输出码序列 % E 错码矩阵% S 校验子矩阵% M 校验子的行的十进制序列%信道编码程序 clear all close all H=1 0 1 1 0 0 0; 1 1 1 0 1 0 0; 1 1 0 0 0 1 0; 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=1 0 1 1 0 0 0; 1 1 1 0 1 0 0; 1 1 0 0 0 1 0; 0 1 1 0 0 0 1; %监督矩阵H B=input(请输入接收码组B:); a,b=size(B); %返回数组R的维数 E=0 0 0 0 0 0 0;0 0 0 0 0 0 1;0 0 0 0 0 1 0;0 0 0 0 1 0 0; 0 0 0 1 0 0 0; 0 0 1 0 0 0 0;0 1 0 0 0 0 0;0 1 0 0 1 0 0; S=rem(B*H,2); %求校验子Si=1; for i=1:1:a M(i,1)=S(i,1).*8+S(i,2).*4+S(i,3).*2+S(i,4); %求校验子所表示的十进制整数 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 4 A(i,:)=B(i,:)+E(4,:); case 8 A(i,:)=B(i,:)+E(5,:); case 13 A(i,:)=B(i,:)+E(6,:); case 7 A(i,:)=B(i,:)+E(7,:); case 14 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 4 disp(注意：第3位出现一个错误！请纠正！); case 8 disp(注意：第4位出现一个错误！请纠正！); case 13 disp(注意：第5位出现一个错误！请纠正！); case 7 disp(注意：第6位出现一个错误！请纠正！); case 14 disp(注意：c2位和c5位出现两个错误！请纠正！); 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.2 仿真结果（1） 输出编码结果和无错误输入时显示图:图3.1 没有出现错误是的仿真图（2） 有一位错误输入时显示图:图3.2 第4位出现错误时的仿真图图3.3 第3位出现错误时的仿真图（3） 有两位错误输入时显示图: 图3.4出现两位错误时的仿真图3.3结果分析1输出编码结果及输入正确接收码的译码结果分析由图可以看出编码的结果的八种情况和在推导过程中运算的结果是一致的，所以我们可以知道程序的编码过程是正确的。对于译码过程而言，当界面显示“请输入接收码组B：”，然后从提示符后输入：0 0 0 0 0 0 0，由于输入的接收码组与编码后的码字一致，它提取了每个码组的前四位，即信息位，由结果看出译码过程是正确的，并没有出现错译的情况，可见程序的译码片段是正确的。2输入一位错误时的结果分析由图可以看出，当界面显示“请输入接收码组B：” 。然后从提示符后输入：1 0 1 0 0 0，由图有一位错误输入时的显示图所知，接收码组的第五位发生了错误，经程序纠检错误后改正了接收序列的错误，并且正确译出了信息位。可见程序的纠错功能也是可以实现的，以上结果进一步证实了，系统译码程序的正确性。3输入两位特定位错误时的结果分析由图有两位特定位错误输入时的显示图知，当输入B=0 1 0 0 1 0 0时，校正子是0011，错误图样是，所以说明理论得以验证。 第4章 总结通过这次的课程设计，我学习到了很多东西，让我对线性编码有了一个全新的认识，对MATLAB的掌握也进步了解很多，为以后的学习中出现的可能问题做好了准备，锻炼了自己的动手能力和设计能力，掌握了一种科技工具，丰富了自己的学习生活。整个实验过程中我懂得了许多东西，在查找的过程中我们也知道了许多原来不知道的东西，对于源代码的修改以及成功利用也树立了对知识应用的信心，相信会对今后的学习工作和生活有非常大的帮助，并且提高了自己的动手实践操作能力，使自己充分体会到了在实验过程中的成功喜悦。让我对MATLAB软件有了更深的了解，对MATLAB语言也有了更加深入的学习和理解。在本次的设计中，我了解了MATLAB中很多函数的用法，提高了我编程的能力，在软件仿真上，提高了自己的动手能力和学习能力，为以后的学习打下了良好的基础。通过对线性分组码中的线性分组码的编译码编程实现，了解到线性分组码的构成方式是把信息序列分成每k个码元一段，并由这k个码元按一定规则产生r 个校验位，组成长度为n=k+r的码字，用(n，k)表示。信息码元与校验位之间为线性关系。并且知道了线性分组码的编码过程信息码元与校验位之间的线性关系实现起来是十分简单的.对于码组长度为n、信息码元为