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

1、吉林建筑大学电气与电子信息工程学院信息理论与编码课程设计报告设计题目：线性分组码编码的分析与实现专业班级： 电子信息工程101 学生姓名： 张 様 学 号： 10210122 指导教师： 吕卅 王超 设计时间： 2013.11.182013.11.29 教师评语：成绩 评阅教师 日期 一、设计的作用、目的信息论与编码是一门理论与实践密切结合的课程,课程设计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。 目前，绝大多数的数字计算机和数字通信系统中广泛采用二进制形式

2、的码。而线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术。通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。2、 设计任务及要求 设计一个（6，3）线性分组码的编译码程序，最基本的是要具备对输入的信息码进行编码，让它具有抗干扰的能力。同时，还要让它具有对接收到的整个码组中提取信息码组的功能。通过课程设计各环节的实践，应

3、使学生达到如下要求：1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；4. 能够使用MATLAB或其他语言进行编程，编写的函数要有通用性。三、设计内容已知一个（6,3）线性分组码的Q矩阵：设码字为(c5, c4, c3, c2, c1, c0) 求出标准生成矩阵和标准校验矩阵，完成对任意信息序列（23个许用码字）的编码。当接收码字R分别为(000000), (000001), (000010), (000100), (001000), (010000

4、), (100000), (100100)时，写出其伴随式S，以表格形式写出伴随式与错误图样E的对应关系。纠错并正确译码，当有两位错码时，假定c5位和c2位发生错误。四、设计原理4.1线性分组码的标准生成矩阵和标准校验矩阵4.1.1线性分组码的性质线性分组码具有如下性质（n，k）的性质：1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。对于长度为n的二进制线性分组码，它有种2n可能的码组，从2n种码组中，可以选择M=2k个码组（kn）组成一种码。这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=2k个码组构成的码集中选出来的，这样剩下的

5、码组就可以对这个分组码进行检错或纠错。对于码组长度为n、信息码元为k位、监督码元为rnk位的分组码，常记作（n，k）码，如果满足2r1n，则有可能构造出纠正一位或一位以上错误的线性码。4.1.2生成矩阵和校验矩阵 线性分组码码空间是由个线性无关的基底，张成的维重子空间，码空间的所有元素都可以写成个基底的线性组合，即这种线性组合特性正是线性分组码。为了深化对线性分组码的理论分析，可将其与线性空间联系起来。由于每个码字都是一个二进制的n重，及二进制n维线性空间Vn中的一个矢量，因此码字又称为码矢。用表示第个基底并写成矩阵形式再将个基底排列成行列的矩阵，得： = 由于个基底即的个行矢量线性无关，矩阵

6、的秩一定等于，当信息元确定后，码字仅由矩阵决定，因此称这矩阵为该线性分组码的生成矩阵。基底的线性组合等效于生成矩阵的行运算，可以产生一组新的基底。利用这点可使生成矩阵具有如下的“系统形式”： 与任何一个分组线性码的码空间相对应，一定存在一个对偶空间。事实上，码空间基底数只是维重空间全部个基底的一部分，若能找出另外个基底，也就找到了对偶空间。既然用个基底能产生一个分组线性码，那么也就能用个基底产生包含个码字的分组线性码，称码是码的对偶码。将空间的个基底排列起来可构成一个矩阵，将这个矩阵称为码空间的校验矩阵，而它正是对偶码的生成矩阵，它的每一行是对偶码的一个码字。和的对偶是互相的，是的生成矩阵又是

7、的校验矩阵，而是的生成矩阵，又是的校验矩阵。由于的基底和的基底正交，空间和空间也正交，它们互为零空间。因此，线性码的任意码字一定正交于其对偶码的任意一个码字，也必定正交于校验矩阵的任意一个行矢量，即。由于生成矩阵的每个行矢量都是一个码字，因此必有。对于生成矩阵符合“系统形式”的系统码，其校验矩阵也是规则的，必为： 上式中的负号在二进制码情况下可以省略，因为模2减法和模2加法是等同的。在本次课程设计中，要求设计（6,3）线性分组码，因此其信息码元及对应码字的关系如下表：信息码元码字系统码字000000000000000001011101001011010110001010110011101100

8、011101100111010100111101100111101100110001011110001111010110111010 表4-1信息码元及对应码字关系4.2线性分组码的伴随式与译码 4.2.1码的距离及检错能力两个码字之间，对应位取之不同的个数，称为汉明距离，用d表示。一个码的最小距离定义为,两个码字之间的距离表示了它们之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个码字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。任何最小距离的线性分组码，其检错能力为纠错能力t为 最小距离表明码集中各码字差异的程度，差异越大越容易区分，抗干扰能力自然越强，因此成了衡

