信息编码设计

1、吉林建筑大学电气与电子信息工程学院信息理论与编码课程设计报告设计题目：线性分组码编码的分析与实现专业班级： 电子信息工程 112 学生姓名： 王朝阳 学 号： 10211218 指导教师： 李红 杨佳 设计时间： 2014.11.242014.12.5 教师评语：成绩 评阅教师 日期 第1章 概述1.1设计的作用、目的信息论与编码是一门理论与实践密切结合的课程,课程设计是其实践性教学环节之一。一方面，通过让学生完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解编码理论和信息论中的基本概念，同时增强其逻辑思维能力，培养和提高学生的自学能力以及综合运用所学理论知识去分析解决实际问题的能力

2、；另一方面是对课堂所学理论知识作一个总结和补充。1.2设计任务及要求设计一个（6, 3）线性分组码的编译码程序：完成对任意序列的编码，根据生成矩阵形成监督矩阵，得到伴随式，并根据其进行译码，同时验证工作的正确性。通过课程设计各环节的实践，应使学生达到如下要求：1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；3. 能够使用MATLAB或其他语言进行编程，编写的函数要有通用性。1.3设计内容已知一个（6,3）线性分组码的校验元与信息元有如下限定关系。设码字为(c5, c4, c3, c2, c1, c0)

3、 求出标准校验矩阵、Q矩阵、标准生成矩阵，完成对任意信息序列（个许用码字）的编码。当接收码字分别为(000000), (000001), (000010), (000100), (001000), (010000), (100000)时，写出其伴随式S，以表格形式写出伴随式与错误图样E的对应关系，纠错并正确译码，当有两位错码时，假定为位和位发生错误。 第2章 线性分组码编码的分析与实现2.1设计原理1. 线性分组码的生成矩阵和校验矩阵（1）线性分组码具有如下性质（n，k）的性质：1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。对于码组长度为n、信息码元为k位、

4、监督码元为rnk位的分组码，常记作（n，k）码，如果满足2r1n，则有可能构造出纠正一位或一位以上错误的线性码。设分组码（n，k）中，k = 3，为能纠正一位误码，要求r3。现取r3，则nkr6。该例子中，信息组为C5 C4 C3,码字为C5 C4 C3 C2 C1 C0.当已知信息组时，按以下规则得到三个校 验元，即 C2=C5+C4 C1=C3+C4 C0=C5+C3这组方程称为校验方程。 （6，3）线性分组码有23（8）个许用码字或合法码字，另有26-23个禁用码字。发送方发送的是许用码字，若接收方收到的是禁用码字，则说明传输中发生了错误。 为了深化对线性分组码的理论分析，可将其与线性空

5、间联系起来。由于每个码字都是一个二进制的n重，及二进制n维线性空间中的一个矢量，因此码字又称为码矢。线性分组码的一个重要参数是码率r=k/n,它说明在一个码字中信息位所占的比重，r越大，说明信息位所占比重越大，码的传输信息的有效性越高。由于(n,k)线性分组，线性分组码的2k个码字组成了n维线性空间的一个K维子空间。因此这2k个码字完全可由k个线性无关的矢量所组成。（2）生成矩阵和校验矩阵 线性分组码码空间是由个线性无关的基底，张成的维重子空间，码空间的所有元素都可以写成个基底的线性组合，即这种线性组合特性正是线性分组码。为了深化对线性分组码的理论分析，可将其与线性空间联系起来。由于每个码字都

6、是一个二进制的n重，及二进制n维线性空间Vn中的一个矢量，因此码字又称为码矢。用表示第个基底并写成矩阵形式再将个基底排列成行列的矩阵，得： = 由于个基底即的个行矢量线性无关，矩阵的秩一定等于，当信息元确定后，码字仅由矩阵决定，因此称这矩阵为该线性分组码的生成矩阵。基底的线性组合等效于生成矩阵的行运算，可以产生一组新的基底。利用这点可使生成矩阵具有如下的“系统形式”： 与任何一个分组线性码的码空间相对应，一定存在一个对偶空间。事实上，码空间基底数只是维重空间全部个基底的一部分，若能找出另外个基底，也就找到了对偶空间。既然用个基底能产生一个分组线性码，那么也就能用个基底产生包含个码字的分组线性码

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

