线性分组码的编译码.doc

《线性分组码的编译码.doc》由会员分享，可在线阅读，更多相关《线性分组码的编译码.doc（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 *实践教学* 兰州理工大学计算机与通信学院2013年秋季学期计算机通信 课程设计 题 目： 线性分组码（7,3）码的编译码仿真设计 专业班级： 通信工程三班 姓 名： 彭佳峰 学 号： 指导教师： 彭 铎 成 绩： 专心-专注-专业摘要 本课题是应用C语言对（7,3）线性分组码的编译码的软件设计。主要做了一下几项工作：对三位正确的信息码进行编码；若输入的三位信息码有错，系统输出提醒，可以重新输入；对七位接收到的码字判断是否有错，并在无错和有一位错误时进行译码，在有多位错误时输出提醒，可以选择重新输入。 关键字：线性分组码 编码 译码 C语言目录前言近年来，随着计算机

2、、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计工作者所面临的重要课题。香农第二定理指出，当信息传输率低于信道容量时，通过某种编译码方法，就能使错误率为任意小。差错控制编码在此定理指导下迅速发展起来，它使得传输数据本身带有规律性，利用规律性来减少错误。线性分组码是差错控制编码的重要一种。它的规律性在于局限在一个码组之内，编码后长为n的一个码组中含有k位信息元和n-k位监督元，监督元是随所传输的信息元而改变的。接收端正式通过监督元和信息元之间的

3、规律性来发现并纠正错误的。1 基本原理1.1线性分组码的基本概念 （1）线性分组码线性分组码是一组固定长度的码组，可表示（n，k），通常它用于前向纠错。在分组码中，监督位被加到信息位之后，形成新的码。在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。当分组码的信息码元与监督码元之间的关系为线性关系时，这种分组码就称为线性分组码。对于长度为n的二进制线性分组码，它有种可能的码组，从码组中，可以选择个码组（kn)组成一种码，称为许用码组。这样，一个k比特信息的线性分组码可以映射到一个长度为n的码组上，该码组是从码组构成的码集中选出来的，这样剩下的码组就可以对个分组码

4、进行检错或纠错。（2） 码重（汉明重量） 把码组中非零位的数量定义为码重。（3）码距（汉明距离）两个码组对应位上数字不同的个数称为码组的距离，简称码距。原则是，让选择的这些码字的码距越长越好。1.2差错控制原理 将信息码分组，并为每个信息组附加若干监督的编码，称为“分组码”。在分组码中，监督码元仅监督本组码中的信息码元。分组码一般用符号（n）、（k）表示，其中k是每组码二进制信息码元的数目。n是码组的总位数，又称为码组的长度。r=n-k为每个码组中的监督码元数目，或称监督位数目。 k位二进制数构成的码组集合为种不同的码组，若组都为有用码组，其中任意码组出现错误都将变成另一码组，则接收端无法检测

5、识别哪一组出错。若只取部分码组为有用码组，则在传输过程中如接收端接收到的码组为非许用码组即禁用码组时，则可知传输错误。以3位二进制数构成的码组为例，它有8种不同的可能组合，若将其全部用来表示天气，则可以表示8种不同天气，例如：000晴、001云、010阴、011雨、100血、101霜、110雾、111雹。其中任一码组在传输中若发生一个或多个错误，则将变成另一个信息码组。这时接收端无法发现错误。若在上述8种码组中次序使用4种来传达天气，例如：000晴、011云、101阴、110雨。这时，虽然只能传达4种不同天气，但是接收端却可能发现码组中的一个错码。如000错码一位，则接收码组将变成100或01

6、1，这三种码组都为禁用码组，故接收端认为接收码错误。要想能够纠正错误，需增加冗余度。1.3线性分组码的纠检错能力 最小码距与码的抗干扰能力之间的关系，通过证明（不给出详细的证明过程），可以得到如下的结论，具体如下：若一种码的最小距离为，则它能检查传输差错个数（称为检错能力）e应满足；若一种码的最小距离为，则它能纠正传输差错个数t应满足；若一种码的最小距离为，则能检查e个错误，同时又能纠正t个一下错误的条件是。2线性分组码的编码2.1监督矩阵 （n,k)码中有n-k个监督元，例如（7,3）码，以序列表示码组，前面三位为信息元。监督元根据以下四个线性方程求得： （2.1） 通常称这四个线性方程为（

