(7,3)循环码编译码软件设计

1、 摘要 本课程设计介绍了（7，3）循环码的编译与译码原理，用C语言编程实现其编码与译码功能。通过C语言平台运用所编写的程序，输入任意的数字信息序列，得出了编码结果。着重在无差错和部分差错的情况下进行了译码，并对译码结果进行分析。关键词:循环码、C语言、编译码目录一、计算机通信11.1通信的概念11.2计算机通信介绍1二、系统设计22.1循环码22.2 编码原理52.3译码原理62.4循环码译码的设计62.5纠错码7三、设计结果及分析93.1程序运行结果93.2运行结果理论分析113.3软件可行性分析12四、总结13参考文献14附：程序清单15一、计算机通信1.1通信的概念通信就是克服距离上的障

2、碍，从一地向另一地传递和交换消息。消息是信息源所产生的，是信息的物理表现，例如，语音、文字、数据、图形和图像等都是消息（Message）。消息由模拟消息（如语音、图像等）以及数字消息（如数据、文字等）之分。所有消息必须在转换成电信号（通常简称为信号）后才能在通信系统中传输。所以，信号（Signal）是传输消息的手段，信号是消息的物资载体。相应的信号可以分为模拟信号和数字信号，模拟信号的自变量可以是连续的或离散的，但幅度是连续的，如电话机、电视摄像机输出的信号就是模拟信号。数字信号的自变量可以是连续的或离散的，但幅度是离散的，如计算机等各种数字终端设备输出的信号就是数字信号。通信的目的是传送消息

3、，但对受信者有用的是消息中包含的有效内容，即信息（Information）。消息是具体的、表面的，而信息是抽象的、本质的，且消息中包含的信息的多少可以用信息量来度量。通信技术，特别是数字通信技术近年来发展非常迅速，它的应用越来越广泛。数字通信系统较模拟通信系统而言，具有抗干扰能力强、便于加密、易于实现集成化、便于与计算机连接等优点。因而，数字通信更能适应对通信技术的高要求。1.2计算机通信介绍计算机通信是一种以数据通信形式出现，在计算机与计算机之间或计算机与终端设备之间进行信息传递的方式。它是现代计算机技术与通信技术相融合的产物，在军队指挥自动化系统、武器控制系统、信息处理系统、决策分析系统、

4、情报检索系统以及办公自动化系统等领域得到了广泛应用。计算机通信按照传输连接方式的不同，可分为直接式和间接式两种。直接式是指将两部计算机直接相联进行通信，可以是点对点，也可以是多点通播。间接式是指通信双方必须通过交换网络进行传输。按照通信覆盖地域的广度，计算机通信通常分为局域式、城域式和广域式三类。局域式是指在一局部的地域范围内（例如一个机关、学校、军营等）建立计算机通信。局域计算机通信覆盖地区的直径在数公里以内。城域式是指在一个城市范围内所建立的计算机通信。城域计算机通信覆盖地区的直径在十公里到数十公里。广域式是指在一个广泛的地域范围内所建立的计算机通信。通信范围可以超越城市和国家，以至于全球

5、。广域计算机通信覆盖地区的直径一般在数十公里到数干公里乃至上万公里。在通常情况下，计算机通信都是由多台计算机通过通信线路连接成计算机通信网进行的，这样可共享网络资源，充分发挥计算机系统的效能。二、系统设计2.1循环码循环码是线性分组码的一种，所以它具有线性分组码的一般特性，此外还具有循环性。循环码的编码和解码设备都不太复杂，且检(纠)错能力强。它不但可以检测随机的错误，还可以检错突发的错误。（n,k）循环码可以检测长为n-k或更短的任何突发错误，包括首尾相接突发错误。循环码是一种无权码，循环码编排的特点是相邻两个数码之间符合卡诺图中的邻接条件，即相邻两个数码之间只有一位码元不同，码元就是组成数

6、码的单元。符合这个特点的有多种方案，但循环码只能是表中的那种。循环码的优点是没有瞬时错误，因为在数码变换过程中，在速度上会有快有慢，中间经过其它一些数码形式，称它们为瞬时错误。这在某些数字系统中是不允许的，为此希望相邻两个数码之间仅有一位码元不同，即满足邻接条件，这样就不会产生瞬时错误。循环码就是这样一种编码，它可以在卡诺图中依次循环得到。循环码又称格雷码（Grey Code）。2.1.1循环码的定义循环码既是采用循环移位特性界定的一类线性分组码，循环码是一种线性代数分组码，记为（n,k）码，其中n为码长，k为信息码元数。如果一个线性分组码的任意一个码字c（n元组）都是一个码字c的循环移位，那

