线性分组码的编译码软件设计

1、摘 要线性分组码一种重要的差错控制编码，它编码与译码电路比较简单，纠错能力也较强，是实际应用中比较流行的差错控制编码方法之一。本文以（7,3）线性分组码为例，在设计中已给定生成矩阵G，针对(7,3)线性分组码，运用C语言编译软件，实现了对输入序列的编码、译码以及对输入接收码组的查错和纠错，该软件程序系统简单易懂，实用性强，不失为一个满足实际需求和课设要求的系统。关键词：差错控制，线性分组码，编译码；前言随着社会经济的迅速发展和科学技术的全面进步，计算机事业的飞速发展，以计算机与通信技术为基础的信息系统正处于蓬勃发展的时期，随着经济文化水平的显著提高，人们对生活质量及工作软件的要求也越来越高。计

2、算机通信是一种以数据通信形式出现，在计算机与计算机之间或计算机与终端设备之间进行信息传递的方式。它是现代计算机技术与通信技术相融合的产物，在军队指挥自动化系统、武器控制系统、信息处理系统、决策分析系统、情报检索系统以及办公自动化系统等领域得到了广泛应用。计算机通信系统是经典的数字通信系统，它是计算机技术和通信技术结合的产物，一方面通信网络为计算机之间的数据传递和交换提供必要的设施和手段；另一方面，数字计算机技术的发展渗透到通信技术中，又提高了通信网络的各种性能，二者相互渗透、互相促进、共同发展。由于计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，数字信号在传

3、输中往往由于各种原因，使得在传送的数据流中产生误码，从而使接收端产生图象跳跃、不连续、出现马赛克等现象，人们对数据传输和存储系统的可靠性提出来了越来越高的要求，经过长时间的努力，通过编译码来控制差错、提高可靠性的方式在信道传输中得到了大量的使用和发展，并形成了一门新的技术叫做纠错编码技术，纠错编码按其码字结构形式和对信息序列处理方式的不同分为两大类：分组码和卷积码，本课程设计主要针对一个包含二进制序列的文档中的数据进行（7,3）线性分组码的编译码，并借助C语言软件，通过编写源程序文件，运行后对系统进行结果分析分析。目录第一章 设计目标1第二章 线性分组码的基本原理12.1 差错控制技术概述12

