循環碼的原理及應用

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

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

g(X)然后將系數提出就得到生成矩陣G。4系統循環碼循環碼也可以構成為系統循環碼。為方便系統碼的構造，將消息多項式和碼式都記為高位在前，即=㈣T，吼，…,叫，)的消息多項式為心),=m0+m{x+…+(1-3)乂設碼式的高次慕部分等于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)因此循環碼的系統碼碼式為c(x)=x'm(x)-[x'm(x)(modg(x))](1-7)將循環碼的系統碼構造步驟總結為：

多項式乘/〃'(*)=(丫〃?仃))多項式求模(余式)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(*)對應的向量Q,'=0,1,…—1是線性無關的，從而得到循環碼系統碼的生成矩陣G、為Poo PoiPio PnPoo PoiPio PnGs=Pk-1.0 Pk-1,1P0,『T 1 0 °\o"CurrentDocument"Pw010??? ??Pk-l/T001(1-11)5循環碼的編碼:利用生成多項式g(')實現編碼：如上所述，但循環碼的生成多項式g")確定時，碼就完全確定了。現在討論生成多項式g(Q給定以后，如何實現循環碼的編碼問題。若己知

(2-1)g(*)=gxX"A+g〃_Slm_S]+..?glx+g0并設信息元多項式m(x)=mk一Ixk-1+mk一2xk-2+.../nlx+mO (2-2)(2-1)要編碼成系統循環碼形式，即碼字的最左邊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)指出了系統循環碼的編碼方法：首先將信息元多項式〃心。乘以it-k n-k(、 n-k,、x成為X"⑴，然后將X'心)除以生成多項式幺⑴得到余式心)，該余式就是校驗元多項式，從而得到碼字多項式c(x)=xn-kni^x)+r(x)。(2-7)綜上所述，系統循環碼的編碼問題，可以歸結為兩個多項式的除法運算，即將工〃一如")除以生成多項式g(Q得到余式,⑴的運算，因此研究多項式除法的電路實現是必要的。

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