信息論循環(huán)碼報告概要

1、級項目報告課程名稱:信息論與編碼課程設(shè)計題目:循環(huán)碼的編碼和譯碼程序設(shè)計合作者完成時間:2012年5_月8_日至5月21日成績:評閱人:摘要循環(huán)碼是線性分組碼中一個重要的子類，具有檢錯糾錯能力強(qiáng)，實現(xiàn)方便 等特點(diǎn)。它具有嚴(yán)密的代數(shù)學(xué)理論，封閉性與循環(huán)性。 (n,k) 循環(huán)碼表示信息位 為 k 位，監(jiān)督位為 (n-k) 位。本次設(shè)計實驗首先分析了 (7,4 )循環(huán)碼的編碼與譯 碼原理，然后，用C語言實現(xiàn)其編碼與譯碼功能。通過C語言平臺運(yùn)行所編寫的程序，觀察了在輸入信息碼情況下輸出對應(yīng)的編碼結(jié)果以及相反的譯碼功 能。通過多組的對比驗證了該 (7,4 )循環(huán)碼的編譯碼程序的正確性。最后，在 程序運(yùn)行

2、的過程中進(jìn)一步分析循環(huán)碼的編譯碼原理，并通過比較仿真模型與理 論計算的性能，證明了仿真模型的可行性。關(guān)鍵詞：循環(huán)碼，編碼與譯碼，C程序。循環(huán)碼的原理與特點(diǎn)循環(huán)碼是線性分組碼的一種，所以它具有線性分組碼的一般特性，此外還 具有循環(huán)性。循環(huán)碼的編碼和解碼設(shè)備都不太復(fù)雜，且檢(糾)錯能力強(qiáng)。它不但可以檢測隨機(jī)的錯誤，還可以檢錯突發(fā)的錯誤。(n,k)循環(huán)碼可以檢測長為n-k或更短的任何突發(fā)錯誤，包括首尾相接突發(fā)錯誤。循環(huán)碼是一種無權(quán)碼，循環(huán)碼編排的特點(diǎn)是相鄰兩個數(shù)碼之間符合卡諾圖 中的鄰接條件，即相鄰兩個數(shù)碼之間只有一位碼元不同，碼元就是組成數(shù)碼的 單元。符合這個特點(diǎn)的有多種方案，但循環(huán)碼只能是表中的

3、那種。循環(huán)碼的優(yōu) 點(diǎn)是沒有瞬時錯誤，因為在數(shù)碼變換過程中，在速度上會有快有慢，中間經(jīng)過 其它一些數(shù)碼形式，稱它們?yōu)樗矔r錯誤。這在某些數(shù)字系統(tǒng)中是不允許的，為 此希望相鄰兩個數(shù)碼之間僅有一位碼元不同，即滿足鄰接條件，這樣就不會產(chǎn) 生瞬時錯誤。循環(huán)碼就是這樣一種編碼，它可以在卡諾圖中依次循環(huán)得到。循 環(huán)碼又稱格雷碼(Grey Code )。循環(huán)碼最大的特點(diǎn)就是碼字的循環(huán)特性，所謂循環(huán)特性是指：循環(huán)碼中任 一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。若(O皆1b-2 .Bj 如)為一循環(huán)碼組，則(2 "Z .5)、嚴(yán)衛(wèi)H O")、.還是許用碼組。也就是說，不論是左移還是

4、右移，也不論移多少位，仍然是許用的循環(huán)碼組。循環(huán)碼編碼原理+ m0其中高幕次為k 1(1)有信息碼構(gòu)成信息多項式m(x)= mk_1 xn_km(x)最咼冪次為n-1,該k-1;n _k用x 乘以信息多項式 m(x)，得到的x過程相當(dāng)于把信息嗎(mz，mi，mo)移位到了(3)碼字德前k個信息位，其后是r個全為零的監(jiān)督位；.n _k用g(x)除x m(x)得到余式r(x),其次數(shù)必小于g(x)的次數(shù)，即小于(n-k),將此r(x)加于信息位后做監(jiān)督位，即將r(x)于J" m(x)相加，得到的多項式必為一碼多項式。根據(jù)上面的討論，可得到在(7, 4)循環(huán)碼編碼的程序框圖如圖 1所下圖示

