CH11差错控制编码.ppt

2019年6月16日7时38分,信电学院信息工程系李世银,1,第11章 差错控制编码,又称信道编码，是提高数字传输可靠性的一种技术。 其基本思想是通过对信息序列作某种变换，使原来彼此独立、相关性极小的信息码元产生某种相关性，在接收端就可以利用这种规律性来检查并纠正信息码元在信到传输中所造成的差错。 比如，考试填空题，改错题,概述,2019年6月16日7时38分,信电学院信息工程系李世银,2,概述 纠错编码的基本原理 纠错编码的性能 简单的实用编码 线性分组码 循环码 卷积码 网格编码调制TCM 其它编码,第11章 差错控制编码,2019年6月16日7时38分,信电学院信息工程系李世银,3,11.1 概述 1.误码的主要形式 （1）随机错误：误码的位置随机（误码间无关联），随机误码主要由白噪声引起。 （2）突发错误：误码成串出现，主要由强脉冲及雷电等突发的强干扰引起。 （3）混合错误：以上两种误码及产生原因的组合。,11.1 差错控制编码的基本概念,差错控制的主要方式,2019年6月16日7时38分,信电学院信息工程系李世银,4,（1）前向纠错（FEC）； （2）检错重发（ARQ）:停发等候重发，返回重发，选择重发； （3）反馈校验（IRQ）； （4）混合纠错（HEC）； （5）检错删除 。,发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正； 不需要反馈信道，特别适合只能提供单向信道场合； 自动纠错，不要求检错重发，延时小，实时性好； 纠错码必须与信道的错误特性密切配合； 若纠错较多，则编、译码设备复杂，传输效率低；,收端把收到的数据序列全部经反向信道送回发端，发端比较发出和送回的数据序列，从而发现有否错误，并把有错误的数据序列再次传送，直到发端没有发现错误； 不需要纠错、检错的编、译码器，设备简单； 需要和正向信道相同的反向信道，实时性差； 发端需要一定容量的存储器以存储发送码组； 仅适应于传输速率较低，信道差错率较低，具有双向传输线路及控制简单的系统。,FEC与ARQ的结合； 发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发； 在实时性和译码复杂性方面是FEC和ARQ的折衷。,11.1 差错控制编码的基本概念,2.差错控制的主要方式,几个概念,2019年6月16日7时38分,信电学院信息工程系李世银,5,监督码元：在接收端识别有无错码，所以在发送端需要在信息码元序列中增加一些除了信息码元之外的差错控制码元，它们称为监督码元。 编码效率(简称码率) ：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n 就是码率。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的码率为1/3。 冗余度：监督码元数(n-k) 和信息码元数 k 之比。 不同的编码方法，有不同的检错或纠错能力。理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。,纠错编码又称为差错控制编码,差错控制编码的分类,2019年6月16日7时38分,信电学院信息工程系李世银,6,3.差错控制编码的分类,（1）线性码：信息码与监督码之间的关系为线性关系（信息位与监督位之间是由一些线性方程联系的）； 非线性码：信息码与监督码之间的关系为非线性关系。 （2）分组码：信息码与监督码以组为单位建立关系（将信息码分组，为每组信码附加若干监督码的编码）； 卷积码：监督码与本组和前面码组中的信息码有关。 （3）系统码：编码后码组中信息码保持原图样顺序(形式)不变; 非系统码：编码后码组中原信息码原图样发生变化。 （4）数学方法： 代数码:建立在代数学基础上的编码 几何码；算术码。,分组码结构,11.2 差错控制编码的基本原理,2019年6月16日7时38分,信电学院信息工程系李世银,7,分组码的结构 将信息码分组，为每组信息码附加若干监督码的编码称为分组码 。 分组码中，监督码元仅监督本码组中的信息码元。 分组码的一般结构,分组码的符号：(n, k) N码组的总位数，又称为码组的长度（码长）， k 码组中信息码元的数目， nk r, 码组中的监督码元数目，或称监督位数目。,纠错编码基本原理,2019年6月16日7时38分,信电学院信息工程系李世银,8,11.2 纠错编码的基本原理,1. 纠错编码的基本原理 理论依据：Shannon信道编码定理。 定理指出：对于一给定的有扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。,2. 纠错编码的基本思想： 发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系 以牺牲通信的有效性（信息传输速率）来提高可靠性 码的检错和纠错能力是用信息量的冗余来换取的。一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。,检错与纠错,2019年6月16日7时38分,信电学院信息工程系李世银,9,3. 检错与纠错的基本概念,11.2 差错控制编码的基本原理,例1，用1位二进制码的2种编码组合，分别表示“月有阴晴圆缺”中“月”的四种状态。0-圆，1-缺。 a. 若任一位或一位以上的错误都会变成另一码组，所以无法检错和纠错。例如，发送“0”，错误收到“1” b. 若用2位二进制（有4个码组），表示“圆、缺” 两种信息。 0 0 -圆，1 1 -缺 用到的：0 0，1 1 称为“许用码组”： 其余不用的，称为“禁用码组”：1 0，0 1 因任一位误码，都会变成禁用码组，所以可检出1位误码。,续,2019年6月16日7时38分,信电学院信息工程系李世银,10,可见 纠错编码之所以具有检错和纠错能力，是因为在信息码元外添加了冗余码元（监督码元）； 直观地，冗余度越大，许（准）用码组间的区别越大，检错和纠错能力越强。,几个术语,c. 若用3位二进制（有8个码组），表示“圆、缺” 两种信息。 0 00 -圆，1 11 -缺。其余为禁用码。 则可发现两位及以下的误码，并纠正1位误码。,11.2 差错控制编码的基本原理,2019年6月16日7时38分,信电学院信息工程系李世银,11,a. 码重W：码组中非零码元的数目。如“011”码字的码重为2； b. 码距d：两码组中对应码元位置上取值不同的个数。如码字“011”与“110”间码距为2； c. 最小码距d0（Hamming距）：准用码组中任两码组间的最小码距。,几个术语,分组码码距和纠检错能力之间的关系,11.2 差错控制编码的基本原理,2019年6月16日7时38分,信电学院信息工程系李世银,12,【证】设一种编码的最小码距为3。任一个码组A位于O点，码组A发生两位以下错码时，不可能变成另一个准用码组，因而能检测错码的位数等于2。,即，若一种编码的最小码距为d0，则将能检测(d0-1)个错码。反之，若要求检测e个错码，则最小码距d0至少应不小于(e +1)。,分组码的码距和检纠错能力的关系,1）一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力为检测e个错码，要求最小码距 d0e+1,续,2019年6月16日7时38分,信电学院信息工程系李世银,13,【证】图中画出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。 判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。从而，就能够纠正两位错码。,2）为了纠正t个错码，要求最小码距d0 2t + 1,续,2019年6月16日7时38分,信电学院信息工程系李世银,14,图中码组A和B之间距离为5。按照检错能力公式，最多能检测4个错码，即e = d0 1 = 5 1 = 4，按照纠错能力公式纠错时，能纠正2个错码。 但是，不能同时做到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地“纠正”了。 例如，码组A若错了3位(超过2位)，就会被误认为码组B错了2位造成的结果，从而被错“纠”为B。这就是说，检错和纠错公式不能同时成立或同时运用。,3）为纠正t个错码，同时检测e个错码，要求最小码距,续,2019年6月16日7时38分,信电学院信息工程系李世银,15,这种纠错和检错结合的工作方式简称纠检结合。,所以，为了在可以纠正t个错码的同时，能够检测e个错码，就需要像下图所示那样，使某一码组（譬如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距,续,2019年6月16日7时38分,信电学院信息工程系李世银,16,这种工作方式是自动在纠错和检错之间转换的。 当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。 所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的情况。,纠检结合,纠错编码性能,2019年6月16日7时38分,信电学院信息工程系李世银,17,由上节所述的纠错编码原理可知，为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。这样作的结果使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。 系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。 一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。,11.3 纠错编码的性能,系统带宽和信噪比的矛盾：,传输速率和信噪比关系,2019年6月16日7时38分,信电学院信息工程系李世银,18,若希望提高传输速率，可看出势必导致信噪比下降，误码率增大。 假设系统原来工作在图中C点，提高速率后由C点升到E点。但加用纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。,传输速率和Eb/n0的关系对于给定的传输系统,式中，RB为码元速率。,几种简单的常用编码,2019年6月16日7时38分,信电学院信息工程系李世银,19,11.4.1 奇偶效验码 在信息码组an-1,an-2,a1中加入监督位a0，使编码后码组中 “1”的个数为奇数（奇效验）或偶数（偶效验）。 偶效验：取校验码（监督码元）a0，使下式成立 an-1an-2 a1 a0 0 即，a0 = an-1an-2 a1 奇效验：取校验码（监督码元） a0，使下式成立 an-1an-2 a1 a0 1 即， a0 = an-1an-2 a1 1 奇偶效验码码组间最小距离d02，至少可检出一位误码。实际，可检测所有奇数个误码。(用于计算机通信）,水平奇偶校验码,11.4 几种简单的常用编码,2019年6月16日7时38分,信电学院信息工程系李世银,20,a1 n -1 a1 n-2 a11 a10 a2 n-1 a2 n-2 a21 a20 am n-1 am n-2 am1 am0,m个码组分别以各自码组为单位作奇效验或偶效验，然后以各码组的最高位、次高位， 依次发送：,11.4.2 水平奇偶效验码,水平奇偶校验码特点,分组进行奇偶校验,发送次序,当突发的错误数小于m个时，每个码组中的误码个数最多为1个，通过奇偶效验可以检出。,2019年6月16日7时38分,信电学院信息工程系李世银,21,水平奇偶效验码特点：,在上面的分析中，整个方阵作为一个“码组”，长度为原来的m倍； 可检出不大于m个的突发错误； 在未增加监督位的条件下，检错能力为原来的m倍，这是香农信道编码定理应用的一个例子。 该编解码所付的代价：缓存空间和延时增大。,水平垂直奇偶校验码,2019年6月16日7时38分,信电学院信息工程系李世银,22,11.4.3 水平垂直二维奇偶效验码（方阵码）,8.1 差错控制编码的基本概念,a1 n-1 a1 n-2 a11 a10 a2 n-1 a2 n-2 a21 a20 an n-1 an n-2 an1 an0,在水平奇偶监督码的基础上增加列的奇偶效验,可检出任一行和任一列的所有奇数个错误，及长度不大于行数（按列发）或不大于列数（按行发）的突发错误。,其他校验码,2019年6月16日7时38分,信电学院信息工程系李世银,23,11.4.4 恒比码 每个码组中含“1”和“0”的个数的比例恒定，又称等重码 能检测出所有奇数个错误，并能部分检测出偶数个错误（成对交换错则检测不出） 简单，适应于对字母或符号进行编码,11.4.5 群计数码 码组中的监督码元是信息序列中“1”码个数的二进制表示； 假设待编码信息序列为1011101，则编码后码组为1011101101； 较强的检错能力，能检测出几乎所有形式的差错（除同时发生“0”变“1”和“1”变“0”的成对错误外）,正反码,2019年6月16日7时38分,信电学院信息工程系李世银,24,例如，码长n = 10，信息位 k = 5，监督位 r = 5。其编码规则为： 若信息位为11001，则码组为11001 11001； 若信息位为10001，则码组为10001 01110。,11.4.6 正反码,正反码的编码：,它是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信息码元相同或者相反则由信息码中“1”的个数而定:,信息位中有奇数个“1”时，监督位是信息位的重复； 当信息位有偶数个“1”时，监督位是信息位的反码。,正反码解码,2019年6月16日7时38分,信电学院信息工程系李世银,25,先将接收码组中信息位和监督位按模 2 相加，得到一个合成码组。然后，由此合成码组产生一个校验码组： 若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组； 若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。 最后，观察校验码组中“1”的个数，按下表进行判决及纠正可能发现的错码。,正反码的解码：,例,2019年6月16日7时38分,信电学院信息工程系李世银,26,例，发送11001 11001，无错接收，则合成码组应为1100111001=00000。由于接收码组信息位中有奇数个“1”，所以校验码组就是00000。按上表判决，结论是无错码。,若传输中产生了差错： 接收码组错成10001 11001，则合成码组100011100101000。由于接收码组中信息位有偶数个“1”，所以校验码组应取合成码组的反码，即10111。按上表判断信息位中左边第2位为错码。 若接收码组错成11001 01001，则合成码组110010100110000。由于接收码组中信息位有奇数个“1”，故校验码组就是10000，按上表判断，监督位中第1位为错码。 若接收码组为10011 11001，则合成码组100111100101010，校验码组与其相同，按上表判断，这时错码多于1个。 上述长度为10的正反码具有纠正1位错码的能力，并能检测全部2位以下的错码和大部分2位以上的错码。,线性分组码,2019年6月16日7时38分,信电学院信息工程系李世银,27,11.5 线性分组码,11.5.1. 基本概念,线性分组码的特点： (1)两许用码组之和（逐位模2和）仍为一许用码组（封闭性）； (2)码组间的最小距离等于非零码的最小码重。,如何编码？校正子,线性分组码：码组中的信息位和监督位之间的关系由线性方程确定。 表示方法：（n，k）,其中n码组总位数；k信息位数,2019年6月16日7时38分,信电学院信息工程系李世银,28,在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式：,在接收端解码时，实际上就是在计算,若S = 0，就认为无错码；若S = 1，就认为有错码。现将上式称为监督关系式，S称为校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。,11.5.2 校正子,校正子 续,2019年6月16日7时38分,信电学院信息工程系李世银,29,例：具有纠正一位误码的分组码（7，4） a6a5a4a3 a2a1a0 n = 7, k = 4, 信息位 监督位 r = nk3,11.5 线性分组码,定义一组确定误码位置的参量：S1S2S3(校正子),由上表可得：,如何确定a2a1a0 ?,监督位确定,当出现一位误码时，校正子能够确定误码的位置。,11.5.2 校正子（续）,2019年6月16日7时38分,信电学院信息工程系李世银,30,由此,编码时监督位的产生：,给出一组信息码a6a5a4a3 ，可计算出监督位a2a1a0。,例,11.5 线性分组码,11.5.3 监督方程,当无误码时，应有,上述方程亦称为监督方程。,2019年6月16日7时38分,信电学院信息工程系李世银,31,例： 设信息码组a6a5a4a30101 则监督位为：,若接收时有一位(a5)码出错： a6a5a4a3 a2a1a00001101 则有：S1a6a5a4a20001=1 S2a6a5a3a10010=1 S3a6a4a3a00011=0 根据校正子 S1 S2 S3110，可判断误码发生在a5，并恢复。,则发送码组： a6a5a4a3 a2a1a0 0101101,11.5 线性分组码,监督矩阵,2019年6月16日7时38分,信电学院信息工程系李世银,32,11.5.4 监督矩阵,11.5 线性分组码,监督矩阵,该监督方程可用矩阵形式表示,前述的 监督方程,2019年6月16日7时38分,信电学院信息工程系李世银,33,前述的监督方程可用矩阵形式表示,11.5 线性分组码,矩阵H称为监督矩阵。,监督矩阵一般式及性质,这里,11.5.4 监督矩阵,2019年6月16日7时38分,信电学院信息工程系李世银,34,一般地，对于任意的监督方程都可用矩阵形式表示,11.5 线性分组码,矩阵H称为监督矩阵。,监督矩阵的性质：,（1）H由码元间的监督关系S唯一确定； （2）H的行向量相互独立，当采用系统码结构时，具有形式H=PIr 其中Ir是r×r单位阵。并称之为典型监督矩阵。 （3）若发A，收到B，HBT0则有误码。,11.5.4 监督矩阵,生成矩阵,2019年6月16日7时38分,信电学院信息工程系李世银,35,11.5.5 生成矩阵,在上例中，根据监督方程，监督位的产生可表示为,可用矩阵表示为,一般式,其中，,11.5 线性分组码,2019年6月16日7时38分,信电学院信息工程系李世银,36,其转置形式：,式中,例,定义 为生成矩阵。 其中Ik是k×k的单位阵，k为信息位数。,发送码组可按下式产生：,直接得到整个码组，而不是只有监督位！,11.5 线性分组码,2019年6月16日7时38分,信电学院信息工程系李世银,37,如，在上例中,可得生成矩阵,发送码组可按下式产生：,11.5 线性分组码,三个关系,2019年6月16日7时38分,信电学院信息工程系李世银,38,11.5.6 校正S与H及误码码组E的关系,11.5 线性分组码,设发送码组为A，接收码组为B 误码码组为：E=B-A=en-1en-2e1e0,在接收端计算校正子为,矩阵E常称为错误样图。（实际中只知道B而并不知道A和E）,S=BHT=A+EHT AHT+EHT = 0 + EHT =EHT,可见，S仅与E和HT有关，S与E之间存在确定关系，所以只需计算S，就可得到E，从而实现检错纠错。,H与G关系,2019年6月16日7时38分,信电学院信息工程系李世银,39,可见，监督矩阵和生成矩阵存在对应关系，线性码既可以由G确定，也可以直接由H生成。,使用场合,11.5.7 H和G矩阵对应关系,2019年6月16日7时38分,信电学院信息工程系李世银,40,通常，编码时使用生成矩阵，译码时使用监督矩阵。,S=BHT=EHT,例,E、S、监督方程、P、H、G六者之间是相互关联，一一对应的。一个改变必然导致其它5者的相应变化。,2019年6月16日7时38分,信电学院信息工程系李世银,41,【例1】给定一个（7，4）线性分组码的生成矩阵,若信息码为d=1101，求该信息码的线性分组编码。,解：,采用生成矩阵进行编码,11.5.8 应用举例,2019年6月16日7时38分,信电学院信息工程系李世银,42,例2,所以，该信息码的线性分组编码为：1101000,2019年6月16日7时38分,信电学院信息工程系李世银,43,【例2】已知线性（6，3）码的生成矩阵为,求线性分组码、各码组的码重、最小码距和该码的差错控制能力。,解： 因为k=3，所以信息码码组组成的矩阵为（3×8阶）矩阵D：,2019年6月16日7时38分,信电学院信息工程系李世银,44,续,则由,2019年6月16日7时38分,信电学院信息工程系李世银,45,可得出分组码码组矩阵为,码重,2019年6月16日7时38分,信电学院信息工程系李世银,46,可见非零码组的最小码重为3，则分组码的最小码距dmin=3； 因此，该分组码能够检2位错；或同时纠1位错，检1位错。,例三,2019年6月16日7时38分,信电学院信息工程系李世银,47,【例3】 已知一线性(7，4)码的生成矩阵为,求当接收端收到码组R=1010110时，所对应的信息码组D。,分析：首先，需要由G推导出H ； 然后，通过H计算S； 再，判断纠错。,解,2019年6月16日7时38分,信电学院信息工程系李世银,48,解：根据前面H与G的关系可得,将接收码组R=1010110代入，可得S,2019年6月16日7时38分,信电学院信息工程系李世银,49,第7位出错。 所以，接收端收到码组 R=1010110时，所对应的信息码组 D= 0010。,汉明码,？,E、S、监督方程、P、H、G六者之间是相互关联，一一对应的。一个改变必然导致其它5者相应变化。 本题S=111对应的是a4出错。所以信息码应为1000。 请大家验证一下！,2019年6月16日7时38分,信电学院信息工程系李世银,50,监督矩阵,错误图样,监督方程,本题S=111对应的是a4出错。所以信息码应为1000。,2019年6月16日7时38分,信电学院信息工程系李世银,51,11.5.9 汉明码,11.5 线性分组码 第四讲,具有下列特点的线性分组码称之为汉明码：,码长：n2r1，信息位k2r-r-1，监督位：rn-k 记为：（n，k）（ 2r1，2r1r ） 最小码距 dmin3，纠错能力 t1 汉明码的编码效率：,监督矩阵,2019年6月16日7时38分,信电学院信息工程系李世银,52,汉明码的监督矩阵有n列r行，它的n列是除全零以外的r位码组构成，且每一码组只在某列中出现一次。 以r=3为例，可构造如下监督矩阵,其编译码可直接根据H、G使用数字电路实现。其中，译码方法采用计算校正子，然后确定错误图样并加以纠正。,编码器,2019年6月16日7时38分,信电学院信息工程系李世银,53,译码器,编码器,方法1：,方法2：,2019年6月16日7时38分,信电学院信息工程系李世银,54,S=BHT=EHT,译码器,扩展汉明码,译码器,方法1：,方法2：,2019年6月16日7时38分,信电学院信息工程系李世银,55,*11.5.10 扩展汉明码,11.5 线性分组码,在汉明码中增加一位校验码（n，k）（n1，k），对所有的位作偶监督。,例：设原汉明码（7，4）： a7a6a5a4 a3a2a1 a7a6a5a4 a3 a2a1 a0 信息位 监督位 信息位 原监督位 偶校验位 监督矩阵：H He,特点,2019年6月16日7时38分,信电学院信息工程系李世银,56,扩展汉明码特点：,11.5 线性分组码,校正子S的确定方法与原汉明码校正子S的确定方法基本相同。只是新增了一个校正子,最小码距：,在纠正1位误码的同时可以检测两为误码。,在某些情况下也可以将，汉明码的码长和信息位缩短，得到缩短汉明码。如（5，2）,交织码,2019年6月16日7时38分,信电学院信息工程系李世银,57,*11.5.11 交织码,目的：减小信道中错误的相关性，将长突发错误离散成短突发错误或随机错误。,措施：将m个（n,k）分组码码组按行排列成一个m×n的码阵，从而得到一个（mn，mk）交织码，并规定以列的顺序自左至右传送。,性能：如果（n,k）可纠正t个误码，则（mn,mk）可纠正不大于mt的单个突发错误，或纠正t个长度不大于m的突发错误。,循环码,2019年6月16日7时38分,信电学院信息工程系李世银,58,11.6.1 循环码的基本概念 （1）定义 对线性分组码T，如对任意 Ti T，Ti 循环左移或循环右移任意位后得到的码组Ti 仍然有Ti T ，则称T为循环码。 （2）码多项式 为用代数理论研究循环码，可将码组用多项式表示，该多项 式称为码多项式。 一般地，长为n的码组an-1an-2a1a0，对应码多项式T(x),11.6 循环码,式中，xi 的系数对应码字中ai的取值。,例：（7,3）的一个码字：1001110 对应 x6x3x2x,码多项式的按模运算,2019年6月16日7时38分,信电学院信息工程系李世银,59,所有，在模运算下，一整数m按模n运算等于其被n除所得之数余数。,（3）码多项式的按模运算,在整数除法中，可进行按n运算， 若（Q为整数，p n）（模 n）,码多项式的除法,2019年6月16日7时38分,信电学院信息工程系李世银,60,类似地，可以定义关于多项式N(x)的除法运算，若,式中Q(x)为整式，余式R(x)的幂 N(x)的幂。 上式可写成：,记为：,此时，码多项式系数仍按模2运算，即只取0和1值。 例：有,例2,2019年6月16日7时38分,信电学院信息工程系李世银,61,再如,由于在模2运算中，用加法代替了减法，故余项,定理1,2019年6月16日7时38分,信电学院信息工程系李世银,62,证明：设 ， (1) i1时，有,定理1 若T(x)是长度为n的循环码中的一个码多项式，则xiT(x)按模xn1运算的余式T(x)必为循环码中的另一码多项式。 P343,可见余式是由码组an-1an-2a1a0左循环一位之后的得到的码组： an-2a1a0an-1,2019年6月16日7时38分,信电学院信息工程系李世银,63,（接定理1证明），若i2,显然，余式为对应码组an-1an-2a1a0左循环两位之后的得到的码组。 一般地，对任意i有：,余式an-i-1an-i-2a1a0an-1an-2an-i+1an-i 对应an-1an-2a1a0左循环i位之后的得到的码组。 证毕,循环码生成多项式,2019年6月16日7时38分,信电学院信息工程系李世银,64,11.6.2 循环码的生成多项式g(x)及生成矩阵,定理2 循环码中，nk 次码多项式g(x)有且只有一个。g(x)称为循环码码生成多项式。 P343 证明：,（1）在含K个信息位的循环码中，除全0码外，其它码组最多只有k-1个连0。否则，经循环移位后前面k个信息码元全为0，而监督码元不全为0的码组，这在线性分组码中是不可能的。 （2）nk次的码多项式g(x)的常数项不能为0，否则该多项式右移一位就会出现k个连0的情况。(因该码组前k-1位为0) （3）nk次的码多项式g(x)只可能有一个，若有两个，两多项式相加后由线性分组码的封闭性仍为码多项式，但由于nk次项和常数项相消，会产生k1连0的情况，由（1）分析，这是不可能的。 综上（1）、（2）和（3），证毕。,循环码生成矩阵,2019年6月16日7时38分,信电学院信息工程系李世银,65,循环码生成矩阵G(x),例,任一码多项式都可由其信息码元和生成矩阵Gx确定：,2019年6月16日7时38分,信电学院信息工程系李世银,66,例如表11-5的(7,3)循环码，n=7, k=3, r=4,唯一的一个(n k) = 4次码多项式代表的码组是第二码组0010111，与它相对应的码多项式，即生成多项式,定理3,其生成矩阵分别为,2019年6月16日7时38分,信电学院信息工程系李世银,67,11.6.2 循环码的生成多项式g(x)及生成矩阵(续),g(x)为码多项式A(x)的一个因式，所以T(x)可被g(x)整除。证毕,循环码生成多项式（续）定理4,推论：次数不大于k1次的任何多项式与g(x)的乘积都是码多项式。,定理 3 在循环码中，所有的码多项式T(x)都能够被g(x)整除。 P344 式11.6-18,证明：因为任一码多项式都可由其信息码元和生成矩阵Gx确定：,2019年6月16日7时38分,信电学院信息工程系李世银,68,11.6.2 循环码的生成多项式g(x)及生成矩阵(续) 定理4 循环码（n，k）的生成多项式g(x)是xn1的一个因式。,其中R(x)的幂小于n。由定理1，R(x)是码多项式，又由定理3，有 R(x)=h(x)g(x)，即有,移项整理得：,即g(x)是xn1的一个因式。证毕,总结,证明：因为g(x)幂为nk，因而可得,定理1 若T(x)是长度为n的循环码中的一个码多项式，则xiT(x)按模xn1运算的余式T(i)(x)必为循环码中的另一码多项式。 定理3 在循环码中，所有的码多项式T(x)都能够被g(x)整除。,2019年6月16日7时38分,信电学院信息工程系李世银,69,11.6.2 循环码的生成多项式g(x)及生成矩阵(续),总结：,监督多项式,定理1 若T(x)是长度为n的循环码的一个码多项式，则xiT(x)按模xn1运算的余式T(i)(x)必为循环码中的另一码多项式。 定理2 循环码中，nk次码多项式g(x)有且只有一个。g(x)称为循环码码生成多项式。 定理3 在循环码中，所有的码多项式T(x)都能够被g(x)整除。 推论：不大于k1次的任何多项式与g(x)的乘积都是码多项式。 定理4 循环码（n，k）的生成多项式g(x)是xn1的一个因式。,生成多项式g(x)的三个性质（充要条件）： （1）g(x)是nk次多项式； （2）g(x)的常数项不等于0； （3）是xn1的一个因式。,2019年6月16日7时38分,信电学院信息工程系李世银,70,则，对任一码多项式，T(x)I(x)g(x)，有 h(x)T(x)=h(x)I(x)g(x)=h(x)g(x)I(x)=(xn+1)I(x) 即若T(x)是许用码组对应的多项式，其与h(x)的乘积h(x)T(x)一定可被 xn1整除。,称h(x)为循环码的一致校验多项式，即监督多项式。 h(x)是常数项为1的k次多项式,由定理4”循环码（n,k）的生成多项式g(x)是xn1的一个因式“可知,*11.6.3 监督多项式,监督矩阵,编译码,2019年6月16日7时38分,信电学院信息工程系李世银,71,根据监督多项式，可得监督矩阵H,其中h*(x)是h(x)的逆多项式。,例,*11.6.3 监督多项式及监督矩阵,2019年6月16日7时38分,信电学院信息工程系李世银,72,例如(7，3)循环码，g(x)=x4+x3+x2+1，则,循环码的编译码,2019年6月16日7时38分,信电学院信息工程系李世银,73,11.6.4 循环码的编码和译码,1.采用循环码生成矩阵：,例：若生成多项式 g(x)x4+x3+x2+1 ，k=3，则其生成矩阵为：,实际的编码方法,对应的矩阵G一般不符合 Ik,Q 的形式。编码输出结果相当于m(x)g(x)为非系统码结构。信息码和监督码不容易区分。,设数据101,则输出为,2019年6月16日7时38分,信电学院信息工程系李世银,74,2. 系统结构循环码的编码方法,11.6.4 循环码的编码和译码（续）,（1）以xn-k乘信息多项式m(x)，得到xn-k m(x)；（幂 n） （2）用g(x)除xn-k m(x)得余式r(x) ( 幂 n-k ) 即 xn-k m(x)Q(x)g(x)+r(x) （3） 编码输出的码多项式 T(x)= xn-k m(x)+r(x) （*） 上述编码方式的合理性： T(x)=xn-km(x)+r(x)Q(x)g(x)+r(x)+r(x)=Q(x)g(x) 因为Q(x)的幂次数小于k，所以Q(x)g(x)一定是循环码的码多项式，显然（*）定义的T(x)为一种系统码结构的循环码。,编译码器,2019年6月16日7时38分,信电学院信息工程系李世银,75,*3. 循环码编码器的电路实现,8.3.4 循环码的编码和译码（续）,除法运算的实现过程： 先将移位寄存器清“0”； 进行n次移位，将被除数全部送入除法器后，在寄存器内，即可得到相应的余式。,例：除数为 g(x)x6x5x4x31 除法电路，(即r=6) 如下图，反馈的接入由g(x)确定,例,（a）多项式除法 多项式除法可用带反馈的移位寄存器实现。,2019年6月16日7时38分,信电学院信息工程系李世银,76,（接上例）计算m(x)/g(x)，设m(x)=x13+x11+x10+x7+x4+x3+x+1,即k=14,0 1 0 1 1 0 0 1 0 0 1 1 0 1 1,000000 100000 010000 101000 110100 011010 001101 000001 100111 110100 111010 111101 111001 011011 001010 余 数,0 0 0 0 0 0 1 1 1 0 0 1 1 1 0,x,6,x,5,x,4,x,3,1,000000,0,100000,1,0,010000,0,0,101000,1,0,110100,1,0,011010,0,0,001101,0,1,000001,1,1,100111,0,1,110100,0,0,111010,1,0,111101,1,1,111001,0,1,011011,1,1,001010,1,0,除法运算在移位进行了r-1位后才开始，运算完成后，要将余式移出，还要做r-1次移位。速度较慢。,实际电路,2019年6月16日7时38分,信电学院信息工程系李世银,77,（b） 实际应用的循环码编码电路 特点：采用“预先乘xn-k方案”（信号直接到达最后一级），边移位 边做除法运算，当k个信息码输入后，同时也完成了除法运算。,（1）当信息位输入时，开关K1、K