4、.2 差错控制原理22.3 线性分组码32.4 线性分组码的纠检错能力3第三章 (7,3）线性分组码的编码43.1（7,3）线性分组码的生成矩阵43.2（7,3）线性分组码的监督矩阵5第四章 （7,3）线性分组码的译码64.1 校正子与错误图样64.2线性分组码C语言程序代码74.3线性分组码编译码流程框图114.4 运行结果分析14第五章 C语言软件简介165.1 C语言软件概述165.2 C语言软件的特点165.3 C语言软件的优点17总结17参考文献18第一章 设计目标计算机通信是一种以数据通信形式出现，在计算机与计算机之间或计算机与终端设备之间进行信息传递的方式。它是现代计算机技术与通

5、信技术相融合的产物，在军队指挥自动化系统、武器控制系统、信息处理系统、决策分析系统、情报检索系统以及办公自动化系统等领域得到了广泛应用。随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计工作者所面临的重要课题，线性分组码是差错控制编码的重要一种，线性分组码的编码与译码电路比较简单，纠错能力也较强，是实际应用中比较流行的差错控制编码方法之一。在本次课程设计中，要设计一个（7，3）线性分组码的编译码程序，最基本的是要具备对输入的信息码进行

6、编码，让它具有抗干扰的能力，同时，还要让它具有对接收到的整个码组中提取信息码组的功能，但是，在实际的通信系统中，由于信道传输特性不理想以及加性噪声的影响，接收到的信息中不可避免地会发生错误，影响通信系统的传输可靠性，因而，本设计还要让该程序具有纠正错误的能力，当接收到的码组中有一位码，发生错误时可以检测到这一位错码，并且可以纠正这一位错码，并且让系统从纠正后的码组中提取正确的信息码组，针对给定的矩阵，完成如下的工作：1 完成对任意信息序列的编码2 根据生成矩阵，形成监督矩阵3 根据得到的监督矩阵，得到伴随式，并根据它进行译4 验证工作的正确性第二章 线性分组码的基本原理2.1 差错控制技术概述

7、数字信号在传输过程中，由于受到干扰的影响，码元波形将变坏，接收端收到后可能发生错误判决，由乘性干扰引起的码间串扰，一般采用均衡的办法纠正。加性干扰的影响一般从合理选择调制制度解调方法以及发送功率等方面考虑，使加性干扰不足以影响达到误码率要求。在仍不能满足要求时，为减少错误、提高通信质量还采用检错、纠错技术，即差错控制措施。差错控制的主要方法是将数据以某种形式编码。差错控制的核心为：抗干扰编码，简称差错控制编码。差错控制编码分为检错码、纠错码两大类。它在码元间建立了某种数学约束关系，并且对特定的信道总存在某种纠错编码信号以实现最小的能量或最小的带宽或最小的时间代价获得最小的数据传输差错。对于不同

8、信道，采用不同类型的差错控制技术。差错控制技术主要有：1) 检错重发：在发送码元序列中加入差错控制码元，接收端利用这些码元检测到有错码时，利用反向信道通知发送端，要求发送端重发，知道正确接收为止。2) 前向纠错：前向纠错是利用接收端在发送码元序列中加入的差错控制码元，不但能够发现错码，还能够将错码恢复其正确值。3) 反馈校验：不需要在发送序列中加入差错控制码元，接收端接收到的码元原封不动的转发会发送端。在发送端将他和原发送码元逐一比较，若发现有不同，就认为接收端接受的序列有错码，发送端立即从发。4) 检错删除：在接收端发现错码后，立即将其删除，不要求重发。这种方法只适合在少数特定系统中，在那里

9、发送码元有大量的多余度，删除部分接收码元不影响应用。2.2 差错控制原理将信息码分组，并为每个信息组附加若干监督的编码，称为“分组码”。在分组码中，监督码元仅监督本组码中的信息码元。分组码一般用符号（n）、（k）表示，其中k是每组码二进制信息码元的数目。n是码组的总位数，又称为码组的长度。r=n-k为每个码组中的监督码元数目，或称监督位数目。k位二进制数构成的码组集合为种不同的码组，若组都为有用码组，其中任意码组出现错误都将变成另一码组，则接收端无法检测识别哪一组出错。若只取部分码组为有用码组，则在传输过程中如接收端接收到的码组为非许用码组即禁用码组时，则可知传输错误。以3位二进制数构成的码组

10、为例，它共有8种不同的可能组合，若将其全部用来表示天气，则可以表示8种不同天气，例如：000晴、001云、010阴、011雨、100雪、101霜、110雾、111雹。其中任一码组在传输中若发生一个或多个错误，则将变成另一个信息码组。这时接收端无法发现错误。若在上述8种码组中秩序使用4种来传达天气，例如：000晴、011云、101阴、110雨。这时，虽然只能传达4种不同的天气，但是接收端却可能发现码组中的一个错码。如000错码一位，则接受码组将变成100或010或011.这三种码组都为禁用码组，故接收端认为接收码错误。要想能够纠正错误，需增加冗余度。2.3 线性分组码线性分组码是一类奇偶校验码，

11、它可以由（n，k）形式表示，编码器将一个k比特信息分组（信息矢量）转变为一个更长的由给定元素符号集组成的n比特编码分组，当这个符号集包含两个元素（0和1），与二进制相对，称为二进制编码。 分组码是对每段k 位长的信息组，以一定规则增加r = n - k个检验元，组成长为n的序列：，称这个序列为码字。在二进制情况下，信息组总共有个( q 进制为个) ，因此通过编码器后，相应的码字也有个，称这个码字集合为( n , k) 分组码。n长序列的可能排列总共有种。称被选取的个 n重为许用码组，其余个为禁用码组，称R = k / n为码率。那么对于（7，3）码即为用7位长的序列表示3位信息码，7位长序列的

