课程设计（论文）-基于C语言的线性分组码编译器设计.doc

《课程设计（论文）-基于C语言的线性分组码编译器设计.doc》由会员分享，可在线阅读，更多相关《课程设计（论文）-基于C语言的线性分组码编译器设计.doc（23页珍藏版）》请在三一文库上搜索。

1、摘要 本文是应用C语言对（7,3）线性分组码的编译码的软件设计。主要做了以下几项工作：对三位正确的信息码进行编码；若输入的三位信息码有错，系统输出提醒，可以重新输入；对七位接收到的码字判断是否有错，并在无错和有一位错误时进行译码，在有多位错误时输出提醒，可以选择重新输入。关键字：线性分组码，编码，译码，C语言21目录一线性分组码的基本概念11.线性分组码12.码重（汉明重量）13.码距（汉明距离）14.最小码距与码的抗干扰能力之间的关系15.主要性质2二编码原理2三译码原理31.译码原理简述32.监督矩阵的计算33.伴随式的计算4四编译码的软件实现51.C语言平台简介52.C语言实现编译码的思

2、想53.整体流程图64.编码流程图65.译码流程图76.基于C语言程序的设计87.运行及结果分析8总结13附录：参考程序14参考文献21一线性分组码的基本概念1.线性分组码 线性分组码是一组固定长度的码组，可表示为（n,k），通常它用于前向纠错。在分组码中，监督位被加到信息位之后，形成新的码。在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。当分组码的信息码元与监督码元之间的关系为线性关系时，这种分组码就称为线性分组码。 对于长度为n的二进制线性分组码，它有种可能的码组，从种码组中，可以选择个码组（kn）组成一种码，称为许用码组。这样，一个k比特信息的线性分组码

3、可以映射到一个长度为n码组上，该码组是从个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。2.码重（汉明重量） 把码组中非零位的数量定义为码重。3.码距（汉明距离） 两个码组对应位上数字不同的个数称为码组的距离，简称码距。原则是，让选择的这些码字的码距越长越好。 码组集合中全体码组之间距离中最小的数值称为该码组集合的最小码距。对于线性分组码来说最小码距等于他的最小重量。4.最小码距与码的抗干扰能力之间的关系 通过证明（不给出详细的证明过程），可以得到如下的结论，具体如下： （1）为了检测e个错误，要求最小码距。 （2）为了纠正t个错误，要求最小码距。 （3）为了纠正t

4、个错误，同时检测e个错误，要求最小码距。 最小码距是线性分组码重要的参数，它反映了线性分组码的抗干扰能力。5.主要性质（1）封闭性：任意两个码组之和仍为一许用码组；（2）有零元：即全零码；（3）结合律，交换律成立。二编码原理 已知线性分组码的生成矩阵因为 （1） 所以，由（1）式可以得到编码方程组： （2） （7，3）线性分组码有三位信息码，四位监督码。三位二进制信息码可能的八种情况：000，001，010，011，100，101，110，111。将信息码代入以上方程组（2），即可得到监督码，在信息码后面附加上监督码就可得到许用码组，许用码组也就是编码结果，是通过这样的计算从个码组中挑选出来的

5、可用的码组，其余的个码组称为禁用码组。对于不同的生成矩阵可以得到不同编码方程，也就可以得到不同的的许用码组，任意两个许用码组之和仍为一个许用码组。通过这条性质，可以检验我们计算出的许用码组的理论值是否正确。信息码、监督码、许用码组之间的对照关系如下表1所示， 由下表既得编码结果的理论值。 表1 信息码、监督码、许用码组对照表信息码C6C5C4监督码C3C2C1C0许用码组0000000000000000111010011101010011101001110111010011101010011101001110101001110100111101001110100111101001110100

6、三译码原理1.译码原理简述 为了描述数据在传输信道中出现差错的情况，引入错误图样的概念。 错误图样：接受序列与发送序列之间的差，用E表示。在错误图样中，0表示对应为没有错误，1表示传输有错。 可见，在译码中，只要设法从接收到的码字R中找到错误图样E，就可恢复发送端发送的码字C，C=R-E，因此，译码的任务就是要找到错误图样E。 首先，假定（7,3）线性分组码中，发送的码字，接收的码字，错误图样。若，说明与不同，传输过程中发生了错误。 所以译码的关键在于找到错误图样E。2.监督矩阵的计算 已知生成矩阵 （3）其中是k阶单位方阵，这里， （4） 监督矩阵 （5） （6）因为 （7）所以由（4）式可

