(7,3)循環(huán)碼編譯碼軟件設(shè)計(jì)

摘要循環(huán)碼的編碼和譯碼都要用到由一個(gè)多項(xiàng)式去除另一個(gè)多項(xiàng)式。對(duì)于接收端譯碼的要求通常有兩個(gè)：檢錯(cuò)與糾錯(cuò)。本次課程設(shè)計(jì)運(yùn)用C語(yǔ)言設(shè)計(jì)的軟件系統(tǒng)能夠?qū)崿F(xiàn)（7，3）循環(huán)碼的編碼與在無(wú)差錯(cuò)和部分差錯(cuò)情況下的譯碼。關(guān)鍵字：循環(huán)碼編碼譯碼目錄TOC\o"1-5"\h\z\o"CurrentDocument"一、目的及意義1二、設(shè)計(jì)結(jié)果2\o"CurrentDocument"循環(huán)碼的介紹2循環(huán)碼的定義22.1.2循環(huán)碼的特點(diǎn)22.1.3循環(huán)碼的多項(xiàng)式表示32.1.4(n,k)循環(huán)碼的生成多項(xiàng)式3\o"CurrentDocument"循環(huán)碼編碼原理6\o"CurrentDocument"循環(huán)碼譯碼原理8\o"CurrentDocument"三、設(shè)計(jì)結(jié)果及分析93.1無(wú)差錯(cuò)編碼仿真結(jié)果9初始界面9正確編碼界面9無(wú)差錯(cuò)編碼仿真結(jié)果104．部分差錯(cuò)編碼圖115．離開(kāi)界面12\o"CurrentDocument"3.2運(yùn)行結(jié)果理論分析13\o"CurrentDocument"軟件可行性分析13四、總結(jié)14\o"CurrentDocument"參考文獻(xiàn)15\o"CurrentDocument"附錄16生成矩陣G后，可以通過(guò)線型變化，使之成為典型矩陣，這時(shí)就可以采用類(lèi)似監(jiān)督矩陣H。由于(n,k)是xn+1的因式，因此可令：h(x)=—H。由于(n,k)是xn+1的因式，因此可令：h(x)=—()=xk+hxk-i+?…+hx+1gG丿k-1115)這里h(x)稱為監(jiān)督多項(xiàng)式。監(jiān)督矩陣為:H(x)=Xn-k-1h*(x)]Xn-k-2h*(x)x-h*(x)

h*(x)h*(x)為h()的逆多項(xiàng)式。二xk+hxk-1+hxk-2hfh12k-1則對(duì)于(7,3)循環(huán)碼，若g(x)=x4+x3+x2+1，貝U：16)h(x)=x7f1=x3+x2+1nh*(x)=x3fxf1(x)=x6+x4+x3「1011000「x5+x3+x2nH=0101100x4+x2+x0010110x3+x+10001011循環(huán)碼編碼原理2.2.1多項(xiàng)式除法電路從前面的分析我們可以看出，循環(huán)碼的編碼和譯碼都要用到由一個(gè)多項(xiàng)式去除另一個(gè)多(x)項(xiàng)式，也主要利用電路來(lái)實(shí)現(xiàn)這種除法運(yùn)算下面先用一個(gè)具體的例子來(lái)說(shuō)明多項(xiàng)式除法電路的工作原理和運(yùn)算過(guò)程。設(shè)多項(xiàng)式為g(x)=x4+x3+x2+1，另一多項(xiàng)式m(x)=x6+x(x)x6fx4xf1=x2+x+1+—x4fx3fx2f1x4fx3fx2f1