8、） 由H矩阵可以建立线性分组码的线性方程组。H矩阵共有n-k行，其中每行代表一个线性方程组的系数，它表示求一个校验位的线性方程。（2） H矩阵的每行与它的分组码的每一个码子的内积为零。（3） 任何一个（n,k）线性分组码，若要纠正小于等于t个错误，则其充要条件是H矩阵中2t列线性无关，由于最小距离d=2t+1.所以也相当于要求H矩阵中任意（d-1）列线性无关。2. 线性分组码的伴随式与译码（1）码的距离及检错能力两个码字之间，对应位取之不同的个数，称为汉明距离，用d表示。一个码的最小距离定义为,两个码字之间的距离表示了它们之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个码字错成另一

9、码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。任何最小距离的线性分组码，其检错能力为纠错能力t为 最小距离表明码集中各码字差异的程度，差异越大越容易区分，抗干扰能力自然越强，因此成了衡量分组码性能最重要的指标之一。估算最小距离是纠错码设计的必要步骤，最原始的方法是逐一计算两两码字间距离，找到其中最小者。含个码字的码集需计算个距离后才能找出，费时太多，实用中还有一些更好更快的方法。线性分组码的最小距离等于码集中时非零码字的最小重量，即 这里利用了群的封闭性，由于分组码是群码，任意两码字之和仍是码字，即。因此任意两码字间的汉明距离其实必是另一码字的重量，表示为。于是可将最小距离问题转化为寻

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

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

12、之间是一一对应的关系。找到了校正子，也就可以找到。而与发送的码字无关。若，则；因此根据是否为0可进行码字的检错。如果接收码字中只有一位码元发生错误，又设错误在第位。即,其他的均为0。在后面的译码程序中，建立了一个校正子与错误图样对应的表。也就是收到一个序列，就可以通过计算得到一个校正子，而每一个校正子都对应着一个错误图样，再通过模尔加上，就可以得到正确的码字。因为在不同的错误序列中，同一位码元错误时对应的是一样的，所以可以利用000000这个正确的码字让它每位依次错误，来求得它的七个校正子。而这时的矩阵就是错误图样。2.2设计步骤1. 编码过程监督矩阵和生成矩阵的关系：由与的分块表示的矩阵形式

13、，。则有或者 。 由Q=则可以求出生成矩阵=由 和可求出监督矩阵为： H=有了生成矩阵后则可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵，即MATLAB函数为： ，其中为编码后的结果，为信息矩阵，为生成矩阵。可以得到信息序列为C = 2. 译码过程对于译码过程来说，由上面可知道监督矩阵：矩阵与码的任何一个许用码字进行相乘的结果必等于0，即若是任一码字，则必有。若不属于许用码字，或有传输差错，且差错位数在码纠错能力内，则运算结果将为非0值，此时，可以纠错或检错重发。 假设c0c5 为第一位至第六位： (1)当接收码字为（000000）时：伴随式所以此时接收编码无错误。 （2）当接收码字为（0

14、00001）时：所以，此时接收编码第一位发生错误，纠错后的正确译码为（0000000）。（3）当接受码字为（000010）时：所以，此时接收编码第二位发生错误，纠错后的正确译码为（0000000）。（4）当接收码字为（000100）时：所以，此时接收编码第三位发生错误，纠错后的正确译码为（0000000）。（5）当接受码字为（001000）时：所以，此时接收编码第四位发生错误，纠错后的正确译码为（0000000）。（6）当接收码字为（010000）时：所以，此时接收编码第五位发生错误，纠错后的正确译码为（0000000）。（7）当接收码字为（100000）时：所以，此时接收编码第六位发生错误，

