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

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

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

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

4、位，仍然是許用的循環(huán)碼組。 循環(huán)碼編碼原理（1） 有信息碼構(gòu)成信息多項(xiàng)式m(x)= +其中高冪次為k-1;（2） 用乘以信息多項(xiàng)式m(x)，得到的 m(x)最高冪次為n-1,該過程相當(dāng)于把信息嗎（，）移位到了碼字德前k個(gè)信息位，其后是r個(gè)全為零的監(jiān)督位;（3） 用g(x)除 m(x)得到余式r(x),其次數(shù)必小于g(x)的次數(shù)，即小于（n-k）,將此r(x)加于信息位后做監(jiān)督位，即將r(x)于 m(x)相加，得到的多項(xiàng)式必為一碼多項(xiàng)式。初始化根據(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)儲(chǔ)存c(x)圖2 編碼程序框圖循環(huán)碼的譯碼原理 糾錯(cuò)碼的譯碼是該編碼能否得到實(shí)際應(yīng)用的關(guān)鍵所在。譯碼器往往比編碼較難實(shí)現(xiàn)，對(duì)于糾錯(cuò)能力強(qiáng)的糾錯(cuò)碼更復(fù)雜。根據(jù)不同的糾錯(cuò)或檢錯(cuò)目的，循環(huán)碼譯碼器可分為用于糾錯(cuò)目的和用于檢錯(cuò)目的的循環(huán)碼譯碼器。 通常，將接收到的循環(huán)碼組進(jìn)行除法運(yùn)算，如果除盡，則說明正確傳輸；如果未除盡，則在寄存器中的內(nèi)容就是錯(cuò)誤圖樣，根據(jù)錯(cuò)誤圖樣可以確定一種邏輯，來確定差錯(cuò)的位置，從而達(dá)到糾錯(cuò)的目的。用于糾錯(cuò)目的的循環(huán)碼的譯碼算法比較復(fù)雜，感興趣的話可以參考一些參考書。而用于檢錯(cuò)目的循環(huán)碼，一般使用ARQ通信方式。檢測(cè)過程也是將接受到的碼組進(jìn)行除法運(yùn)算，

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

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

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

9、根據(jù)錯(cuò)誤圖樣表來糾正(7,4）循環(huán)碼中的一位錯(cuò)誤，其伴隨式如表1所示。BCH（7，4）循環(huán)碼錯(cuò)誤圖樣表：錯(cuò)誤圖樣錯(cuò)誤圖樣碼字伴隨式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)碼錯(cuò)誤圖樣表上式指出了系統(tǒng)循環(huán)碼的譯碼方法：將收到的碼字R(x) 用g(x) 去除，如果除盡則無錯(cuò)；否

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

11、215;100% = 57.1%。設(shè)傳輸信道的誤碼率為p ，據(jù)此設(shè)定信道模型存在如下關(guān)系：傳輸正確概率為(1 p)n，信息幀傳輸錯(cuò)誤概率為Pe=1-(1-p) n，每幀僅發(fā)生1 位錯(cuò)誤的概率為Pe=Cn1p(1-p) n-1=np(1-p) n-1, 則1 位錯(cuò)誤幀在總的錯(cuò)誤幀中的概率為表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 一定的條件下，信息幀錯(cuò)誤概率隨著比特誤碼率p 的增加而增加，最壞條件下幀錯(cuò)誤 概率幾乎為100%，此時(shí)系統(tǒng)失去通信能力。（2） 在典型的通信環(huán)境下（ p為10-3 10-5 5，幀長n =128 1024，np <1 ） ， 當(dāng)p 0 時(shí)，R 1，表明當(dāng)比特誤碼率p 足夠小的情況下，絕大多數(shù)信息幀錯(cuò)誤是每幀1 位錯(cuò)誤，因此糾正每幀1 位錯(cuò)誤有實(shí)際應(yīng)用價(jià)值。程序運(yùn)行結(jié)果1初始化界面圖32正確編碼界面圖43正確譯碼界面圖5 4信息位有一位錯(cuò)誤時(shí)的譯碼

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

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

15、技術(shù)及其應(yīng)運(yùn)大全M 電子工業(yè)出版社 1994.8附 錄/*(7,4)循環(huán)碼的編譯及糾檢錯(cuò)實(shí)現(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、); /*進(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; /*生成多項(xiàng)式為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; /*進(jìn)行編碼操作*/ 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(); /*譯碼并進(jìn)行糾檢錯(cuò)*/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+) /*進(jìn)入除法電路*/ temp=reg2; /*計(jì)算伴隨式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、輸入錯(cuò)誤位數(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+) /*糾正一位錯(cuò)誤*/ d=reg2*reg1*(!reg0); Outputi=d+Inputi; if(Outputi=2) Outputi

21、=0; temp=reg2; x=0; /*S(x)進(jìn)行自發(fā)運(yùn)算以求得錯(cuò)誤位數(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