循环码的原理及应用

通信传输课程设计题目循环码的原理及应用 英文题目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,'