15、纠错后的正确译码为（0000000）。 （8）当接收码字为（100100）时： 所以，此时接收编码第六位和第三位发生错误，纠错后的正确译码为（0000000）。 因为伴随式与差错图样之间存在其中由上面的关系可知的关系。 当编码矩阵与生成矩阵的转置矩阵相乘时，若当其中的一位编码或两位出现差错时会有八种情况，则这些情况列出错码矩阵如下表二：校正子S错误图样E000000000101000001110000010011000100100001000010010000 001100000表2 伴随式与错误图样的对应关系第3章 仿真程序及结果分析3.1 仿真程序 % G 生成矩阵% H 校验矩阵% C

16、编码矩阵% I 输入信息序列% R 信道输出码% A 纠错输出码序列% E 错码矩阵% S 校验子矩阵% M 检验子的行的十进制序列%信道编码程序clear allclose allH=0 1 1 1 0 0;1 0 1 0 1 0;1 1 0 0 0 1;G=gen2par(H);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);disp(所得的编码结果：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;B=inp

17、ut(请输入接收码组B:);a,b=size(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);i=1;for i=1:1:a M(i,1)=S(i,1).*4+S(i,2).*2+S(i,3);endfor 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,:

18、); 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,:); endendfor i=1:1:a switch(M(i,1) case 0 disp(没有出现错误); case 1 disp(第一位出现错误); case 2 disp(第二位出现错误); case 3 disp(第三位出现错误); case 4 disp(第四位出现错误); case 5 disp

19、(第五位出现错误); case 6 disp(第六位出现错误); case 7 disp(第六位和第三位出现错误); endend A=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） 在提示符后输入：0 0 0 0 0 0，按下回车：图1无错误输入显示图这是输出的结果，结果显示没有错误。（2）在提示符后输入：0 0 0 0 0 0，按下回车： 图2 有一位错误输入时显示图 以上接收码组的第一位发生了错误，经程序纠

20、检错误后改正了接收序列的错误，并且正确译出了信息位。可见程序的纠错功能也是可以实现的，以上结果进一步证实了系统译码程序的正确性。（3）在提示符后输入：1 0 0 1 0 0，按下回车：图3 有两位错误输入时显示图 以上接收码组的第六位和第三位发生了错误，经程序纠检错误后，改正了接收序列的错误，并且正确译出了信息位。可见程序的纠错功能也是可以实现的，以上结果进一步证实了系统译码程序的正确性。3.3结果分析1. 由图1 输出编码结果和正确输入时显示图所示的结果可以看出编码的结果的十六种情况和在推导过程中运算的结果是一致的，可以见得程序的编码过程是正确的。对于译1输出编码结果及输入正确接收码的译码结

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

22、的结果分析 由图3 有两位特定位错误输入时的显示图知，当输入R=1 0 0 1 0 0时，校正子是0011，错误图样是100100，所以结果显示与理论相符。 第四章 总 结两周的课程设计快要接近尾声，我的设计任务也较顺利地完成。回想我刚接到我的设计题目时，脑海里没有完整的设计计划。通过去图书馆查阅资料，有了完整且可行的计划。在把理论的知识弄懂后，我用MATLAB软件仿真，MATLAB语言简单，使用性好，刚开始对于它并不熟悉，通过这次课设，到处查资料，使我渐渐了解了MATLAB的很多函数用法，提高了我的编程能力。尤其当我的编程所得到的结果与我理论推导的相一致时，我感到无比的欣慰。总之，此次课设使我学到很多东西，不仅提高了我的动手能力及自学能力，还知道了我的不足之处，今后应加强。这次课设能进展如此顺利，多亏了老师们不辞辛苦，不厌其烦的耐心指导，同学们之间互相协作，还有我使用的参考书的编者们的帮助，在此我诚挚地感谢您们！为期一周的课程设计结束了，我在这段时间内学到了很多东西。以前我们学的知识，因为有些知识比较难懂，自己在课后也没有去查阅课外资料去理解、去弄懂。这次我有时间和精力去专心学习与这门课的更多知识，不再仅仅只局限于课本。在老师给我们布置自己的设计内容后，我就去图书馆查阅资料，寻找与设计有关的书籍。我们找了专业课课本和一些与MATLAB有关的书。然后找到自己之前在MAT