其中，m(x)為被除式，gO為除式。商式q(x)q(x)=x2+x+1而余式r(x)為r(x)=x+118)19)輸出m(x18)19)輸出m(x)D一D01DD23圖2.g(x)=x4+x3+x2+1的除法電路圖中，符號(hào)D表示單級(jí)移位寄存器，一般可用D觸發(fā)器組成；十——表示模2圖中，符號(hào)D器，完成模2加法運(yùn)算。從圖中可以看出由四級(jí)(等于多項(xiàng)式g(x)的次數(shù))移位寄存器D0，DJD2，D3和三級(jí)模2加法器就組成g(x)=x4+x3+x2+1的除法電路。它實(shí)際上是一個(gè)具有反饋的線性移位寄存器。運(yùn)算過(guò)程如表2所示，從表中可以看出，只有等到第五次移位時(shí)才得到上式的首次系數(shù)，七位移位后除法運(yùn)算完畢，這時(shí)在DDDD中的存數(shù)即為余式01230-X3+0-x2+x+1的系數(shù)0011.表2.g(x)=x4+x3+x2+1除法電路運(yùn)算過(guò)程移位脈沖輸入m(x)移位后存數(shù)輸出移位后反饋0000000000011000000002°C)01000000031(X4)1010000004°C)0101000005°C)10011(2)101160(1)11111(x1)101170。)1100余式13商式1011由圖3運(yùn)算過(guò)程可以看出，在第一至第四次的移位中，除法電路只是接受輸入多項(xiàng)式m(x)中x6,x5,x4,x3的系數(shù)，只有在第5個(gè)移位脈沖到來(lái)以后，才正式開(kāi)始運(yùn)算。循環(huán)碼譯碼原理對(duì)于接收端譯碼的要求通常有兩個(gè)：檢錯(cuò)與糾錯(cuò)。達(dá)到檢錯(cuò)目的的譯碼十分簡(jiǎn)單，通過(guò)判斷接收到的碼組多項(xiàng)式是否能被生成多項(xiàng)式g(x)整除作為依據(jù)。如果除盡，則說(shuō)明正確傳輸；如果未除盡，則在寄存器中的內(nèi)容就是錯(cuò)誤圖樣，根據(jù)錯(cuò)誤圖樣可以確定一種邏輯，來(lái)確定差錯(cuò)的位置，從而達(dá)到糾錯(cuò)的目的。糾錯(cuò)碼的譯碼是該編碼能否得到實(shí)際應(yīng)用的關(guān)鍵所在。譯碼器往往比編碼較難實(shí)現(xiàn)，對(duì)于糾錯(cuò)能力強(qiáng)的糾錯(cuò)碼更復(fù)雜。而用于檢錯(cuò)目的循環(huán)碼，一般使用ARQ通信方式。檢測(cè)過(guò)程也是將接受到的碼組進(jìn)行除法運(yùn)算，如果除盡，則說(shuō)明傳輸無(wú)誤；如果未除盡，則表明傳輸出現(xiàn)差錯(cuò)，要求發(fā)送端重發(fā)用于這種目的的循環(huán)碼經(jīng)常被成為循環(huán)冗余校驗(yàn)碼，即CRC校驗(yàn)碼。CRC校驗(yàn)碼由于編碼電路、檢錯(cuò)電路簡(jiǎn)單且易于實(shí)現(xiàn)，因此得到廣泛的應(yīng)用。在通過(guò)MODEM傳輸文件的協(xié)議如ZMODEM、XMODEM協(xié)議中均用到了CRC校驗(yàn)技術(shù)。在磁盤(pán)、光盤(pán)介質(zhì)存儲(chǔ)技術(shù)中也使用該方法。當(dāng)碼字c通過(guò)噪聲信道傳送時(shí)，會(huì)受到干擾而產(chǎn)生錯(cuò)誤。如果信道產(chǎn)生的錯(cuò)誤圖樣是e，譯碼器收到的n重接受矢量是y則」表示為：TOC\o"1-5"\h\zy=c+e(20)上式也可以寫(xiě)成多項(xiàng)式形式：y(x)=c(x)+e(x)(21)譯碼器的任務(wù)就是從y(x)中得到e(x)，然后求的估值碼字d)=y(x)+eO(22)并從中得到信息組m(x)。循環(huán)碼譯碼可按以下三個(gè)步驟進(jìn)行：由接收到的y(x)，計(jì)算伴隨式s(x);根據(jù)sO伴隨式找出對(duì)應(yīng)的估值錯(cuò)誤圖樣e(x)；計(jì)算c(x)=y(x)+e(x)，得到估計(jì)碼字c(x)。若c(x)=c(x),則譯碼正確，否則，若c(xLc(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,3)循環(huán)碼的sG)共有23=8個(gè)可能的表達(dá)式，可以根據(jù)錯(cuò)誤圖樣表來(lái)糾正(7,3)循環(huán)碼中意味的錯(cuò)誤。