7、么称此线性分组码为一个循环码。2.1.2循环码的特点若是一个码字，则它的循环移位也是一个码字。循环码是线性分组码的一种，所以它具有线性分组码的一般特性，此外还具有循环性。循环码的编码和解码设备都不太复杂，且检(纠)错能力强。它不但可以检测随机的错误，还可以检错突发的错误。（n,k）循环码可以检测长为n-k或更短的任何突发错误，包括首尾相接突发错误。 循环码是一种无权码，循环码编排的特点是相邻两个数码之间符合卡诺图中的邻接条件，即相邻两个数码之间只有一位码元不同，码元就是组成数码的单元。符合这个特点的有多种方案，但循环码只能是表中的那种。循环码的优点是没有瞬时错误，因为在数码变换过程中，在速度上

8、会有快有慢，中间经过其它一些数码形式，称它们为瞬时错误。这在某些数字系统中是不允许的，为此希望相邻两个数码之间仅有一位码元不同，即满足邻接条件，这样就不会产生瞬时错误。循环码就是这样一种编码，它可以在卡诺图中依次循环得到。循环码又称格雷码（ Grey Code ）。循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。若为一循环码组，、还是许用码组。也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码组。2.1.3循环码的多项式表示设码长为n的循环码表示为，其中为二进制数，通常把码组中各码元当做二进制的系数，即把上式中

9、长为n的各个分量看做多项式： (1) 的各项系数，则码字与码多项式一一对应，这种多项式中，x仅表示码元位置的标记,因此我们并不关心x的取值，这种多项式称为码多项式。我们用多项式来表示循环码的码字 （2） 也就是一个n长码字可以用一个次多项式来表示。它的循环特性，可由多模多项式来表示，例如左移一位，相当于乘x，应该指出，这里采用了模多项式运算。同样，左移两位相当于乘以等等。2.1.4（n,k）循环码的生成多项式一个（n,k）循环码，它共有个码字，从中取出其前面位的码字，以表示，它的次数为。则都是码字，且k个码字彼此独立，因此可以作为码的生成矩阵的k行。一经确定，码也就确定了，编码的问题也就解决了

10、。因此，我们称为码的生成多项式。生成矩阵可以表示如下 （3）循环码的优点是没有瞬时错误，因为在数码变换过程中，在速度上会有快有慢，中间经过其它一些数码形式，称它们为瞬时错误。这在某些数字系统中是不允许的，为此希望相邻两个数码之间仅有一位码元不同，即满足邻接条件，这样就不会产生瞬时错误。因此，循环码可以写成，为K位信息元矩阵。变换上式可得 得 （4） 式中，为信息码组多项式。由（2-4）可以看出，所有用生成的码字都是生成多项式的倍式。也就是说，凡是一个码字多项式一定能被除尽。反之，能被除尽的次数不大于（n-1）次的多项式，也一定是码多项式。由此可以得出循环码编码方法如下：首先将次数小于（k-1）

11、次的信息码组多项式乘以,得到，其次数 小于等于次。然后用生成多项式去除，得到除式为，它的次数小于的次数，把此余式的系数作为监督元附加在信息码组后面，就得到一个必能被除尽的多项式，且它必是一个码多项式，运算过程为： （5） （6）式中为商式，为余式，则码多项式为 （7）而余式可以写成 模 （8）且由于它是循环码，故必是的一个因式，也就是说，它必能被g(x)整除，即： 模 （9）式中，为次数次，的次数为k次。该结论可以这样来说明：如果表示一个码多项式，则它也是的一个倍式。因此可以写成 （10）而乘以x相当于一次循环移位，又因为 幂次 ，幂次所以能除尽，必能除尽。因此，我们可以说每个（n,k）循环码

12、都是由幂次为n-k可以除尽的因式产生的，反之可以说每个这样的因式可以产生一个（n,k）循环码。上述结论说明了能除尽的诸因式确定了所有长度为n的循环码。举例（7,3）循环码生成多项式，可以求得（7,3）循环码所有码字如表1所示表1 （7,3）循环码所有码字序号信息码循环码 序号信息码循环码 0 0000000000 4 1001001110 1 0010011101 5 1011010011 2 0100100111 6 1101101001 3 0110111010 7 1111110100 2.2 编码原理根据给定的（n，k ）值，再根据循环码生成定理对所给定信息位k，选定生成多项式g(x)

