信息论循环码报告概要

1、级项目报告课程名称:信息论与编码课程设计题目:循环码的编码和译码程序设计合作者完成时间:2012年5_月8_日至5月21日成绩:评阅人:摘要循环码是线性分组码中一个重要的子类，具有检错纠错能力强，实现方便 等特点。它具有严密的代数学理论，封闭性与循环性。 (n,k) 循环码表示信息位 为 k 位，监督位为 (n-k) 位。本次设计实验首先分析了 (7,4 )循环码的编码与译 码原理，然后，用C语言实现其编码与译码功能。通过C语言平台运行所编写的程序，观察了在输入信息码情况下输出对应的编码结果以及相反的译码功 能。通过多组的对比验证了该 (7,4 )循环码的编译码程序的正确性。最后，在 程序运行

2、的过程中进一步分析循环码的编译码原理，并通过比较仿真模型与理 论计算的性能，证明了仿真模型的可行性。关键词：循环码，编码与译码，C程序。循环码的原理与特点循环码是线性分组码的一种，所以它具有线性分组码的一般特性，此外还 具有循环性。循环码的编码和解码设备都不太复杂，且检(纠)错能力强。它不但可以检测随机的错误，还可以检错突发的错误。(n,k)循环码可以检测长为n-k或更短的任何突发错误，包括首尾相接突发错误。循环码是一种无权码，循环码编排的特点是相邻两个数码之间符合卡诺图 中的邻接条件，即相邻两个数码之间只有一位码元不同，码元就是组成数码的 单元。符合这个特点的有多种方案，但循环码只能是表中的

3、那种。循环码的优 点是没有瞬时错误，因为在数码变换过程中，在速度上会有快有慢，中间经过 其它一些数码形式，称它们为瞬时错误。这在某些数字系统中是不允许的，为 此希望相邻两个数码之间仅有一位码元不同，即满足邻接条件，这样就不会产 生瞬时错误。循环码就是这样一种编码，它可以在卡诺图中依次循环得到。循 环码又称格雷码(Grey Code )。循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任 一许用码组经过循环移位后，所得到的码组仍然是许用码组。若(O皆1b-2 .Bj 如)为一循环码组，则(2 "Z .5)、严卫H O")、.还是许用码组。也就是说，不论是左移还是

4、右移，也不论移多少位，仍然是许用的循环码组。循环码编码原理+ m0其中高幕次为k 1(1)有信息码构成信息多项式m(x)= mk_1 xn_km(x)最咼幂次为n-1,该k-1;n _k用x 乘以信息多项式 m(x)，得到的x过程相当于把信息吗(mz，mi，mo)移位到了(3)码字德前k个信息位，其后是r个全为零的监督位；.n _k用g(x)除x m(x)得到余式r(x),其次数必小于g(x)的次数，即小于(n-k),将此r(x)加于信息位后做监督位，即将r(x)于J" m(x)相加，得到的多项式必为一码多项式。根据上面的讨论，可得到在(7, 4)循环码编码的程序框图如图 1所下图示

5、:初始化图2编码程序框图循环码的译码原理纠错码的译码是该编码能否得到实际应用的关键所在。译码器往往比编码 较难实现，对于纠错能力强的纠错码更复杂。根据不同的纠错或检错目的， 循环码译码器可分为用于纠错目的和用于检错目的的循环码译码器。CRC通常，将接收到的循环码组进行除法运算，如果除尽，贝U说明正确传 输；如果未除尽，则在寄存器中的内容就是错误图样，根据错误图样可以确 定一种逻辑，来确定差错的位置，从而达到纠错的目的。用于纠错目的的循 环码的译码算法比较复杂，感兴趣的话可以参考一些参考书。而用于检错目 的循环码，一般使用 ARQ通信方式。检测过程也是将接受到的码组进行除法 运算，如果除尽，则说

