(6,3)线性分组码编码分析与实现

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

2、码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。1.2 设计任务及要求设计一个（6, 3）线性分组码的编译码程序：完成对任意序列的编码，根据生成矩阵形成监督矩阵，得到伴随式，并根据其进行译码，同时验证工作的正确性。1理解信道编码的理论基础，掌握信道编码的基本方法；2掌握生成矩阵和一致校验矩阵的作用和求解方法；3针对线性分组码分析其纠错能力，并能够对线性分组码进行译码；4能够使用MATLAB或其他语言进行编程，实现编码及纠错，编写的函数要有通用性。1.3设计内容已知一个（6,

3、3）线性分组码的Q矩阵：设码字为(c5, c4, c3, c2, c1, c0) 求出标准生成矩阵和标准校验矩阵，完成对任意信息序列（23个许用码字）的编码。当接收码字R分别为(000000), (000001), (000010), (000100), (001000), (010000), (100000), (100100)时，写出其伴随式S，以表格形式写出伴随式与错误图样E的对应关系。纠错并正确译码，当有两位错码时，假定c5位和c2位发生错误。第2章 写所设计题目2.1设计原理1. 线性分组码的标准生成矩阵和标准校验矩阵（1）（n，k）线性分组码的性质1、封闭性。任意两个码组的和还是许

4、用的码组。2、码的最小距离等于非零码的最小码重。对于长度为n的二进制线性分组码，它有种2n可能的码组，从2n种码组中，可以选择M=2k个码组（k<n）组成一种码。这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=2k个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。对于码组长度为n、信息码元为k位、监督码元为rnk位的分组码，常记作（n，k）码，如果满足2r1n，则有可能构造出纠正一位或一位以上错误的线性码。（2）生成矩阵和校验矩阵线性分组码码空间是由个线性无关的基底，张成的维重子空间，码空间的所有元素都可以写成个基底的线性组合，即这种

5、线性组合特性正是线性分组码。为了深化对线性分组码的理论分析，可将其与线性空间联系起来。由于每个码字都是一个二进制的n重，及二进制n维线性空间Vn中的一个矢量，因此码字又称为码矢。用表示第个基底并写成矩阵形式再将个基底排列成行列的矩阵，得： = 个基底即的个行矢量线性无关，矩阵的秩一定等于，当信息元确定后，码字仅由矩阵决定，因此称这矩阵为该线性分组码的生成矩阵。基底不是唯一的，生成矩阵也就不是唯一的。事实上，将个基底线性组合后产生另一组个矢量，只要满足线性无关的条件，依然可以作为基底张成一个码空间。不同的基地有可能生成同一个码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同

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

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

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

9、设计的必要步骤，最原始的方法是逐一计算两两码字间距离，找到其中最小者。含个码字的码集需计算个距离后才能找出，费时太多，实用中还有一些更好更快的方法。线性分组码的最小距离等于码集中时非零码字的最小重量，即 这里利用了群的封闭性，由于分组码是群码，任意两码字之和仍是码字，即。因此任意两码字间的汉明距离其实必是另一码字的重量，表示为。于是可将最小距离问题转化为寻找最轻码字问题，含个码字的码集仅需计算次。码的检错能力取决于码的最小距离，但还需说明的另一点是码的总体检错能力不仅仅与有关。检错能力只是说明距离的差错一定能纠，并非说距离大于的差错一定不能纠。事实上，如果有个码子，就存在 个距离，这并非相等的

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

11、，也是研究码的结构、改善码集内部关系从而发现新的好码的重要工具。但目前除了少数几类码如汉明码、极长码等的重量分布已知外，还有很多码的重量分布并不知道，距离分布与性能之间确切的定量关系对于大部分码而言尚在进一步研究当中，特别当 和 较大时，要得出码重分布是非常困难的。重量谱可以如下多项式来表示，称为重量算子，即 式中的含义：在码长的码集里，包括重量为0的码子个（线性码一定包含一个重量为0的全0码），码重为1的码字个，重量为n的码字个。(2)伴随式与译码 码字在传输过程中受到各种干扰，接收端收码已不一定等于发码，两者间的差异就是差错，差错是多样化的，我们定义差错的式样为差错图样,即 对于二进制码，

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

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

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

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