7、得： （8）因此由（5）、（6）、（8）式可得监督矩阵为 （9）3.伴随式的计算 定义：其中；在（7,3）线性分组码中，。因为成立。所以，伴随式。 （1）如果接收的码字与发送的码字相同，就是传输中没有差错，此时，错误图样,。 （2）如果接收的码字有一位错误，就有，这时，S等于H的某一列，也就是其转置矩阵的某一行。 （3）如果接收到的码字有两个或多个错误时，S与举证的任意一行都不相等。四编译码的软件实现1.C语言平台简介 C语言是Combined Language（组合语言）的中英混合简称。是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它可以作为工作系统设计语言，编写系

8、统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。各类科研都需要用到C语言，具体应用比如单片机以及嵌入式系统开发。其语言特点如下： （1）C是中级语言。它把高级语言的基本结构和语句与低级语言的实用性结合起来。C 语言可以像汇编语言一样对位、字节和地址进行操作， 而这三者是计算机最基本的工作单元。 （2）C是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化

9、。 （3）C语言功能齐全。具有各种各样的数据类型，并引入了指针概念，可使程序效率更高。另外C语言也具有强大的图形功能，支持多种显示器和驱动器。 （4）C语言适用范围大。适合于多种操作系统，如Windows、DOS、UNIX等等；也适用于多种机型。 （5）C语言对编写需要硬件进行操作的场合，明显优于其它解释型高级语言，有一些大型应用软件也是用C语言编写的。 2.C语言实现编译码的思想（n,k）线性分组码原理就是对k位信息码进行编码，产生n-k位的监督码，监督码与信息码之间呈线性关系，使得k位信息码后附带着n-k位的监督码，从而减少传输过程中的差错。编码思想如下： （1）根据给定的生成矩阵G，求得

10、监督码与信息码之间呈线性关系即编码方程。 （2）输入信息码，代入上述编码方程中，得到各监督码。 （3）监督码附带在信息码之后，一起输出，即得到编码结果。 对于（7,3）线性分组码来说，译码思想如下： （1）根据生成矩阵计算出监督矩阵H，由H计算出伴随式S。 （2）如果S=0,0,0,0，R1无错。 （3）如果S与H的转置矩阵的某一行相等，则有一个错误，找到相应的错误图样E，则正确的接收到的码字R2=R1+E（二进制异或）。 （4）译出的码为R2的前3位。 （5）如果S不等于H转置的任意一行，则有两个或多个错误，不能得到正确的译码结果。开始3.整体流程图选择函数编码函数译码函数结束 图1 整体流

11、程图4.编码流程图 初始化输入信息码C13并代入编码方程储存并输出编码结果C27返回 图2 编码流程图初始化5.译码流程图输入接收到的码字R17输入生成矩阵G37，计算出监督矩阵H47其转置矩阵HT74计算出伴随式S4S4=0,0,0,0是否S4等于HT74的第i行接收端认为传输无错是否错误图样E7=0,0,0,0,0,0,0接收端认为传输有错，但不能纠正接收端认为传输中有一个错误，此时错误图样Ei=1输出译码结果R2i=R1i+Ei返回 图3 译码流程图6.基于C语言程序的设计 就（7，3）线性分组码的编码与译码程序如附录所示：7.运行及结果分析（1）初始化界面的设计图4 初始化界面图 通过

12、初始化界面，可以选择编码或译码函数。（2）正确编码的运行结果 只运行编码函数，可得编码结果如下：图5 输入信息码为000时的译码结果示意图图6 输入信息码为001和010时的译码示意图图7 输入信息码为011和100时的译码示意图图8 输入信息码为101和110时的译码结果示意图 图9 输入信息码为111时的译码结果示意图 三位信息码C6C5C4可以有八种可能的情况，即000，001，010，011，100，101,110,111。 通过编码部分程序可以得到的编码结果如上图所示。观察编码结果，与表1对照，运行程序所得的值与理论值完全相同，程序正确。（3）输入的码中有非二进制码时的处理结果 图1

13、0 输入信息码有错时的提醒示意图（4）由生成矩阵计算出监督矩阵H及其转置矩阵HT：图11 监督矩阵及其转置矩阵的计算示意图 由输入的生成矩阵G，得到监督矩阵H并计算其转置矩阵HT，方法见译码原理。（5）正确译码的运行结果（由于图太多所以下面每种情况只举一个例子） 图12 正确译码结果示例示意图（6）接收的码字有一位错时（8个许用码组每个码组有一位错码的情况有8种，所以接收到的码字有一位错码时共有64种情况。下图为其中一例。） 图13 接收到的码字有一位错码示例示意图（7）接收的码字有两位错码（下图为其中一例）图14 接收的码字有两位错示例示意图总结这次课程设计历时二个星期多左右，通过这两个星期