7、7,3）码的一致监督关系或一致监督方程组。表一 信息码与许用码组对应表 一致监督关系是从个n重矢量中挑选出来的，具有封闭性。把这种结构形式的线性分组码称为线性系统分组码。信息组码组信息组码组000100001101010110011111 将一致的监督方程组移动并记成矩阵形式：（2.2） 或者记成以下形式： （2.3） （2.4）式中P是阶矩阵，是r阶单位方阵。称具有这种子形式的H矩阵为典型阵。上式可以简写成： 一致监督矩阵H完全确定了线性分组码的规律性，找到了H矩阵也就确定了线性分组码的构造。2.2生成矩阵生成矩阵反映了信息元和监督元之间的直接关系。对于上例，可将编码方程改写为： （2.5）

8、 式中 （2.6）称为（7,3）码的生成矩阵。系统码的生成矩阵具有的形式，称为典型生成矩阵。通常，二进制（n,k)线性系统码的生成矩阵G具有如下形式： （2.7）G矩阵的每行都是一个码字。有了G矩阵或H矩阵，线性分组码的构造就确定了，根据C=IG，就可计算出该码组的全部码元。 比较P矩阵和Q矩阵，便知,或。这就是说，P的第一行就是Q的第一列，P的第二行就是Q的第二列.因此，H一定，Q也就确定，反之亦然。 （2.8） （2.9）3线性分组码的译码为了描述数据在传输信道中出现差错的情况，引入了错误图样的概念。错误图样：错误图样是接收序列和发送序列之间的差，用表示。在错误图样中，表示对应位没有传错，

9、表示传输有错。例如：发送序列,接收序列，则错误图样。可见，在译码时，只要设法从中找到错误图样，就可恢复发送端发送的码字,。因此，译码的任务就是要找到。首先，我们假定:发送码组为,接收码组为,错误图样。若，说明与不同，码字的位发生了错误。由于每个码字必须满足矩阵每行所确定的线性方程，因而收到后，可用矩阵检查，若等于则认为是码字，没有错误；否则就认为不是码字，产生了错误。定义:，将称为接收向量的伴随式。显然仅与错误图样有关，而与发送的码字无关。若,则；若，则。因此根据是否可为可进行码字的检查。假如接收码字中只有一位码元发送错误，又设错误在第为，即，其它的均为，则为的第行，为的第列。 （3.1） (

10、3.2) (3.3) (3.4)接收端根据这个结果便可判断出接收码的第位发生错误，从而实现纠错。如果接收码组中有多位码元同时发生错误，设错误在，位，即，其余的，同理可知： （3.5）这说明相当于H矩阵的第，列的线性组合，假设这个线性组合为0，即伴随式序列，则在接收端是不能判断出接收码组中中有错（此时的错误称不可检错误）。假设这个线性组合恰好相当于矩阵的某一列，在接收端根据这个结果来纠错，则会做出错误的纠正；假设这个线性组合的结果与矩阵中的任一列都不相当，则根据这个结果只能检测出中有错，而不能进行纠正。综上所述，一个（n,k)码要能纠正所有单个错，则由所有单个错误图样确定的均不相同且不等于。若要

11、能纠正个错误，显然要求个错的所有可能组合的错误模式都必须有不同的伴随式与之对应。4设计与仿真4.1 C语言平台简介C语言是Combined Language（组合语言）的中英混合简称。是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。各类科研都需要用到C语言，具体应用比如单片机以及嵌入式系统开发。其语言特点如下： （1）C是中级语言。它把高级语言的基本结构和语句与低级语言的实用性结合起来。C 语言可以像汇编语言一样对位、字节和地址进行操作， 而这三者是计算机最基本的工

12、作单元。 （2）C是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化。 （3）C语言功能齐全。具有各种各样的数据类型，并引入了指针概念，可使程序效率更高。另外C语言也具有强大的图形功能，支持多种显示器和驱动器。 （4）C语言适用范围大。适合于多种操作系统，如Windows、DOS、UNIX等等；也适用于多种机型。 （5）C语言对编写需要硬件进行操作的场合，明显优于其它解释型高