9、量分组码性能最重要的指标之一。估算最小距离是纠错码设计的必要步骤，最原始的方法是逐一计算两两码字间距离，找到其中最小者。含个码字的码集需计算个距离后才能找出，费时太多，实用中还有一些更好更快的方法。线性分组码的最小距离等于码集中时非零码字的最小重量，即 这里利用了群的封闭性，由于分组码是群码，任意两码字之和仍是码字，即。因此任意两码字间的汉明距离其实必是另一码字的重量，表示为。于是可将最小距离问题转化为寻找最轻码字问题，含个码字的码集仅需计算次。4.2.2伴随式与译码 假设接收端收到的码字为，那么它和原来发送端发送的码字之间就有可能存在着误差。即在码组中的任意一位就有可能出错。这样我们在接收端

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

11、。在后面的译码程序中，建立了一个校正子与错误图样对应的表。也就是收到一个序列，就可以通过计算得到一个校正子，而每一个校正子都对应着一个错误图样，再通过模尔加上，就可以得到正确的码字。因为在不同的错误序列中，同一位码元错误时对应的是一样的，所以可以利用0000000这个正确的码字让它每位依次错误，来求得它的八个校正子。而这时的矩阵就是错误图样。5、 设计步骤5.1编码过程监督矩阵和生成矩阵的关系：由与的分块表示的矩阵形式，。则有或者 。已知给出的（6,3）线性分组码的矩阵： 则可以根据求出生成矩阵：由 和可求出监督矩阵为：有了生成矩阵后则可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵，即MA

12、TLAB函数为： ，其中为编码后的结果，为信息矩阵，为生成矩阵。则编码的所有情况为： 编码序列： 信息位 | 监督位 5.2译码过程对于译码过程来说，同样由上知道监督矩阵：矩阵与码的任何一个许用码字进行相乘的结果必等于0，即若是任一码字，则必有。若不属于许用码字，或有传输差错，且差错位数在码纠错能力内，则运算结果将为非0值，此时，可以纠错或检错重发。(1)当接受码字为（00000000）时：伴随式所以此时接受编码无错误。（2） 当接受码字为（00000001）时：伴随式所以，此时接受编码第一位发生错误，纠错后的正确译码为（000000）。 （3）当接受码字为（00000010）时：伴随式所以，

13、此时接受编码第二位发生错误，纠错后的正确译码为（000000）。（4）当接受码字为（00000100）时：伴随式所以，此时接受编码第三位发生错误，纠错后的正确译码为（000000）。（5）当接受码字为（00001000）时：伴随式所以，此时接受编码第四位发生错误，纠错后的正确译码为（000000）。（6）当接受码字为（00010000）时：伴随式所以，此时接受编码第五位发生错误，纠错后的正确译码为（000000）。（7）当接受码字为（00100000）时：伴随式所以，此时接受编码第六位发生错误，纠错后的正确译码为（000000）。（8）当接受码字为（100100）时：伴随式所以，此时接受编码第

14、五位和第二位发生错误，纠错后的正确译码（110110）。当编码矩阵与生成矩阵的转置矩阵相乘时，若当其中的一位编码或两位出现差错时会有八种情况，则这些情况列出错码矩阵如下：校正子S错误图样E000000000001000001010000010011000100100001000101010000110100000111010010表5.1 伴随式与错误图样的对应关系6、 仿真程序及结果分析 6.1 MATLAB简介1 基本功能MATLAB是很实用的数学软件它在数学类科技应用软件中在数值运算方面首屈一指。MATLAB可以进行运算、绘制函数和数据、实现算法、创建用户界面、连接接其他编程语言的程序等

15、，主要应用于工程计算、控制设计、信号处理与通讯、金融建模设计与分析等领域。 MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且mathwork也吸收了像Maple等软件的优点,使MATLAB成为一个强大的数学软件。可以直接调用,用户也可以将自己编写的实用程序导入到MATLAB函数库中方便自己以后调用，此外许多的MATLAB爱好者都编写了一些经典的程序，用户可以直接进行下载就可以用。2 基本应用MATLAB 产品族可以用来进行以下各种工作： 数值分析 数值和符号计算 工程与科学绘图