12、可能排列总共有个。许用码组有个，其余个禁用码组，码率为R=3/7=42.86%。对于长度为n的二进制分组码，可以表示成（n，k），通常用于前向纠错。在分组码中，监督位加到信息位之后，形成新码，在编码中，k个信息位，被编为n位长度，（n-k）个监督码的作用是实现检错和纠错。2.4 线性分组码的纠检错能力在分组码中，我们把码组C中非零分量（对二进制来说，即1分量）的数目定义为码组C的汉明重量。两个码组对应位上数字不同的个数称为码组的距离，简称码距，也称汉明距离。对（n，k）线性码来说，个码字中所有可能码字之间的汉明距离中最小的距离称为该码的最小汉明距离，用dmin表示。而对于线性分组码来说，线性分

13、组码的最小距离等于它的最小重量。一个线性分组码码的最小距离dmin和码的抗干扰能力有如下关系：1) 若要检测m个错码，要求最小距离dminm+12) 若要纠正t个错码，要求最小距离dmin2t+13) 若要纠正t个错码同时检测m个（m>t）错码，要求码的最小距离dminm+t+1由上可知，一个（n,k）线性分组码有两个重要参数。一个是它的最小距离dmin，它反映了码的抗干扰能力，dmin越大，码的纠错或检错能力越强；另一个是码率R=k/n，它表示信息位在码组中所占的比重，R越大，说明信息位占的比重越高，故码的有效性越高。显然，我们希望构造一个R高且dmin大的码，但实际上这两者是矛盾的。