13、级语言，有一些大型应用软件也是用C语言编写的。 开始 结束编码函数解码函数 选择函数4.2整体流程图 图4.1 整体流程图 4.3编码流程图 初始化输入信息码C13并代 入编码方程 存储并输出编码结果 C27 返回 图4.2 编码流程图 4.4译码流程图 初始化输入接收到的码字R17输入生成矩阵G37，计算出监督矩阵H47其转置矩阵HT74计算出伴随式S4图4.3 译码流程图 S4=0000 S4=HT74的 第i行接收端认为传输有错，但不能纠正错误图样E7=接收端认为传输无错输出译码结果R2i=R1i+Ei 返回接收端认为传输中有一个错误，此时错误图样Ei=1 5 仿真结果及分析(1) 初始

14、化界面设置 图5.1 初始化界面的设置 通过初始化界面，可以选择编码或者译码。（2） 编码的结果图5.2 输入信息码为111时的编码结果 图5.3 输入信息码为010和110时的编码结果 图5.4 输入信息码为101和011时的编码结果 三位信息码有八种情况，即000,001,010,011,100,101,110,111.通过编码程序的编码结果来看，与表1对比，发现编码结果与理论值相一致，表明程序正确。（3）输入信息码中有非二进制码是的处理结果 图5.5 输入信息码有错误时的提醒示意图(4) 译码的结果 图5.6 监督矩阵及转置矩阵的计算示意图 （5）正确译码时的运行结果图5.7 译码正确时

15、的示意图 （6） 运行错误时的结果 图5.8 运行有一个错误时的结果示意图图5.9 运行有两位错码时的结果示意图设计总结 此次课程设计主要针对线性分组码编码译码提出自己的设计方案，并利用C语言来实现自己的软件设计。设计中用到了很多计算机通信课程中学到的知识，例如：差错控制技术等。由于对所学概念掌握的不准确，原理不是很清晰，虽然条条框框的理论知识一大推，但由于没有经过实践的检验，当正式用时却不知道怎么用，更不知道该往哪用，从而导致在设计的过程中不能抓住重点，不清楚到底该怎么做，使得在设计过程中绕了许多弯路，做了许多的无用功。设计过程中查阅了大量的有关线性分组码编码与译码的书籍，巩固了以前所学过的

16、知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合的必要性，只有理论知识是远远不够的，它更多的只是用来应付考试，而当正真实际操作时却是困难重重，所以只有把所学的理论知识与实践相结合起来，并从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计过程中遇到的问题，可以说得是很多，例如刚开始时，对线性分组码的理解不是很透彻，不知道其编码与译码的方法；后来刚熟悉了原理，却因为对C语言知识掌握不扎实，编写不出来正确的程序，以致又花费了好多时间继续学习C语言 编程和上网查找相关资料，导致恶性循环，待编好程序时已费了很多功夫，这毕竟跟

17、平时的理论知识有着很大的关联，故在以后的学习中一定要稳扎稳打，深刻理解理论知识，为今后的实践性活动打下坚实的基础，以免到时又像这次一样再费周折；同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。总之，通过这次课程设计之后，我发现自己的不足之处还很多，我下去以后一定把以前所学过的知识重新温故。对我而言，知识上的收获重要，精神上的丰收更加可喜。让我知道了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰的后面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课程设计必将成为我人生旅途上一个非常美好的回忆！参考文献1 吴玲

18、达，李国辉，杨冰 等著. 计算机通信原理与技术M. 国防科技大 学出版，2003,32 潘新民 著. 计算机通信技术M. 电子工业出版社，2003,73 孙丽华 著. 信息论与纠错编码M. 电子工业出版社，2005,34 Proakis 著. 张力军 译. 数字通信（第四版）M. 电子工业出版社，2004,75 庞振平，韩松洋，崔树林 著. 计算机程序设计基础M.华南理工大学出版社， 2007,2致谢这次课程设计得以顺利完成，要感谢的人实在太多了。首先我要衷心感谢我的指导老师彭老师，您严谨的治学态度，开阔的思维，循循善诱的指导一直给我很大的帮助。在做课程设计的过程中遇到了很多困难。但是每次彭老

19、师都给我耐心的指导，我从中学到了很多知识。彭老师教学的态度和对学术一丝不苟的精神，是我一生要学习的榜样，这将对我以后的生活和学习产生积极的影响。同时我还要感谢在这次课程设计中给与我帮助的同学，是你们在我有困难时伸出援助之手，给我讲解，帮忙调试电路，正是你们的帮助与支持，我才能克服一个个困难，才能顺利地完成这次课程设计,谢谢你们。附录/*这是（7,3）线性分组码的编译码及验证程序*/#include#include#include/*函数声明*/void Begin();void Code();void Decoding();/*主函数*/main()printf(n这是（7,3）线性分组码的编