6、明传输无误；如果未除尽，则表明传输出现差错，要 求发送端重发。用于这种目的的循环码经常被成为循环冗余校验码，即 校验码。CRC校验码由于编码电路、检错电路简单且易于实现，因此得到广泛的应用。在通过MODE传输文件的协议如ZMODEMXMODE协议中均用到 了 CRC校验技术。在磁盘、光盘介质存储技术中也使用该方法。在SystemView中没有提供专用的 CRC循环冗余校验码编码器，读者可 根据有关参考书设计一个相应的仿真电路。如果不想亲自动手设计，可以在 CDMAB( IS95 )中找到一个现成的专用的CRC编码器和译码器。该图符位、校验位12比特、尾部全零 8860bps (192bit/0

7、.2ms= 860 )的并可用对应的译码器译码观察输(Frame Q)是的接入信道的数据帧品质指示编码器，其中使用了多种不同比 特率的数据模型，通过 CRC校验来判断接入信道的质量好坏。其中规定每一 帧的长度为20ms的数据。一个典型IS-95-A标准规定的9600信道的CRC测 试码的长度为192比特，其中信息位172 比特。感兴趣的读者可以加入一个速率为 PN数据，然后观察经过 CRC编码后的波形。 出波形是否与输入的 PN码一致。(14)当码字c通过噪声信道传送时，会受到干扰而产生错误。如果信道产生的 错误图样是e,译码器收到的n重接受矢量是y,则表示为：y=c+e (13) 上式也可以

8、写成多项式形式：y(x)=c(x)+e(x)A译码器的任务就是从y(x)中得到e(x)，然后求的估值码字(15)AAc(x)=y(x)+ e(x)A并从中得到信息组m(x)。循环码译码可按以下三个步骤进行：(1)有接收到的y(x)计算伴随式s(x);A(2)根据伴随式s(x)找出对应的估值错误图样e(x);AAA计算c(x)=y(x)+ e(x)，得到估计码字c(x)。若c(x)=c(x),则Ag(x)的次数为n - k 次，g(x)除E(x)后得余式(即伴随式)的最 n-k-1次，故S(x)共有2n-k个可能的表达式，每一个表达式对应一译码正确，否则，若c(x) Hc(x)，则译码错误。由于

9、 高次数为 个错误格式。可以知道(7,4 )循环码的S(x)共有2(7-4) = 8个可能的表达式, 可根据错误图样表来纠正(7,4 )循环码中的一位错误，其伴随式如表1所示。BCH(7, 4)循环码错误图样表:错误图样错误图样码字伴随式S(x)伴随式E6(x)=x61000000x2100E5(x)=x50100000x2+x110E4(x)=x40010000X2+X+1111E3(x)=x30001000x+1011E2(x)=x20000100x2+1101E1(x)=x10000010x010EO(x)=xO00000011001E(x)=000000000000表1 BCH (7,

10、 4)循环码错误图样表上式指出了系统循环码的译码方法：将收到的码字 R(x)用g(x)去除，如 果除尽则无错；否则有错。如果有错，可由余式 S(x) 一一找出对应图样，然后 将错误图样E(x)与R(x)模2和，即为所求码字C(x)，从而实现纠错目的。根据前面的讨论，可得(7, 4)循环码译码的程序框图如图2所示图2 译码程序框图基于C语言程序编写就74循环码的编码与译码程序如附录所示:运行及分析运行结果理论分析由循环码性质我们可以知道，对于（7，4）循环码来说，最小码距d0=4，可以检测出3位错误，纠正1位错误，编码效率为4 7 X 100% = 57.1%。设传输信道的误码率为P，据此设定信

11、道模型存在如下关系： 传输正确概率为（1 - P）n，信息帧传输错误概率为 Pe=1-（1-P）n，每帧仅发生1 位错误的概率为Fe=Crip（1-p） n-1= np（1-p） n-1,则1位错误帧在总的错误帧中的概 率为心自"00% = ("00%表2为其Pe,P e1,R的模拟结果PPe艮1R/%10-10.5217030.37200971.3010-20.06793470.065903697.0110-30.006979030.006958199.7010-40.000699790.0006995899.9710-50.0000699790.0006995899.9