13、，所有码多项式c(x)都能被g(x)整除，且次数小于n- k。若已知 (11)并设信息元多项式 (12)要编码成系统循环码形式，即码字的最左边k位是信息元，其余n- k位是校验元，则要用乘以m(x)，再加上校验元多项式r(x),这样得到的码字多项式 (13)式（2-6）中。c(x)一定是g(x)的倍数，即有多项式 （14）或 （15）注意到为次多项式，而r(x)最多为n- k-1次多项式 （16）即必是除以的余式。上述过程指出了系统循环码的编码方法：（1）将信息组乘以变成，乘以的目的是将提高次。 （2）然后将得到的除以，得到商和余式，可知该余式 分子，即为校验多项式，从而得到码字多项式 (17

14、)2.3译码原理设发送的码字为C(x),接收到的码字为R(x),如果C(x)= R(x)，则说明收到的码字正确；如果C(x)R(x)，则说明收到的码字出现错误，则有： （18） 公式（2-11）中的E(x)称为错误图样。当E(x)=0时说明没有错误，用g(x)去除R(x)， = (19)因为是由生成的,故必能为除尽，显然与同余式，以除所得余式称为伴随式，。由式（2-12）可知， （20）若则；若，则。这说明,仅与错误图样有关，而与发送的码字无关,由此可以确定错误图样表。由于的次数为次，除后得到余式（即伴随式）的次数为次，故共有个表达式，每个可能的表达式对应一个错误格式，可以知道（15,7）循环

15、码的S(x)共有个表达式，可以根据错误图样表来纠正（7.3）循环码的一位错误。 系统循环码的译码方法：将收到的码字用去除，如果除尽则无错；否则有错。如果有错可由余式一一找出对应图样，然后将错误图样与模2相加，即为所求码字，从而实现纠错目的。2.4循环码译码的设计纠错码的译码是该编码能否得到实际应用的关键所在。译码器往往比编码较难实现，对于纠错能力强的纠错码更复杂。根据不同的纠错或检错目的，循环码译码器可分为用于纠错目的和用于检错目的的循环码译码器。通常，将接收到的循环码组进行除法运算，如果除尽，则说明正确传输；如果未除尽，则在寄存器中的内容就是错误图样，根据错误图样可以确定一种逻辑，来确定差错

16、的位置，从而达到纠错的目的。用于纠错目的的循环码的译码算法比较复杂，感兴趣的话可以参考一些参考书。而用于检错目的循环码，一般使用ARQ通信方式。检测过程也是将接受到的码组进行除法运算，如果除尽，则说明传输无误；如果未除尽，则表明传输出现差错，要求发送端重发。用于这种目的的循环码经常被成为循环冗余校验码，即CRC校验码。CRC校验码由于编码电路、检错电路简单且易于实现，因此得到广泛的应用。在通过MODEM传输文件的协议ZMODEM、XMODEM协议中均用到了CRC校验技术。在磁盘、光盘介质存储技术中也使用该方法。2.5纠错码纠错码(errorcorrectingcode)，在传输过程中发生错误后

17、能在收端自行发现或纠正的码。仅用来发现错误的码一般常称为检错码。为使一种码具有检错或纠错能力，须对原码字增加多余的码元，以扩大码字之间的差别，即把原码字按某种规则变成有一定剩余度（见信源编码）的码字，并使每个码字的码之间有一定的关系。关系的建立称为编码。码字到达收端后，可以根据编码规则是否满足以判定有无错误。当不能满足时，按一定规则确定错误所在位置并予以纠正。纠错并恢复原码字的过程称为译码。检错码与其他手段结合使用，可以纠错。纠错编码又称信道编码，它与信源编码是信息传输的两个方面。它们之间存在对偶的关系。应用信道译码直接对一些自然信息进行处理，可以去掉剩余度，以达到压缩数据的目的。为了使一种码

