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

1、吉林建筑大学电气与计算机学院信息理论与编码课程设计报告 设计题目：线性分组码编码的分析与实现 专业班级： 电子信息工程 121 学生姓名： 学 号： 指导教师： 设计时间： 2016.1.112016.1.22 教师评语：成绩 评阅教师 日期 第1章 概述1.1设计的作用、目的信息论与编码是一门理论与实践密切结合的课程,课程设计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本

2、思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。1.2设计任务及要求线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术。通过设计一组（7,3）线性分组码，来完成对任意序列的编码，根据生成矩阵形成监督矩阵，得到伴随式下，并根据其进行译码，同时验证工作的正确性，最基本的是要具备对输入的信息码进行编码，让它具有抗干扰的能力。1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2. 掌握哈夫曼编码/

3、费诺编码方法的基本步骤及优缺点；3. 深刻理解信道编码思想与目的，理解线性分组码的基本原理与编码过程。 4. 能够使用MATLAB或其他语言进行编程，编写的函数要有通用性。1.3设计内容已知一个（7,3）线性分组码的校验元与信息元有如下限定关系。设码字为(c6,c5, c4, c3, c2, c1,c0) 。 求出标准校验矩阵、Q矩阵、标准生成矩阵，完成对任意信息序列（23个许用码字）的编码。当接收码字分别为(),(),(),(),(), (),(),(),()时，写出其伴随式S，以表格形式写出伴随式与错误图样E的对应关系，纠错并正确译码，当有两位错码时，假定为c5位和c2位发生错误。第2章

4、线性分组码编码的分析与实现2.1设计原理1. 线性分组码的生成矩阵和校验矩阵（1）线性分组码的性质 线性分组码的任意两个码组的和还是许用的码组。码的最小距离等于非零码的最小码重。对于长度为n的二进制线性分组码，它有2n可能的码组，从2n种码组中，可以选择M=2k个码组（kn）组成一种码。这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=2k个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。对于码组长度为n、信息码元为k位、监督码元为rnk位的分组码，常记作（n，k）码，如果满足2r1n，则有可能构造出纠正一位或一位以上错误的线性码。（2）生成

5、矩阵和校验矩阵 线性分组码码空间是由个线性无关的基底，张成的维重子空间，码空间的所有元素(即码字)都可以写成个基底的线性组合，即 这种线性组合特性正是线性分组码名称的来历。显然，研究线性分组的关键是研究基底、子空间和映射规则，可把子空间和映射关系如图2.1所示：k维k重信组空间m n维n重空间 n-k维n重对偶空间DGHk维n重码空间C 图2.1 码空间与映射用表示第个基底并写成矩阵形式，再将个基底排列成行列的矩阵，得： 由于个基底即的个行矢量线性无关，矩阵的秩一定等于，当信息元确定后，码字仅由矩阵决定，因此称这矩阵为该线性分组码的生成矩阵。基底不是唯一的，生成矩阵也就不是唯一的。事实上，将个

6、基底线性组合后产生另一组个矢量，只要满足线性无关的条件，依然可以作为基底张成一个码空间。不同的基地有可能生成同一个码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。基底的线性组合等效于生成矩阵的行运算，可以产生一组新的基底。利用这点可使生成矩阵具有如下的“系统形式”： 这里是矩阵；是单位矩阵，从而保证了矩阵的秩是。与任何一个分组线性码的码空间相对应，一定存在一个对偶空间。事实上，码空间基底数只是维重空间全部个基底的一部分，若能找出另外个基底，也就找到了对偶空间。既然用个基底能产生一个分组线性码，那么也就能用个基底产生包含个码字的分组线性码，称码是码的对偶码。将空间

7、的个基底排列起来可构成一个矩阵，将这个矩阵称为码空间的校验矩阵，而它正是对偶码的生成矩阵，它的每一行是对偶码的一个码字。和的对偶是互相的，是的生成矩阵又是的校验矩阵，而是的生成矩阵，又是的校验矩阵。由于的基底和的基底正交，空间和空间也正交，它们互为零空间。因此，线性码的任意码字一定正交于其对偶码的任意一个码字，也必定正交于校验矩阵的任意一个行矢量，即。由于生成矩阵的每个行矢量都是一个码字，因此必有。对于生成矩阵符合“系统形式”的系统码，其校验矩阵也是规则的，必为： 上式中的负号在二进制码情况下可以省略，因为模二减法和模二加法是等同的。（3）信息码元及对应码字的关系（n，k）码字中的任一码字，均

8、可以由这组基底的线性组合生成，即 式中的是个信息元组的信息组，因此其信息码元及对应码字的关系如表一所示：表2.1 信息码元及对应码字关系信息组码字0000010100111001011101112. 线性分组码的伴随式与译码 （1）码的距离及检错能力两个码字之间，对应位取之不同的个数，称为汉明距离，用d表示。一个码的最小距离定义为,两个码字之间的距离表示了它们之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个码字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。任何最小距离的线性分组码，其检错能力为纠错能力t为 最小距离表明码集中各码字差异的程度，差异越大越容易区分，抗干