5、:初始化圖2編碼程序框圖循環(huán)碼的譯碼原理糾錯碼的譯碼是該編碼能否得到實際應(yīng)用的關(guān)鍵所在。譯碼器往往比編碼 較難實現(xiàn)，對于糾錯能力強(qiáng)的糾錯碼更復(fù)雜。根據(jù)不同的糾錯或檢錯目的， 循環(huán)碼譯碼器可分為用于糾錯目的和用于檢錯目的的循環(huán)碼譯碼器。CRC通常，將接收到的循環(huán)碼組進(jìn)行除法運(yùn)算，如果除盡，貝U說明正確傳 輸；如果未除盡，則在寄存器中的內(nèi)容就是錯誤圖樣，根據(jù)錯誤圖樣可以確 定一種邏輯，來確定差錯的位置，從而達(dá)到糾錯的目的。用于糾錯目的的循 環(huán)碼的譯碼算法比較復(fù)雜，感興趣的話可以參考一些參考書。而用于檢錯目 的循環(huán)碼，一般使用 ARQ通信方式。檢測過程也是將接受到的碼組進(jìn)行除法 運(yùn)算，如果除盡，則說

6、明傳輸無誤；如果未除盡，則表明傳輸出現(xiàn)差錯，要 求發(fā)送端重發(fā)。用于這種目的的循環(huán)碼經(jīng)常被成為循環(huán)冗余校驗碼，即 校驗碼。CRC校驗碼由于編碼電路、檢錯電路簡單且易于實現(xiàn)，因此得到廣泛的應(yīng)用。在通過MODE傳輸文件的協(xié)議如ZMODEMXMODE協(xié)議中均用到 了 CRC校驗技術(shù)。在磁盤、光盤介質(zhì)存儲技術(shù)中也使用該方法。在SystemView中沒有提供專用的 CRC循環(huán)冗余校驗碼編碼器，讀者可 根據(jù)有關(guān)參考書設(shè)計一個相應(yīng)的仿真電路。如果不想親自動手設(shè)計，可以在 CDMAB( IS95 )中找到一個現(xiàn)成的專用的CRC編碼器和譯碼器。該圖符位、校驗位12比特、尾部全零 8860bps (192bit/0

7、.2ms= 860 )的并可用對應(yīng)的譯碼器譯碼觀察輸(Frame Q)是的接入信道的數(shù)據(jù)幀品質(zhì)指示編碼器，其中使用了多種不同比 特率的數(shù)據(jù)模型，通過 CRC校驗來判斷接入信道的質(zhì)量好壞。其中規(guī)定每一 幀的長度為20ms的數(shù)據(jù)。一個典型IS-95-A標(biāo)準(zhǔn)規(guī)定的9600信道的CRC測 試碼的長度為192比特，其中信息位172 比特。感興趣的讀者可以加入一個速率為 PN數(shù)據(jù)，然后觀察經(jīng)過 CRC編碼后的波形。 出波形是否與輸入的 PN碼一致。(14)當(dāng)碼字c通過噪聲信道傳送時，會受到干擾而產(chǎn)生錯誤。如果信道產(chǎn)生的 錯誤圖樣是e,譯碼器收到的n重接受矢量是y,則表示為：y=c+e (13) 上式也可以

8、寫成多項式形式：y(x)=c(x)+e(x)A譯碼器的任務(wù)就是從y(x)中得到e(x)，然后求的估值碼字(15)AAc(x)=y(x)+ e(x)A并從中得到信息組m(x)。循環(huán)碼譯碼可按以下三個步驟進(jìn)行：(1)有接收到的y(x)計算伴隨式s(x);A(2)根據(jù)伴隨式s(x)找出對應(yīng)的估值錯誤圖樣e(x);AAA計算c(x)=y(x)+ e(x)，得到估計碼字c(x)。若c(x)=c(x),則Ag(x)的次數(shù)為n - k 次，g(x)除E(x)后得余式(即伴隨式)的最 n-k-1次，故S(x)共有2n-k個可能的表達(dá)式，每一個表達(dá)式對應(yīng)一譯碼正確，否則，若c(x) Hc(x)，則譯碼錯誤。由于

9、 高次數(shù)為 個錯誤格式?？梢灾?7,4 )循環(huán)碼的S(x)共有2(7-4) = 8個可能的表達(dá)式, 可根據(jù)錯誤圖樣表來糾正(7,4 )循環(huán)碼中的一位錯誤，其伴隨式如表1所示。BCH(7, 4)循環(huán)碼錯誤圖樣表:錯誤圖樣錯誤圖樣碼字伴隨式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)循環(huán)碼錯誤圖樣表上式指出了系統(tǒng)循環(huán)碼的譯碼方法：將收到的碼字 R(x)用g(x)去除，如 果除盡則無錯；否則有錯。如果有錯，可由余式 S(x) 一一找出對應(yīng)圖樣，然后 將錯誤圖樣E(x)與R(x)模2和，即為所求碼字C(x)，從而實現(xiàn)糾錯目的。根據(jù)前面的討論，可得(7, 4)循環(huán)碼譯碼的程序框圖如圖2所示圖2 譯碼程序框圖基于C語言程序編寫就74循環(huán)碼的編碼與譯碼程序如附錄所示:運(yùn)行及分析運(yùn)行結(jié)果理論分析由循環(huán)碼性質(zhì)我們可以知道，對于（7，4）循環(huán)碼來說，最小碼距d0=4，可以檢測出3位錯誤，糾正1位錯誤，編碼效率為4 7 X 100% = 57.1%。設(shè)傳輸信道的誤碼率為P，據(jù)此設(shè)定信