18、具有检错或纠错能力，必须对原码字增加多余的码元，以扩大码字之间的差别，使一个码字在一定数目内的码元上发生错误时，不致错成另一个码字。准确地说，即把原码字按某种规则变成有一定剩余度的码字，并使每个码字的码元间有一定的关系。关系的建立称为编码。码字到达收端后，用编码时所用的规则去检验。如果没有错误，则原规则一定满足，否则就不满足。由此可以根据编码规则是否满足以判定有无错误。当不能满足时，在可纠能力之内按一定的规则确定错误所在的位置，并予以纠正。纠错并恢复原码字的过程称为译码；码元间的关系为线性时，称为线性码；否则称为非线性码。检错码与其他手段结合使用，可以纠错。检错反馈重发系统（ARQ系统）就是一

19、例。在构造纠错码时，将输入信息分成k位一组以进行编码。若编出的校验位仅与本组的信息位有关，则称这样的码为分组码。若不仅与本组的k个信息位有关，而且与前若干组的信息位有关，则称为格码。这种码之所以称为格码，是因为用图形分析时它象篱笆或格架。线性格码在运算时为卷积运算，所以叫卷积码。2.5.1纠错原理纠错码能够检错或纠错，主要是靠码字之间有较大的差别。这可用码字之间的汉明距离d(x，y)来衡量。它的定义为码字x与y之间的对应位取不同值的码元个数。一种纠错码的最小距离d定义为该种码中任两个码字之间的距离的最小值。一种码要能发现e个错误,它的最小距离d应不小于e+1。若要能纠正t个错误，则d应不小于2

20、t+1。一个码字中非零码元的个数，称为此码字的汉明重量。一种码中非零码字的重量的最小值，称为该码的最小重量。对线性码来说，一种码的最小重量与其最小距离在数值上是相等的。在构造线性码时，数字上是从n维空间中选一k维子空间，且使此子空间内各非零码字的重量尽可能大。当构造循环码时,可进一步将每一码字看成一多项式,将整个码看成是多项式环中的理想,这一理想是主理想,故可由生成多项式决定；而多项式完全可由它的根规定。这样,就容易对码进行构造和分析。这是BCH码等循环码构造的出发点。一般地说，构造一种码时，均设法将它与某种代数结构相联系，以便对它进行描述，进而推导它的性质，估计它的性能和给出它的译码方法。若

21、一种码的码长为n，码字数为M,或信息位为h,以及最小距离为d，则可把此码记作n,M,d码。若此码为线性码，常简记作(n，k)或(n,k,d)码。人们还常用R=log2M/n表示码的信息率或简称码率,单位为比特/码元。R越大,则每个码元所携带的信息量越大，编码效率越高。纠错码实现中最复杂的部分是译码。它是纠错码能否应用的关键。根据式(1),采用的码长n越大,则误码率越小。但n越大，编译码设备也越复杂,且延迟也越大。人们希望找到的译码方法是:误码率随码长n的增加按指数规律下降;译码的复杂程度随码长n的增加接近线性地增加；译码的计算量则与码长n基本无关。可惜，已经找到的码能满足这样要求的很少。不过由

22、于大规模集成电路的发展，既使应用比较复杂的但性能良好的码，成本也并不太高。因此，纠错码的应用越来越广泛。纠错码传输的都是数字信号。这既可用硬件实现，也可用软件实现。前者主要用各种数字电路，主要是采用大规模集成电路。软件实现特别适合计算机通信网等场合。因为这时可以直接利用网中的计算机进行编码和译码，不需要另加专用设备。硬件实现的速度较高，比软件可快几个数量级。在传信率一定的情况下，如果采用纠错码提高可靠性，要求信道的传输率增加，带宽加大。因此，纠错码主要用于功率受限制而带宽较大的信道，如卫星、散射等系统中。纠错码还用在一些可靠性要求较高，但设备或器件的可靠性较差，而余量较大的场合，如磁带、磁盘和

23、半导体存储器等。三、设计结果及分析3.1程序运行结果3.1.1程序初始化界面 1.初始化界面 图1程序初始化界面3.1.2正确编码界面图2 正确编码界面图2输入的是111信息码，对其进行编译，编译结果如图2所示。3.1.3 无差错编码仿真结果图3 无差错编码仿真结果图对编译结果1110010进行无差错编码，编码结果如图3所示。3.1.4 部分差错编码图图4 部分差错编码图对编码结果1110010进行部分差错编码，结果显示s=0010，结果如图4所示。3.1.5离开界面图5 离开界面所有编译结束之后，按照菜单提示，输入相应的输入命令c、d、e进行输入。3.2运行结果理论分析 由循环码性质可知，（