20、译码及验证的软件设计：n);printf(n);Begin();void Begin()char ch;fflush(stdin);printf( -n);printf(n);printf( - 输入c代表编码函数Code -);printf(n); printf(n);printf( - 输入d代表译码函数Decoding -);printf(n);printf(n);printf( -n);ch=getchar();if(ch=c)Code(); else if(ch=d)Decoding();void Code()int C13,C27;int i;printf(输入三位信息码:n);f

21、or(i=0;i3;i+)scanf( %d,&C1i);for(i=0;i3;i+)if(C1i!=0&C1i!=1)printf(输入的信息码有错，请检查后重新选择输入n); Begin();for(i=0;i3;i+)C2i=C1i;C23=C10+C12;C24=C10+C11+C12;C25=C10+C11;C26=C11+C12;for(i=0;i7;i+)if(C2i=2)C2i=0;else if(C2i=3)C2i=1;printf(编码结果为:n);for(i=0;i7;i+)printf( %d,C2i);printf(n);printf(_n); Begin();voi

22、d Decoding()int G37,P34,Q43,R17,HT73,R27,C3;int H47=0,S4=0,E7=0;int i,j,n,k,t=0;printf(n输入生成矩阵G:n);for(i=0;i3;i+)for(j=0;j7;j+)scanf( %d,&Gij);printf(n计算出矩阵P:n);for(i=0;i3;i+)for(j=3;j7;j+)Pij-3=Gij; for(i=0;i3;i+)for(j=0;j4;j+)printf(%20d,Pij);printf(n);printf(计算出矩阵Q:n);for(i=0;i3;i+)for(j=0;j4;j+)

23、Qji=Pij;for(i=0;i4;i+)for(j=0;j3;j+) printf(%26d,Qij); printf( );printf(n);printf(计算监督矩阵H:n);for(i=0;i4;i+)for(j=0;j3;j+)Hij=Qij;for(i=0;i4;i+)j=3;Hii+j=1;for(i=0;i4;i+)for(j=0;j7;j+)printf(%11d,Hij);printf( );printf(n);printf(计算H的转置矩阵HT:n);for(i=0;i4;i+)for(j=0;j7;j+)HTji=Hij;for(i=0;i7;i+)for(j=0;

24、j4;j+)printf(%20d,HTij);printf(n);printf(输入接收到的码字R1:n);for(i=0;i7;i+)scanf( %d,&R1i);printf(计算伴随式S:n);for(i=0;i4;i+)for(j=0;j7;j+)Si=Si+R1j*HTji;for(i=0;i4;i+)if(Si%2=0)Si=0;else if(Si%2=1)Si=1;for(i=0;i4;i+)printf(%2d,Si);printf(n_n);for(i=0;i4;i+)t=t+Si;/*当S=0时，接收端认为传输无错。但是实际上，也可能存在多个错误，把此事的错误成为不可

25、就错误。*/if(t=0)printf(接收端认为接受的码字R1无错，此时错误图样E为:);for(i=0;i7;i+)printf(%2d,Ei);for(i=0;i7;i+)R2i=R1i+Ei;if(R2i=2)R2i=0;for(i=0;i3;i+)Ci=R2i; printf(n译码结果C为:n);for(i=0;i3;i+)printf(%2d,Ci);printf(n_n);if(t!=0)for(k=0;k7;k+)for(j=0,n=0;j4;j+)if(Sj=HTkj)n+;/*S=HT中的某一行时，有一个错误或者多个错误。若是一个错误，系统可以正确纠正，若是多个错误，按此

26、方法纠错，会做出错误纠正。*/ while(n=4) Ek=1; printf(此时接受的码字有一个错误，错误图样E为:n); for(i=0;i7;i+) printf(%2d,Ei); for(i=0;i7;i+) R2i=R1i+Ei; if(R2i=2)R2i=0;for(i=0;i3;i+)Ci=R2i; printf(n译码结果C为:n); for(i=0;i3;i+) printf(%2d,Ci); printf(n_n);Begin(); break; /*S!=HT中的任意一行时，系统只能检错不能纠错。*/ while(k=7) printf(n此时接收到的码字有错，但不能确定错误图样。n); printf(n_n);Begin(); break;