循环码编译码软件测试.doc

摘要循环码的编码与译码电路比较简单，纠错能力也较强，是应用比较广泛的差错控制编码方法之一。循环码的编码和译码都要用到由一个多项式去除另一个多项式。对于接收端译码的要求通常有两个：检错与纠错。达到检错目的的译码十分简单。 关键字：循环码 编码 译码 目录一、目的及意义1 二、设计结果22.1循环码的介绍22.1.1循环码的定义22.1.2循环码的特点22.1.3循环码的多项式表示32.1.4（n,k）循环码的生成多项式32.2循环码编码原理6 2.3循环码译码原理8 三、设计结果及分析9 3.1无差错编码仿真结果9 1.初始界面92.正确编码界面93.无差错编码仿真结果104部分差错编码图115离开界面123.2运行结果理论分析133.3软件可行性分析13四、总结14 参考文献15 附录16 一、目的及意义 在实际的通信系统中，由于信道传输特性不理想以及加噪声的影响，接收到的信息中不可避免的会发生错误，影响通信系统的传输可靠性。随着数字通信技术的发展，各种业务对系统误码率的要求逐渐提高，差错控制编码技术是提高数字通信可靠性的有效方法之一。循环码的编码与译码电路比较简单，纠错能力也较强，是应用比较广泛的差错控制编码方法之一。通过完成本课题的设计，拟达到以下目的：1.学习循环码编、译码的基本原理，并重点掌握（7,3）循环码的编码与译码；2. 查找并分析选择一个合理的生成多项式；3.用C语言分别编程实现（7,3）循环码的编码与译码部分；4.输入任意的数字信息序列，仿真并分析（7,3）循环码的编码结果；5.分别在无差错和部分差错的情况下仿真并分析（7,3）循环码的译码结果；6.分析软件的可行性。 二、设计原理 2.1循环码的介绍循环码是线性分组码中一个重要的分支。它的检、纠错能力较强，编码和译码设备并不复杂，而且性能较好，不仅能纠随机错误，也能纠突发错误。循环码是目前研究得最成熟的一类码，并且有严密的代数理论基础，故有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现，所以循环码受到人们的高度重视。 2.1.1循环码的定义循环码是一种线性代数分组码，记为（n,k）码，其中n为码长，k为信息码元数。 2.1.2循环码的特点若是一个码字，则它的循环移位也是一个码字。循环码是线性分组码的一种，所以它具有线性分组码的一般特性，此外还具有循环性。循环码的编码和解码设备都不太复杂，且检(纠)错能力强。它不但可以检测随机的错误，还可以检错突发的错误。（n,k）循环码可以检测长为n-k或更短的任何突发错误，包括首尾相接突发错误。循环码是一种无权码，循环码编排的特点是相邻两个数码之间符合卡诺图中的邻接条件，即相邻两个数码之间只有一位码元不同，码元就是组成数码的单元。符合这个特点的有多种方案，但循环码只能是表中的那种。循环码的优点是没有瞬时错误，因为在数码变换过程中，在速度上会有快有慢，中间经过其它一些数码形式，称它们为瞬时错误。这在某些数字系统中是不允许的，为此希望相邻两个数码之间仅有一位码元不同，即满足邻接条件，这样就不会产生瞬时错误。循环码就是这样一种编码，它可以在卡诺图中依次循环得到。循环码又称格雷码（ Grey Code ）。循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。若为一循环码组，则、还是许用码组。也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码组。 2.1.3循环码的多项式表示设码长为n的循环码表示为，其中为二进制数，通常把码组中各码元当做二进制的系数，即把上式中长为n的各个分量看做多项式： (2-1)的各项系数，则码字与码多项式一一对应，这种多项式中，x仅表示码元位置的标记,因此我们并不关心x的取值，这种多项式称为码多项式。我们用多项式来表示循环码的码字 （2-2）也就是一个n长码字可以用一个次多项式来表示。它的循环特性，可由多模多项式来表示，例如左移一位，相当于乘x 模 应该指出，这里采用了模多项式运算。同样，左移两位相当于乘以等等。 2.1.4（n,k）循环码的生成多项式一个（n,k）循环码，它共有个码字，从中取出其前面位的码字，以表示，它的次数为。则都是码字，且k个码字彼此独立，因此可以作为码的生成矩阵的k行。一经确定，码也就确定了，编码的问题也就解决了。因此，我们称为码的生成多项式。生成矩阵可以表示如下 （2-3）因此，循环码可以写成，式中为K位信息元矩阵。变换上式可得， （2-4）式中，为信息码组多项式。由（2-4）可以看出，所有用生成的码字都是生成多项式的倍式。也就是说，凡是一个码字多项式一定能被除尽。反之，能被除尽的次数不大于（n-1）次的多项式，也一定是码多项式。由此可以得出循环码编码方法如下：首先将次数小于（k-1）次的信息码组多项式乘以,得到，其次数小于等于次。然后用生成多项式去除，得到除式为，它的次数小于的次数，把此余式的系数作为监督元附加在信息码组后面，就得到一个必能被除尽的多项式，且它必是一个码多项式，运算过程为： （2-5） （2-6）式中为商式，为余式，则码多项式为 （2-7）而余式可以写成 模 （2-8）且由于它是循环码，故必是的一个因式，也就是说，它必能被g(x)整除，即： 模 （2-9）式中，为次数次，的次数为k次。该结论可以这样来说明：如果表示一个码多项式，则它也是的一个倍式。因此可以写成 （2-10）而乘以x相当于一次循环移位，又因为 幂次 （2-11） ，幂次 （2-12）所以能除尽，必能除尽。因此，我们可以说每个（n,k）循环码都是由幂次为n-k可以除尽的因式产生的，反之可以说每个这样的因式可以产生一个（n,k）循环码。上述结论说明了能除尽的诸因式确定了所有长度为n的循环码。举例（7,3）循环码生成多项式，可以求得（7,3）循环码所有码字如下表所示 序号信息码循环码序号信息码循环码 0 0000000000 4 1001001110 1 0010011101 5 1011010011 2 0100100111 6 1101101001 3 0110111010 7 1111110100 图1.（7,3）循环码的系统码 从表中可以看出，（7,3）循环码正是具有循环性质的（7,3）增余汉明码。 2.1.5循环码的生成矩阵和一致校验矩阵对所有的i=0,1,2,k-1，用生成多项式除，有： （2-13）式中是余式，表示为： （2-14）因此，是的倍式，即是码多项式，由此得到系统形式的生成矩阵为： 同样，由G=0可以得到系统形式的一致校验矩阵为： 如已知（7，3）循环码的生成多项式和校验多项式分别为：，。写得其生成矩阵和校验矩阵分别为： 生成矩阵G后，可以通过线型变化，使之成为典型矩阵，这时就可以采用类似监督矩阵H。由于（n,k）是的因式，因此可令： （2-15）这里称为监督多项式。监督矩阵为： 为的逆多项式。 （2-16）则对于（7,3）循环码，若，则： 2.2循环码编码原理 2.2.1多项式除法电路从前面的分析我们可以看出，循环码的编码和译码都要用到由一个多项式去除另一个多项式，也主要利用电路来实现这种除法运算下面先用一个具体的例子来说明多项式除法电路的工作原理和运算过程。设多项式为，另一多项式，根据多项式除法运算规则，可得 （2-17）其中，为被除式，为除式。商式 （2-18）而余式为 （2-19）与此除法运算对应的除法电路如下图所示输出 图2.的除法电路图中，符号D表示单级移位寄存器，一般可用D触发器组成；表示模2加法器，完成模2加法运算。从图中可以看出由四级（等于多项式的次数）移位寄存器，和三级模2加法器就组成的除法电路。它实际上是一个具有反馈的线性移位寄存器。运算过程如图3所示，从表中可以看出，只有等到第五次移位时，才得到上式的首次系数，七位移位后除法运算完毕，这时在中的存数即为余式的系数0011. 表2.除法电路运算过程移位脉冲 输入移位后存数 输出 移位后反馈 0 0 0000 0 0000 1 1000 0 00002 0100 0 00003 1010 0 0000 4 0101 0 0000 5 1001 1011 6 1111 1011 7 1100余式商式 1011 由图3运算过程可以看出，在第一至第四次的移位中，除法电路只是接受输入多项式中的系数，只有在第5个移位脉冲到来以后，才正式开始运算。 2.3循环码译码原理对于接收端译码的要求通常有两个：检错与纠错。达到检错目的的译码十分简单，通过判断接收到的码组多项式是否能被生成多项式整除作为依据。如果除尽，则说明正确传输；如果未除尽，则在寄存器中的内容就是错误图样，根据错误图样可以确定一种逻辑，来确定差错的位置，从而达到纠错的目的。纠错码的译码是该编码能否得到实际应用的关键所在。译码器往往比编码较难实现，对于纠错能力强的纠错码更复杂。 而用于检错目的循环码，一般使用ARQ通信方式。检测过程也是将接受到的码组进行除法运算，如果除尽，则说明传输无误；如果未除尽，则表明传输出现差错，要求发送端重发。用于这种目的的循环码经常被成为循环冗余校验码，即CRC校验码。CRC校验码由于编码电路、检错电路简单且易于实现，因此得到广泛的应用。在通过MODEM传输文件的协议如ZMODEM、XMODEM协议中均用到了CRC校验技术。在磁盘、光盘介质存储技术中也使用该方法。 当码字c通过噪声信道传送时，会受到干扰而产生错误。如果信道产生的错误图样是e，译码器收到的n，重接受矢量是y,则表示为： （2-20）上式也可以写成多项式形式： （2-21）译码器的任务就是从y(x)中得到，然后求的估值码字 （2-22）并从中得到信息组。 循环码译码可按以下三个步骤进行：（1）由接收到的，计算伴随式;（2）根据伴随式找出对应的估值错误图样；（3）计算，得到估计码字。若,则译码正确，否则，若 ，则译码错误。由于的次数为次，除后得余式（即伴随式）的最高次数为次，故共有个可能的表达式，每一个表达式对应一个错误格式。可以知道（7,3）循环码的共有个可能的表达式，可以根据错误图样表来纠正（7,3）循环码中意味的错误。 三设计结果及分析 3.1程序运行结果 1.初始界面 图 3 .初始化界面 程序编译无错误后运行，出现界面如上图所示。 2.正确编码界面 图4 . 正确编码界面 在C环境下，输入“c”,再输入3位信息位，软件执行后输出7位循环编码。 例如输入的是110，系统输出的是1101000. 图5 . 正确编码界面为检验程序的正确性，再输入一组3位信息位111，系统输出7位循环码为1110010.3.无差错编码仿真结果 图6 . 无差错编码仿真结果图输入“e”,系统将进行译码操作，当输入的译码信息和编码结果一样时，系统就会把正确将信息位从该码组译出来。输入7位为1101000，与编码输入的3个信息位的结果相同，检验无错误。 图7 .无差错编码结果图 输入7位1110010，输出与译码结果输入111后的编码结果相同，检验无错误。4部分差错编码图 图8 .一位差错编码图 当输入的译码信息与编码的结果错一位码时，系统就会检测出该错误并将其纠正过来，从而译出真确的信息位。 输入7位1101010，译码结果为110，译码信息与编码结果出现1位错误，系统自动将错误改正，输出为1101000。图9 . 一位差错编码结果图同上图，输入的7位为1110000，译码信息与编码结果出现1位错误，系统自动改正，输出7位信息1110010。 5离开界面图10 .离开界面软件检验结束，输入“e”,退出运行系统。 3.2运行结果理论分析 由循环码性质可知，（7,3）循环码的最小码距d=4,可以检测出小于等于3位错误，纠正1位错误，编码效率为42.8%。设传输正确概率为p,据此设定信道模型存在如下关系：传输正确概率为，信息传输错误概率为，每帧仅发生1位错误的概率为： （3-1） 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 表3 .模拟结果 综合上表的模拟结果和理论结果可以看出，通信系统的帧传输具有以下性质：（1）在n一定的情况下，信息帧错误传输概率随着比特误码率的增加而增加，最坏情况下帧错误概率几乎为100%，此时系统失去通信能力。（2）在典型的通信环境下，当比特误码率足够小时，绝大多数信息帧错误时每帧1位错误，因此纠正每帧错误有实用价值。3.3软件可行性分析由上述结果可知，该软件的操作方法为程序通过编译运行后，在C环境下，当输入c后按回车键，然后就会提示输入信息，当输入3位的信息位再按回车键，系统就会输出7位的循环编码。当输入d后按回车键，系统会进行译码的操作，当输入的译码信息和编码结果一样时，系统就会正确将信息位从该码组译出来。当输入的译码信息与编码的结果错一位码时，系统就会检测出该错误并将其纠正过来，从而译出真确的信息位。当输入e后按回车，就会退出系统。由此可知，该系统能够实现（7，3）循环码的编码与在无差错和部分差错情况下的译码，因此该软件具有可行性。 四总结通过本次课设，我对循环码的编码和译码的基本原理有了较深的理解，学到了很多的知识。循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码。它有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现；同时循环码的性能也较好，具有较强的检错和纠错能力。我的题目是循环码编译码的软件设计，在这两周中遇到了好多问题，由于以前学习C语言没有用心，编程的过程中出现了很多问题。例如，由于输入法的问题导致程序出现了错误。后来，通过同学的帮助，发现并改正了这个错误。最终实现了循环码编译码的软件设计。这次课设让我受益匪浅，让我理解了纠错码的原理和循环冗余码CRC的原理。真正地做到了输入任意的数字信息序列，得出编码结果。还学会了在无差错和部分差错的情况下进行译码。 这次设计不仅仅加深了对课程理论知识的了解，并更加熟悉了计算机语言，软件的应用。并让我了解，学习知识不仅仅只在课本上，还有更多更广的渠道获得更宽广的知识。最后感谢老师对我们的精心指导和帮助，感谢同学们对我的帮助。 参考文献1樊昌信 著.通信原理M.国防工业出版社，1999,10.2 宋祖顺 著.现代通信原理M.电子工业出版社,2001,23 黄亚新，米央著.信息编码技术及其应用大全M.电子工业出版社，1994.84 孙丽华 著.信息论与纠错编码M.电子工业出版社，2005,35 Proakis 著，张力军 译.数字通信（第四版）M.电子工业出版社，2004,76 潘新民 著.计算机通信技术M.电子工业出版社，2003,7 7 贾世楼 著.信息论理论基础(第二版).哈尔滨工业大学出版社 附录循环码编码译码软件设计程序/*(7,3)循环码的编译及纠检错*/#include#include #include/*函数声明*/void Begin();void Code();void Decoding();/*主函数*/void main() printf(n This software 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=reg2+inputi; /*生成多项式为g(x)=x4+x3+x2+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; int reg4=0,0,0,0; int temp,i,d,x,p; printf(n intput the information code of bit 7:); for(i=0;i7;i+) scanf(%d,&inputi); /*输入接收码组*/ for(i=0;i=2n); getchar(); exit(0); printf( n);printf(s(x)=);for(i=3;i=0;i-)p