24、7,3）循环码的最小码距d=4,可以检测出小于等于3位错误，纠正1位错误，编码效率为42.8%。传输正确概率为，信息传输错误概率为，每帧仅发生1位错误的概率为表2 模拟结果 0.521703 0.372009 71.30 0.0679347 0.0659036 97.01 0.00697903 0.0069581 99.70 0.00069979 0.00069958 99.97 0.000069979 0.00069958 99.97 表2为，的模拟结果，综合上表的模拟结果和理论结果可以看出，通信系统的帧传输具有以下性质：（1）在n一定的情况下，信息帧错误传输概率随着比特误码率的增加而增加，

25、最坏情况下帧错误概率几乎为100%，此时系统失去通信能力。（2）在典型的通信环境下（），当时， ，表明当比特误码率足够小时，绝大多数信息帧错误时每帧1位错误，因此纠正每帧错误有实用价值。3.3软件可行性分析由上述结果可知，该软件的操作方法为程序通过编译运行后，在C环境下，当输入c后按回车键，然后就会提示输入信息，当输入3位的信息位再按回车键，系统就会输出7位的循环编码。当输入d后按回车键，系统会进行译码的操作，当输入的译码信息和编码结果一样时，系统就会正确将信息位从该码组译出来。当输入的译码信息与编码的结果错一位码时，系统就会检测出该错误并将其纠正过来，从而译出真确的信息位。当输入e后按回车，

26、就会退出系统。信息多项式和余数多项式可以合并成一个新的多项式（称为循环码的码多项式），则该多项式是生成多项式的整数倍，即能被声称多项式整除。根据这一原理，在发送端用信息码多项式除以生成多项式所得的余数多项式就是所要加的监督位。由此可知，该系统能够实现（7，3）循环码的编码与在无差错和部分差错情况下的译码，因此该软件具有可行性。四、总结通过本次课程设计，我对循环码的编码和译码的基本原理有了较深的理解，学到了很多的知识。循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码。它有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现；同时循环码的性能也较好，具有较强

27、的检错和纠错能力。这两周中遇到了好多问题，由于以前学习C语言没有用心，编程的过程中出现了很多问题。例如，由于输入法的问题导致程序出现了错误。后来，通过同学的帮助，发现并改正了这个错误。最终实现了循环码编译码的软件设计。这次课程设计让我受益匪浅，让我理解了纠错码的原理和循环冗余码CRC的原理。真正地做到了输入任意的数字信息序列，得出编码结果。还学会了在无差错和部分差错的情况下进行译码。最后感谢老师对我们的精心指导和帮助，感谢同学们对我的帮助。参考文献1樊昌信著通信原理M 国防工业出版社 1999.102宋祖顺著现代通信原理M 电子工业出版社 2001.23黄新亚 米央编著 信息编码技术及其应运大

28、全M 电子工业出版社 1994.84孙丽华 谢仲华 陈荣伶编 信息论与纠错编码 北京 电子工业出版社 20055Proakis著 张力军 译 数字通信（第四版）M 电子工业出版社 2004.76潘新民著计算机通信技术M 电子工业出版社 2003.77吴伶达 李国辉 杨冰等著 计算机通信原理与技术M 国防科技大学出版社 2003.3附：程序清单/*(7,3)循环码的编译及纠检错*/#include#include #include/*函数声明*/void Begin();void Code();void Decoding();/*主函数*/void main() printf(n This so

29、ftware main function is carries on the code and the decoding to (7,3) cyclic code .n); Begin();/*进行编码*/void Code() int input3; int output7; int reg3=0, 0, 0; int temp,i,j,t; printf(Please input the information code :); for(i=0;i3;i+) scanf(%d,&input i); /*输入3位信息码*/ for(i=0;i3;i+) /*进行除法操作*/ temp=reg

30、2+inputi;/*生成多项式为g(x)=x4+x2+x+1*/ if(temp=2)temp=0; reg2=reg1+temp; if(reg2=2)reg2=0; reg1=reg0; reg0=temp; for (i=0;i3;i+)outputi=inputi;/*进行编码操作*/for (i=3;i0;j-) regj=regj-1; reg0=0; outputi=temp; printf( );printf(n);printf(The information code output is:n);for(i=0;i7;i+)printf (%d,outputi);/*输出编码结果*/printf(n);printf( );printf(n);Begin();/*译码并进行纠检错*/void Decoding()int input 7,output7;