三．設(shè)計(jì)結(jié)果及分析3.1程序運(yùn)行結(jié)果1.初始界面圖3.初始化界面程序編譯無(wú)錯(cuò)誤后運(yùn)行，出現(xiàn)界面如上圖所示。2.正確編碼界面圖4.正確編碼界面在C環(huán)境下，輸入“C”，再輸入3位信息位，軟件執(zhí)行后輸出7位循環(huán)編碼。例如輸入的是110，系統(tǒng)輸出的是1101000.

圖5.正確編碼界面為檢驗(yàn)程序的正確性，再輸入一組3位信息位111，系統(tǒng)輸出7位循環(huán)碼為1110010.3.無(wú)差錯(cuò)編碼仿真結(jié)果圖6.無(wú)差錯(cuò)編碼仿真結(jié)果圖輸入“e”，系統(tǒng)將進(jìn)行譯碼操作，當(dāng)輸入的譯碼信息和編碼結(jié)果一樣時(shí)，系統(tǒng)就會(huì)把正確將信息位從該碼組譯出來(lái)。輸入7位為1101000，與編碼輸入的3個(gè)信息位的結(jié)果相同，檢驗(yàn)無(wú)錯(cuò)誤。

圖7.無(wú)差錯(cuò)編碼結(jié)果圖輸入7位1110010，輸出與譯碼結(jié)果輸入111圖7.無(wú)差錯(cuò)編碼結(jié)果圖4．部分差錯(cuò)編碼圖圖8.—位差錯(cuò)編碼圖當(dāng)輸入的譯碼信息與編碼的結(jié)果錯(cuò)一位碼時(shí)，系統(tǒng)就會(huì)檢測(cè)出該錯(cuò)誤并將其糾正過(guò)來(lái)，從而譯出真確的信息位。輸入7位1101010，譯碼結(jié)果為110，譯碼信息與編碼結(jié)果出現(xiàn)1位錯(cuò)誤，系統(tǒng)自動(dòng)將錯(cuò)誤改正，輸出為1101000。

圖9.一位差錯(cuò)編碼結(jié)果圖同上圖，輸入的7位為1110000，譯碼信息與編碼結(jié)果出現(xiàn)1位錯(cuò)誤，系統(tǒng)自動(dòng)改正輸出7位信息1110010。5．離開(kāi)界面圖10.離開(kāi)界面軟件檢驗(yàn)結(jié)束，輸入“e”，退出運(yùn)行系統(tǒng)。

