信道编码简介.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,编码理论,周武旸,wyzhou,中国科学技术大学,助教,刘磊：,liul,第一章 序论,编码理论的内容包括三个方面,以保证数字信息传输和处理的可靠性为目的的差错控制编码（,error-control coding,），又称为信道编码（,channel coding,）；,以提高数字信息传输、存储处理的有效性为宗旨的信源编码（,Source coding,）；,以增加数字信息传输、存储的安全性为目标的数据加密编码（,data encryption,）；,我们主要讨论差错控制编码技术。,差错控制编码技术是适应数字通信抗噪声干扰的需要而诞生和发展起来的，它是于,1948,年、著名的信息论创始人,C.E.Shannon,（香农）在贝尔系统技术杂志发表的,“,A Mathematical Theory of Communication,”,一文，开创了一门新兴学科和理论：信息论和编码理论。,1.1,信道编码的历史及研究现状,1948,年，,Bell,实验室的,C.E.Shannon,发表的,通信的数学理论,，是关于现代信息理论的奠基性论文，它的发表标志着信息与编码理论这一学科的创立。,Shannon,在该文中指出，任何一个通信信道都有确定的信道容量,C,，如果通信系统所要求的传输速率,R,小于,C,，则存在一种编码方法，当码长,n,充分大并应用最大似然译码（,MLD,，,Maximum Likelihood Decdoding,）时，信息的错误概率可以达到任意小。从,Shannon,信道编码定理可知，随着分组码的码长,n,或卷积码的约束长度,N,的增加，系统可以取得更好的性能（即更大的保护能力或编码增益），而译码的最优算法是,MLD,，,MLD,算法的复杂性随,n,或,N,的增加呈指数增加，因此当,n,或,N,较大时，,MLD,在物理上是不可实现的。因此，构造物理可实现编码方案及寻找有效译码算法一直是信道编码理论与技术研究的中心任务。,Shannon,指出了可以通过差错控制码在信息传输速率不大于信道容量的前提下实现可靠通信，但却没有给出具体实现差错控制编码的方法。,20,世纪,40,年代，,R.Hamming,和,M.Golay,提出了第一个实用的差错控制编码方案，使编码理论这个应用数学分支的发展得到了极大的推动。通常认为是,R.Hamming,提出了第一个差错控制码。当时他作为一个数学家受雇于贝尔实验室，主要从事弹性理论的研究。他发现计算机经常在计算过程中出现错误，而一旦有错误发生，程序就会停止运行。这个问题促使他编制了使计算机具有检测错误能力的程序，通过对输入数据编码，使计算机能够纠正这些错误并继续运行。,Hamming,所采用的方法就是将输入数据每,4,个比特分为一组，然后通过计算这些信息比特的线性组合来得到,3,个校验比特，然后将得到的,7,个比特送入计算机。计算机按照一定的原则读取这些码字，通过采用一定的算法，不仅能够检测到是否有错误发生，同时还可以找到发生单个比特错误的比特的位置，该码可以纠正,7,个比特中所发生的单个比特错误。这个编码方法就是分组码的基本思想，,Hamming,提出的编码方案后来被命名为汉明码。,Hamming,1915-1998,虽然汉明码的思想是比较先进的，但是它也存在许多难以接受的,缺点,。首先，汉明码的,编码效率比较低,，它每,4,个比特编码就需要,3,个比特的冗余校验比特。另外，在一个码组中只能,纠正单个的比特错误,。,M.Golay,研究了汉明码的这些缺点，并提出了两个以他自己的名字命名的高性能码字：一个是二元,Golay,码，在这个码字中,Golay,将信息比特每,12,个分为一组，编码生成,11,个冗余校验比特，相应的译码算法可以纠正,3,个错误。另外一个是三元,Golay,码，它的操作对象是三元而非二元数字。三元,Golay,码将每,6,个三元符号分为一组，编码生成,5,个冗余校验三元符号。这样由,11,个三元符号组成的三元,Golay,码码字可以纠正,2,个错误。,汉明码和,Golay,码的基本原理相同。它们都是将,q,元符号按每,k,个分为一组然后通过编码得到,n-k,个,q,元符号作为冗余校验符号，最后由校验符号和信息符号组成有,n,个,q,元符号的码字符号。得到的码字可以纠正,t,个错误，编码码率为为,k/n,。这种类型的码字称为,分组码,，一般记为,(q,n,k,t),码，二元分组码可以简记为,(n,k,t),码或者,(n,k),码。汉明码和,Golay,码都是线性的，任何两个码字经过模,q,的加操作之后，得到的码字仍旧是码集合中的一个码字。,在,Golay,码提出之后最主要的一类分组码就是,Reed-Muller,码。它是,Muller,在,1954,年提出的，此后,Reed,在,Muller,提出的分组码的基础上得到了一种新的分组码，称为,Reed-Muller,码，简记为,RM,码,在,1969,年到,1977,年之间，,RM,码在火星探测方面得到了极为广泛的应用。即使在今天，,RM,码也具有很大的研究价值，其快速的译码算法非常适合于光纤通信系统。,在,RM,码提出之后人们又提出了,循环码,的概念。循环码实际上也是一类分组码，但它的码字具有循环移位特性，,即码字比特经过循环移位后仍然是码字集合中的码字,。这种循环结构使码字的设计范围大大增加，同时大大简化了编译码结构。循环码的另一个特点就是它可以用一个幂次为,n-k,的多项式来表示，这个多项式记为,g(D),，称为生成多项式，其中,D,为延迟算子。循环码也称为循环冗余校验,(CRC,，,Cyclic Redundancy Check),码，并且可以用,Meggitt,译码器来实现译码。由于,Meggitt,译码器的译码复杂性随着纠错能力,t,的增加而呈指数形式的增加，因此通常,CRC,码用于纠正只有单个错误的应用情况，,常用做检错码而非纠错码,。,循环码的一个非常重要的子集就是分别由,Hocquenghem,在,1959,年、,Bose,和,Ray-Chaudhuri,研究组在,1960,年几乎同时提出的,BCH,码,(BCH,，,Bose Chaudhuri Hocquenghem),，,BCH,码的码字长度为,n,q,m,-1,，其中,m,为一个整数。二元,BCH,码（,q=2,）的纠错能力限为,t2,）的情况，得到了,RS,（,Reed-Solomon,）码。,1967,年，,Berlekamp,给出了一个非常有效的译码算法后，,RS,码得到了广泛的应用。此后，,RS,码在,CD,播放器、,DVD,播放器中得到了很好的应用。,虽然分组码在理论分析和数学描述方面已经非常成熟，并且在实际的通信系统中也已经得到了广泛的应用，但分组码固有的,缺陷,大大限制了它的进一步发展。,首先,，由于分组码是,面向数据块,的，因此，在译码过程中必须等待整个码字全部接收到之后才能开始进行译码。在数据块长度较大时，引入的系统延时是非常大的。分组码的,第二个缺陷,是它要求,精确的帧同步,，即需要对接收码字或帧的起始符号时间和相位精确同步。另外，大多数基于代数的分组码的译码算法都是,硬判决算法,，而不是对解调器输出未量化信息的软译码，从而造成了一定程度的增益损失。,分组码所存在的固有缺点可以通过采用其他的编码方法来改善。这种编码方法就是卷积码。卷积码是,Elias,等人在,1955,年提出的。卷积码与分组码的不同在于：它充分利用了各个信息块之间的相关性。通常卷积码记为,(n,，,k,，,N),码。卷积码的,编码,过程是,连续进行,的，依次连续将每,k,个信息元输入编码器，得到,n,个码元，得到的码元中的检验元,不仅与本码的信息元有关，还与以前时刻输入到编码器的信息元,(,反映在编码寄存器的内容上,),有关,。同样，在卷积码的译码过程中，不仅要从本码中提取译码信息，还要充分利用以前和以后时刻收到的码组从这些码组中提取译码相关信息，而且,译码也是可以连续进行的,，这样可以保证卷积码的译码,延时相对比较小,。通常，在系统条件相同的条件下，在达到相同译码性能时，卷积码的信息块长度和码字长度都要比分组码的信息块长度和码字长度小，相应译码复杂性也小一些。,Elias,1923-2001,卷积码的译码通常有如下几个比较流行的译码算法：,由,Wozencraft,和,Reiffen,在,1961,年提出，,Fano,和,Jelinek,分别在,1963,年和,1969,年进行改进了的序贯译码算法。该算法是基于码字树图结构的一种次优概率译码算法。,由,Massey,在,1963,年提出的门限译码算法。这个算法利用码字的代数结构进行代数译码。,由,Viterbi,在,1967,年提出的,Viterbi,算法。该算法是基于码字格图结构的一种最大似然译码算法，是一种最优译码算法。,在,Viterbi,译码算法提出之后，卷积码在通信系统中得到了极为广泛的应用。如,GSM,、,3G,、商业卫星通信系统等。,Viterbi,CDMA,之父,近年来，在信道编码定理的指引下，人们一直致力于寻找能满足现代通信业务要求、结构简单、性能优越的好码，并在分组码、卷积码等基本编码方法和最大似然译码算法的基础上提出了许多构造好码及简化译码复杂性的方法，提出了乘积码、代数几何码、低密度校验码,(LDPC,，,Low Density Parity Check),、分组,-,卷积级联码等编码方法和逐组最佳译码、软判决译码等译码方法以及编码与调制相结合的网格编码调制,(TCM,，,Trellis Coded Modulation),技术。其中对纠错码发展贡献比较大的有级联码、软判决译码和,TCM,技术等。,Gallager,虽然软判决译码、级联码和编码调制技术都对信道码的设计和发展产生了重大影响，但是其增益与,Shannon,理论极限始终都存在,2,3dB,的差距。,在,1993,年于瑞士日内瓦召开的国际通信会议,(1CC93),上，两位任教于法国不列颠通信大学的教授,C.Berrou,、,A.Glavieux,和他们的缅甸籍博士生,P.Thitimajshima,首次提出了一种新型信道编码方案,Turbo,码，由于它很好地应用了,Shannon,信道编码定理中的随机性编、译码条件，从而获得了几乎接近,Shannon,理论极限的译码性能。仿真结果表明，在采用长度为,65536,的随机交织器并译码迭代,18,次情况下，在信噪比,Eb/N0=0.7dB,并采用二元相移键控,(BPSK),调制时，码率为,1/2,的,Turbo,码在加性高斯白噪声信道上的误比特率,(BER)=10,-5,，达到了与,Shannon,极限仅相差,0.7dB,的优异性能。,(1/2,码率的,Shannon,极限是,0dB),。,Berrou and Forney,1997,年，,Host,、,Johannesson,、,Ablov,提出了编织卷级码（,Woven Convolutional Code,WCC,）的概念，随后编织码（,Woven code,）便发展起来了。它是一种组合码，其系统结构可完全包容传统分组码、卷级码以及各类,Turbo,码，开创了编码领域的一个新天地。,编织码的结构综合了并行级联卷级码（,Turbo,码）和串行级联卷级码的结构特点，当外编码器个数足够多时，该码型完全拥有了,Shannon,编码定理中随机长码的特性，因此，其纠错性能理论上比,Turbo,码要优异。,但编织码的编码结构复杂性较高，编码效率也不高，目前研究最多的是,1/3,的编织卷级码，译码采用,BCJR,算法的迭代译码。,发展概括,1948,年，,Shannon,发表开创性文章“通信的数学理论”；,1950,年，,Hamming,发明了汉明码；,1955,年，,Elias,引入了卷级码；,1957,年，,Prange,提出了循环码；,1960,年，,Bose/Chaudhuri/Hocquenghem,发明了,BCH,码；,Reed,和,Solomon,提出了,RS,码；,1962,年，,Gallager,提出了,LDPC,码；,1967,年，,Berlekamp,引入了,BCH/RS,码的快速译码算法；,1968,年，,Gallager,著书,Information theory and reliable communication,；,1971,年，,Viterbi,引入卷级码的最大似然译码；,1972,年，,BCJR,算法的提出；,1981,年，,Tanner,提出了用于理解信道编码理论的,Tanner,图；,1982,年，,Ungerboeck,引入编码调制；,1993,年，,Berrou/Glaveieux/Thitimajshima,提出了,Turbo,码；,1995,年，,MacKay,重新发现了,LDPC码；,1997,年，,Host/Johannesson/Ablov,提出了编织卷级码。,2000,年，,Aji,与,McEliece,总结了应用消息传递思想进行译码的码型；,2003,年，,Koetter,与,Vardy,提出了,RS,码的代数软判决译码；,高效纠错编码的研究现状,20,世纪,90,年代以后，以迭代译码为基础的高效纠错码成为主要研究对象，不再将精力放在以代数为基础的代数码上，而是寻找新的纠错码的认识方式，其中有以,Tanner,图为基础发展起来的编译码的可视化方法，如因子图，以及基于图中双边上信息传递的和积算法，还有用于评估码字性能限的数值化方法密度进化、典型集合界理论等。,由于最大似然译码性能最好，但复杂度随码长指数增加（物理上不可实现），因此必须研究新的编译码方案，期望在性能和复杂度之间取得平衡。如串行级联码、乘积码等编码方案的目标都是为了构造出具有较大等效分组长度的纠错码，并且允许将最大似然译码分为几个较简单的译码步骤（一种次优但可实现的译码策略）；另一种次优方法是迭代译码（,Gallager,的贡献），,1993,年,Berrou,提出的,Turbo,码采用软输出迭代译码，性能与,Shannon,限仅差,0.7dB,，,1996,年，,MacKay,与,Neal,仿真的,LDPC,码性能与,Shannon,限仅差,0.0045dB,，这表明，迭代译码方法已成为靠近,Shannon,限的高效纠错码的基本特征。,总之，为实现高效纠错，不是采用级联方式构造随机长码，就是采用迭代译码，或两者均采用，以逼近,Shannon,限。,端到端的通信系统模型,从图中可知，数字通信的主要技术问题包括：信源编译码、信道编译码、数字调制解调、基带传输、信道与噪声、接收时必须要解决的同步问题、为了使通信过程保密，要进行保密编译码的处理等。,同步,无线信道,比有线信道要恶劣的多！,1.2,简单的编码方式回顾,在设计数字通信系统时，首先应从合理地选择调制解调方法、合适的发射功率等方面考虑，若仍不能满足系统误码率要求，则要考虑采用本章所讲的差错控制编码措施。,纠错码,，是当消息经过有噪信道传输或要恢复存储的数据时用来纠错的。用来传输消息的物理介质叫做,信道,（如电话线、卫星连接、用于移动通信的无线信道等）。因为纠错码试图克服信道中噪声造成的损害，因此其编码过程又称为,信道编码,，它是提高数字信号传输可靠性的有效方法之一。,数字通信系统框图,常用的差错控制方式有三种：,检错重发方式，又称为自动重发请求（,ARQ,），发送端发送能够发现错误的码，由接收端判断接收中有无错误发生。如果发现错误，则通过反向信道把这一判决结果反馈给发送端，然后发送端再把错误的信息重发一次。,前向纠错方式（,FEC,）：发送端发送能够纠正错误的码，接收端收到后自动纠正传输中的错误，特点是单向传输。,混合,纠错方式（,HEC,）：发送端发送既能自动纠错，又能检测的码。接收端收到码流后，检查差错情况，如果错误在纠错能力范围以内，则自动纠错，如果超过了纠错能力，但能检测出来，则经过反馈信道请求发送端重发。,差错控制编码的基本原理,在信息码元序列中附加一些监督码元，在两者之间建立某种校验关系，当这种校验关系因传输错误而受到破坏时，可以被发现和纠正。不同的编码方法，有不同的检错和纠错能力。一般来说，付出的代价越大，检（纠）错的能力就越强。这里所说的代价，指增加的监督码元的多少。例如，若编码序列中，平均每两个信息码元就有一个监督码元，则这种编码的多余度为,1/3,，或者说，这种编码的编码速率为2/3,，可见，差错控制编码是以降低信息传输速率来换取信息传递的可靠性提高。,差错控制编码的分类,根据 的函数关系，可分为线性码和非线性码。,根据信息码元和监督码元之间的约束方式，可分为分组码和卷积码。在分组码中，监督码元仅与本码组的信息码元有关，而在卷积码中，监督码元不仅与本组的信息码元有关，还与前面若干组的信息码元有关。,误差控制编码的目标,用可以纠正的错误个数来衡量纠错能力；,快速有效地对消息进行编码；,快速有效地对消息进行解码；,单位时间内所能传输的信息,bit,数尽量大（即尽量减少冗余度）。,矛盾！折衷！,使用纠错编码的原因,权衡,1,：差错性能和带宽；,权衡,2,：功率与带宽；,权衡,3,：数据速率与带宽；,权衡,4,：容量与带宽；,几种常用的简单检错码,奇偶监督码,就是在原信息码元后面附加一个监督码元，使得码组中的,“,1,”,的个数为奇数或偶数。接收端译码时，对各码元进行模,2,加运算，其结果为,0,或,1,，如果传输过程中任何一位发生错误，就会使校验条件不满足，但当有偶数个错误发生时，这种编码就无能为力了。,行列监督码（水平奇偶监督码）,对行和列都实施奇偶监督。,恒比码,：,即码字中,“,1,”,和,“,0,”,的数目保持恒定比例的码。,1.2.1,线性分组码,基本名词定义,在信道编码中，非零码元的数目称为,汉明重量,（,Hamming Weight),，也称为码重,。记为,w(c),。,两个等长码组之间相应位取值不同的数目称为这两个码组的,汉明距离,（,Hamming Distance,），简称,码距,。记为,d(c,1,c,2,),可得,d(c,1,c,2,)=w(c,1,-c,2,),。,例,:,考虑有两个码字,0100,1111,的码,C,，则,w(0100)=1,w(1111)=4,这两个码字间的汉明距离为,3,。通过观察，有,w(0100-1111)=w(1011)=3,=d(0100,1111),码组集中任意两个码字之间距离的最小值称为,最小码距,（,d,min,），它关系着这种编码的检错和纠错能力。,为检测出,e,个错码，,为纠正,t,个错码，,为检测出,e,个错码,同时纠正,t,个错码，,且,线性码具有下述性质,两个属于该码的码字的和仍是一个属于该码的码字；,全零字总是一个码字；,一个线性码的两个码字之间的最小距离等于任何非零码字的最小汉明重量。,例：码,C,0000,1010,0101,1111,是一个分组长度为,4,的线性分组码。,以分组码为例，一般以（,n,，,k,）表示，,k,是信息码元数目，,n,是码组总码元数，又称为码长，因此，,n,k,r,就是监督码元的数目。,信道编码可表示为由编码前的信息码元空间,U,k,到编码后的码字空间,C,n,的一个映射,f,，即：,f,：,U,k,C,n,编码速率为,R=k/n在二进制情况下，共有,2,k,个不同的信息组，相应地有,2,k,个不同的码字，称为许用码组，其余,2,n,2,k,个就称为禁用码组。,（,7,，,4,）,线性分组码,举例,基本,概念,分组码：将信息码分组，为每组信码附加若干监督码的编码，称为分组码。,线性分组码：每个监督码元都是码组中某些信息码元的线性相加得到的。,下面以（,7,，,4,）分组码进行说明。,其码字,据此，可得到,16,个码字，,d,min,3,，能检测出,2,个错误，纠正,1,个错误。,监督矩阵,H,和生成矩阵,G,将上面的方程重写为：,这就是监督矩阵！,H,矩阵是一个,r,n,的矩阵，它的每行之间是线性无关的。将,H,矩阵分为两部分：,所以，,P,矩阵是一个,rk,阶的矩阵，,I,r,是,r,阶的单位阵。,可写为,H,P I,r,形式的矩阵称为典型监督矩阵。如果监督矩阵,H,不是一个典型矩阵，可以对它进行初等变换，化为典型监督矩阵。,这个式子说明,H,矩阵与码字的转置乘积为零，据此可作为接收码字,A,是否出错的依据。,若把监督方程补充为下列方程：,定义：,则有：,因此，由信息码元和生成矩阵,G,就可产生全部码字。,观察,G,，可得,其中：,因此，可写为上式形式的,G,矩阵就称为典型生成矩阵。,(7,4),线性分组码编码器,例：已知,（,6,，,3,）码的生成矩阵为试,求：,（,1,）编码,码组和各个码组的码重,；,（,2,）最小,码距,d,min,和该码的差错控制能力；,解：,（,1,）由,3,位码组成的信息码组矩阵为：,因此，,（,2,）最小码距,d,min,3,，该码能检错,2,位，或纠错,1,位，或纠错,1,位同时检错,1,位的能力。,(6,3),线性分组码编码器,伴随式（校正子）,S,码组在传输中可能由于干扰而出错，例如发送码组为,A,，接收到的码组却是,B,，它们都是,n,位码的行矢量，我们就定义,E,B,A,为错码矩阵。,其中,B,A,E,定义 为伴随式,有：,因此，如果传输无错，,S,矩阵为零矩阵；如果有错误，,S,就是一个非零矢量，就能从伴随式确定错误图样，然后从接收到的码字中减去错误图样，即,A,B,E,，注意这里的加减都是模,2,加运算，就可得到正确的码组了。,应该注意的是，上式的解答不是唯一的。我们知道，,B,是一个,1,n,的矩阵，,H,T,是一个,n,r,的矩阵，所以,S,是一个,1,r,的矩阵，因此它有,2,r,种可能。而错误图样,E,的个数远大于,2,r,，因此，必然有多个错误图样对应同一个校正子,S,。而错误图样等于,B,A,，即与接收到的码组是一一对应的，为了选择正确的结果，要使用最大似然比准则，选择与,B,最相似的,A,。从几何意义上来说，就是选择与,B,距离最小的码组，也就是差错矢量,E,中,1,码最少的矢量。,对于（,7,，,4,）码来说，它的伴随式与错误图样的对应关系如下表所示：,由表可以看出，伴随式,S,的,2,r,种形式分别代表,A,码无错和,2,r,1,种有错的图样。,例：仍以上面的例题，已知生成矩阵,G,如下，列出,S,与,E,的对照表。当收到码组,B,1 1 1 0 1 1,时，解出对应的信息码组,D,。,解：已知生成矩阵为：,I,k,Q,我们知道,S,有,2,3,种形式，相应的码重最小的,E,矢量有,8,种。,S,与,E,的对照表如下：,我们知道，（,6,，,3,）码具有纠错,1,位的能力，虽然,S,111,时对应一种双错图案，但除此之外的双错不能得到纠正。,查表我们可知，,E,矢量为：,E=0 1 0 0 0 0,这样我们就可得到正确的码组,A,，即,所以，信息码组为：,伴随式,译码步骤归纳如下：,1.,原始发送矢量为,A,；,2.,计算接收矢量,B,的伴随式,S=B,H,T,；,3.,由伴随式,S,决定相对应的错误图样,E,；,4.,将,B,译成 。,伴随式译码器,例,3(7,4),线性分组码的译码电路,前面已经给出,(7,4),线性分组码的生成矩阵,G,为和监督矩阵,H,为,假设消息序列为,(0010),则经过编码后的序列为,A=(0010101),接收后为,B=(,1,010101),如何通过译码电路纠正错误！,根据公式,S=BH,T,其中,S=s,2,s,1,s,0,B=b,6,b,5,b,4,b3,b,2,b,1,b,0,可得以下关系：,s,2,=b,6,+b,5,+,b,4,+,b,2,s,1,=b,6,+b,5,+,b,3,+,b,1,s,0,=b,6,+b,4,+,b,3,+,b,0,根据公式,S=EH,T,其中,E=e,6,e,5,e,4,e,3,e,2,e,1,e,0,可得以下关系：,e,6,=s,2,+s,1,+s,0,;e,5,=s,2,+s,1,e,4,=s,2,+s,0,;e,3,=s,1,+s,0,e,2,=s,2,;e,1,=s,1,;e,0,=s,0,纠正了错误，输出变为了,0010101,！,汉明码（,Hamming,）,为了指示所有单错位置和无错情况，线性分组码的码长,n,、信息码元长度,k,和监督码元长度,r,之间满足不等式：,上式取等号时，就是汉明码。由以上方法构成的线性分组码中，能纠正单个错误的线性分组码称为汉明码，是,Hamming,于,1949,年提出的。,此时，,n,、,k,、,r,的关系为：,n=2,r,1,k=n r=2,r,r 1,其中,r,为 的正整数。,由 ，我们可知，,上式在给定信息码组长度,k,后，可以求出能纠正单错的码组最小长度,n,，而且,d,min,=3,。这样我们就可知道，,k=1/4/11,时，,n=3/7/15,。构成（,3,，,1,）、（,7,，,4,）、（,15,，,11,）码。,汉明码的编码效率为：当,r,很大时，趋于,1,。,1.2.2,循环码,2024/11/28 周四,62,引言,在处理线性分组码时，在分组码的结构上加入了线性限制的条件，这些结构上的性质可以帮助我们寻找好的能够快速、简易地编码和译码的线性分组码；本章，我们将研究线性分组码中的一个重要子类：循环码，该码在结构上有另外的限制，即一个码字任意循环移位的结果仍是一个有效码字。,循环码是,1957,年由,Prange,首先提出的，其特点是,:,(1),可以用反馈移位寄存器很容易实现编码和伴随式计算,;(2),由于循环码有很多固有的代数结构，从而可以找到各种简单使用的译码方法。,2024/11/28 周四,63,多项式的运算加法：,f,1,(D)=D,3,+D+1,f,2,(D)=D+1,则,f,1,(D)+f,2,(D)=D,3,乘法：,f,1,(D)*f,2,(D)=D,4,+D,2,+D+D,3,+D+1,=D,4,+D,3,+D,2,+1,除法：,f,1,(D)/f,2,(D),D,2,+D,D+1 D,3,+D+1,D,3,+D,2,D,2,+D+1,D,2,+D,1,2024/11/28 周四,64,如果一个,(n,k),线性码具有以下的属性，则称为循环码,(cyclic code):,如果,n,元组,c=c,0,c,1,c,n-1,是子空间,S,的一个码字，则经过循环移位得到的,c,(1),=c,n-1,c,0,c,n-2,也同样是,S,中的一个码字；或者，一般来说，经过,j,次循环移位后得到的,c,(j),=c,n-j,c,n-j+1,c,n-1,c,0,c,1,c,n-j-1,也是,S,中的一个码字。,2024/11/28 周四,65,码字,c=c,n-1,c,1,c,0,的各个分量可以看作是多项式,c(D),的系数，即,c(D)=c,n-1,D,n-1,+c,1,D+c,0,每一项的存在或不存在对应了,n,元组中相应的位置为,1,或,0,，如果,c,n-1,非,0,，那么多项式的阶数为,n-1,。,2024/11/28 周四,66,如（,7,，,3,）循环码的全部码字为：,2024/11/28 周四,67,为了便于计算，常用码多项式表示码字，如（,n,，,k,）循环码，其多项式表示为：,第,2,号码字可用多项式表示为：,2024/11/28 周四,68,生成多项式,g(D),及生成矩阵,G,如果一种码的所有码多项式都是多项式,g(D),的倍式，则称,g(D),为该码的生成多项式。在循环码中，次数最低的多项式（,0,除外）就是生成多项式,g(D),，其他码多项式都是其倍数。且该,g(D),的阶数为,r=n k,，常数项为,1,，是,D,n,+1,的一个因式。为了寻求生成多项式，必须对,D,n,+1,进行因式分解。,2024/11/28 周四,69,以,D,7,1,为例：D,7,+1=(D+1)(D,3,+D+1)(D,3,+D,2,+1),这样，我们可知，,（,n,，,k,）,g(D),（,7,，,6,）,D+1,（,7,，,4,）,D,3,+D+1,或,D,3,+D,2,+1,（,7,，,3,）,(D+1)(D,3,+D+1),或,(D+1)(D,3,+D,2,+1),（,7,，,1,）,(D,3,+D+1)(D,3,+D,2,+1),2024/11/28 周四,70,循环码的生成矩阵多项式为：,然后将系数提出就得到生成矩阵,G,。,2024/11/28 周四,71,例如，已知（,7,，,4,）码的生成多项式,g(D)=D,3,+D,2,+1,，求生成矩阵。,解：,k=4,这样我们就可直接,得到生成矩阵,G,为：,2024/11/28 周四,72,由,A,MG,，其中,M=m,k-1,m,k-2,m,1,m,0,表示输入信息码元序列，我们可求出编码后的输出码组序列，,但这样得到的循环码不是一个系统码。,所谓系统码，指的是码组,A,的左边,k,位与,M,中的,k,个元素相同，而后面,n k,位是,M,中元素的线性组合，表示监督码元。,为了得到系统码，就要求,G,矩阵的左边是一个,k,阶的单位阵，即是一个典型生成矩阵,G=I,k,Q,形式。,2024/11/28 周四,73,这样的系统码用多项式表示即为：,A(D)=D,n-k,M(D)+r(D)式中,M(D),是不大于,k-1,次多项式，,D,n-k,M(D),是不大于,n-1,次多项式，,r(D),是不大于,r-1,次多项式，称为监督码多项式，它等于,D,n-k,M(D),除以,g(D),得到的余式，表示为,r(D)=D,n-k,M(D)mod g(D),或,2024/11/28 周四,74,由于典型生成矩阵,G=I,k,Q,形式，与单位矩阵,I,k,每行对应的信息多项式为：,D,n-k,m,i,(D)=D,n-k,D,k-i,=D,n-i,，,i,1,2,k,r,i,(D)=D,n-i,mod g(D),由此得到生成矩阵中每行的码生成多项式为：,C,i,(D)=D,n-i,+ri,(D),i=1,2,k,这样系统循环码生成矩阵多项式的一般表示式为：,2024/11/28 周四,75,例,2,：我们再对前面我们的例题进行求解，已知,g(D)=D,3,+D,2,+1,，希望给出系统循环码的生成矩阵。,解：,r,1,(D)=D,6,mod g(D)=D,2,+D,r,2,(D)=D,5,mod g(D)=D+1,r,3,(D)=D,4,mod g(D)=D,2,+D+1,r,4,(D)=D,3,mod g(D)=D,2,+1,所以，我们可写出生成矩阵多项式为：,2024/11/28 周四,76,生成矩阵,G,可写为：,其实这个矩阵我们也可以通过初等变换从第,74,页的矩阵得到。,2024/11/28 周四,77,2024/11/28 周四,78,监督多项式,h(D),和监督矩阵,H,由于,GH,T,=0,对循环码相应的有,g(D)h(D)0,mod(D,n,+1),监督矩阵多项式可写为：,其中,系数不同！,2024/11/28 周四,79,例如：（,7,，,3,）循环码的生成多项式为,g(D)=D,4,+D,3,+D,2,+1,，求其监督矩阵。,解：,2024/11/28 周四,80,循环码的编码和译码,我们知道，系统码用多项式表示即为：,A(D)=D,n-k,M(D)+r(D),编码的关键是求出,r(D),，而,r(D),则要通过,来求解。,2024/11/28 周四,81,例：已知（,7,，,4,）系统循环码的生成多项式为,g(D)=D,3,+D,2,+1,，若信息码为,1001,，求编码后的循环码组。,解：信息码多项式为,M(D)=D,3,+1,，,其对应的码组为,1001011,2024/11/28 周四,82,多项式除法可以用带反馈的线性移位寄存器来实现。,g(D),与移位寄存器的反馈逻辑相对应。如假设,g(D)=,D,6,+D,5,+D,4,+D,3,+1,，则采用内接异或门的电路如下图所示，,2024/11/28 周四,83,以（,7,，,4,）系统循环码为例，已知它的生成多项式为,g(D)=D,3,+D,2,+1,，所对应的编码电路入下图所示。,2024/11/28 周四,84,“,与”门,1,在,1,拍,4,拍接通，其余时间断开；“与”门,2,在,5,拍,7,拍接通，其余时间断开。用,3,级移位寄存器,D1,、,D2,和,D3,以及两个模,2,加法器实现除法电路，反馈逻辑与,g(D),相对应。“或”门把信息码元和校验码元合路，输出编码码组,A(D),。由于输入信息码组直接加到除法电路的高端，相当于自动乘以,D,3,。当信息码组,M=1 0 1 0,时，编码过程如下表所示。在,0,拍时对移位寄存器状态清零。,2024/11/28 周四,85,节拍,1,2,3,4,5,6,7,信息码元,1,0,1,0,0,0,0,D,11,1,0,1,0,0,0,D,2,0,1,1,0,1,0,0,D,3,1,1,1,0,0,1,0,输出编码,1,0,1,0,0,0,1,2024/11/28 周四,86,我们知道，发送码组多项式,A(D),是多项式,g(D),的倍式，如果经过信道传输后发生错误，接收码组多项式,B(D),不再是,g(D),的倍式，可表示为：,或写成：,S(D)=remB(D)/g(D),其中,S(D),是,B(D),除以,g(D),后的余式，是不大于,r-1,次的码组多项式，称为伴随多项式或校正子多项式。,2024/11/28 周四,87,接收码组多项式,B(D),可表示为发送码组多项式与差错多项式之和，即B(D)=A(D)+E(D),由,S(D),就可进一步确定,E(D),。对于一个,S(D),，,E(D),可能有多种形式。由,S(D),确定,E(D),时同样使用最大似然比准则。对最小码重的差错多项式,E(D),，由上式求出对应的伴随多项式,S(D),，将,E(D),与,S(D),的对应关系列成译码表。当收到任一码组,B(D),后，利用,S(D)=remB(D)/g(D),求出,S(D),，对照译码表找到,E(D),，再用,B(D)=A(D)+E(D),求,A(D),，即,A(D)=B(D)+E(D),2024/11/28 周四,88,例：已知（,7,，,4,）系统循环码的生成多项式为,gD)=D,3,+D,2,+1,，试构成译码表。若接收码组,B=1 0 0 0 1 0 1,，求发送码组。,解：根据,S(D)=remB(D)/g(D),，对码重为,1,的差错多项式,E(D),，求出相应的多项式,S(D),，将其对应结果列成译码表如下：,当接收码组无误时，,E(D)=0,，则,S(D)=0,。,本题给出的接收码组为：,B=1 0 0 0 1 0 1,E(D),D,6,D,5,D,4,D,3,D,2,D,1,S(D),D,2,+D,D+1,D,2,+D+1,D,2,+1,D,2,D,1,2024/11/28 周四,89,接收码组多项式为：,B(D)=D,6,+D,2,+1,伴随多项式,S(D),为：,查表得到：,E(D)=D,5,由,B(D),和,E(D),可得到译码码组多项式：,A(D)=B(D)+E(D)=D,6,+D,5,+D,2,+1,相应的码组为：,A=1 1 0 0 1 0 1,由于是系统循环码，所以信息码组为：,M,1 1 0 0,2024/11/28 周四,90,其译码电路如下：,2024/11/28 周四,91,由于循环码具有很强的检测能力，因此常用于,CRC,校验，目前已有四个国际标准：,CRC-12,:g(D)=D,12,+D,11,+D,3,+D,2,+D+1,CRC-16,:g(D)=D,16,+D,15,+D,2,+1,CRC-CCITT