信道编码简介ppt课件.ppt

编码理论,周武旸中国科学技术大学,助教刘磊：,第一章 序论,编码理论的内容包括三个方面以保证数字信息传输和处理的可靠性为目的的差错控制编码（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码的码字长度为nqm-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理论极限始终都存在23dB的差距。在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(c1,c2),可得d(c1,c2)=w(c1-c2)。例:考虑有两个码字0100,1111的码C，则w(0100)=1,w(1111)=4,这两个码字间的汉明距离为3。通过观察，有 w(0100-1111)=w(1011)=3=d(0100,1111),码组集中任意两个码字之间距离的最小值称为最小码距（dmin），它关系着这种编码的检错和纠错能力。为检测出e个错码，为纠正t个错码，为检测出e个错码,同时纠正t个错码，且,线性码具有下述性质,两个属于该码的码字的和仍是一个属于该码的码字；全零字总是一个码字；一个线性码的两个码字之间的最小距离等于任何非零码字的最小汉明重量。例：码C0000,1010,0101,1111是一个分组长度为4的线性分组码。,以分组码为例，一般以（n，k）表示，k是信息码元数目，n是码组总码元数，又称为码长，因此，nkr就是监督码元的数目。信道编码可表示为由编码前的信息码元空间Uk到编码后的码字空间Cn的一个映射f，即：f：UkCn,编码速率为R=k/n。在二进制情况下，共有2k个不同的信息组，相应地有2k个不同的码字，称为许用码组，其余2n2k个就称为禁用码组。,（7，4）线性分组码举例,基本概念 分组码：将信息码分组，为每组信码附加若干监督码的编码，称为分组码。线性分组码：每个监督码元都是码组中某些信息码元的线性相加得到的。下面以（7，4）分组码进行说明。其码字,据此，可得到16个码字，dmin3，能检测出2个错误，纠正1个错误。,监督矩阵H和生成矩阵G,将上面的方程重写为：,这就是监督矩阵！,H矩阵是一个rn的矩阵，它的每行之间是线性无关的。将H矩阵分为两部分：所以，P矩阵是一个rk阶的矩阵，Ir是r阶的单位阵。可写为HP Ir形式的矩阵称为典型监督矩阵。如果监督矩阵H不是一个典型矩阵，可以对它进行初等变换，化为典型监督矩阵。,这个式子说明H矩阵与码字的转置乘积为零，据此可作为接收码字A是否出错的依据。若把监督方程补充为下列方程：,定义：则有：因此，由信息码元和生成矩阵G就可产生全部码字。,观察G，可得 其中：因此，可写为上式形式的G矩阵就称为典型生成矩阵。,(7,4)线性分组码编码器,例：已知（6，3）码的生成矩阵为试求：（1）编码码组和各个码组的码重；（2）最小码距dmin和该码的差错控制能力；,解：（1）由3位码组成的信息码组矩阵为：,因此，,（2）最小码距dmin3，该码能检错2位，或纠错1位，或纠错1位同时检错1位的能力。,(6,3)线性分组码编码器,伴随式（校正子）S,码组在传输中可能由于干扰而出错，例如发送码组为A，接收到的码组却是B，它们都是n位码的行矢量，我们就定义EBA为错码矩阵。其中BAE定义 为伴随式,有：因此，如果传输无错，S矩阵为零矩阵；如果有错误，S就是一个非零矢量，就能从伴随式确定错误图样，然后从接收到的码字中减去错误图样，即ABE，注意这里的加减都是模2加运算，就可得到正确的码组了。,应该注意的是，上式的解答不是唯一的。我们知道，B是一个1n的矩阵，HT是一个nr的矩阵，所以S是一个1r的矩阵，因此它有2r种可能。而错误图样E的个数远大于2r，因此，必然有多个错误图样对应同一个校正子S。而错误图样等于BA，即与接收到的码组是一一对应的，为了选择正确的结果，要使用最大似然比准则，选择与B最相似的A。从几何意义上来说，就是选择与B距离最小的码组，也就是差错矢量E中1码最少的矢量。,对于（7，4）码来说，它的伴随式与错误图样的对应关系如下表所示：由表可以看出，伴随式S的2r种形式分别代表A码无错和2r1种有错的图样。,例：仍以上面的例题，已知生成矩阵G如下，列出S与E的对照表。当收到码组B1 1 1 0 1 1时，解出对应的信息码组D。解：已知生成矩阵为：Ik Q,我们知道S有23种形式，相应的码重最小的E矢量有8种。S与E的对照表如下：,我们知道，（6，3）码具有纠错1位的能力，虽然S111时对应一种双错图案，但除此之外的双错不能得到纠正。,查表我们可知，E矢量为：E=0 1 0 0 0 0 这样我们就可得到正确的码组A，即 所以，信息码组为：,伴随式译码步骤归纳如下：1.原始发送矢量为A；2.计算接收矢量B的伴随式S=BHT；3.由伴随式S决定相对应的错误图样E；4.将B译成。,伴随式译码器,例3(7,4)线性分组码的译码电路,前面已经给出(7,4)线性分组码的生成矩阵G为和监督矩阵H为,假设消息序列为(0010),则经过编码后的序列为A=(0010101),接收后为B=(1010101),如何通过译码电路纠正错误！,根据公式S=BHT,其中S=s2,s1,s0,B=b6,b5,b4,b3,b2,b1,b0,可得以下关系：s2=b6+b5+b4+b2 s1=b6+b5+b3+b1 s0=b6+b4+b3+b0根据公式S=EHT,其中E=e6,e5,e4,e3,e2,e1,e0,可得以下关系：e6=s2+s1+s0;e5=s2+s1e4=s2+s0;e3=s1+s0e2=s2;e1=s1;e0=s0,纠正了错误，输出变为了0010101！,汉明码（Hamming）,为了指示所有单错位置和无错情况，线性分组码的码长n、信息码元长度k和监督码元长度r之间满足不等式：上式取等号时，就是汉明码。由以上方法构成的线性分组码中，能纠正单个错误的线性分组码称为汉明码，是Hamming于1949年提出的。此时，n、k、r的关系为：n=2r 1 k=n r=2r r 1 其中r为 的正整数。,由，我们可知，上式在给定信息码组长度k后，可以求出能纠正单错的码组最小长度n，而且dmin=3。这样我们就可知道，k=1/4/11时，n=3/7/15。构成（3，1）、（7，4）、（15，11）码。汉明码的编码效率为：当r很大时，趋于1。,1.2.2 循环码,2023/1/12,62,引言,在处理线性分组码时，在分组码的结构上加入了线性限制的条件，这些结构上的性质可以帮助我们寻找好的能够快速、简易地编码和译码的线性分组码；本章，我们将研究线性分组码中的一个重要子类：循环码，该码在结构上有另外的限制，即一个码字任意循环移位的结果仍是一个有效码字。循环码是1957年由Prange首先提出的，其特点是:(1)可以用反馈移位寄存器很容易实现编码和伴随式计算;(2)由于循环码有很多固有的代数结构，从而可以找到各种简单使用的译码方法。,2023/1/12,63,多项式的运算,加法：f1(D)=D3+D+1,f2(D)=D+1 则 f1(D)+f2(D)=D3乘法：f1(D)*f2(D)=D4+D2+D+D3+D+1=D4+D3+D2+1除法：f1(D)/f2(D)D2+D D+1 D3+D+1 D3+D2 D2+D+1 D2+D 1,2023/1/12,64,如果一个(n,k)线性码具有以下的属性，则称为循环码(cyclic code):如果n元组c=c0,c1,cn-1是子空间S的一个码字，则经过循环移位得到的c(1)=cn-1,c0,cn-2也同样是S中的一个码字；或者，一般来说，经过j次循环移位后得到的 c(j)=cn-j,cn-j+1,cn-1,c0,c1,cn-j-1也是S中的一个码字。,2023/1/12,65,码字c=cn-1 c1,c0的各个分量可以看作是多项式c(D)的系数，即 c(D)=cn-1Dn-1+c1D+c0 每一项的存在或不存在对应了n元组中相应的位置为1或0，如果cn-1非0，那么多项式的阶数为n-1。,2023/1/12,66,如（7，3）循环码的全部码字为：,2023/1/12,67,为了便于计算，常用码多项式表示码字，如（n，k）循环码，其多项式表示为：第2号码字可用多项式表示为：,2023/1/12,68,生成多项式g(D)及生成矩阵G,如果一种码的所有码多项式都是多项式g(D)的倍式，则称g(D)为该码的生成多项式。在循环码中，次数最低的多项式（0除外）就是生成多项式g(D)，其他码多项式都是其倍数。且该g(D)的阶数为r=n k，常数项为1，是Dn+1的一个因式。为了寻求生成多项式，必须对Dn+1进行因式分解。,2023/1/12,69,以D71为例：D7+1=(D+1)(D3+D+1)(D3+D2+1)这样，我们可知，（n，k）g(D)（7，6）D+1（7，4）D3+D+1或D3+D2+1（7，3）(D+1)(D3+D+1)或(D+1)(D3+D2+1)（7，1）(D3+D+1)(D3+D2+1),2023/1/12,70,循环码的生成矩阵多项式为：然后将系数提出就得到生成矩阵G。,2023/1/12,71,例如，已知（7，4）码的生成多项式g(D)=D3+D2+1，求生成矩阵。解：k=4 这样我们就可直接得到生成矩阵G为：,2023/1/12,72,由AMG，其中M=mk-1 mk-2 m1 m0表示输入信息码元序列，我们可求出编码后的输出码组序列，但这样得到的循环码不是一个系统码。所谓系统码，指的是码组A的左边k位与M中的k个元素相同，而后面n k位是M中元素的线性组合，表示监督码元。为了得到系统码，就要求G矩阵的左边是一个k阶的单位阵，即是一个典型生成矩阵G=Ik Q形式。,2023/1/12,73,这样的系统码用多项式表示即为：A(D)=Dn-kM(D)+r(D)式中M(D)是不大于k-1次多项式，Dn-kM(D)是不大于n-1次多项式，r(D)是不大于r-1次多项式，称为监督码多项式，它等于Dn-kM(D)除以g(D)得到的余式，表示为 r(D)=Dn-kM(D)mod g(D)或,2023/1/12,74,由于典型生成矩阵G=Ik Q形式，与单位矩阵Ik每行对应的信息多项式为：Dn-kmi(D)=Dn-kDk-i=Dn-i，i1,2,k ri(D)=Dn-i mod g(D)由此得到生成矩阵中每行的码生成多项式为：Ci(D)=Dn-i+ri(D),i=1,2,k 这样系统循环码生成矩阵多项式的一般表示式为：,2023/1/12,75,例2：我们再对前面我们的例题进行求解，已知g(D)=D3+D2+1，希望给出系统循环码的生成矩阵。解：r1(D)=D6 mod g(D)=D2+D r2(D)=D5 mod g(D)=D+1 r3(D)=D4 mod g(D)=D2+D+1 r4(D)=D3 mod g(D)=D2+1 所以，我们可写出生成矩阵多项式为：,2023/1/12,76,生成矩阵G可写为：其实这个矩阵我们也可以通过初等变换从第74页的矩阵得到。,2023/1/12,77,2023/1/12,78,监督多项式h(D)和监督矩阵H,由于GHT=0,对循环码相应的有g(D)h(D)0,mod(Dn+1)监督矩阵多项式可写为：其中,系数不同！,2023/1/12,79,例如：（7，3）循环码的生成多项式为g(D)=D4+D3+D2+1，求其监督矩阵。解：,2023/1/12,80,循环码的编码和译码,我们知道，系统码用多项式表示即为：A(D)=Dn-kM(D)+r(D)编码的关键是求出r(D)，而r(D)则要通过 来求解。,2023/1/12,81,例：已知（7，4）系统循环码的生成多项式为g(D)=D3+D2+1，若信息码为1001，求编码后的循环码组。解：信息码多项式为M(D)=D3+1，其对应的码组为1001011,2023/1/12,82,多项式除法可以用带反馈的线性移位寄存器来实现。g(D)与移位寄存器的反馈逻辑相对应。如假设g(D)=D6+D5+D4+D3+1，则采用内接异或门的电路如下图所示，,2023/1/12,83,以（7，4）系统循环码为例，已知它的生成多项式为g(D)=D3+D2+1，所对应的编码电路入下图所示。,2023/1/12,84,“与”门1在1拍4拍接通，其余时间断开；“与”门2在5拍7拍接通，其余时间断开。用3级移位寄存器D1、D2和D3以及两个模2加法器实现除法电路，反馈逻辑与g(D)相对应。“或”门把信息码元和校验码元合路，输出编码码组A(D)。由于输入信息码组直接加到除法电路的高端，相当于自动乘以D3。当信息码组M=1 0 1 0时，编码过程如下表所示。在0拍时对移位寄存器状态清零。,2023/1/12,85,2023/1/12,86,我们知道，发送码组多项式A(D)是多项式g(D)的倍式，如果经过信道传输后发生错误，接收码组多项式B(D)不再是g(D)的倍式，可表示为：或写成：S(D)=remB(D)/g(D)其中S(D)是B(D)除以g(D)后的余式，是不大于r-1次的码组多项式，称为伴随多项式或校正子多项式。,2023/1/12,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),2023/1/12,88,例：已知（7，4）系统循环码的生成多项式为g(D)=D3+D2+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,2023/1/12,89,接收码组多项式为：B(D)=D6+D2+1 伴随多项式S(D)为：查表得到：E(D)=D5 由B(D)和E(D)可得到译码码组多项式：A(D)=B(D)+E(D)=D6+D5+D2+1 相应的码组为：A=1 1 0 0 1 0 1 由于是系统循环码，所以信息码组为：M1 1 0 0,2023/1/12,90,其译码电路如下：,2023/1/12,91,由于循环码具有很强的检测能力，因此常用于CRC校验，目前已有四个国际标准：CRC-12:g(D)=D12+D11+D3+D2+D+1CRC-16:g(D)=D16+D15+D2+1CRC-CCITT:g(D)=D16+D12+D5+1CRC-32:g(D)=D32+D26+D23+D22+D16+D12+D11+D10+D8+D7+D5+D4+D2+D+1,