循環(huán)碼的原理及應(yīng)用

通信傳輸課程設(shè)計題目循環(huán)碼的原理及應(yīng)用 英文題目PrincipleandApplicationofCycIicCodes專業(yè)通信工程摘要循環(huán)碼是線性分組碼中最重要的一種子類，是目前研究得比較成熟的一類碼。它的檢、糾借能力較強，編碼和譯碼設(shè)備并不復(fù)雜，而且性能較好，不僅能糾正隨機錯誤，也能糾正突發(fā)錯誤。循環(huán)碼還有易于實現(xiàn)的特點，很容易用帶反饋的移位寄存器實現(xiàn)其硬件。循環(huán)碼具有許多特殊的代數(shù)性質(zhì)，這些性質(zhì)有助于按照要求的糾錯能力系統(tǒng)地構(gòu)造這類碼，并且簡化譯碼算法，目前發(fā)現(xiàn)的大部分線性碼與循環(huán)碼有密切關(guān)系正是由于循環(huán)碼具有碼的代數(shù)結(jié)構(gòu)清晰、性能較好、編譯碼簡單和易于實現(xiàn)的特點，因此在目前的計算機糾借系統(tǒng)中所使用的線性分組碼兒乎都是循環(huán)碼。關(guān)鍵字：循環(huán)碼；編碼；解碼；檢錯；糾錯；MatlabPrincipleandApplicationofCyclicCodesAbstractCycliccodeisalinearblockcodeofasub-classofthemostimportant,isthemorematurestudiedaclassofcodes.Itsreview,errorcorrectionability,codinganddecodingequipmentisnotcomplicated,andtheperformanceisbetter,notonlycancorrectrandomerrors,bursterrorscanbecorrected.Cycliccodealsofeatureseasytoimplement,itiseasytousefeedbackshiftregisterswiththehardware.Cycliccodehasmanyspecialalgebraicproperties,thesepropertiescontributetotheerrorcorrectionabilityofthesystemasrequiredtoconstructsuchcodes,andsimplifythedecodingalgorithm,currentlyfoundinmostofthecloselyrelatedlinearcodesandcycliccodespreciselybecausecycliccodeshaveaclearcodeofalgebraicstructure,betterperformance,encodinganddecodingfeaturessimpleandeasytoimplement,sointhepresentcomputersystemusedbytheerror-correctinglinearblockcodesarealmostalwayscycliccodes.Thisreportdetailsthedefinitionofcycliccodesgeneratedbyageneratorpolynomialmatrixandtheprocessofsystem-generatedmatrix,andwriteintheMatlabenvironment,thecyclecodeencoderanddecodertoachievetheencodinganddecodingfunction.Analysisanddiscussionofthiscodeerrorisfound,theabilitytocorrecterrors.Keywords:Cycliccodes;encoding;decoding;enordetection;collection;MatlabTOC\o"1-5"\h\z\o"CurrentDocument"摘要 IAbstract II\o"CurrentDocument"第一章緒論 1第二章算法原理 22.1循環(huán)碼定義 2\o"CurrentDocument"2.2循環(huán)碼的多項式描述 2\o"CurrentDocument"2.3生成多項式g(x)及生成矩陣G 2\o"CurrentDocument"2.4系統(tǒng)循環(huán)碼 3\o"CurrentDocument"2.5循環(huán)碼的編碼： 4\o"CurrentDocument"2.6循環(huán)碼的解碼 67循環(huán)碼檢錯與糾錯能力 7第三章循環(huán)碼的應(yīng)用 81循環(huán)碼在微機網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用 8\o"CurrentDocument"3.2循環(huán)碼在CDMA中的應(yīng)用 8\o"CurrentDocument"3.3循環(huán)碼在數(shù)字通信中的應(yīng)用 8\o"CurrentDocument"3.4在前向糾錯中的應(yīng)用 8\o"CurrentDocument"3.5循環(huán)碼在鐵路通訊安全中的應(yīng)用 9\o"CurrentDocument"參考文獻 11附錄AMatlab代碼直接實現(xiàn) 12附錄B拓展：以(7.3)碼為例 14第一章緒論數(shù)字信號在傳輸過程中，由于受到干擾的影響，碼元波形將變壞。接受端收到后可能發(fā)生錯誤判決。由乘性干擾引起的碼間串?dāng)_，可以采用均衡的辦法糾。而加性干擾的影響則需要用其他辦法解決。在設(shè)計數(shù)字通信系統(tǒng)時，應(yīng)該首先從合理選擇調(diào)制制度，解調(diào)方法以及發(fā)送功率等方面考慮，使加性干擾不足以影響達到誤碼率要求。在仍不能滿足要求時，就要考慮采用差錯控制措施。差錯控制編碼也叫糾借編碼，不同的編碼方法，有不同的檢借或糾借能力。循環(huán)碼是編碼方式的一種，檢錯率高.循環(huán)碼用來檢測隨機或突發(fā)錯誤是非常有效的.在通信軟件中大多數(shù)采用循環(huán)碼進行數(shù)據(jù)差錯控制。循環(huán)碼是線性碼的一個重要的子類，它有以下兩大特點：第一，碼的結(jié)構(gòu)可以用代數(shù)方法來構(gòu)造和分析，并且可以找到各種實用的譯碼方法；第二，由于其循環(huán)特性，編碼運算和伴隨式計算，可用反饋移位寄存器來實現(xiàn)，硬件實現(xiàn)簡單。循環(huán)碼是在嚴密的代數(shù)學(xué)理論基礎(chǔ)上建立起來的，這種碼的編碼和解碼設(shè)備都不太復(fù)雜，而且糾借的能力較強。顧名思義，循環(huán)碼除具有線性碼的一般性質(zhì)之外，還具有循環(huán)性，即任一碼組循環(huán)一位以后，仍為該碼中的一個碼組。第二章算法原理1循環(huán)碼定義設(shè)C使某（n,k）線性分組碼的碼字集合，如果對任C=（Cz，Cz，…，c°）€C,它的循環(huán)移位。⑴也屬于C,則稱該（n,k）碼為循環(huán)碼。該碼在結(jié)構(gòu)上有另外的限制，即一個碼字任意循環(huán)移位的結(jié)果仍是一個有效碼字。其特點是：（1）可以用反饋移位寄存器很容易實現(xiàn)編碼和伴隨式的計算；（2）由于循環(huán)碼有很多固有的代數(shù)結(jié)構(gòu)，從而可以找到各種簡單使用的譯碼辦法。如果一個（n,k）線性碼具有以下的屬性，則稱為循環(huán)碼：如果n元組c=｛c°q,…｝是子空間S的一個碼字，則經(jīng)過循環(huán)移位得到的點=｛%1，。。，一￡心｝也同樣是S中的一個碼字：或者，一般來說，經(jīng)過j次循環(huán)移位后得到的C°）= …,c,T，Co，Ci，…,Cfi｝也是S中的一個碼字。2.2循環(huán)碼的多項式描述碼字的多項式描述，一個n元碼字可以用一個次數(shù)不超過n-l的多項式唯一表示c=（C”_]C心…C]C°）,c（x）= +&_次'1+…++c° （1-1）其中，我們不關(guān)心X的具體位置，其次數(shù)只表示相應(yīng)碼元的位置。稱這樣的c（x）為C的碼字多項式。3生成多項式g（x）及生成矩陣G如果一種碼的所有碼多項式都是多項式g（x）的倍式，則稱g（x）為該碼的生成多項式。在循環(huán)碼中，次數(shù)最低的多項式（0除外）就是生成多項式歡力，