16、 控制系统的设计与仿真 图像处理技术 数字信号处理技术 通讯系统设计与仿真 2.1 特点此高级语言可用于技术计算 此开发环境可对代码、文件和数据进行管理 交互式工具可以按迭代的方式探查、设计及求解问题 二维和三维图形函数可用于可视化数据 各种工具可用于构建自定义的图形用户界面 2.2优势（1）友好的工作平台和编程环境MATLAB由一系列工具组成。这些工具方便用户使用MATLAB的函数和文件，其中许多工具采用的是图形用户界面。包括MATLAB桌面和命令窗口、历史命令窗口、编辑器和调试器、路径搜索和用于用户浏览帮助、工作空间、文件的浏览器。随着MATLAB的商业化以及软件本身的不断升级，MATLA

17、B的用户界面也越来越精致，更加接近Windows的标准界面，人机交互性更强，操作更简单。而且新版本的MATLAB提供了完整的联机查询、帮助系统，极大的方便了用户的使用。简单的编程环境提供了比较完备的调试系统，程序不必经过编译就可以直接运行，而且能够及时地报告出现的错误及进行出错原因分析。 （2）简单易用的程序语言MATLAB一个高级的矩阵/阵列语言，它包含控制语句、函数、数据结构、输入和输出和面向对象编程特点。用户可以在命令窗口中将输入语句与执行命令同步，也可以先编写好一个较大的复杂的应用程序（M文件）后再一起运行。新版本的MATLAB语言是基于最为流行的C语言基础上的，因此语法特征与C语言极

18、为相似，而且更加简单，更加符合科技人员对数学表达式的书写格式。使之更利于非计算机专业的科技人员使用。而且这种语言可移植性好、可拓展性极强，这也是MATLAB能够深入到科学研究及工程计算各个领域的重要原因。 （3）强大的科学计算机数据处理能力MATLAB是一个包含大量计算算法的集合。其拥有600多个工程中要用到的数学运算函数，可以方便的实现用户所需的各种计算功能。函数中所使用的算法都是科研和工程计算中的最新研究成果，而前经过了各种优化和容错处理。在通常情况下，可以用它来代替底层编程语言，如C复数的各种运算、三角函数和其他初等数学运算、多维数组操作以及建模动态仿真等。 6.2 仿真程序% H 监督

19、矩阵% 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); %信道译码程序

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

21、数 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) cas

22、e 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);

23、 %显示正确的编码 j=1; while j=3 %提取信息位 I(:,j)=A(:,j); j=j+1; end disp(译出的信息序列I=); disp(I); %显示原信息码6.3 仿真结果图6.1 输出编码结果和无错误输入图6.2 有一位错误输入时显示图图6.3 有两位错误输入时显示图6.4结果分析1输出编码结果及输入正确接收码的译码结果分析由图6-1可以看出编码的结果的八种情况和在推导过程中运算的结果是一致的，所以我们可以知道程序的编码过程是正确的。对于译码过程而言，当界面显示“请输入接收码组B：” ，然后从提示符后输入：0 0 0 0 0 0，由于输入的接收码组与编码后的码字一致

24、，它提取了每个码组的前四位，即信息位，由结果看出译码过程是正确的，并没有出现错译的情况，可见程序的译码片段是正确的。2输入一位错误时的结果分析由图6-1可以看出，当界面显示“请输入接收码组B：” 。然后从提示符后输入：1 0 1 0 0 0，由图6-2 有一位错误输入时的显示图所知，接收码组的第五位发生了错误，经程序纠检错误后改正了接收序列的错误，并且正确译出了信息位。可见程序的纠错功能也是可以实现的，以上结果进一步证实了，系统译码程序的正确性。3输入两位特定位错误时的结果分析由图6-3 有两位特定位错误输入时的显示图知，当输入B=1 0 0 1 0 0时，校正子是111，错误图样是10010

25、0，所以说明理论得以验证。 7、 体会及建议 通过这次的课程设计，我学习到了很多东西，让我对线性编码有了一个全新的认识，对Matlab的掌握也进步了很多，为以后的学习中出现的可能问题做好了准备，锻炼了自己的动手能力和设计能力，掌握了一种科技工具，丰富了自己的学习生活。整个实验过程中我懂得了许多东西，在查找的过程中我们也知道了许多原来不知道的东西，对于源代码的修改以及成功利用也树立了对知识应用的信心，相信会对今后的学习工作和生活有非常大的帮助，并且提高了自己的动手实践操作能力，使自己充分体会到了在实验过程中的成功喜悦。让我对MATLAB软件有了更深的了解，对MATLAB语言也有了更加深入的学习和理解。在本次的设计中，我了解了MATLAB中很多函数的用法，提高了我编程的能力，在软件