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

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

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

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

4、位，仍然是許用的循環(huán)碼組。 循環(huán)碼編碼原理（1） 有信息碼構(gòu)成信息多項式m(x)= +其中高冪次為k-1;（2） 用乘以信息多項式m(x)，得到的 m(x)最高冪次為n-1,該過程相當于把信息嗎（，）移位到了碼字德前k個信息位，其后是r個全為零的監(jiān)督位;（3） 用g(x)除 m(x)得到余式r(x),其次數(shù)必小于g(x)的次數(shù)，即小于（n-k）,將此r(x)加于信息位后做監(jiān)督位，即將r(x)于 m(x)相加，得到的多項式必為一碼多項式。初始化根據(jù)上面的討論，可得到在（7，4）循環(huán)碼編碼的程序框圖如圖1 所下圖示：m(x)xn-k確定余式r(x): rx=m(x)xn-kg(x)確定c(x):

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

6、如果除盡，則說明傳輸無誤；如果未除盡，則表明傳輸出現(xiàn)差錯，要求發(fā)送端重發(fā)。用于這種目的的循環(huán)碼經(jīng)常被成為循環(huán)冗余校驗碼，即CRC校驗碼。CRC校驗碼由于編碼電路、檢錯電路簡單且易于實現(xiàn)，因此得到廣泛的應用。在通過MODEM傳輸文件的協(xié)議如ZMODEM、XMODEM協(xié)議中均用到了CRC校驗技術(shù)。在磁盤、光盤介質(zhì)存儲技術(shù)中也使用該方法。 在SystemView中沒有提供專用的CRC循環(huán)冗余校驗碼編碼器，讀者可根據(jù)有關(guān)參考書設(shè)計一個相應的仿真電路。如果不想親自動手設(shè)計，可以在CDMA庫（IS95）中找到一個現(xiàn)成的專用的CRC編碼器和譯碼器。該圖符（FrameQ）是的接入信道的數(shù)據(jù)幀品質(zhì)指示編碼器，其

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

8、x)+e(x) （14）譯碼器的任務就是從y(x)中得到，然后求的估值碼字= y(x)+ （15） 并從中得到信息組。 循環(huán)碼譯碼可按以下三個步驟進行： （1）有接收到的y(x)計算伴隨式s(x);（2）根據(jù)伴隨式s(x)找出對應的估值錯誤圖樣；（3）計算= y(x)+ ，得到估計碼字。若=c(x),則譯碼正確，否則，若c(x)，則譯碼錯誤。由于g(x) 的次數(shù)為n - k 次，g(x) 除E(x) 后得余式（即伴隨式）的最高次數(shù)為n-k-1次，故S(x) 共有2n-k 個可能的表達式，每一個表達式對應一個錯誤格式?？梢灾?7,4）循環(huán)碼的S(x) 共有2(7-4) = 8個可能的表達式，可

9、根據(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)=x10000010x010E0(x)=x000000011001E(x)=000000000000表1 BCH（7，4）循環(huán)碼錯誤圖樣表上式指出了系統(tǒng)循環(huán)碼的譯碼方法：將收到的碼字R(x) 用g(x) 去除，如果除盡則無錯；否

10、則有錯。如果有錯，可由余式S(x) 一一找出對應圖樣，然后將錯誤圖樣E(x) 與R(x) 模2 和，即為所求碼字C(x) ，從而實現(xiàn)糾錯目的。根據(jù)前面的討論，可得（7，4）循環(huán)碼譯碼的程序框圖如圖2 所示初始化由R(x)確定S(x)：R(x)g(x)的余式S(x)=0，無誤碼誤碼 是否 由S(x)確定錯誤圖樣E(x) 否糾錯C(x)=E(x)+R(x)存儲C(x)圖 2 譯碼程序框圖基于C語言程序編寫就74循環(huán)碼的編碼與譯碼程序如附錄所示：運行及分析運行結(jié)果理論分析由循環(huán)碼性質(zhì)我們可以知道，對于（7，4）循環(huán)碼來說，最小碼距d0=4，可以檢測出3 位錯誤，糾正1 位錯誤，編碼效率為4 7 &#

11、215;100% = 57.1%。設(shè)傳輸信道的誤碼率為p ，據(jù)此設(shè)定信道模型存在如下關(guān)系：傳輸正確概率為(1 p)n，信息幀傳輸錯誤概率為Pe=1-(1-p) n，每幀僅發(fā)生1 位錯誤的概率為Pe=Cn1p(1-p) n-1=np(1-p) n-1, 則1 位錯誤幀在總的錯誤幀中的概率為表2 為其Pe,Pe1,R 的模擬結(jié)果PPePe1R/%10-10.5217030.37200971.3010-20.06793470.065903697.0110-30.006979030.006958199.7010-40.000699790.0006995899.9710-50.0000699790.00

12、06995899.97表2 Pe,Pe1,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 ） ， 當p 0 時，R 1，表明當比特誤碼率p 足夠小的情況下，絕大多數(shù)信息幀錯誤是每幀1 位錯誤，因此糾正每幀1 位錯誤有實際應用價值。程序運行結(jié)果1初始化界面圖32正確編碼界面圖43正確譯碼界面圖5 4信息位有一位錯誤時的譯碼

13、界面圖65信息位有二位錯誤時的譯碼界面圖76信息位有三位錯誤時的譯碼界面圖8RS碼在現(xiàn)代通信系統(tǒng)中的應用幾乎所有的現(xiàn)代化通信系統(tǒng)都把糾錯編碼作為一個基本組成部分，RS碼由于具有強有力的糾錯功能，已經(jīng)被NASA、ESA、CCSDS等空間組織接受，用于空間信道糾錯。RS循環(huán)碼在車載無線通信、M元擴頻通信系統(tǒng)中的應用以及QAM系統(tǒng)等方面都有很廣泛的應用，可以說它已經(jīng)成為無線通信系統(tǒng)中不可或缺的一部分。實驗過程遇到的問題及解決方法 本次實驗讓我感覺非常棘手，一方面的原因是自己對信道編碼的不熟悉，之前做的實驗都是對信源進行編碼，現(xiàn)在是對信道進行編碼；另一方面是書本對于此部分的介紹內(nèi)容相對較少，要自己在網(wǎng)

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

15、技術(shù)及其應運大全M 電子工業(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(

16、); /*進行編碼*/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)=x3+x2+1*/ if(temp=2) temp=0; reg2=r

17、eg1+temp; if(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("_"); printf("n"); printf(" The information code output is: n"); for(i=0;i<7;i+)

18、 printf( " %d ",Outputi); /*輸出編碼結(jié)果*/ printf("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&

19、quot;,&Inputi); /*輸入接受碼組*/ for(i=0;i<7;i+) /*進入除法電路*/ 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) /*

20、輸入錯誤位數(shù)大于2位*/ printf(" "The error >=2" n"); getchar(); exit(0); printf("_n"); 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

21、=0; temp=reg2; x=0; /*S(x)進行自發(fā)運算以求得錯誤位數(shù)*/ reg2=temp+reg1; if(reg2=2)reg2=0; reg1=reg0; reg0=temp+x; /*輸出4位信息源*/ printf("The decoding bit4 is:"); for(i=0;i<4;i+) printf(" %d ",Outputi); printf("n"); printf("The Decoding bit7 is:"); /*輸出7位譯碼結(jié)果*/ for(i=0;i<7;i+) printf(" %d ",O