9、扰能力自然越强，因此成了衡量分组码性能最重要的指标之一。估算最小距离是纠错码设计的必要步骤，最原始的方法是逐一计算两两码字间距离，找到其中最小者。含个码字的码集需计算个距离后才能找出，费时太多，实用中还有一些更好更快的方法。线性分组码的最小距离等于码集中时非零码字的最小重量，即 式中，符号 表示 重量（1的个数）。这里利用了群的封闭性，由于分组码是群码，任意两码字之和仍是码字，即。因此任意两码字间的汉明距离其实必是另一码字的重量，表示为成下面公式形式。于是可将最小距离问题转化为寻找最轻码字问题，含个码字的码集仅需计算次。码的检错能力取决于码的最小距离，但还需说明的另一点是码的总体检错能力不仅仅

10、与有关。检错能力只是说明距离的差错一定能纠，并非说距离大于的差错一定不能纠。事实上，如果有个码子，就存在 个距离，这并非相等的。比如最小距离 ，检错力 ，是由码的距离决定，只要 朝 方向偏差大于1就会出现译码差错；然而若朝方向偏差3，译码时仍可正确地判断为而非。可见，总体的、平均的纠错能力不但与最小距离有关，而且与其余码距离或者说与码子的重量分布特性有关，把码距（码重）的分布特性称为距离（重量）谱，其中最小的重量就是。正如信息论各符号等概时熵最大一样，从概念上可以想象到:当所有码距相等时是（重量谱为线谱）码的性能应该最好；或者退一步说，当各码距相当不大时（重量谱为窄谱）性能应该叫好。事实证明确

11、实如此，在同样的条件下，窄谱的码一般比宽谱的码更优。纠错重量谱的研究具有理论与现实意义，不仅仅是计算各种译码差错概率的主要依据，也是研究码的结构、改善码集内部关系从而发现新的好码的重要工具。但目前除了少数几类码如汉明码、极长码等的重量分布已知外，还有很多码的重量分布并不知道，距离分布与性能之间确切的定量关系对于大部分码而言尚在进一步研究当中，特别当 和 较大时，要得出码重分布是非常困难的。 重量谱可以如下多项式来表示，称为重量算子，即 式中的含义：在码长的码集里，包括重量为0的码子个（线性码一定包含一个重量为0的全0码），码重为1的码字个，重量为n的码字个。（2）伴随式与译码 码字在传输过程中

12、受到各种干扰，接收端收码已不一定等于发码，两者间的差异就是差错，差错是多样化的，我们定义差错的式样为差错图样,即 对于二进制码，模2减等同模2加，因此有 利用码字与校验矩阵的正交性，可检验收码是否错误,即 定义运算结果为伴随式,即 可见，虽然本身与发码有关，但乘以后的伴随式 仅与差错图有关，只反映信道对码字造成怎样的干扰而与发什么码无关了。可以先利用收码和已知的算出的伴随式；再利用算出差错图样。这种思路下的编译码过程如图所示。在此过程中，和的计算都是确定性的，而从计算却带有随机性。这是因为伴随式是一个重失量，二进制时只有种肯那个的组合，而差错图样是重失量，因此与不存在一一对应关系。假设接收端收

13、到的码字为，那么它和原来发送端发送的码字之间就有可能存在着误差。即在码组中的任意一位就有可能出错。这样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要表达的意思。为了描述数据在传输信道中出现错误的情况，引入了错误图样，在错误图样中，0代表对应位没有传错，1代表传输错误。实际上错误图样就是收序列与发送序列的差。所以在译码中用接收到的码字模尔加错误图样就可以得到发送端的正确码字。因此译码的过程就是要找到错误图样E。定义：校正子 因为是编得的正确码字。根据前面所叙述，它和监督矩阵的转置相乘为0。显然，仅与错误图样有关，它们之间是一一对应的关系。找到了校正子，也就可以找到。而与发送的码字无关

14、。若，则；因此根据是否为0可进行码字的检错。如果接收码字中只有一位码元发生错误，又设错误在第位。即,其他的均为0。在后面的译码程序中，建立了一个校正子与错误图样对应的表。也就是收到一个序列，就可以通过计算得到一个校正子，而每一个校正子都对应着一个错误图样，再通过模尔加上，就可以得到正确的码字。因为在不同的错误序列中，同一位码元错误时对应的是一样的，所以可以利用这个正确的码字让它每位依次错误和两位特定错误，来求得它的八个校正子。而这时的矩阵就是错误图样。2.2设计步骤1. 编码过程根据已知检验元与信息的关系，设码字为（c6,c5, c4, c3, c2, c1,c0) 。由上式关系式移相可得如下

15、的关系式： 由移相所得的关系式可以写出监督矩阵和生成矩阵。有了生成矩阵后可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵，即MATLAB函数为：其中为编码后的结果，为信息矩阵，为生成矩阵。则编码所有情况为： 三位信息码 四位监督码 2. 译码过程 对于译码过程来说，由求得的监督矩阵： 本设计以（7，3）为例。任何一个码字与监督矩阵（7，3）码的转置进行相乘的结果必等于0，即若是任一码字，则必有。若不属于许用码字，或有传输差错，且差错位数在码纠错能力内，则运算结果将为非0值，说明有错误出现。在一定的纠错能力内可以纠错，当超过纠错能力时，则不能纠错。设接收的码字（c6,c5, c4, c3, c