12、7表2 P e,Pei,R的模拟结果（n=7）综合表2的模拟结果和理论分析可知，通信系统的帧传输具有下列性质：（1） 在n 定的条件下，信息帧错误概率随着比特误码率P的增加而增 加，最坏条件下帧错误 概率几乎为100%此时系统失去通信能力。（2） 在典型的通信环境下（P为10-3 10-5 5,帧长n =128 - 1024，np<1 ），当P T 0时，R T1,表明当比特误码率P足够小的情况下，绝大多 数信息帧错误是每帧1位错误，因此纠正每帧1位错误有实际应用价值。程序运行结果1初始化界面This sofCw«re P>ain function is carried

13、on the code 4rtd the decoding to <7>4> c典 lie code.to carrsf an the decoding code to CKit please toinput *c* to Cart'S* on the code in put in pint * e*2. 正确编码界面This softuAre nain function is carries on the code and the decoding to <7,4> cc lie cods *input * c * toon the codeinput

14、d" co carry on the decoding code input * e' co exit pleast toPlcAse Input Che InfornACion code L 0 1The Infoirncion code output Is： 0 10 1110input "c' to carry on the code - in狙山'd' to carry on the decoding code - input "e* to exit please to -3. 正确译码界面input the infomna

15、tioncode of bit7te 1 Q 1s<x>= a e e rhe detading bit! is: rhe Decodinsi bit? is:inputtocarry on (lie codeingpiut'(Vtocarry on t】紆 decodingcode-input* ft*taexit pleASft to=input the inforntiqn code of fait7-l 1 0 1 1 1 Qs<K>- 1 1 BIhe decodins bit4 is: 0 1 0 1 rhe Decoding bit? is: 0

16、1 0 1input "c" to cai*i*y on t】裕 codeinput 'd' ta carry on the decoding Codfe input "e" to exit please to4. 信息位有一位错误时的译码界面input the inf oriniat ion code of bit7：B 1 B 1 1 1 BR<M>- 000The decoding bit4 is: 0The Decoding bit? is: 0Input *c* to CAffy an th* code-input

17、*d* to cftt-ry cn the decodinGr code input W to exit please to=input the Inf ornat ion code of bit?：1 101110B<x)= 1 1 Bthe decoding bit4 is: 0the Decoding bit? ia ± 0input *c* to citFFy on the code -input to carry on the decoding code =- input 'e' to exit plcASe to -5. 信息位有二位错误时的译码界面

18、pbls SoftwAr? naln functiOrt Is C机rri亡窑 On the cvric And the MrCodlng to <7,4C其 lie code.ioiHit f to c«irrsr o” the codeinput * d* to ciiTjry D" the decoding code - in(hit 'e， to exitto-input the infion code af blt7：0 1 1 0 1 1 a&fls<x>= 010The decoding bit4 is: Q 1The Dec

19、oding bit7 is: 01input *c* to carry on tlie code-input 'rt' to CArry on the dflcoding cods input '亡'to exit please to6. 信息位有三位错误时的译码界面this saftuAPC naln Function is carries an tJie code and tlw decoding to <7,4> eye ic code rinput *C* to cArrv on the code -input 'd' to

20、carry on the decoding cdde - input 't* to exit please to -AiniHit tJw infornation code of bit7：l 0 1 1 1 1 fls<x>= 0 1 0The decoding blt4 is i 1011ihE DecDdiny bit? iszlQllieeinput * C* to Chrrv on the codeinput *d* to carry on the decoding code input 's' to exit please toRS码在现代通信系