16、4）当接受码字为时：伴随式所以，此时接受编码第三位发生错误，纠错后的正确译码为。（5）当接受码字为时：伴随式所以，此时接受编码第四位发生错误，纠错后的正确译码为。（6）当接受码字为时：伴随式所以，此时接受编码第五位发生错误，纠错后的正确译码为。（7）当接受码字为时：伴随式所以，此时接受编码第六位发生错误，纠错后的正确译码为。（8）当接受码字为时：伴随式因为伴随式与差错图样之间存在其中由上面的关系可知，所以，此时接受编码第五位和第二位发生错误，纠错后的正确译码（110110）。当编码矩阵与生成矩阵的转置矩阵相乘时，若当其中的一位编码或两位出现差错时会有八种情况，则这些情况列出错码矩阵如下：校正子

17、S错误图样E000000000001000001010000010011000100100001000101010000110100000111010010表5.1 伴随式与错误图样的对应关系第3章 仿真程序及结果分析3.1 仿真程序 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=

18、'); %显示输出码字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;0 1 0 0 1 0; S=rem(B*H',2); %求校验子Si=1; for i=1:1:a M(i

19、,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 4 A(i,:)=B(i,:)+E(4,:); case 6 A(i,:)=B(i,:)+E(5,:); case 5 A(i,:)=B(i,:)+E(6,:); case 3 A(i,:)=B(i,:)+E(7,:); case 7 A(i,:)=B(i,:)

20、+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 6 disp('注意：第4位出现一个错误！请纠正！'); case 5 disp('注意：第5位出现一个错误！请纠正！'); case 3 disp('

21、;注意：第6位出现一个错误！请纠正！'); case 7 disp('注意：第5位和第2位出现两个错误！请纠正！'); 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 仿真结果 图一 输出编码结果和无错误输入 图二 有一位错误输入时显示图图三 有两位错误输入时显示图3.3结果分析

22、1输出编码结果及输入正确接收码的译码结果分析由图一可以看出编码的结果的八种情况和在推导过程中运算的结果是一致的，所以我们可以知道程序的编码过程是正确的。对于译码过程而言，当界面显示“请输入接收码组B：” ，然后从提示符后输入：0 0 0 0 0 0，由于输入的接收码组与编码后的码字一致，它提取了每个码组的前四位，即信息位，由结果看出译码过程是正确的，并没有出现错译的情况，可见程序的译码片段是正确的。2输入一位错误时的结果分析由图二可以看出，当界面显示“请输入接收码组B：” 。然后从提示符后输入：0 1 0 0 0 0，由图二有一位错误输入时的显示图所知，接收码组的第五位发生了错误，经程序纠检错

23、误后改正了接收序列的错误，并且正确译出了信息位。可见程序的纠错功能也是可以实现的，以上结果进一步证实了，系统译码程序的正确性。3输入两位特定位错误时的结果分析由图三可以看出，当界面显示“请输入接收码组B：”。然后从提示符后输入：0 1 0 0 1 0, 由图三有两位错误输入时的显示图所知，接收码组的第五位和第二位发生了错误，经程序纠检错误后改正了接收序列的错误，并且正确译出了信息位，校正子是111，错误图样是100100，所以说明理论得以验证，可见程序的纠错功能也是可以实现的，第4章 总结通过这次的课程设计，让我对MATLAB软件有了更深的了解，对MATLAB语言也有了更加深入的学习和理解。在本次的设计中，我了解了MATLAB中很多函数的用法，提高了我编程的能力，在软件仿真上，提高了自己的动手能力和学习能力，为以后的学习打下了良好的基础。我学习到了很多东西，让我对线性编码有了一个全新的认识，对Matlab的掌握也进步了很多，为以后的学习中出现的可能问题做好了准备，锻炼了自己的动手能力和设计能力，掌握了一种科技工具，丰富了自己的学习生活。整个实验过程中我懂得了许多东西，在查找的过程中我们也知道了许多原来不知道的东西，对于源代码的修改以及成功利用也树立了对知识应用的信心，相信会对今后的学习工作和生