14、编码的主要任务就是如何找到一种方法，在满足一定R的条件下，使dmin尽可能地大。在此选择在课堂上涉及到的（7,3）线性分组码进行编程，完成对任意信息序列的编码。第三章 (7,3）线性分组码的编码3.1（7,3）线性分组码的生成矩阵选用码组的信息组为，码字为。当已知信息组时，按以下规则得到四个校验元，即 (1)这组方程称为校验方程。 （7,3）码有许用码组有个，其余个禁用码组，码率为R=3/7=42.86%。发送方发送的是许用码字，若接收方收到的是禁用码字，则说明传输中发生了错误。为了深化对线性分组码的理论分析，可将其与线性空间联系起来。由于每个码字都是一个二进制的n重，即二进制n维线性空间中的

15、一个矢量，因此码字又称为码矢。线性分组码的一个重要参数是码率R=k/n,它说明在一个码字中信息位所占的比重，R越大，说明信息位所占比重越大，码的传输信息的有效性越高。由于(n,k)线性分组，线性分组码的个码字组成了n维线性空间的一个k维子空间。因此这个码字完全可由k个线性无关的矢量所组成。设此k个矢量为，有生成矩阵形式为： (2)(n,k)码字中的任一码字均可由这组基底的线性组合生成，即： Ci=CnCn-1Cn-2Cn-k·G (3)上式中CnCn-1Cn-2Cn-k是k个信息元组成的信息组。表3-1 按上式编出的（7，3）码信息组码字00000000000010010011010

16、010011001101101011001001100101101111111011010101111111001对于表3-1给出的（7,3）线性分组码，可将其写成矩阵形式：（4）其中，（7,3）线性分组码的生成矩阵为（5）3.2（7,3）线性分组码的监督矩阵（7,3）线性分组码的四个校验元由式（1）所示的线性方程组决定的，把（1）式移相有：（6）上式的矩阵形式为：（7）这里的四行七列矩阵称为（7,3）线性分组码的一致监督矩阵（一致校验矩阵），用H表示，即：（8）第四章 （7,3）线性分组码的译码译码器的功能按系统设计要求分为检错译码和纠错译码两种，对于纠错译码，其工作又分为译码成功和译码失败

17、两种状态。译码成功是只译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字。译码失败是指译码器不能输出一个确切的码字，通常此时的译码器输出y与检错译码输出相同。4.1 校正子与错误图样假设接收端收到的码字为R，那么它和原来发送端发送的码字C之间就有可能存在着误差。即在码组C=C6C5C4C3C2C1C0中的任意一位就有可能出错。这样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要表达的意思。为了描述数据在传输信道中出现错误的情况，引入了错误图样E，在错误图样中，0代表对应位没有传错，1代表传输错误。实际上错误图样E就是收序列与发送序列的差。所以在译码中用接收到的码字R模二加错

18、误图样E就可以得到发送端的正确码字C。因此译码的过程就是要找到错误图样E。定义：校正子 S=CHT=(R+E)HT=RHT+EHT=EHT （9）因为C是编得的正确码字，根据前面所叙述，它和监督矩阵的转置相乘为0。显然，S仅与错误图样有关，它们之间是一一对应的关系。找到了校正子S，也就可以找到E。而与发送的码字无关。若E=0，则S=0；因此根据S是否为0可进行码字的检错。如果接收码字R中只有一位码元发生错误，又设错误在第i位。即,其他的均为0。在后面的译码程序中，建立了一个校正子S与错误图样E对应的表。也就是收到一个R序列，就可以通过计算得到一个校正子，而每一个校正子都对应着一个错误图样E，再

19、通过R模尔加上E，就可以得到正确的码字C。因为在不同的错误序列R中，同一位码元错误时对应的E是一样的，所以可以利用0000000这个正确的码字让它每位依次错误，来求得它的八个校正子。而这时的矩阵R就是错误图样E。这样就算得了8个校正子S。而这时的错误序列R，就是错误图样E，所以有： E与S都已经得到，这时就可以建立一个表来将它们一一对应起来了。H矩阵与(n,k)码的任何一个许用码字进行相乘的结果必等于0。若不属于许用码字，或有传输差错，且差错位数在(n,k)码纠错能力内，则运算结果将为非0值，此时，可以纠错或检错重发，校正子和错码位置的关系如下：表4-1校正子和错码的位置关系S1S2S3错码位

20、置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码4.2线性分组码C语言程序代码#include "stdio.h"#include "conio.h"#include "stdlib.h"main()int i,j,k,u,m,n,r,B=0,p,t;int Input100,h10=0,g10=0;int a1010,b1010,s1010,R1010;int G37=1,0,0,1,1,1,0,0,1,0,0,1,1,1,0,0,1,1,1,0,1;int H47=1,0,1

21、,1,0,0,0,1,1,1,0,1,0,0,1,1,0,0,0,1,0,0,1,1,0,0,0,1;int M74=1,1,1,0,0,1,1,1,1,1,0,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1;/生成矩阵Gprintf("给定的生成矩阵G:n");for(i=0;i<3;i+)for(j=0;j<7;j+)printf("%3d",Gij);printf("n");/监督矩阵Hprintf("由此可得监督矩阵H:n");for(i=0;i<4;i+)for(j=

22、0;j<7;j+)printf("%3d",Hij);printf("n");/监督矩阵的转置矩阵Mprintf("监督矩阵的转置矩阵M:n");for(i=0;i<7;i+)for(j=0;j<4;j+)printf("%3d",Mij);printf("n");/编码部分printf("请输入信息码,以数字2作为结束!n");for(i=0;i+)scanf("%d",&Inputi);if(Inputi=2)break;u=

23、i;p=u%3;switch (p)case 0:u=u/3;printf("共输入%d位，补0位!n",u*3);break;case 1:Inputi=0;Inputi+1=0;u=i+2;u=u/3;printf("共输入%d位，补两位!n",u*3-2);break;default:Inputi=0;u=i+1;u=u/3;printf("共输入%d位，补一位!n",u*3-1);break;i=0;for(m=0;m<u;m+)for(n=0;n<3;n+,i+)amn=Inputi;for(m=0;m<u

24、;m+)for(n=0;n<3;n+)printf("%3d",amn);printf("n");printf("编码矩阵:n");for(m=0;m<u;m+)for(r=0;r<7;r+)for(n=0;n<3;n+)B+=(amn*Gnr);if(B=2)B=0;if(B=3)B=1;bmr=B;B=0;for(m=0;m<u;m+)for(r=0;r<7;r+)printf("%3d",bmr);printf("n");/译码部分for(m=0;m&l

25、t;u;m+)for(i=0;i<4;i+)for(r=0;r<7;r+)B+=(bmr*Mri);if (B%2=0)B=0;else B=1;smi=B;B=0;printf("伴随式为:n");for(m=0;m<u;m+)for(i=0;i<4;i+)printf("%3d",smi);printf("n");printf("伴随式为0,因此没有误码!nn");printf("还原信息码:n");for(m=0;m<u;m+)for(r=0;r<3;r

26、+)printf("%3d",bmr);printf("n");printf("n");t=getch();printf("*验证部分!*n");t=1;while(t!=2)p=1;while(p)printf("请输入码组,每组位数为7的倍数,以2作为结束!n");for(i=0;i+)scanf("%d",&Inputi);if(Inputi=2)break;if(i%7=0)p=0;else p=1;printf("输入不是7的倍数!请重新输入!n&

27、quot;); u=i/7; i=0; for(m=0;m<u;m+)for(n=0;n<7;n+,i+)Rmn=Inputi;printf("您的输入为:n");for(m=0;m<u;m+)for(n=0;n<7;n+)printf("%3d",Rmn);printf("n");for(m=0;m<u;m+)for(i=0;i<4;i+)for(r=0;r<7;r+)B+=(Rmr*Mri);if (B%2=1)B=1;else B=0;smi=B;B=0;printf("伴随式

28、为:n");for(m=0;m<u;m+)for(i=0;i<4;i+)printf("%3d",smi);printf("n");r=0; p=0; B=0; j=0; k=0;for(m=0;m<u;m+)B=(sm0*1000)+(sm1*100)+(sm2*10)+(sm3); if(B=0)printf("第%d行正确!n",(m+1);else if(B=1110)r=0;printf("第%d行,第%d个有误!n",(m+1),(r+1);else if(B=111)r=1

29、;printf("第%d行,第%d个误!n",(m+1),(r+1);else if(B=1101)r=2;printf("第%d行,第%d个误!n",(m+1),(r+1);else if(B=1000)r=3;printf("第%d行,第%d个误!n",(m+1),(r+1);else if(B=100)r=4;printf("第%d行,第%d个误!n",(m+1),(r+1);else if(B=10)r=5;printf("第%d行,第%d个有误!n",(m+1),(r+1);else

30、if(B=1)r=6;printf("第%d行,第%d个有误!n",(m+1),(r+1);else printf("第%d行出错码数等于或大于2个!n",(m+1);p=1;if(B!=0&&p!=1)printf("修改后的编码n");Rmr+=1;if(Rmr=2)Rmr=0;for(k=0;k<7;k+)printf("%3d",Rmk);printf("n");printf("还原正确的信息码为:n");for(k=0;k<3;k+)pr

31、intf("%3d",Rmk);printf("n");B=0;printf("输入数字2结束验证! 按其他键继续验证!n");scanf("%d",&t);printf("n");4.3线性分组码编译码流程框图Y 开始输出G、H、T；输入信息码 p=0?补1位信息码amn =Inputi编码矩阵bmr= amn*Gnr校正子smi= bmr*Mrism=0?传输无误，还原信息码bmrY N N 输入信息码Inputiiu,u%3p p=1? p=2?补0位补2位N N Y 验证部分Y

32、i%7=0?输入InputiRmn =Inputismi=Rmr*MriY 输出伴随式SmB=(sm0*1000)+(sm1*100)+(sm2*10)+(sm3)B=0?B=111?B=1110?正确第一个有误第二个有误Y Y YN N N 验证部分N B=1101？B=10？B=100？B=1000？第三个有误第七个有误第六个有误第五个有误第四个有误B=1？出错大于1个t=2?修改后的编码Rmr还原的信息码返回YYYYYNNNNNNY4.4 运行结果分析图1 打开程序显示图打开程序时显示出给定的生成矩阵G，以及由此可得的监督矩阵H，并显示出监督矩阵的转置矩阵M。图2 自动编码译码显示图当输

33、入数组时，数组与生成矩阵G相乘可得编码矩阵。因为计算机运行没有传输干扰问题，因此编码矩阵即为理想的接受矩阵。接受矩阵与矩阵M相乘即可得出伴随式，伴随式为零可以得出接受无误，因此可以还原出输入的信息码。图3 验证部分显示图在许用码组中选出三组，将第一行第3个数修改为0，第三行第2个和第3个数修改为1。即输入作为接受矩阵，用以验证译码检错，纠错能力。因为已知最小海明距离为3，即能检查出两个错误以及能纠正一个错误。计算出伴随式，由第一行1 1 0 1与监督矩阵比较可知，此行伴随式与监督矩阵的第3列相同，因此可知第3位有误，从而实现检查出一位错误，并且同时纠正出一位错误。第二行伴随式0 0 0 0为零

34、，因此判断出此行接收码组无误。第三行伴随式1 0 1 0与监督矩阵的所有列都不同，因此无法纠错，程序用输入数字2作为结束标志。第五章 C语言软件简介5.1 C语言软件概述 C语言是Combined Language（组合语言）的中英混合简称。是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。因此，它的应用范围广泛，不仅仅是在软件开发上，而且各类科研都需要用到C语言，具体应用比如单片机以及嵌入式系统开发。5.2 C语言软件的特点 a) C是中级语言。它把高级语言的基本结

35、构和语句与低级语言的实用性结合起来。C 语言可以像汇编语言一样对位、字节和地址进行操作， 而这三者是计算机最基本的工作单元。b) C是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化。c) C语言功能齐全。具有各种各样的数据类型，并引入了指针概念，可使程序效率更高。另外C语言也具有强大的图形功能，支持多种显示器和驱动器。而且计算功能、逻辑判断功能也比较强大，可以实现决策目的的

36、游戏。d) C语言适用范围大。适合于多种操作系统，如Windows、DOS、UNIX等等；也适用于多种机型。e) C语言对编写需要硬件进行操作的场合，明显优于其它解释型高级语言，有一些大型应用软件也是用C语言编写的。f) C语言具有绘图能力强，可移植性，并具备很强的数据处理能力，因此适于编写系统软件，三维，二维图形和动画,它是数值计算的高级语言。5.3 C语言软件的优点 简洁紧凑、灵活方便，C语言一共只有32个关键字,9种控制语句，程序书写形式自由，主要用小写字母表示。它把高级语言的基本结构和语句与低级语言的实用性结合起来。 C 语言可以像汇编语言一样对位、字节和地址进行操作，而这三者是计算机最基本的工作单元。 a) 运算符丰富。C语言的运算符包含的范围很广泛，共有34种运算符。C语言把括号、赋值、强制类型装换等都作为运算符处理。从而使C语言的运算类型极其丰富，表达式类型多样化。灵活使用各种运算符可以实现在其它高级语言中难以实现的运算。b) 数据结构丰富。C语言的数据类型有：整型、实型、字符型、数组类型、指针类型、结构体类型、共用体类型等。能用来实现各种复杂的数据结构的运算。并引入了指针概念，使程序效率更高。另外C语言具有强大的图形功能，支持多种显示器和驱动器。且计算功能、逻辑判断功能强大。c) C是结构式语言。结构式语言的显著特点