11、道模型存在如下關(guān)系： 傳輸正確概率為（1 - P）n，信息幀傳輸錯誤概率為 Pe=1-（1-P）n，每幀僅發(fā)生1 位錯誤的概率為Fe=Crip（1-p） n-1= np（1-p） n-1,則1位錯誤幀在總的錯誤幀中的概 率為心自"00% = ("00%表2為其Pe,P e1,R的模擬結(jié)果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的模擬結(jié)果（n=7）綜合表2的模擬結(jié)果和理論分析可知，通信系統(tǒng)的幀傳輸具有下列性質(zhì)：（1） 在n 定的條件下，信息幀錯誤概率隨著比特誤碼率P的增加而增 加，最壞條件下幀錯誤 概率幾乎為100%此時系統(tǒng)失去通信能力。（2） 在典型的通信環(huán)境下（P為10-3 10-5 5,幀長n =128 - 1024，np<1 ），當(dāng)P T 0時，R T1,表明當(dāng)比特誤碼率P足夠小的情況下，絕大多 數(shù)信息幀錯誤是每幀1位錯誤，因此糾正每幀1位錯誤有實際應(yīng)用價值。程序運(yùn)行結(jié)果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機(jī)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碼在現(xiàn)代通信系

21、統(tǒng)中的應(yīng)用RS幾乎所有的現(xiàn)代化通信系統(tǒng)都把糾錯編碼作為一個基本組成部分， RS 碼由于具有強(qiáng)有 力的糾錯功能，已經(jīng)被 NASA 、 ESA、CCSDS 等空間組織接受，用于空間信道糾錯。 循環(huán)碼在車載無線通信、 M 元擴(kuò)頻通信系統(tǒng)中的應(yīng)用以及 QAM 系統(tǒng)等方面都有很廣泛的 應(yīng)用，可以說它已經(jīng)成為無線通信系統(tǒng)中不可或缺的一部分。實驗過程遇到的問題及解決方法本次實驗讓我感覺非常棘手，一方面的原因是自己對信道編碼的不熟悉，之前做的實 驗都是對信源進(jìn)行編碼，現(xiàn)在是對信道進(jìn)行編碼；另一方面是書本對于此部分的介紹內(nèi)容 相對較少，要自己在網(wǎng)上找資料學(xué)習(xí)，網(wǎng)上知識點(diǎn)太泛濫而且很多都是太學(xué)術(shù)化，不容易 理解，

22、因此要自己編程那是難上加難。此次實驗的 C 程序我也是參考網(wǎng)上其中的一份并在 其基礎(chǔ)上根據(jù)自己的需要加上了自己的部分代碼，網(wǎng)上對于這方面的資源真的蠻少，也許 是自己找的還不夠徹底吧，總的來說，這次實驗收獲不多，對于這方面還沒掌握，我會繼 續(xù)努力。參考文獻(xiàn)1 潘新民主編 . 計算機(jī)通信技術(shù) （ 第 2 版）. 北京. 電子工業(yè)出版 社.20062孫麗華 謝仲華 陳榮伶編 信息論與糾錯編碼 .北京. 電子工業(yè)出版社.20053樊昌信著. 通信原理 M. 國防工業(yè)出版社 .1999.104宋祖順著。現(xiàn)代通信原理 M. 電子工業(yè)出版社 .2001.25黃新亞米央編著 信息編碼技術(shù)及其應(yīng)運(yùn)大全 M 電子

23、工業(yè)出版社1994.8附錄/*(7,4) 循環(huán)碼的編譯及糾檢錯實現(xiàn) */ #include<stdio.h> #include<math.h> #include<stdlib.h>/* 函數(shù)聲明 */ void Begin();void Code();void Decoding();/* 主函數(shù) */ main()printf("nThis software main function is carries on the code and the decoding to (7,3) cyclic code.n ");Begin();/*

24、進(jìn)行編碼 */ 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+)/*進(jìn)行除法操作 */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;/* 進(jìn)行編碼操作 */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);/*輸出編碼結(jié)果 */IIprintf("n");printf("printf("n");Begin();/* 譯碼并進(jìn)行糾檢錯 */ 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、+)/*進(jìn)入除法電路 */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)/*輸入錯誤位數(shù)大于 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) 進(jìn)行自發(fā)運(yùn)算以求得錯誤位數(shù) */reg2=temp+reg