21、统中的应用RS几乎所有的现代化通信系统都把纠错编码作为一个基本组成部分， RS 码由于具有强有 力的纠错功能，已经被 NASA 、 ESA、CCSDS 等空间组织接受，用于空间信道纠错。 循环码在车载无线通信、 M 元扩频通信系统中的应用以及 QAM 系统等方面都有很广泛的 应用，可以说它已经成为无线通信系统中不可或缺的一部分。实验过程遇到的问题及解决方法本次实验让我感觉非常棘手，一方面的原因是自己对信道编码的不熟悉，之前做的实 验都是对信源进行编码，现在是对信道进行编码；另一方面是书本对于此部分的介绍内容 相对较少，要自己在网上找资料学习，网上知识点太泛滥而且很多都是太学术化，不容易 理解，

22、因此要自己编程那是难上加难。此次实验的 C 程序我也是参考网上其中的一份并在 其基础上根据自己的需要加上了自己的部分代码，网上对于这方面的资源真的蛮少，也许 是自己找的还不够彻底吧，总的来说，这次实验收获不多，对于这方面还没掌握，我会继 续努力。参考文献1 潘新民主编 . 计算机通信技术 （ 第 2 版）. 北京. 电子工业出版 社.20062孙丽华 谢仲华 陈荣伶编 信息论与纠错编码 .北京. 电子工业出版社.20053樊昌信著. 通信原理 M. 国防工业出版社 .1999.104宋祖顺著。现代通信原理 M. 电子工业出版社 .2001.25黄新亚米央编著 信息编码技术及其应运大全 M 电子

23、工业出版社1994.8附录/*(7,4) 循环码的编译及纠检错实现 */ #include<stdio.h> #include<math.h> #include<stdlib.h>/* 函数声明 */ void Begin();void Code();void Decoding();/* 主函数 */ main()printf("nThis software main function is carries on the code and the decoding to (7,3) cyclic code.n ");Begin();/*

24、进行编码 */ void Code()int Input4;int Output7;int reg3=0,0,0;int temp,i,j,t;printf("Please input the information code :");for(i=0;i<4;i+)scanf(" %d",&Inputi);/*输入 4 位信息码 */for(i=0;i<4;i+)/*进行除法操作 */temp=reg2+Inputi;/*生成多项式为g(x)=xA3+xA2+1*/if(temp=2) temp=0;reg2=reg1+temp;if

25、(reg2=2)reg2=0;reg1=reg0;reg0=temp;for(i=0;i<4;i+) Outputi=Inputi;/* 进行编码操作 */for(i=4;i<7;i+)temp=reg2;for(j=2;j>0;j-)regj=regj-1;reg0=0;Outputi=temp;printf("IIprintf("n");printf(" The information code output is: n");for(i=0;i<7;i+)printf( " %d ",Output

26、i);/*输出编码结果 */IIprintf("n");printf("printf("n");Begin();/* 译码并进行纠检错 */ void Decoding() int Input7,Output7;int reg3=0,0,0;int temp,i,d,x,p;printf("ninput the information code of bit7:");for(i=0;i<7;i+)scanf(" %d",&Inputi);/*输入接受码组 */for(i=0;i<7;i

27、+)/*进入除法电路 */temp=reg2;/*计算伴随式 S(x)*/reg2=reg1+temp;if(reg2=2)reg2=0;reg1=reg0;reg0=temp+Inputi;if(reg0=2)reg0=0;p=reg2+2*reg1+4*reg0;if(p!=1&&p!=2&&p!=3&&p!=7&&p!=8&&p!=13&&p!=14&&p!=0)/*输入错误位数大于 2位*/printf(" "The error >=2" n");getchar();exit(0);printf("printf("s(x)=");for(i=2;i>=0;i-)printf(" %d",regi);printf("n");for(i=0;i<7;i+)/*纠正一位错误 */d=reg2*reg1*(!reg0);Outputi=d+Inputi;if(Outputi=2) Outputi=0;temp=reg2;x=0;/*S(x) 进行自发运算以求得错误位数 */reg2=temp+reg