16、2, c1,c0) ，则：(1) 当接收码字为（）时： 所以由伴随矩阵知此时接收编码无错误，纠错后译码为（）。（2） 当接收码字为（）时： 所以由伴随矩阵知此时接收编码c0发生错误，纠错后译码为（）。（3）当接收码字为（）时： 所以由伴随矩阵知此时接收编码c1发生错误，纠错后译码为（）。（4） 当接收码字为（）时： 所以由伴随矩阵知此时接收编码c2发生错误，纠错后译码为（）。（5） 当接收码字为（）时： 所以由伴随矩阵知此时接收编码c3发生错误，纠错后译码为（）。（6） 当接收码字为（）时： 所以由伴随矩阵知此时接收编码c4发生错误，纠错后译码为（）。（7） 当接收码字为（）时： 所以由伴随矩

17、阵知此时接收编码c5发生错误，纠错后译码为（）。 （8）当接收码字为（）时： 所以由伴随矩阵知此时接收编码c6发生错误，纠错后译码为（）。 （9）当接收码字为（）时：所以，此时接收编码c5位和c2位发生错误，纠错后的正确译码（）。根据所发生的差错情况，列出所有错码矩阵如下表2.2所示：表2.2 伴随式与错误图样的对应关系校正子 差错图样 000000010010010010001101011111100011第3章 仿真程序及结果分析3.1 仿真程序% H 监督矩阵% G 生成矩阵 % C 编码矩阵% I 输入信息序列 % B 信道输出码 % A 纠错输出码序列 % E 错码矩阵% S 校验子

18、矩阵% M 校验子的行的十进制序列%信道编码程序 clear allclose 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

19、 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); %求校验子所表示的十进制整

20、数 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) c

21、ase 0 disp(没有出现错误！); case 1 disp(注意：第c0位出现一个错误！请纠正！); case 2 disp(注意：第c1位出现一个错误！请纠正！); case 4 disp(注意：第c2位出现一个错误！请纠正！); case 8 disp(注意：第c3位出现一个错误！请纠正！); case 13 disp(注意：第c4位出现一个错误！请纠正！); case 7 disp(注意：第c5位出现一个错误！请纠正！); case 14 disp(注意：c2位和c5位出现两个错误！请纠正！); end endA=rem(A,2); %求出正确的编码 disp(检纠错后的码组A=)

22、; 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 第c3位出现错误时的仿真图（3） 有两位错误输入时显示图: 图3.3 出现两位错误时的仿真图3.3 结果分析 当输入没有错误码字时。仿真过程中，在MATLAB界面输入：0 0 0 0 0 0 0矩阵，由于输入的接收码组与编码后的码字一致，它提取了每个码组的前四位，即信息位，由结果看出

23、译码过程是正确的，并没有出现错译的情况，可见程序的译码片段是正确的。 当输入一位错误码字时，仿真过程中，在MATLAB界面输入：0 1 0 0 0 0 0矩阵，仿真结果显示有一位错误输入时，可知接收码组的第c5位发生了错误，经程序纠检错误后改正了接收序列的错误，并且正确译出了信息位。可见程序的纠错功能也是可以实现的，以上结果进一步证实了，系统译码程序的正确性。当输入两位特定位错误码字时的结果分析同理由仿真结果可以看出，当输入B=0 1 0 0 1 0 0矩阵时，校正子是0011，错误图样是，所以可以得知接收码组的第c5位和c2位发生了错误，说明理论得以验证。可以得到仿真的经过与手算的经过是一致

24、的，满足了题设基本要求。 由仿真结果可以看出，编码的结果与在推导过程中运算的结果是一致的，所以我们可以知道程序的编码运行过程是正确的。实际在计算过程中，设接收码字为（c6,c5, c4, c3, c2, c1,c0) 。以接收码字（）为例，在实际接收时，它的伴随矩阵为（0001），在中在第一行的位置，即第c0位出现错误。同时将码字（）输入到MATLAB里进行双向验证，MATLAB输出的界面显示为有一位错误，并显示：第c0位出现一个错误！请纠正！所以，我们从中可以看出，不管是实际计算结果，还是仿真结果都是一致的，双向验证的结果都是正确的，满足了系统的基本要求。第4章 总结 这次为期二周的编码课程设计，使我收获了很多。线性分组码是差错控制编码的重要一种。线性分组码的编码与译码纠错能力较强，是实际应用中比较流行的差错控制编码方法之一。我们选择MATLAB语言作为编程语言，因为MATLAB语言是比较容易实现，在实际应用过程中使用的非常广泛，也是我们应该熟练掌握的语言。运用MATLAB语言进行编程，可以较明显的知道编码的过程和译码时出现的错误。线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较