14、的学习，发现了自己的很多不足，自己知识的很多漏洞，看到了自己的实践经验还是比较缺乏，理论联系实际的能力还急需提高。课程设计是培养我们综合运用所学知识，发现、提出、分析和解决实际问题，锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。此次课程设计主要针对线性分组码编码译码提出自己的设计方案，并利用C语言来实现自己的软件设计。设计中用到了很多计算机通信课程中学到的知识，例如：差错控制技术等。由于对所学概念掌握的不准确，原理不是很清晰，虽然条条框框的理论知识一大推，但由于没有经过实践的检验，当正式用时却不知道怎么用，更不知道该往哪用，从而导致在设计的过程中不能抓住重点，不清楚到底该怎

15、么做，使得在设计过程中绕了许多弯路，做了许多的无用功。设计过程中查阅了大量的有关线性分组码编码与译码的书籍，巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合的必要性，只有理论知识是远远不够的，它更多的只是用来应付考试，而当正真实际操作时却是困难重重，所以只有把所学的理论知识与实践相结合起来，并从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计过程中遇到的问题，可以说得是很多，例如刚开始时，对线性分组码的理解不是很透彻，不知道其编码与译码的方法；后来刚熟悉了原理，却因为对C语言知识掌握不扎实，编写不

16、出来正确的程序，以致又花费了好多时间继续学习C语言 编程和上网查找相关资料，导致恶性循环，待编好程序时已费了很多功夫，这毕竟跟平时的理论知识有着很大的关联，故在以后的学习中一定要稳扎稳打，深刻理解理论知识，为今后的实践性活动打下坚实的基础，以免到时又像这次一样再费周折；同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。总之，通过这次课程设计之后，我发现自己的不足之处还很多，我下去以后一定把以前所学过的知识重新温故。对我而言，知识上的收获重要，精神上的丰收更加可喜。让我知道了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰的后

17、面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课程设计必将成为我人生旅途上一个非常美好的回忆！衷心的向各位老师致以崇高的敬意，谢谢老师！附录：参考程序/*这是（7,3）线性分组码的编译码及验证程序*/#include#include#include/*函数声明*/void Begin();void Code();void Decoding();/*主函数*/main()printf(n这是（7,3）线性分组码的编译码及验证的软件设计：n);printf(n);Begin();void Begin()char ch;fflush(stdin);printf( -n);printf

18、(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);for(i=0;i3;i+)scanf( %d,&C1i);for(i=0;i3;i+)if(C1i!=0&C1i!=1)printf(输入的信息码有错，请检查后重新选择

19、输入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();void Decoding()int G37,P34,Q43,R17,HT73,R27,C3;int H47=0,S4=0,E7=0;int i,j,n,k,t=0;prin

20、tf(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+)Qji=Pij;for(i=0;i4;i+)for(j=0;j3;j+) printf(%26d,Qij); printf( );printf(n);printf(计算

21、监督矩阵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;j4;j+)printf(%20d,HTij);printf(n);printf(输入接收到的码字R1:n);for(i=0;i7;i+)scanf( %d,&R1i)

22、;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时，接收端认为传输无错。但是实际上，也可能存在多个错误，把此事的错误成为不可就错误。*/if(t=0)printf(接收端认为接受的码字R1无错，此时错误图样E为:);for(i=0;i7;i+)printf(%2d,Ei);for(i=0;i

23、7;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中的某一行时，有一个错误或者多个错误。若是一个错误，系统可以正确纠正，若是多个错误，按此方法纠错，会做出错误纠正。*/ while(n=4) Ek=1; printf(此时接受的码字有一个错误，错误图样E为:n); for(i=0;i7;i+) print

24、f(%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;参考文献1 潘新民 著. 计算机通信技术M. 电子工业出版社. 2007，8.2 樊昌信 著. 通信原理M. 国防工业出版社. 1999，10.3 孙丽华 著. 信息论与纠错编码M. 电子工业出版社. 2005，3. 4 谭浩强 著. C程序设计（第二版）. 清华大学出版社.1999，12.5 王连相 著. C/C+程序设计教程. 中国铁道出版社.2006，8.