其他碼多項式都是其倍數(shù)。且該的階數(shù)為，?=〃-#,常數(shù)項為1,是x"+l的一個因式。為了尋求生成多項式，必須對x"+l進行因式分解。循環(huán)碼的生成矩陣多項式為:X-g(X)G(X)=(1-2)G(X)=(1-2)Xg(X)

g(X)然后將系數(shù)提出就得到生成矩陣G。4系統(tǒng)循環(huán)碼循環(huán)碼也可以構(gòu)成為系統(tǒng)循環(huán)碼。為方便系統(tǒng)碼的構(gòu)造，將消息多項式和碼式都記為高位在前，即=㈣T，吼，…,叫，)的消息多項式為心),=m0+m{x+…+(1-3)乂設(shè)碼式的高次慕部分等于m(x),即c(x)二+砂+ Cn_k+lxn~k+l+…+Cz廣=xn~k?川(x)+p(x) 8zp(x)<r=n-k(1-4)其中P(x)稱為校驗位多項式，由于碼式是生成式的倍式，所以p(x)+xim(x)=a(x)g(x)=0(modg(x))|(1-5)P(x)=-V血(X?(modg⑴)(1一6)因此循環(huán)碼的系統(tǒng)碼碼式為c(x)=x'm(x)-[x'm(x)(modg(x))](1-7)將循環(huán)碼的系統(tǒng)碼構(gòu)造步驟總結(jié)為：

多項式乘/〃'(*)=(丫〃?仃))多項式求模(余式)g3))=p(x)(1-8)多項式減3〃7(X))-P(X)=MX)如果令m3)為單項式丫+1,1=0,1,…,#—1對+i=o(x)g(x)+p.(%),礦p,?(x)vr(1-9)Ci(x)=p,(X)+xE(1-10)那么容易看到，G(*)對應(yīng)的向量Q,'=0,1,…—1是線性無關(guān)的，從而得到循環(huán)碼系統(tǒng)碼的生成矩陣G、為Poo PoiPio PnPoo PoiPio PnGs=Pk-1.0 Pk-1,1P0,『T 1 0 °\o"CurrentDocument"Pw010??? ??Pk-l/T001(1-11)5循環(huán)碼的編碼:利用生成多項式g(')實現(xiàn)編碼：如上所述，但循環(huán)碼的生成多項式g")確定時，碼就完全確定了?，F(xiàn)在討論生成多項式g(Q給定以后，如何實現(xiàn)循環(huán)碼的編碼問題。若己知

(2-1)g(*)=gxX"A+g〃_Slm_S]+..?glx+g0并設(shè)信息元多項式m(x)=mk一Ixk-1+mk一2xk-2+.../nlx+mO (2-2)(2-1)要編碼成系統(tǒng)循環(huán)碼形式，即碼字的最左邊k位是信息元，其余〃位是校驗元，則要用X乘以'〃(*),再加上校驗元多項式'(*),這樣得到的碼字多項式c(x)為c(x)=xn一k叭x)+r(x)=ink一\xn一1+ink一2xn-2+..jn0xn-k+m-k-Ixn-k-l+...rlx+rO(2-3)其中r(%)=77?-k-Ixn一S1+...小+rO其中c(x)=X 灰X)+Hx)=a(x)g(x)(2-4)c(x)=X 灰X)+Hx)=a(x)g(x)(2-4)(2-5)〃一Ac(x)=X〃?(工)+r(x)=° modg(x)注意到g(x)為H—k次多項式，而尸(x)最多為〃-k-1次多項式，必有r(x)=xm(x),modg(x) (2-6)即心)必是煩-如3除以g(x)的余式。式(2-6)指出了系統(tǒng)循環(huán)碼的編碼方法：首先將信息元多項式〃心。乘以it-k n-k(、 n-k,、x成為X"⑴，然后將X'心)除以生成多項式幺⑴得到余式心)，該余式就是校驗元多項式，從而得到碼字多項式c(x)=xn-kni^x)+r(x)。(2-7)綜上所述，系統(tǒng)循環(huán)碼的編碼問題，可以歸結(jié)為兩個多項式的除法運算，即將工〃一如")除以生成多項式g(Q得到余式,⑴的運算，因此研究多項式除法的電路實現(xiàn)是必要的。

2.6循環(huán)碼的解碼利用生成多項式g(x)實現(xiàn)編碼：如上所述，但循環(huán)碼的生成多項式83)確定時，碼就完全確定了?，F(xiàn)在討論生成多項式g")給定以后，如何實現(xiàn)循環(huán)碼的編碼問題。若己知 g(x)=gnkx~k+g—廣'+…g'X+g。(3-1)并設(shè)信息元多項式 ，心)=〃jL+fL 呵+〃7。 (3-2)(3-3)其中,0)= +-.-^+/oc")一定是g(x)的倍式，即c(x)=x"-。心)+尸0)=G0)g0)c(x)=xn^km(x)+r(x)=0 modg(x).注意到g(x)為〃-#次多項式，而'(X)最多為〃-AT次多項式，r(x)=x(3-3)其中,0)= +-.-^+/oc")一定是g(x)的倍式，即c(x)=x"-。心)+尸0)=G0)g0)c(x)=xn^km(x)+r(x)=0 modg(x).注意到g(x)為〃-#次多項式，而'(X)最多為〃-AT次多項式，r(x)=xn^km(x)modg(x)>即心)必是f⑴除以g⑴的余式。式(3-7)指出了系統(tǒng)循環(huán)碼的編碼方法：首先將信息元多項式〃'(X)乘以V-成為然后將'"〃[⑴除以生成多項式巴⑴得到余式心)，該余式就是校驗元多項式，從而得到碼字多項式c(x)=亳心)+r(x) (3_8)綜上所述，系統(tǒng)循環(huán)碼的編碼問題，可以歸結(jié)為兩個多項式的除法運算，即將、1〃7(乃除以生成多項式g")得到余式尸(X)的運算。(3-4)(3-5)(3-6)必有(3-7)2.7循環(huán)碼檢錯與糾錯能力由于循環(huán)碼是一種線性分組碼，所以其糾檢錯能力與線性分組碼相當(dāng)。而線性分組碼的最小距離可用來衡量碼的抗干擾能力，那么一個碼的最小距離就與它的糾檢借能力有關(guān)。定理：對于任一個線性分組碼，若要在碼字內(nèi)檢測e個錯誤，要求碼的最小距離糾正t個錯誤，要求碼的最小距離d22，+l；糾正t個錯誤同時檢測e 個錯誤，則要求d>t+e+Y,循環(huán)碼的譯碼分檢借譯碼與糾錯譯碼兩類。在無記憶信道上，對碼字C,差錯圖案。和接收向量r的多項式描述為TOC\o"1-5"\h\z尸(x)=c(x)+e(x) (4-1)定義,(X)的伴隨多項式為s(x)s(x)=r(x)(modg(x))2 r_i (4-2)=50+5{X+52X+…+S-X由于c(x)=a(x)g(x)=0(modg(x)),所以s(x)=e(x)(modg(x)) (4-3)由此可見，s(x)更0則一定有差錯產(chǎn)生，或說滿足e(x)(modg(x))壬0的差錯圖樣產(chǎn)生，它滿足e(x)(modg(x))=0。循環(huán)碼的檢借譯碼即是計算S(x)并判斷是否為0第三章循環(huán)碼的應(yīng)用1循環(huán)碼在微機網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用在微機局部網(wǎng)絡(luò)中由于信息傳輸所造成的錯誤會影響系統(tǒng)的工作性能，降低系統(tǒng)的靠性。因此采用循環(huán)碼編碼，進行數(shù)據(jù)傳輸，是提高系統(tǒng)性能和可靠性的重要措施。生成多項式G(X)的選取；并行信息傳輸技術(shù)；接收檢測技術(shù)；接收碼檢借電路；發(fā)現(xiàn)雙列、糾正單列錯碼的并行傳輸；2循環(huán)碼在CDMA中的應(yīng)用碼分多址是衛(wèi)星通信與移動電臺通信中的一種重要的多址方式，碼序列的選擇是CDMA系統(tǒng)中的重要因素.選擇碼序列的關(guān)鍵在于它們應(yīng)當(dāng)具有良好的相關(guān)系數(shù)H,同時還應(yīng)當(dāng)具有足夠的可供選擇的碼序列數(shù)目A(即地址數(shù)目)。循環(huán)碼是一種糾錯碼，通常只用來提高數(shù)據(jù)通信的可靠性，抵抗信道中的干擾和噪聲，然而下面的定理證明，某些循環(huán)碼同樣具有良好的相關(guān)系數(shù)H和足夠的碼序列數(shù)目，因而也適合用作CDMA中的碼序列。3循環(huán)碼在數(shù)字通信中的應(yīng)用循環(huán)碼是編碼方式的一種，檢錯率高.循環(huán)碼用來檢測隨機或突發(fā)錯誤是非常有效的.在通信軟件中大多數(shù)采用循環(huán)碼進行數(shù)據(jù)差錯控制。數(shù)字通信要求傳輸過程中所造成的數(shù)碼差借足夠低，引起傳輸差錯的根本原因是信道內(nèi)存在著噪聲，以及信道特性不理想所造成的碼間串?dāng)_，雖然我們可以通過提高通信系統(tǒng)的信噪比及抗噪聲性能，將差錯減小到一定程度，但要進一步提高通信系統(tǒng)的可靠性,就需要采用差錯控制技術(shù)。4在前向糾錯中的應(yīng)用循環(huán)碼是線性分組碼的一個重要子類，有嚴密的數(shù)學(xué)結(jié)構(gòu)，具有糾、檢錯能力，且編碼、解碼用軟件、硬件都容易實現(xiàn)。研究了循環(huán)碼實現(xiàn)的方法和應(yīng)用原理，結(jié)果表明，將該方法應(yīng)用于前向糾錯方式中，能大大提高通信質(zhì)量。數(shù)字通信要求傳輸過程中所造成的數(shù)碼差錯足夠低，引起傳輸差錯的根本原因是信道內(nèi)存在著噪聲，以及信道特性不理想所造成的碼間串?dāng)_。雖然可以通過提高通信系統(tǒng)的信噪比及抗噪聲性能，將差錯減小到一定程度，但要進一步提高通信系統(tǒng)的可靠性，就須采用差借控制技術(shù)。差錯控制的基本工作方式有4種，即前向糾錯、檢錯重發(fā)、信息反饋和混合糾錯,在測井系統(tǒng)中，采用單芯電纜進行數(shù)據(jù)通信，由于受傳輸線的限制，雙向信息傳輸不能同時進行，若采用信息反饋或檢錯重發(fā)或混合糾錯方式，傳輸線乂用作反饋信道，必然導(dǎo)致傳輸速率降低，為此,通信中采用前向糾錯方式。糾借編碼的目的在于利用編碼后碼字的規(guī)律性。應(yīng)用實例：在單芯電纜測井系統(tǒng)的數(shù)據(jù)傳輸中，應(yīng)用了循環(huán)碼糾錯編碼。生產(chǎn)測井中需要的參數(shù)主要有溫度、壓力、含水率、磁定位信號、流量等，由于油井環(huán)空測試只能在油井環(huán)空范圍內(nèi)進行，測井難度大大增加。鎧裝單芯電纜內(nèi)有一條電纜芯，與外層鎧裝構(gòu)成了兩股傳輸線,其中外層鎧裝在傳輸中可作地線。首先將各物理量轉(zhuǎn)變成數(shù)字信號，并將各種信號的傳送從時間上分開，從而實現(xiàn)了分時傳送。為了使傳輸信號具有同步能力，對傳輸數(shù)據(jù)進行了雙相位信號碼編碼；為了降低傳輸誤碼率，采用了（18,13）循環(huán)碼。該碼最小碼距6/nuii=3,編碼效率為*=昱><100%=72.2%,不僅能糾正一n18個錯誤，同時還能檢出一個錯誤。實驗表明，經(jīng)過500m單芯電纜的傳輸，由井下至地面發(fā)送數(shù)據(jù)波特率為5kb/s時，雖然在發(fā)送端設(shè)計了幅度均衡電路,但由于信道對不同頻率信號的衰減不同，造成“1”和“0”信號由井下發(fā)往地面后接收幅度不同。統(tǒng)計結(jié)果顯示，未采用循環(huán)碼糾借編碼時，誤碼率為0.3%,采用循環(huán)碼后，誤碼率降至0.01%以下。這樣大大提高了通信質(zhì)量，收到良好效果。3.5循環(huán)碼在鐵路通訊安全中的應(yīng)用隨著數(shù)字化技術(shù)在鐵路運輸系統(tǒng)中的應(yīng)用，要求數(shù)據(jù)傳輸具有高可靠性和低誤碼率。因此在通訊信道達不到要求時，需要應(yīng)用循環(huán)碼技術(shù)進行檢錯和糾錯。目前,很多成熟的數(shù)字化技術(shù)己經(jīng)在鐵路運輸中得到應(yīng)用，其中有許多系統(tǒng)需要對數(shù)據(jù)進行采集、傳輸和處理，要求數(shù)據(jù)在傳輸中具有高度的可靠性和很低的誤碼率。但由于鐵路行業(yè)的特殊性，有些通訊信道還達不到應(yīng)用系統(tǒng)的誤碼率要求，因此檢錯和糾錯成為系統(tǒng)應(yīng)用必須解決的問題，而循環(huán)碼是當(dāng)前應(yīng)用最多、最廣的檢借和糾借技術(shù)。循環(huán)碼在糾錯中的應(yīng)用：當(dāng)采用循環(huán)碼編碼后的碼在實際中發(fā)生變化時，如果改變的位數(shù)小于循環(huán)碼中非零編碼的最碼重半數(shù)或改變的連續(xù)位數(shù)在可糾正范圍內(nèi)，該編碼將不再屬于此循環(huán)碼集，在接收時就能檢測到此類錯誤，并通過還原得到原始編碼，從而達到糾借的目的。當(dāng)用循環(huán)碼進行糾錯時，可根據(jù)不同的使用場合使用不同的循環(huán)碼。如果使用循環(huán)碼來糾正隨機錯誤，那么就要求循環(huán)碼中具有最小碼重的非零編碼的碼重盡可能的大，因為其碼重決定了此循環(huán)碼糾正隨機錯誤的能力。如果使用循環(huán)碼來糾正突發(fā)錯誤，就要求循環(huán)碼中非零編碼的最長非零位數(shù)盡可能的少，因為它決定了此循環(huán)碼糾正突發(fā)錯誤的能力。循環(huán)碼在系統(tǒng)中的應(yīng)用：隨著鐵路調(diào)度管理信息系統(tǒng)(DMIS)、調(diào)度集中系統(tǒng)(CTC)的大面積的推廣使用，由于有些通訊信道還達不到相應(yīng)的誤碼率要求，在通訊中會出現(xiàn)一些誤碼，影響系統(tǒng)的正常使用，通過應(yīng)用循環(huán)碼檢錯功能，可以使通道質(zhì)量提升到滿足系統(tǒng)誤碼率的要求。在無線傳送方面，因為屬于開放式傳播，突發(fā)干擾較多，造成通訊中有較多的突發(fā)錯誤包，可使用循環(huán)碼進行檢錯，并進行適度的糾錯。例如，在無線車次號、無線調(diào)車防護、應(yīng)答器、道口預(yù)警等系統(tǒng)中采用循環(huán)碼糾錯方式，可以有效保證系統(tǒng)的正常通訊。參考文獻樊信昌，曹麗娜通信原理（第6版）國防工業(yè)出版社2006唐向宏等MATLAB及在電子信息類課程中的應(yīng)用電子工業(yè)出版社2005附錄AMatlab代碼直接實現(xiàn)clear;clc:closeall;%清屏N=U;%信息碼的行數(shù)n=7;%碼長k=4;%信息位長sig=randint(N,k)%信號碼元code二encode(sig,n,k,cyclic')』iM、編碼sigl=decode(code,n,k,'