[信息与通信]新第5章差错控制编码.ppt

1,第5章 差错控制编码,5.1 引言 5.2 差错控制编码的基本原理 5.3 常用的简单编码 5.4 线性分组码 5.5 循环码,2,5.1 引言,数字信号在传输过程中受到干扰的影响，使信号波形变坏，发生误码，可以采用一些方法解决。,有效性信源编码 可靠性信道编码,3,0 、复习,模拟信源：在无线广播中，信源一般是一个语音源（话音或音乐）；在电视广播中，信源主要是活动图像的视频信号源。这些信源的输出都是模拟信号，所以称之为模拟源。,信源编码：将模拟信息源的输出转化为数字信号，即A/D转换。,信源编码目的：提高通信有效性，减少原消息的冗余度。,5.1 引言,4,差错出现原因 外界噪声 传输中码间串扰,解决方法 合理地设计基带信号，选择调制、解调方式，采用均衡技术，发送功率等因素，使误比特率降低。 差错控制措施。,5.1 引言,5,差错控制编码属信道编码，要求在满足有效性前提下，尽可能提高数字通信的可靠性。 差错控制编码是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号。例如奇偶校验。 差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。,5.1 引言,6,按功能分：检错码和纠错码 按监督码元与信息码元关系分：线性码与非线性码 按信息码元与监督码元之间的约束关系不同分：分组码与卷积码 按信息码元在编码后是否保持原来的信号形式分：系统码与非系统码 按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码 按码元的取值分：二进制码与多进制码,1、差错控制编码分类,5.1 引言,7,2、误码类型,随机误码,突发误码,错码出现是随机的、错码之间统计独立。 由随机噪声引起 存在随机误码的信道称为随机信道无记忆信道,差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关 例如：脉冲噪声，存储系统中磁带的缺陷或读写头接触不良引起，再例如用手机过涵洞，且无发射天线 存在这种差错的信道称为突发信道有记忆信道,5.1 引言,3、错误图样,例如： 设发送数据序列为：00000000001111111111 接收数据序列为： 01101001001111001001 错误图样（差错序列）：发送数据序列与接收序列对应码位的模和 则差错序列为： 01101001000000110110 可见 发生了两个长度分别为和的突发差错，其错误图样分别为1101001和11011 突发长度：指突发差错首位与末位之间的长度（中间可能有没错的码位）,9,说明 差错序列或错误图样中的“”表示对应码位没错，而“”表示有错 实际信道很复杂，所出现的差错并不是单一的，往往是随机和突发差错并存，只不过以某种错误为主 一般说来，纠正随机差错的编译码方法和设备比较简单，成本较低，效果较显著；而纠正突发差错的编译码方法和设备比较复杂，成本较高，效果也不如前者显著,5.1 引言,10,4、信道类型,随机信道,突发信道,混合信道,5.1 引言,11,5、差错控制方法,检错重发（ARQ） 停发等候重发 返回重发 选择重发 前向纠错（FEC） 反馈校验（IRQ） 混合方式（HEC）,5.1 引言,12,（1）检错重发法（ARQ） Automatic Repeat reQuest,收端在接收到的信码中发现错码时，就通知发端重发，直到正确接收为止。例如奇偶校验。 检错重发方式只用于检测误码，能够在接收单元中发现错误，但不一定知道该错误码的具体位置。 需具备双向信道。,5.1 引言,图5.1-1（b) 检错重发（ARQ),判断有无错误,14, 停发等候重发,图5.1-2 停发等候重发,5.1 引言,15,发端在Tw时间内送出一个码组； 收端收到后检查。 如果未发现错误，则发回一个认可信号（ACK）给发送端，发送端收到ACK信号再发下一个码组 若检测到错误，则发回一个否认信号（NAK），发送端收到NAK信号后重发前一码组，并再次等候ACK信号或NAK信号 发送两个码组之间有停顿时间TI，影响了传输效率,5.1 引言,16, 返回重发,图5-2(b) 返回重发,其发送端不停地送出一个个连续码组，不再等候收端返回的ACK信号 一旦收端发现错误并返回NAK信号，则发端从下一码组开始重发前面的N个码组 N的大小取决于信号传递及处理所带来的延时,5.1 引言,17,5.1 引言,图5.1-3 返回重发,18, 选择重发,也是连续不断地发送码组，收端检测到错误后发回NAK信号。 与返回重发不同的是，发端并不重发错误码组后的所有码组，而只重发有错的那个码组,5.1 引言,19,图5.1-4 选择重发,5.1 引言,20,三者比较 选择重发传输效率最高，但成本最贵：控制机制复杂，发端和收端都要有数据缓冲器； 返回重发、选择重发需要全双工数据链路，而停发等候重发只要求半双工的数据链路。,5.1 引言,21,（2）前向纠错法（FEC） Forward Error Correction,图5.1-5 前向纠错（FEC),5.1 引言,22,发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正 不需要反馈信道，特别适合只能提供单向信道场合 自动纠错，不要求检错重发，延时小，实时性好 纠错码必须与信道的错误特性密切配合 若纠错较多，则编、译码设备复杂，传输效率低,5.1 引言,23,（3）信息反馈校验法（IRQ） Information Repeat reQuest,接收端将接收到的信码原封不动地转发回发端，并与原发送信码相比较，若发现错误，发端再重发。,5.1 引言,24,收端把收到的数据序列全部经反向信道送回发端，发端比较发出和送回的数据序列，从而发现有否错误，如果有错误，发端将数据序列再次传送，直到发端没有发现错误。 不需要纠错、检错的编、译码器，设备简单。 需要和正向信道相同的反向信道，实时性差 发端需要一定容量的存储器以存储发送码组 仅适应于传输速率较低，信道差错率较低，具有双向传输线路及控制简单的系统,5.1 引言,25,（4）混合纠错检错（HEC） Hybrid Error Correction,FEC与ARQ的结合 发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发。 在实时性和译码复杂性方面是FEC和ARQ的折衷。,5.1 引言,26,5.1 引言,27,核心问题,发现错误 纠正错误,5.1 引言,28,5.2 差错控制编码的基本原理,在信息码序列中加监督码就称为差错控制编码，也叫纠错编码。 不同的编码方法，有不同的检错和纠错能力，增加监督码元越多，检（纠）错能力越强。 差错控制编码原则上是降低编码效率来换取可靠性提高。（即误码率更小）。,29,理论依据：Shannon信道编码定理。 定理指出： 对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。,1、纠错编码的理论依据,5.2 差错控制编码的基本原理,30,5.2 差错控制编码的基本原理,31,2、纠错编码的基本思想,5.2 差错控制编码的基本原理,发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系 以牺牲通信的有效性（信息传输速率）来提高可靠性 码的检错和纠错能力是用信息量的冗余来换取的。一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。,32,码长：码字中码元的数目。 码距：两个码组之间对应位上码元取值不同的个数，定义为两码字的距离，简称码距（d）。 对于二进制称作这两个码字的汉明距离。如两码字“10011”与“11010”间码距为2。,3、码距与检错和纠错能力的关系,5.2 差错控制编码的基本原理,（1）几个概念,33,最小码距：在一个码字集合中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为dmin或d0 码重：码字中非零码元的数目定义为该码字的重量，简称码重。如“10011”码字的码重为3。,纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。,5.2 差错控制编码的基本原理,34,举例说明：假如要传送A、B两个消息,编码一： 消息A-“0”；消息B-“1” 最小码距1 若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力。,5.2 差错控制编码的基本原理,35,编码二： 消息A-“00”；消息B-“11” 最小码距2 “00、11”称为许用码组，而“01、10”称为禁用码组 若传输中产生一位错码，则变成“01”或“10”，收端判决为有错，但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。 这表明增加一位冗余码元后码具有检出一位错码的能力,5.2 差错控制编码的基本原理,编码三： 消息A-“000”；消息B-“111” 最小码距3 传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。 在产生一位错码（错1位概率远远大于错2位、3位概率）情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。例如收到110，认为是111。 这表明增加两位冗余码元后码具有检出两位错码或纠正一位错码的能力。,37,一个码能检测e个错码，则要求其最小码dmine+1 一个码能纠正t个错码，则要求其最小dmin2t+1 一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 dmine+t+1 (et),（2）最小码距与检错和纠错能力的关系,5.2 差错控制编码的基本原理,38,(a) 检e个错,图5.2-2(a) 码距与检错纠错能力的关系,A、B都为许用码； A发生e个错； B不能靠在球面上，否则收到B无法判断是否为错码； dmine+1,5.2 差错控制编码的基本原理,39,1,(b)纠正t个错码,图5.2-2(b) 码距与检错纠错能力的关系,A、B都为许用码； A、B都发生t个错； dmin2t+1,5.2 差错控制编码的基本原理,40,(c)纠正t个错码，检测e个错码,图5.2-2(c) 码距与检错纠错能力的关系,A、B都为许用码； 当误码数小于等于t时，可纠正误码； 当误码数大于t小于等于e时，不会落入另一码组的纠错范 围内。 dmine+t+1,5.2 差错控制编码的基本原理,41,当码长n=7, P=10-3时，则有,假设随机信道中发送“0”码与发送“1”码传错概率相等都为P,且P1,则在码长为n的码组中发生r个错误的概率为：,4、误码率,大概率事件,5.2 差错控制编码的基本原理,42,设n=k+r 指一个码组中信息位所占比重，用 表示 =k/n=k/(k+r)，其中k为信息码元的数目，n为码长 编码效率是衡量纠错性能的一个重要指标，一般情况下，监督位越多，检纠错能力越强，但相应的编码效率也越低,5、编码效率,一次课,5.2 差错控制编码的基本原理,43,奇偶监督码 二维奇偶监督码 恒比码 正反码,5.3 常用的简单编码,44,1、奇偶监督码,5.3 常用的简单编码,奇偶监督码：在信息码元后附加一位监督位，使得码组中 “1”的个数为偶数或奇数。,45,最小码距dmin=2 只能检测出单个或奇数个错误，不能纠错 应用：以随机错误为主的计算机通信系统，难于对付突发错误 编码效率=k/n=k/(k+1),5.3 常用的简单编码,46,将经过奇偶监督编码的码元序列按行排成方阵，每行为一组奇偶监督码，但发送时按列的顺序传输 接收端将码元排成发送时的方阵形式，再按行进行奇偶校验 能够发现某行上所有奇数个错误以及突发长度不大于方阵行数的突发错误 编码效率,2、水平奇偶监督码,5.3 常用的简单编码,表5-1 水平奇偶监督码,表5-2 水平奇偶监督码接收端出现突发误码示例,结论：能够发现突发长度不大于方阵行数的突发错误,49,又称为方阵码、行列监督码、二维奇偶监督码。 将水平奇偶监督码推广到二维。即在水平监督基础上再对方阵中每一列进行奇偶校验，发送时按列的顺序传输 接收端将码元排成发送时的方阵形式，再分别按行、按列进行奇偶校验,3、水平垂直奇偶监督码,5.3 常用的简单编码,50,能够发现某行、某列上所有奇数个错误以及突发长度不大于方阵行数或列数的突发错误； 有可能检测出偶数个错误（在行上检测不出，但有可能在列上检测出），但当偶数个错误刚好构成矩形时，则检测不出 可纠正一些错误,5.3 常用的简单编码,表5-3 水平垂直奇偶监督码,发送顺序,表5-4 水平垂直奇偶监督码接收端纠错示例,例如：当码组中仅在一行有奇数个错误时，能够确定错误位置，并纠正它。,表5-5 水平垂直奇偶监督码接收端检错示例,0,1,1,构成矩形的偶数个误码检测不出。,0,0,表5-6 水平垂直奇偶监督码接收端检错示例,0,1,有可能检测出偶数个误码。,0,0,1,55,4、ISBN国际图书统一编号 International Standard Book Number,无误码，若不能被11整除，有误码,5.3 常用的简单编码,56,5.3 常用的简单编码,能被11整除，无误码。,57,5.4 线性分组码 （重点）,(1) 分组码： 先将信息码分组，然后给每组信码附加若干监督码的编码称为分组码，用符号(n,k)表示，k是信息码的位数，n是编码组总位数，又称为码长，r=n-k为监督位数。 (2) 代数码： 建立在代数学基础上的编码，称为代数码。例如奇偶校验码。,1、基本概念,58,(3) 线性码： 线性码中信息位和监督位是按一组线性方程构成的。线性码是一种代数码。奇偶监督码是最简单的线性码。 (4) 线性分组码： 信息码分组后，附加的监督码和信息码由一些线性代数方程联系着的编码称为线性分组码。,5.4 线性分组码,59,2、线性分组码的性质,任意两个许用码组之和（逐位模2和）仍为一许用码组，即具有封闭性。 最小码距=非零码的最小码重（1的个数）。（因为线性分组码中必有一个全0码组）,5.4 线性分组码,60,以汉明码为例来说明编码原理。汉明码是一种设计用来纠正一位错码且编码效率较高的线性分组码。（7，4）汉明码的编码效率为：,3、线性分组码的编码原理,5.4 线性分组码,61,发送端编码：将一位监督码元附加在信息码元后，使得码元中“1”码元个数为偶数。 接收端译码： 计数接收码组中“1”码元个数是否为偶数，即计算：S=an-1+ an-2+ a0 （模2加）（5.4-1） S=0认为没错，S=1认为有错。 （5.4-1）式称为监督方程/监督关系式，S称为校正子/校验子/伴随式,（1）回忆奇偶监督偶校验码,5.4 线性分组码,62,监督位增加到2位：有两个监督方程，两个校验子； 两个校验子组合有四种（如00表示无错，01、10、11则可表示一位错码的三种可能位置） 监督位增加到r位：可指示一位错码的（2r-1）个可能位置 对于（n，k)分组码，若希望用r=n-k个监督位构造出的r个监督关系式来指示一位错码的n种可能位置，则要求：,可以这样来考虑,2r-1n 即2r k+r+1 （5.4-2）,5.4 线性分组码,63,欲纠正一位错码，由（5.4-2）式知r 3。取r=3，则n=k+r=7 设7位码元为：a6a5 a0； 三个校正子：S1、S2、S3； 可规定S1S2S3的八种组合与一位错码的对应关系（也可规定为另一种对应关系）：,构造一（n，k)分组码，k=4并能纠正一位错码,(2) 汉明码的构造,5.4 线性分组码,64,表5-9 S1S2S3的八种组合与一位错码的对应关系,5.4 线性分组码,S1= a2+a4+a5+a6 S2= a1+a3+a5+a6 S3= a0+a3+a4+a6,(5.4-3),监督方程（模2加）: 仅当有一个错码且位置在a2、a4、a5、a6时，S1为1，否则为0。这就意味着这四个码元构成偶数监督关系，即：,66,（3）发端编码的原则：,信息码元a6 、a5 、a4、a3来源于待编码的信息序列； 监督码元 a2 、a1、 a0的取值应根据信息码元按监督关系式来决定，即使前面三式中的S1、 S2 、S3均为0(000表示无错码）：,5.4 线性分组码,67,a2 = a4+a5+a6 a1 = a3+a5+a6 a0 = a3+a4+a6,给定信息位后，根据上式算出各监督位，该编码的所有码组如表5-10：,(5.4-4),a6+a5+a4+a2=0 a6+a5+a3+a1=0 a6+a4+a3+a0=0,(5.4-5),5.4 线性分组码,表5-10 许用码组,69,该汉明码的编码效率较高 R=k/n=4/757% 该码的最小码距为3，能纠正一个错码或检测两个错码 设收到码组0000011，按监督方程计算可得：S1=0，S2=1，S3=1；再根据校正子组合与一位错码位置的对应关系，可知错码发生在a3位，并加以纠正。0001011,5.4 线性分组码,70,（4）监督矩阵,沿（7，4）汉明码出发，式（5.4-4）可改写成： 1 a6+ 1 a5+ 1 a4 +0 a3+ 1 a2 + 0 a1+ 0 a0=0 1 a6+ 1 a5+ 0 a4 +1 a3+ 0 a2 + 1 a1+ 0 a0=0 1 a6+ 0 a5+ 1 a4 +1 a3+ 0 a2 + 0 a1+ 1 a0=0 写成矩阵形式：,(5.4-6),5.4 线性分组码,71,H称为线性码监督矩阵,可化简为： HAT=0T 或AHT=0,5.4 线性分组码,72,rn阶矩阵 H确定了编码时监督码元与信息码元的关系 把具有PIr形式的H矩阵称为典型形式的监督矩阵，其中P为r k阶矩阵, Ir为r r阶单位方阵 当H不是典型阵时，可变换为典型阵。由典型阵构成的码组称为系统码，非典型阵构成的码组称为非系统码 H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关,监督矩阵H特点,5.4 线性分组码,73,上式右部前面矩阵就是监督矩阵H中的P矩阵。,(5) 生成矩阵,同样，监督码生成方程（5.4-5）式也可写成矩阵形式，即,(5.4-7),5.4 线性分组码,74,其中Q=PT可见，Q为k r阶矩阵。,或写成,5.4 线性分组码,75,生成矩阵G：在Q矩阵的左边加上一个k k阶矩阵， 即,5.4 线性分组码,76,k n阶矩阵 编码方法完全由生成矩阵G确定 把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中，Ik为kk阶单位方阵，Q为k r阶矩阵 由典型生成矩阵产生的分组码一定是系统码 G矩阵的各行应线性无关，每行均为许用码组,生成矩阵G特点,5.4 线性分组码,77,例5-2 已知（6，3）汉明码的生成矩阵如下， (1)列出所有许用码组; (2)最小码距d0; (3)检错纠错能力 (4)编码效率,5.4 线性分组码,（1）,（3）,（4）,（2）,80,设（7,4）线性码的生成矩阵G为：,当信息位为0001时， （1）试求其后的监督位。 （2）监督矩阵H,5.4 线性分组码,81,解： （1）,82,（2）监督矩阵H 根据生成矩阵和监督矩阵的关系： G= IkQ，H=PIr 其中P=QT，可得监督矩阵H为：,83,错误矩阵/错误图样E： 设发送码组为A，接收码组为B，,(6) 校正子与检错,则错误矩阵,5.4 线性分组码,84,接收端计算校正子S，即 S=BHT=(A+E)HT=AHT+EHT=0+ EHT= EHT 可见校正子只与E有关，即错误图样与校正子之间有确定的关系，所以可从错误图样与校正子的关系表中确定错码位置，加以纠正。,5.4 线性分组码,85,以（7，4）汉明码为例 设发送码组A=（0001011） 接收码组 B=（0000011） 则收端译码过程如下： 计算校正子,查表得a3为错误位置，即可纠正（0001011）,5.4 线性分组码,86,5.4 线性分组码,4、（7，4）汉明码编译码仿真,汉明码编译码仿真,87,设A1和 A2为码中任意两许用码组， 则有 A1HT=0 A2HT=0 于是A1HT+ A2HT=（ A1 + A2）HT=0 即（ A1 + A2）必是该码中一许用码组,例5-3 证明线性分组码的封闭性。（略）,p319：9-6,作 业,5.4 线性分组码,88,5.5 循环码,循环码是一种重要的线性分组码。这种码的编码和解码设备都不太复杂，且有较强的检（纠）错能力。 共n位。通常前k位为信息位，后r位为监督位。,5.5.1 循环码的编码原理,89,循环码的特点： 封闭性； 循环性；即码中任一码组循环一位(将最右端的码元移到左端或反之）以后，仍为该码中的一个码组。,5.5.1 循环码的编码原理,90,若(an-1,an-2,a1,a0)是一(n,k)循环码的码组，则 (an-2 ,an-3 ,a1,a0 ,an-1) (an-3 ,an-4 , , a0 , an-1 ,an-2) ( a0 ,an-1 , an-2 ,an-3 ,a2 ,a1) 也都是该循环码的码组。,5.5.1 循环码的编码原理,91,表5-10一种（7，3）循环码的全部码字,把码长为n的码组中的各码元当作n-1次多项式的系数 若码组A=（an-1，an-2，a1，a0)，则其相应的码多项式为： T(x)= an-1xn-1+ an-1xn-1+ + a1x+ a0 对于（7，3）循环码的任意码组可表示为： T(x)= a6x6+ a5x5+ a4x4 + a3x3 + a2x2 + a1x+ a0 如码组（1100101）对应的码多项式可表示为 T7(x)= 1x6+1 x5+ 0 x4 + 0 x3 + 1 x2 + 0 x+1 = x6 + x5 + x2 +1,1、码多项式T(x),93,码多项式与码组的关系： 本质上是一回事，仅是表示方法的不同而已。对于二进制码组，多项式的每个系数不是0就是1，x仅是码元位置的标志。因此，这里并不关心x的取值。,0+0=0 0+1=1 1+0=1 1+1=0 0*0=0 0*1=0 1*1=1,5.5.1 循环码的编码原理,94,若一个整数m可以表示为:,则在模n运算下，有mp（模n），同样对于多项式而言：,则可以写为：F(x)R(x) （模N(x)）。,即一任意多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x),5.5.1 循环码的编码原理,95,例如码组（1100101）对应的码多项式可为： T7(x)= x6 + x5 + x2 +1 其被x3+1除得 x6 + x5 + x2 +1 1 （模x3+1）,5.5.1 循环码的编码原理,96,在循环码中，若T(x)是一个长为n的许用码组，则xi T(x)在按模xn+1运算下，也是一许用码组。即若 xi T(x)Ti(x) （模xn+1） 则Ti(x) 也是一许用码组，且为A(x)码组向左循环移位i次的结果。,重要结论,5.5.1 循环码的编码原理,97,例如A4=0111001，对应的码多项式为 ：,A4向左循环移1位得A7=1110010，这相当于将A4(x)乘以x，即,A7向左循环移1位得A6=1100101，但若将A7(x)乘以x得到多项式为 对于(7，3)循环码的码多项式，其最高次数不能超过6，解决该问题的办法是对上式作模x7+1运算得余作为码多项式,98,例如：,其对应的码组为0101110，它正是表5-10中第3码字。,结论：一个码长为n的(n，k)循环码，它必为按模xn+1运算的一个余式。,5.5.1 循环码的编码原理,99,循环码完全由其码组长度n和生成多项式g(x)所决定 问题：寻找构成生成矩阵的k个线性无关的许用码组,2、循环码的生成多项式与生成矩阵,5.5.1 循环码的编码原理,100,生成多项式： 如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如(7,3)循环码中，,其它码多项式都是g(x)的倍式， 即,101,（n，k)循环码中一定能找到这样一个码组：前面的k-1位都是0，而第k位及第n位为1，其它各位gi为0或1： （00001gn-k-1gn-k-2 g2 g11),其对应的码多项式为g(x)，且 g(x)一定是码中唯一的一个n-k次多项式，这唯一的n-k次多项式g(x)称为码的生成多项式,5.5.1 循环码的编码原理,102,也就是说，最高次方为n-k，最后一位为1的多项式即为生成多项式g(x) 如（7，3）循环码， T(x)= a6x6+ a5x5+ a4x4 + a3x3 + a2x2 + a1x+ a0前k-1位为0，即前两位为0，因为k=3，也就是最高次方为n-k=4，最后一位a0为1的多项式即为g(x) 。,5.5.1 循环码的编码原理,103,例如： 上表中的编码为(7, 3)循环码，n = 7, k = 3, n k = 4，其中唯一的一个(n k) = 4次码多项式代表的码组是第二码组0010111，与它对应的码多项式即生成多项式为： g(x) = x4 + x2 + x + 1。,104,可以证明生成多项式g(x)具有以下特性： （1） g(x)是一个常数项为1的 次多项式； （2） g(x)是 的一个因式； （3）该循环码中其它码多项式都是g(x)的倍式。 g(x)， xg(x) ， xk-1g(x),5.5.1 循环码的编码原理,105,g(x)， ， xk-1g(x)都是许用码组，连同g(x)共k个许用码组，构成码的生成矩阵G(x),注：该生成矩阵并不是典型形式的，但可通过线性变换变换成典型的生成矩阵。,5.5.1 循环码的编码原理,106,一旦生成多项式g(x)确定以后，该循环码的生成矩阵G(x)就可以确定，进而该循环码的所有码字就可以确定。生成矩阵G(x)的每一行都是一个码组。,5.5.1 循环码的编码原理,107,例5-4试求表5-10 （7，3）循环码的生成多项式和生成矩阵。,解：对（7,3）循环码，n=7，k=3, r=4 由上例已知生成多项式为：g(x)= x4+x2+x+1,5.5.1 循环码的编码原理,将第1行与第3行模2加作为第1行，则有,为典型生成矩阵,108,接上例设信息码为101，求整个码组。,解：整个码组A=信息码*G（典型的） 故 A=1 0 1 =1 0 1 1 1 0 0,5.5.1 循环码的编码原理,109,例5-5 已知循环码的生成多项式为 ， 当信息位为1000时，写出它的监督位和整个码组。 解：由生成多项式可知n-k=3，而k=4，所以n7,110,第1行+第3行+第4行 第1行,第2行+第4行 第2行,非典型,典型,当信息位为1000时，整个码组为,111,监督位为 101,112,已知（7，4）循环码的全部码组为：,试写出该循环码的生成多项式g(x)和生成矩阵G，并将G化成典型矩阵。,5.5.1 循环码的编码原理,113,解：n=7，k=4，n-k=3 上述码组中的(n-k)=3次码多项式为第2组，它所对应的码多项式g(x)即为生成多项式：g(x)=x3+x+1。 生成矩阵为：,114,5.5.2 循环码的编码、解码方法,1、编码方法,（1）原理,用码多项式来表示为：,A = mk-1 mk-2 m0 ar-1 a1 a0,式中M(x)是信息码组码多项式，所以只需要确定r(x) 已知循环码的所有码字都能够被g(x)整除，r(x)可由下式确定：,115,设信息位对应的多项式为m(x) 用xn-k乘m(x)，相当于把信息码后附加上（n-k）个“0” （详细解释） 用g(x)除xn-k m(x)，得到余式为r(x) 编出码组为：T(x)= xn-k m(x)+ r(x),(2)编码步骤,5.5.2 循环码的编码、解码方法,116,例如:信息码为110，它相当于m(x)x2+x。当n-