3.2運(yùn)行結(jié)果理論分析由循環(huán)碼性質(zhì)可知，（7,3）循環(huán)碼的最小碼距d=4，可以檢測(cè)出小于等于3位錯(cuò)誤，糾正1位錯(cuò)誤，編碼效率為42.8%。設(shè)傳輸正確概率為p,據(jù)此設(shè)定信道模型存在如下關(guān)系:傳輸正確概率為6-p丄，信息傳輸錯(cuò)誤概率為p二1-6-），每幀僅發(fā)生1位錯(cuò)誤的概e率為：(P}IP率為：(P}IPE2丿X100%二X100%23)表3.模擬結(jié)果PPEPE1PE210-10.5217030.37200971.3010-20.06793470.065903697.0110-30.006979030.006958199.7010-40.000699790.0006995899.9710-50.0000699790.0006995899.97綜合上表的模擬結(jié)果和理論結(jié)果可以看出，通信系統(tǒng)的幀傳輸具有以下性質(zhì)：（1）在n—定的情況下，信息幀錯(cuò)誤傳輸概率隨著比特誤碼率的增加而增加，最壞情況下幀錯(cuò)誤概率幾乎為100%，此時(shí)系統(tǒng)失去通信能力。（2）在典型的通信環(huán)境下，當(dāng)比特誤碼率足夠小時(shí)，絕大多數(shù)信息幀錯(cuò)誤時(shí)每幀1位錯(cuò)誤，因此糾正每幀錯(cuò)誤有實(shí)用價(jià)值。3.3軟件可行性分析由上述結(jié)果可知，該軟件的操作方法為程序通過(guò)編譯運(yùn)行后，在C環(huán)境下，當(dāng)輸入c后按回車(chē)鍵，然后就會(huì)提示輸入信息，當(dāng)輸入3位的信息位再按回車(chē)鍵，系統(tǒng)就會(huì)輸出7位的循環(huán)編碼。當(dāng)輸入d后按回車(chē)鍵，系統(tǒng)會(huì)進(jìn)行譯碼的操作，當(dāng)輸入的譯碼信息和編碼結(jié)果一樣時(shí)，系統(tǒng)就會(huì)正確將信息位從該碼組譯出來(lái)。當(dāng)輸入的譯碼信息與編碼的結(jié)果錯(cuò)一位碼時(shí)，系統(tǒng)就會(huì)檢測(cè)出該錯(cuò)誤并將其糾正過(guò)來(lái)，從而譯出真確的信息位。當(dāng)輸入e后按回車(chē)，就會(huì)退出系統(tǒng)。由此可知，該系統(tǒng)能夠?qū)崿F(xiàn)（7，3）循環(huán)碼的編碼與在無(wú)差錯(cuò)和部分差錯(cuò)情況下的譯碼，因此該軟件具有可行性。四．總結(jié)通過(guò)本次課設(shè)，我對(duì)循環(huán)碼的編碼和譯碼的基本原理有了較深的理解，學(xué)到了很多的知識(shí)。循環(huán)碼是線性分組碼的一個(gè)重要子集，是目前研究得最成熟的一類(lèi)碼。它有許多特殊的代數(shù)性質(zhì)，這些性質(zhì)有助于按所要求的糾錯(cuò)能力系統(tǒng)地構(gòu)造這類(lèi)碼，且易于實(shí)現(xiàn)；同時(shí)循環(huán)碼的性能也較好，具有較強(qiáng)的檢錯(cuò)和糾錯(cuò)能力。我的題目是循環(huán)碼編譯碼的軟件設(shè)計(jì)，在這兩周中遇到了好多問(wèn)題，由于以前學(xué)習(xí)C語(yǔ)言沒(méi)有用心，編程的過(guò)程中出現(xiàn)了很多問(wèn)題。例如，由于輸入法的問(wèn)題導(dǎo)致程序出現(xiàn)了錯(cuò)誤后來(lái)，通過(guò)同學(xué)的幫助，發(fā)現(xiàn)并改正了這個(gè)錯(cuò)誤。最終實(shí)現(xiàn)了循環(huán)碼編譯碼的軟件設(shè)計(jì)。這次課設(shè)讓我受益匪淺，讓我理解了糾錯(cuò)碼的原理和循環(huán)冗余碼CRC的原理。真正地做到了輸入任意的數(shù)字信息序列，得出編碼結(jié)果。還學(xué)會(huì)了在無(wú)差錯(cuò)和部分差錯(cuò)的情況下進(jìn)行譯碼。這次設(shè)計(jì)不僅僅加深了對(duì)課程理論知識(shí)的了解，并更加熟悉了計(jì)算機(jī)語(yǔ)言，軟件的應(yīng)用。并讓我了解，學(xué)習(xí)知識(shí)不僅僅只在課本上，還有更多更廣的渠道獲得更寬廣的知識(shí)。最后感謝老師對(duì)我們的精心指導(dǎo)和幫助，感謝同學(xué)們對(duì)我的幫助。參考文獻(xiàn)樊昌信著.通信原理[M].國(guó)防工業(yè)出版社，1999,10.宋祖順著.現(xiàn)代通信原理[M].電子工業(yè)出版社,2001,2⑶黃亞新，米央著.信息編碼技術(shù)及其應(yīng)用大全[M].電子工業(yè)出版社，1994.8[4]孫麗華著.信息論與糾錯(cuò)編碼[M].電子工業(yè)出版社，2005,3⑸Proakis著，張力軍譯.數(shù)字通信（第四版）[M].電子工業(yè)出版社，2004,7⑹潘新民著.計(jì)算機(jī)通信技術(shù)[M].電子工業(yè)出版社，2003,7[7]賈世樓著.信息論理論基礎(chǔ)（第二版）.哈爾濱工業(yè)大學(xué)出版社附錄附錄循環(huán)碼編碼譯碼軟件設(shè)計(jì)程序/*(7,3)循環(huán)碼的編譯及糾檢錯(cuò)*/#include<stdio.h>#include<math.h>#include<stdlib.h>/*函數(shù)聲明*/voidBegin();voidCode();voidDecoding();/*主函數(shù)*/voidmain(){printf("\nThissoftwaremainfunctioniscarriesonthecodeandthedecodingto(7,3)cycliccode.\n");Begin();}/*進(jìn)行編碼*/voidCode()intinput[3];intoutput[7];intreg[3]={0,0,0};inttemp,i,j,t;printf("Pleaseinputtheinformationcode:");for(i=0;i<3;i++)scanf("%d",&input[i]);for(i=0;i<3;i++){temp=reg[2]+input[i];if(temp==2)temp=0;reg[2]=reg[1]+temp;/*輸入3位信息碼*//*進(jìn)行除法操作*//*生成多項(xiàng)式為g(x)=xA4+xA3+xA2+1*/if(reg[2]==2)reg[2]=0;reg[1]=reg[0];reg[0]=temp;}for(i=0;iv3;i++)output[i]=input[i];/*進(jìn)行編碼操作*/for(i=3;i<7;i++){temp=reg[2];for(j=2;j>0;j--)reg[j]=reg[j-1];reg[0]=0;output[i]=temp;}printf("");printf("\n");printf("Theinformationcodeoutputis:\n");for(i=0;i<7;i++)printf("%d",output[i]);/*輸出編碼結(jié)果*/printf("\n");printf("");printf("\n");Begin();}/*譯碼并進(jìn)行糾檢錯(cuò)*/voidDecoding(){intinput[7],output[7];intreg[4]={0,0,0,0};inttemp,i,d,x,p;printf("\nintputtheinformationcodeofbit7:");for(i=0;i<7;i++)scanf("%d",&input[i]);/*輸入接收碼組*/for(i=0;i<7;i++)/*進(jìn)入除法電路*/{temp=reg[2];reg[2]=reg[1]+temp;if(reg[2]==2)reg[2]=0;reg[1]=reg[0];reg[0]=temp+input[i];if(reg[0]==2)reg[0]=0;}p=reg[2]+2*reg[1]+3*reg[0];if(p!=1&&p!=2&&p!=3&&p!=7&&p!=8&&p!=13&&p!=14&&p!=0){/*輸入錯(cuò)誤位數(shù)大于2位*/printf("\"Theerror>=2\"\n");getchar();exit(0);}printf("\n");printf("s(x)=");for(i=3;i>=0;i--)printf("%d",reg[i]);printf("\n");for(i=0;i<7;i++)/*糾正一位錯(cuò)誤*/{d=reg[2]*reg[1]*(!reg[0]);output[i]=d+input[i];if(output[i]==2)