CRC性能分析与生成多项式选取的研究.docx

学校代号10462学号07083051004分类号TP3I1密级公开CRC性能分析及生成多项式选取的研究(坏七超±t鹭统硕士学位论文CRC性能分析及生成多项式选取的探讨魏艳郑州轻工业学院学位申请人：魏艳导师姓名及职称：马吉明教授专业名称：计算机应用技术学科门类：工学论文提交日期：2008年6月ADissertationSubmittedtoZhengzhouUniversityof1.ightIndustryfortheAcademicDegreeofMasterofEngineeringScienceAnalysisonCRCPerformanceandResearchonPolynomialSelectionCandidateiWeiYanSupervisor:MaJi-mingMajorjConiputerApplicationandTechnologySchlofComputerandCommunicationEngineeringZhengzhouUniversityof1.ightIndustryZhcngzhouJune2008郑州轻工业学院学位论文原创性声明本人慎重声明：所呈交的学位论文，是本人在导师的指导下，独立进行探讨工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发衣或撰写过的作品成果。对本文的探讨做出重要贡献的个人和集体，均已在文中作出了明确的声明并表示了谢意。本人学位论文与资料若有不实，情愿担当一切相关的法律贲任。学位论文作者签名：年月日郑州轻工业学院学位论文学问产权声明书本人完全了解学校有关爱护学问产权的规定，即：探讨生在校攻读学位期间论文工作的学问产权单位属于郑州轻工业学院。学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采纳影卬、缩印或扫描等复制于段保存和汇编本学位论文。同时，本人保证，毕业后结合学位论文探讨课题再撰写的文章一律注明作者单位为郑州轻工业学院。保密论文待解密后适用本声明。学位论文作者签名：指导老师签名：年月日摘要循环冗余校验码(CR。是一种常用的检错编码，它具有很强的检错实力，同时实现也较简洁，因此在各种网络系统中得到了广泛应用。在嵌入式网络系统和其他应用环境中，CRC常常用于信息传输过程中的差错检测。可是，目前常用的CRC生成多项式的差错检测实力并不是完全像人们认为的那么优秀，通过仿典试验探讨，发觉口前常用的生成多项式其综合检;则实力有确定的局限性，要么是检借实力比其他一些生成多项式差，要么就是检错实力仅仅是在某些数据帧长度表现的比较优秀.而且这些缺点和局限性缺似乎被忽视这在很大程度上是由于很少有资料和文献介绍以何种标精确定生成多项式的结构引起的.对于上面提出的问题，本文从常用的生成多项式的检错性能分析动身，得出两个重要的结论：(D生成多项式的比特数越大，其差错检测实力越强，漏检错误率越低：(2)生成多项式比特数相同的状况下，差错检测实力相同：漏检错误概率范用大致相同，但是对于不同的信道误码率，乂有不同的漏检错误概率。这两个结论对后面更加深化的探时供应了理论依据和支持。基于上述探讨结论，通过对嵌入式网络系统特性的探讨，在此应用背景卜;重点探讨了CRC的最小码距和漏检错误概率两个主要的性能影响因素对其检错性能的影响，选取部分3bitsl6bi(s的生成多项式为探讨样本，采纳仿真方法获得不同形式的生成多项式的最小码距和漏检错误概率的具体数据，在对性能因素分析基础上，结合仿或数据，提出了一种CRC生成多项式选取方法，一方面作为对不同结构的生成多项式直观具体的评价方法，另一方面在特定应用环境下性能更优的生成多项式供应了具体的。应用选取方法，以嵌入式网络系统常用的各种类型的生成多项式为主要考察样本，险证目前常用生成多项式存在一些局限性的同时，也筛选出了在嵌入式网络系统中性能较好的其它生成多项式，对今后工作的进步深化开展具有较好的参考价值。关键词I循环冗余校验码，生成多项式，战入式网络通信系统，仿真ABSTRACTCyclicRedundancyCode(CRC)providesafirstlineofdefenseagainstdatacorruptioninmanynetworksandiscommonlyusedforerrordetectioninembeddednetworksandotherapplications.Unfortunately,manycommonlyusedCRCpolynomialsprovidesignificantlylessc11ordetectioncapabilitythantheymight.Anexhaustiveexplorationrevealsthat11>stpreviouslypublishedCRCpolynomialsarceitherinferiortoalternativesorarconlygoodchoicesforparticularmessagelengths.Unfortunatelytheseshortcomingsandlimitationsoftenseemtobeoverlooked.ThisislargelybecausethereislittlepublishedguidanceandlessquantitativedataUPOnwhichtobasetradeofdecisions.'ohelpimprovethissituation,first,thisPaPergivesananalysisfortheerrordetectioncapabilityofcommonlyusedpolynomialsfromtheacademicandemulator.Itrevealstwoconclusions:(1)oneisthesizeofCRCsisrelatetothePerfbrmanee.(2)'hestructureofpolynomialsisalsorelatedtotheerrordetectionperformanceofpolynomials.Thispaperproposes“good、generalpurposeCRCsforerrordetectionapplicationsthatencompassmanycurrentandfutureembeddednetworkprotocols.Dcscribingapolynomialselectionprocessforembeddednetworkapplicatinsandproposesasetofgoodgeneralpurposepolynomials.Somenewpolynomialsprovidegoodperformancefor3-tol6-bilCRC-Throughtheparticularcmlationalprocess,whichvalidatesthenewpolynomialshavethestrengtherrordetectionabilityononehand,andontheotherhand,provesthefeasibilityandvalidityofthisneth<xl,provideusmuchmoreacademicanddataoourfuturework.Theapplicationoftheselectionvalidatesthelocalizationofstandards,andthenprovidessomegoodperformancepolymonailsforembeddednetworks.Keywords:CRC.Polynomials,EmbeddedNetworks.Simulation第一章绪论11.1 立题背景11.2 课题探讨的意义21.3 论文主要内容支配314小结4其次章差错限制理论和系统仿真探讨52.1 差错限制编码相关5数字通信系统及信道模型5差错限制系统和编码的分类6循环码理论7缩短循环码152.2 系统仿真探讨162.2.1 步骤162.2.2 MatIab/Simulink仿真工具182.2.3 S-函数简介192.3 小结20第三章循环冗余校验码的性能分析及仿真211.1 性能分析213.1.1CRC检错原理分析22差错检测实力分析22涉检错误概率分析231.2 仿真原理及方法24差错检测实力仿真24漏检错误率仿真261.3 仿真结果27差错检测实力仿真结果27漏检错误概率仿真结果281.4 结论29第四章探究生成多项式的选取标准314. 1应用背毋314.1 性能影响因素分析32汉明距离，码重以及漏枪错误概率的关系32仿真数据分析334.2 联入式网络系统中生成多项式的选取35生成多项式选取方法的理论依据和设计思想35生成多项式选取方法的具体步骤364.3 结论39第五章生成多项式选取方法的应用405. 1方法的应用结果405.1 方法应用结果的分析415. 2.18bits生成多项式的性能比较416. 2.212bits生成多项式的性能比蛟437. 2.316bits生成多项式的性能比较47小结515.2 结论51第六章结论及展望546. 1论文主要完成的工作546.1 存在的问Sg和不足546.2 小结55参考文献56附录攻读硕士学位期间发表论文书目60致谢62第一章绪论1.1 立题背景提高信息传输的牢靠性和有效性，始终是通信领域探讨和追求的目标。1948年，现代信息理论的莫基人C.E.Shannon在他的开创性论文“Amathematicalthcorj,ofCOmmUniCaIiOn”"2中首次阐明白在有噪信道中实现牢靠通信的方法，提出了闻名的有噪信道编码定理，通过某种编码方法，使得随若码长的蝌加误码率达到的彦小。该理论奠定了差错限制码的基石。香农信道编码定理：1) R<C,当采纳最大似然洋码时，能以随意小的错误率Pr(E)传递速率为R的信息.码长N要足够大.2) R>C,存在有效的编码方法实现满足Pb要求的速率为R的信息。香农证明码长N足够大时，随机选择的码有高概率为好码。其中，C是信道容量，R是码率，高斯白噪声信道的信道容量C的计算方法如下：C=IVIog,(l+-XWr5)(1-1)式中，W是信道所供应的带宽，代=ES是信号功率，ES是信号能量，是分组信号的持续时间即信号宽度，抬/W是单位频带的信号功率，NO是单位频带的噪声功率，弋/WV11是信噪比。从对Shannon信道编码定理的分析中可以看出，Shannon在对定理的证明中引用了三个基本条件：I)采纳随机编码、译码方式；3) 编译码长度1.-无穷，即码长无限；4) 译码采纳最大似然译码算法。也就是说，在信道传输速率R不超过信道容量C的前提下，只有在码组长度无限长的码集合中随机的选择编码码字并且在接收端采纳最大似然译码算法时，才能使误码率接近零。但是，最大似然译码的困难性随编码长度指数增加，当编码码长趋于无穷大时，最大似然洋码是不行能实现的。因此，构造物理可实现的编码方案及找寻有效译码算法始终是信道编码理论与技术探讨的中心任务。香农编码定理以后汉明(Hamming),斯列宾(SlePian),普兰奇(Prange)等学拧专家，在50年头初，依据香农的思想，给出了一系列设计“好”码和有效译码的方法以)。纠借码越来越受到大家的重视，同时无论在理论上还是实际中都得到了飞速发展。目前常用的纠错编码按其码字结构形式和对信息序列处理方式的不同可分为两大类：分组码和卷积码。分组码是把信息序列按k位信息-组进行分组,每k位信息通过编码器变换成码长为n(n>k)的码字，每个码字的n位码元仅与本组k位信息有关，与其他码组无关。卷积码是把信息序列以k个为一组，通过编码器输出长为n(nk)的一个子码。但是该子码的n-k个校验元不仅与本子码的信息元有关，而且也与其前m个子码的信息元有关。在通信系统中应用最广泛的分组码是汉明码和循环码IS句，1950年R.Hamming提出了第一个差错限制编码方案一一二进制汉明码，多进制汉明码是由戈莱和科克(Cgke)发展而来的。1957年普兰奇(Pnlnge)首先引入外府环码的概念及码多项式的表示方法，自此以后，分组码的理论，特殊是循环码的理论得到快速发展.循环码的显著优点是，它的编码和伴随式计算可以用简洁的具有反馈连接的寄存器来实现。另外,由于循环码有良好的代数特性，人们可以用“代数”这个强有力的数学工具对循环码进行深化探讨，并可找到各种简洁有效的译码方法。在实际应用中，常对个循环码的码长和信息有所约束，因此缩短循环码随之产生，它是在(n,k)循环码的2,个码字中选择出前i个信息位均为0值的码字(有2一个这样的码字)作为(n-i,k-i)缩短循环码的码字。这样就可以省去若干位不用传输，提高传输的效率。循环冗余校验码是一类应用范围比较广的缩短循环码，而且本版上是一种系统码。随着它的广泛应用，有关它的原理、性能、理论分析及应用等各个方面的探讨都取得了不同程度的进展。1.2 课题探讨的意义目前循环冗余校验码是探讨比较丰富的一个课题，目前两个主要的探讨手段是理论分析和计算机仿真分析。尽管国内外关于这类码的探讨成果已经特别丰富，但是大多只是在既有标准上提出一些提高性能的方法，一些学术期刊出现过运用理论分析的方法对这类码的性能进行探讨的文章，探讨的热点也是聚集在有关循环冗余校验码的编译码算法方面，希望通过各种高效的算法提高循环冗余校验码的校验速率.例如：CRC校验在USB限制器设计中的实现：EpON中校验码的并行算法实现：/兆以太嗣CRC的算法与VII设计与实现等件式这些若眼于探讨如何提高CRC校验算法的效率以及具体的算法实现方面，无论是应用范闱和探讨深度都有确定的局限性。因此深化的对这类编码性能进行探讨就显得很有必要。很少有人真正从CRC的校验性能方面进行探讨，主要是由干目前为止关于生成多项式选取标准的文献或资料信息供应的比较少，仃些文章中的理论分析并没仃描述得特别清楚明白，雄以让人接着探讨卜去。人们并不真正了解为什么要选择目前常用的CRC码为标准的生成多项式，因此只有通过分析现有的牛成多项式的性能因素，才能更好的分析出选择生成多项式的标准，从而为今后的生成多项式的探讨供应更多更全面的探讨资料，进而有机会构造出性能更优越的生成多项式。同时由于理论探讨和实现之间巨大差距的存在，单从理论上进行设计和分析是不够的。仿其探讨将搭起理论和实现之间的桥梁，对编码的性能探讨具有实际的指导意义。1.3 论文主要内容支配本文主要从CRC的性能理论分析入手，考察其各种性能影响因素，由于理论分析的方法只能获得宏观相识，所以借助仿真软件进行限验可以避开硬件试验的条件问题、编理试验的难度问题,从而可以快速、可视化地视察试验结果,具有省时低耗的优势。首先通过对目前几种标准的CRC码性能的分析和总结，为后面的生成多项式的相关探讨供应了可行性理论支持。其次结合嵌入式网络通信系统的应用背景对3bits-l6bits的生成多项式进行全面、具体的探讨，提出一种选取“好”码的方法。方法的提出岩重考虑在嵌入式网络通信系统的应用环境中生成多项式能达到最低漏检率，而且在较大的数据帧长度范围内都能够保持较好的校验性能。最终通过仿真模型进步验证了这些“好”码的性能,而Il从另个角度也证明白这种方法的可行性，不仅拓展了探讨思路，也为下步的探讨奠定了理论基础。本文主要内容支配如E：第一章介绍课题探讨的背景和意义，及论文的主要内容，支配。第二率介绍差错限制理论和系统仿真的相关内容。第三章利用近世代数多项式理论对常用生成多项式性能进行分析，同时采纳仿真试验的方法给出了不同标准的CRC码得检借实力和不行检测率、信道误码率之间的关系图，并从关系图中总结出了两个有关生成多项式选取的结论。第四章以第三章的探讨内容为基础和依据，扩展探讨范围，以嵌入式网络通信系统为应用背景，考虑在此背景下，影响生成多顼式性能的主要因素.依据对各种因素的分析和仿真，提出f一种选取性能志向的生成多项式的方法，方法的提出扩展f对CRC性能探讨的范围，为更深化探讨CRC码性能打下基训。第五章利用上章提出的选取方法，采纳具体的仿真方法，以嵌入式网络系统环境中常见的生成多项式类型为考察对象，在验证目前标准生成多项式局限性的同时,也筛选出了些性能较好的其它生成多项式。第六章总结整个论文的探讨内容及结论，指出今后工作的方向和任务。1.4 小结本章若重介绍r课题的探讨背景和意义，并提出J'目前主要相关探讨所存在的问题.基于存在的问题,介绍了课题的主要探讨内容。最终绐出了论文的主要章节.支配。第二章差错限制理论和系统仿真探讨2.1差缙限制编码相关21.1收字通信系统及值道模型对于一个数字通信系统，如通信、雷达、遥测遥感、数字计算机的存储系统和内部运算以及计算机之间的数据传输等，都可归结为图2”所示的模型。图2-1数字通伯系统模型Fig.2-1ThemodelofdigitalC(HnnIUniCdIionsystem依据实际信道的统计特性可以划分为几种志向信道模型“3：二进制硬判决状况下，信道的信道转移概率矩阵可用P=AxiA11"AuAii.PioAiJ1.AuI-PhJ(2-1)表示。假如八”<>/%,则称这种信道为二进制对称信道，简称BSC.BSC为随机信道。否则，称为不对称信道。若八”=M»=0,则称为Z信道。假如信道输入是二进制符号，而输山是离散的"("=/严2)进制符号,其信道转移概率矩阵为“Jp(OIO)MIo).p(<7-l0)-1.Xn)MII)X<-11>)J(2-2)则这种信道为离散无记忆信道，简称DMC.BSC,DMC可以用图2-2表示.图2-2协机信道和离散无记忆信道Pig.2-2Randomchannelinddiscretenomemorychannel在作删除判决状况下，信道可用图2-3所示的模型表示，称为二进制删除信道，简称BEC图2-3二进制删除信道Fig.2-3Binardeletechannel这三种信道模型都是实际信道的简化模皇，探讨中针对不同的传输特性，选用不同的模型。例如卫星信道一般可以看做BSJ2.1.2差借限制系统和编码的分类在数字通信系统中，差错限制的方式有以下三类重传反馈方式(ARQ)。通信系统中的ARQ方式的工作原理可以描述为：发送端发出检错码，接收端收到码元后，在译码涔依据该码的编码规则，判决收到的码序列中有无错误产生，并通过反馈信道把判决结果用判决信号告知发送端。发送端依据这些判决信号，把接收端认为有钳的信息再次发送，直到接收端认为正确接收为止。ARQ方式一般适用于点对点的通信，译码设备较简洁；检错码的检错实力比纠错码的纠错实力要高的多，因而整个系统的纠钳实力较强：它的检错码的检错实力于信道干扰的变更基本无关，所以适用性较强.前向纠错方式(FEC)1.FEC方式的工作原理为：发送端发送纠错码，接收端收到码字后，通过纠错译码器不仅能自动地发觉错误，而且能自动地订正接收码字传输中的错误。因此，卜EC方式具有对多用户的同播通信，洋码的实时性较好,限制电路简洁的优点。但同时也存在译码设备比较困难，所用纠错码必需与信道的干扰状况相匹配，适应性差，编码效率较低的缺点。联合纠错方式(HFC：)。HFC方式是发送端发送的码不仅能够被检测出错误，而口具有确定的纠错实力。接收端收到码序列以后，首先检测错误状况，假如在纠错码的纠错实力以内,则自动进行纠错.假如错误很多，超过码的纠错实力，但能检测出来，则接收端通过反馈信息，要求发端重新传送有错的信息。HFC克服了FEC方式译码设备困难和ARQ方式实时性差的缺点，具仃很强的纠错实力和适应性,因此得到广泛的应用。上述三种方式，都要用编码来赋以差错限制功能，不论是自动纠错或者是只检钳然后通过反馈重传来纠钳的码字，统称之为纠错编码。依据不同的分类标准编码也会有不同的分类方法，具体分类如图2-4所示：信道编码图2-4信道编码分类Fig.24Categoryofchannelcoding由图2-4可以看出依据监督元与信息组之间的关系,纠错编码可分为分组码和卷积码两大类。其中分组码是把信息序列按k位信息组进行分组，每k位信息通过编码器变换成码长为n(n>k)的码字，每个码字的n位码元仅与本组k位信息有关，与其他码组无关。而卷枳码虽然也是把信息序列按h位信息一组进行分段，每段。位信息通过编码器相应输出一个长为n"mAk)的码段，但.是该码段不仅与本段输入的k,位信息有关,而且也与前若干段信息元有关。本文主要探讨的是分组码的一类至要的分支一一循环码，它是线性分组码的一个子集，应用特别广泛。21.3环码理论循环码是线性分组码的一个重要子集，它有很多特殊的代数性质，这理性质有助于按所要求的纠错实力系统地构造这类码.Il易于实现：同时循环码的性能也较好，具有较强的检错和纠错实力。它的编译码电路简洁易于实现，循环冗余码与循环码有亲密的关系，因此循环码特殊引人注目，对它的探讨也比较深化和系统。卜.面从编码理论方面探讨循环码。循环码的结构完全建立在有限域的基础上，可以用近世代数的方法精确描述。循环码是1957年由普兰奇提出的，此后几十年中得到了充分探讨和发展。起初，人们相识到并感爱好的是循环码的外在特点，即循环码码字的循环移位仍旧是码字，这个特点给循环码的编译码实现带来r便利.在以后的实践中，人们从循环群的角度，在代数结构、纠错性能限制等方面找到r循环码更加吸引人的优越之处“目前，实际差错限制系统中所运用的线性分组码几乎都是循环码或循环码的子类。2.1.3.1几个基本概念I)线性分组码线性分组码中的线性是指码字中码元间的约束关系是线性的。而分组则是对编码方法而言的。即编码时将每k个信息位分为一组进行独立处理，变换成长度为n(n>k)的二进制码字.(n,k)线性分组科是把信息流的每k个码元分成一组，通过线性变换，映射成由n个码元组成的码字.从空间角度，每个码字可看成是n维线性空间中的一个矢量，n个科元正是n个矢量元素码元的值取自字符集X=IXO,x,xg,当q=2时是二进制码,当q>2时是q进制码。二元分组码是最基本、最重要的。k位二进制信息组仃种组合，构成GF(2)上的k维k重矢任空间：而n位二进制数共有乃种组合，构成GF(2)上的n维n重矢量空间，通常2n>2<纠错编码的任务是在n维n重矢量空间的211种可能组合选择2上个构成一个子空间，或称许用码码集C,然后设法将k比特信息组一一对应的映射到许用码码集C,然后设法将k比特信息组一一对应地映射到许用码码集C,不同的编码身法对应不同的码集以及不同的映射算法，把这样得到的码称为(n.k)线性分组码。不编码时,一个二进制码元可携带I比特信息(传信率为Ib/符号)；编码后，n个二进制码元携带k比特信息(传信率为(kn)b符号)。定义kn=Rc为二元分组码的码率，或者说是效率，在GF(2)上，汉明重量：n重矢量R中，非零元素的个数称为该n重的汉明距离，简称重量，用W(r)表示.汉明距离：逐位比较两个n重矢量Rl和R2的对应各位，其中取值不同的元素个数称为RI和R2的汉明距离，用d(Rl,R2)表示。2)信息码元与监督码元信息码元乂称为信息序列或信息位,这是发端由信息编码后得到的被传送的信息数据比特，通常以k表示。由信息码元组成的信息组为：M=（mz,mm,.nw）在二元码的状况卜.，每个信息码元m的取值只有。和I,故总的信息码字数共有2卜个，即不同信息吗元取值的组合共有21.监督码元又称为监督位或附加数据比特，这是为了检纠错码而在信道编码时加入的推断数据位。通常以r表示，即为：n=k+r或r=n-k.经过分组编码后的编码又称为（n.k）码，即表示总码长为n位，其中信息码长（码元数）为k位，监督码长（码元数）为r=n-k通常称其为长为n的码字。3）许用码字与禁用码字信道编码后的总码长为n,总的码字数应为21.即为信Z其中被传送的信息码字有2%通常称为许用码字：其余的码字共有2"减去21不传送，称为禁用码字。发送端误码限制编码的任务正是寻求某种规则从总码字2。中选出许用码字：而接收端译码的任务则是利用相应的规则来推断及校正收到的码字是否符合许用码字。通常乂把信息码元数目k与编码后的总码元数目（码字长度）n之比称为信道编码的编码效率或编码速率，表示为：R=kn=k（k+r）.这是衡量纠错码性能的一个重要指标，一般状况E，监督位越多（即r越大），检纠错实力越强，但相应的编码效率也随之降低了。4）码重与码距，最小码距在分组编码后，每个码字中码元为''I”的数目称为码的重量，筒称码全。两个码字对应位置上取值不同（I或0）的位数，称为码字的距离，简称码距，又称汉明距离，通常用d表示。例如:OOO与IOI之间的码距d=2：OoO与Ill之间的码距d=3.对于（n,k）码，许用码字为2卜个，各码字之间距离最小值称为最小码距。2.1.3.2检错和纠错的基本原理首先以三位二进制码组为例，说明检错纠错的基本原理。三位二进制码元共有8种可能的组合：00。、OOI、0I0,OlkI00.IO1.IIO.Ill,假如这8种码组可能传递消息，若在传输过程中发生一个误码，则一种码组会错误地变成另一种码组。由于每一种码组都可能出现，没有多余的信息量，因此接收端不行能发觉错误，以为发送的就是另一种码组.但若我们只选其中（X）、01,1（）,Il四种信息，而第3位是附加的，这位附加的监督码元与前面两位码元一起，保证科组中“I”码的个数为偶数.除上述4种许用码组以外的另外4种不满足这种校瞪关系的码组即为上面提到的禁用码组，在编码后的发送码元中是不行能出现的。接收时旦出现这些禁用码组，就表明传输过程中发生了错误。用这种简洁的校验关系可以发觉个和三个错误，但不能订正错误。例如，当接收到的码组为010时，我们可以断定这是禁用码组，但无法推断原来是表2-1一种(7,3)循环码的全部码字Tab.2-1Akindof(7.3)Circlecode序号码字信息位aa疝监督位“阳启Ian100000002001Olll3010HlO401110015100IOll6101HOO711001018IllOOlO为J'利用代数理论探讨循环码，可以将码字用代数多项式来表示，这个多项式被称为码多项式，对手许用循环码A=(u,aN,a,ao),可以将它的码多项式表示为：(x)=a,l.lxnl+a_2.xn2+wl.v+a0(2-3)对于二进制码字，多项式的每个系数不是。就是I，X仅是码元位置的标记。因此,这里并不关切X的取值。而表2-1的任一码字可以表示为：A(X)=af,x6+5"5+«0例如，在表中第七码字可以表示为：47fx)=l6+lxx5+0×x4+0r5+lxx2+0×x+1=x6+x5+x2+l在整数运算中,有模n运算。例如，在模2运算中，有1+1=2三0(模2),l+2=3三l(模2),2x3=6三0(模2)等。因此,若一个整数m可以表示为：巴=Q+'"(2-4)其中，p<n,Q是整数则在模n运算下，有m三p(模n),也就是说，在模n运算下，整数m等于其被n除所得的余数。在码多项式运算中也有类似的按模运算法则。若随意多项式F(X)被一个n次多项式N(X)除,得到商式Q(X)和一个次数小于n的余式R(x),也就是说/Y.V)NgQ()-*IHX)N(X)(2-5)则可以写为：F(x)三R(x)(模N(x)这时，码多项式系数仍按模2运算，即只取值0和I,假设:计算12+l除以X'+I的值可得:留意，在上述运算中，由于是模2运算，因此，加法和减法是等价的，在式子中通常用加法运莫符。这样也可以表示为：+J+1三/+x+l(模J+)在循环码中，若A(X)是一个长为n的许用码字，则X1A(X)在按模xn+1运兑3亦是一个许用码字，也就是假如：MA(X)三ApX)亦是一个许用码字，并且，ATX)正是A(X)代表的码字向左循环移位i次的结果。例如，由制刀=0+/+/+】表示的循环码，其码长n=7,现给定i=3,则：x,-47(A-)=.r36+x5+x2+l)=(-9+-8+-5+x3)=fri+x3+a-2+xX梗V7+”其对应的码字为0101110,它正是表中第3码字。上述分析和演算可以得到一个重要的结论：一个长度为n的循环码，它必为按模(x"l)运算的个余式。2.1.3.4生成多项式和生成矩阵循环码除全0码字外的其余码字称为生成多项式，用g(x)表示。可以证明生成多项式g(x)具有以下特性：g(x)是一个常数项为1的r=n-k次多项式：g(x)是xrl的一个因式：该循环码中其他码多项式都是g(x)的倍式。为了保证构成的生成矩阵G的各行线性不相关，通常用g(x)来构造生成矩阵，这时，生成矩阵G(X)可以表示成为：xtig(xi.xt2gfx>CCJ=.(2-6)Xg(X)&(X).其中MM=XZ+qx+l,因此，一旦生成多项式g(x)确定以后，该循环码/时工)的生成矩阵就可以确定，从而该循环码的全部码字就可以确定。明显，GfG=.不符合G=EQl形式，所以此生成矩阵不是典型形式，不过，可以通过简沾的代数变换将它变成典型矩阵。现在以表的(7.3)循环码为例，来构造它的生成矩阵和生成多项式，这个循环码主要参数为：n=7,k=3,r=4,从表中可以看到，其生.成多项式可以用第1码字构造：g(x)A(XJ-'+X+12g().r6+X4+3A2G(X)=用O=X5+X3+X2+XR(X).V4+X2+X+1IOl11G=010111010111在上面的例子中，是利用表给出的(7,3)循环码的全部码字，构造J'它的生成多项式和生成矩阵。但在实际循环码设计过程中，通常只给出码长和信息位数，这就须要设计生成多项式和生成矩阵，这时可以利用g(x)所具有基本特性进行设计。首先，生成多项式g(x)是d+1的个冈式，其次g(x)是个r次闪式，因此，就可以先对进行冈式分解，找到他的r次因式。下面仍以(7.3)循环码为例进行分析。第步：对丁+1进行因式分解得:+l=fx+iX+x2+IJ(.r3+x+其次步：构造生成多项式g(x)为了求(7.3)循环码的生成多项式g(x),要从式/+I=*+nF+F+Ux+x+I)中找到knk次的因子，不难看出，这样的因子有两个，即：fx+lXj÷.v2+U-.r4+.r2+x+l(x+1Xx3+xj+l>-.v4+x3+xj+1；以上两式都可作为生成多项式用。不过，选用的生成多项式不同，产生出的循环码码字就不同。用式仆+I"/+/+"-/+/+一作为生成多项式产生的循环码即为表所列。当然，在得到生成矩阵G和监笆矩阵H的关系，得到监督矩阵I1.除此之外，还可以利用循环码的特点来确定监督矩阵I1.由于(n.k)循环码中g(x)是1+i的因式,因此可令:h(.V)=-_里=xk+HH.v+1(2-7)g(X)tl-2g(x)这里h(x)称为监督多项式，与GUJ=.所表示的G(X)相对应，监督矩阵表示XXfXJX(X)为:设发送的码字为C(X),收到的码字为U(X).假如设幻=WX)-字外是个长为b的成区间差错模式，则称C(X)在传送的过程中出现一个长为b的成区间错误。定理加叽设C是一个q元®nr循环码,则C可以检查出随意长为，"的成区间错误。证明设“)=c1>+平+*广，凡是发送的码字，在传送的过程中出现了一个长BMr的成区间错误，切=%+3卅*&,则C(X)存在相连的b个系数，记为第m+l,m+2,，m+b个，使得当j<m+或/>,+/>时，町=0,而仁m。出2工O，于是，dXj=<+%+6小""=x""%m+/.2X+J./"J令)=emt,l+emi,2x+emt,fh'则deg(a(x)=b-lr-l«其中deg(f(x)是求多项式的次数其中g(x)循环循C的生成多项式,则deg(g(x)=r且g(R不能整除川外。因为g(x)的零次项的系数不为零,所以g(x)不能整除e(x),否贝4,假设奸x“3即x(xm-la(x),因为勿必与v'"+互素,所以W斗"八因此,我们有g(x)不能整除c(x)+e(x>.这说明c(x)+e(x)不是码字，即循环码C可以查出长为方r的成区间错误。21.4丽i环码循环码生成多项式必是x"-1的因子，但在绝大部分(n,k)x-的因式相对而言数目不多，所能组合出来的因式次数也是有限的，并不是任何(n,k)取值都能产生循环码.为了满足实际中对1】和卜的多种要求和限制，同一般线性分组码一样，循环码也常常运用缩短码的形式，即缩短循环码.缩短循环码是在(nM循环码的2k个码字中选择出前i个信息位均为O值的码字作为(n-ik-i)缩短循环码的码字。缩短循环码的码集是(n,k)循环码集的了集，因此它的码字也确定能被g(x)除尽，即它是g(x)的倍式。缩短循环码的全部码多项式的次数不会超过n-il次：反之，全部次数小于等于ni次且能被g(x)整除的多项式必是(ni.k-i)缩短码的码多项式。由于缩短循环码是选择前i个信息位均为O值的码字，删去前i位而缩短的，在此过程中没有捌除过“I”，因此缩短码码址不变，于是(n-i,k-i)缩短循环码的绢错实力与原(n.k)循环码相同，只是编码率降低了。缩短循环码的生成矩阵和校验矩阵可在原循环码的生成矩阵和校验矩阵的基础上去掉一部分行、列而得到。比如，由以/+x+1为生成多项式生成的(7,4)系统循环码求缩短为(5,2)缩短循环码的生成矩阵和校验矩阵.分析：.+1=(工+1“+./+1*3工+“。本题n-k=7-4=3,因此生成多项式的次数为3。I有两个3次因式，取其中随意一个都能生成(7.4)循环码，现取We=F+.-Af