新第5章差错控制编码

null第5章 差错控制编码第5章 差错控制编码5.1 引言 5.2 差错控制编码的基本原理 5.3 常用的简单编码 5.4 线性分组码 5.5 循环码null5.1 引言数字信号在传输过程中受到干扰的影响，使信号波形变坏，发生误码，可以采用一些方法解决。 有效性——信源编码 可靠性——信道编码null0 、复习 模拟信源：在无线广播中，信源一般是一个语音源（话音或音乐）；在电视广播中，信源主要是活动图像的视频信号源。这些信源的输出都是模拟信号，所以称之为模拟源。 信源编码：将模拟信息源的输出转化为数字信号，即A/D转换。 信源编码目的：提高通信有效性，减少原消息的冗余度。5.1 引言null差错出现原因 外界噪声 传输中码间串扰解决方法 合理地设计基带信号，选择调制、解调方式，采用均衡技术，发送功率等因素，使误比特率降低。 差错控制措施。5.1 引言null 差错控制编码属信道编码，要求在满足有效性前提下，尽可能提高数字通信的可靠性。 差错控制编码是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号。例如奇偶校验。 差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。5.1 引言null 按功能分：检错码和纠错码 按监督码元与信息码元关系分：线性码与非线性码 按信息码元与监督码元之间的约束关系不同分：分组码与卷积码 按信息码元在编码后是否保持原来的信号形式分：系统码与非系统码 按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码 按码元的取值分：二进制码与多进制码1、差错控制编码分类5.1 引言null2、误码类型 随机误码 突发误码错码出现是随机的、错码之间统计独立。 由随机噪声引起 存在随机误码的信道称为随机信道／无记忆信道差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关 例如：脉冲噪声，存储系统中磁带的缺陷或读写头接触不良引起，再例如用手机过涵洞，且无发射天线 存在这种差错的信道称为突发信道／有记忆信道5.1 引言null3、错误图样例如： 设发送数据序列为：00000000001111111111 接收数据序列为： 01101001001111001001 错误图样（差错序列）：发送数据序列与接收序列对应码位的模２和 则差错序列为： 01101001000000110110 可见 发生了两个长度分别为７和５的突发差错，其错误图样分别为1101001和11011 突发长度：指突发差错首位与末位之间的长度（中间可能有没错的码位）null说明 差错序列或错误图样中的“０” 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示对应码位没错，而“１”表示有错 实际信道很复杂，所出现的差错并不是单一的，往往是随机和突发差错并存，只不过以某种错误为主 一般说来，纠正随机差错的编译码方法和设备比较简单，成本较低，效果较显著；而纠正突发差错的编译码方法和设备比较复杂，成本较高，效果也不如前者显著5.1 引言null 4、信道类型 随机信道 突发信道 混合信道5.1 引言null5、差错控制方法检错重发（ARQ） 停发等候重发 返回重发 选择重发 前向纠错（FEC） 反馈校验（IRQ） 混合方式（HEC）5.1 引言null（1）检错重发法（ARQ） Automatic Repeat reQuest 收端在接收到的信码中发现错码时，就 通知 关于发布提成方案的通知关于xx通知关于成立公司筹建组的通知关于红头文件的使用公开通知关于计发全勤奖的通知 发端重发，直到正确接收为止。例如奇偶校验。 检错重发方式只用于检测误码，能够在接收单元中发现错误，但不一定知道该错误码的具体位置。 需具备双向信道。5.1 引言null图5.1-1（b) 检错重发（ARQ)判断有无错误null① 停发等候重发图5.1-2 停发等候重发5.1 引言null发端在Tw时间内送出一个码组； 收端收到后检查。 如果未发现错误，则发回一个认可信号（ACK）给发送端，发送端收到ACK信号再发下一个码组 若检测到错误，则发回一个否认信号（NAK），发送端收到NAK信号后重发前一码组，并再次等候ACK信号或NAK信号 发送两个码组之间有停顿时间TI，影响了传输效率5.1 引言null② 返回重发图5-2(b) 返回重发其发送端不停地送出一个个连续码组，不再等候收端返回的ACK信号 一旦收端发现错误并返回NAK信号，则发端从下一码组开始重发前面的N个码组 N的大小取决于信号传递及处理所带来的延时5.1 引言null5.1 引言图5.1-3 返回重发null③ 选择重发也是连续不断地发送码组，收端检测到错误后发回NAK信号。 与返回重发不同的是，发端并不重发错误码组后的所有码组，而只重发有错的那个码组5.1 引言null图5.1-4 选择重发5.1 引言null三者比较 选择重发传输效率最高，但成本最贵：控制机制复杂，发端和收端都要有数据缓冲器； 返回重发、选择重发需要全双工数据链路，而停发等候重发只要求半双工的数据链路。5.1 引言null（2）前向纠错法（FEC） Forward Error Correction图5.1-5 前向纠错（FEC)5.1 引言null发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正 不需要反馈信道，特别适合只能提供单向信道场合 自动纠错，不要求检错重发，延时小，实时性好 纠错码必须与信道的错误特性密切配合 若纠错较多，则编、译码设备复杂，传输效率低5.1 引言null（3）信息反馈校验法（IRQ） Information Repeat reQuest接收端将接收到的信码原封不动地转发回发端，并与原发送信码相比较，若发现错误，发端再重发。5.1 引言null收端把收到的数据序列全部经反向信道送回发端，发端比较发出和送回的数据序列，从而发现有否错误，如果有错误，发端将数据序列再次传送，直到发端没有发现错误。 不需要纠错、检错的编、译码器，设备简单。 需要和正向信道相同的反向信道，实时性差 发端需要一定容量的存储器以存储发送码组 仅适应于传输速率较低，信道差错率较低，具有双向传输线路及控制简单的系统5.1 引言null（4）混合纠错检错（HEC） Hybrid Error CorrectionFEC与ARQ的结合 发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发。 在实时性和译码复杂性方面是FEC和ARQ的折衷。5.1 引言null5.1 引言null核心问题 发现错误 纠正错误5.1 引言5.2 差错控制编码的基本原理5.2 差错控制编码的基本原理 在信息码序列中加监督码就称为差错控制编码，也叫纠错编码。 不同的编码方法，有不同的检错和纠错能力，增加监督码元越多，检（纠）错能力越强。 差错控制编码原则上是降低编码效率来换取可靠性提高。（即误码率更小）。 null理论依据：Shannon信道编码定理。 定理指出： 对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。1、纠错编码的理论依据5.2 差错控制编码的基本原理null5.2 差错控制编码的基本原理5.2 差错控制编码的基本原理5.2 差错控制编码的基本原理2、纠错编码的基本思想 发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系…… 以牺牲通信的有效性（信息传输速率）来提高可靠性 码的检错和纠错能力是用信息量的冗余来换取的。一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。5.2 差错控制编码的基本原理5.2 差错控制编码的基本原理 码长：码字中码元的数目。 码距：两个码组之间对应位上码元取值不同的个数，定义为两码字的距离，简称码距（d）。 对于二进制称作这两个码字的汉明距离。如两码字“10011”与“11010”间码距为2。3、码距与检错和纠错能力的关系（1）几个概念null 最小码距：在一个码字集合中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为dmin或d0 码重：码字中非零码元的数目定义为该码字的重量，简称码重。如“10011”码字的码重为3。纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。5.2 差错控制编码的基本原理null举例说明：假如要传送A、B两个消息编码一： 消息A----“0”；消息B----“1” 最小码距1 若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力。 5.2 差错控制编码的基本原理null编码二： 消息A----“00”；消息B----“11” 最小码距2 “00、11”称为许用码组，而“01、10”称为禁用码组 若传输中产生一位错码，则变成“01”或“10”，收端判决为有错，但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。 这表明增加一位冗余码元后码具有检出一位错码的能力5.2 差错控制编码的基本原理null编码三： 消息A----“000”；消息B----“111” 最小码距3 传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。 在产生一位错码（错1位概率远远大于错2位、3位概率）情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。例如收到110，认为是111。 这表明增加两位冗余码元后码具有检出两位错码或纠正一位错码的能力。5.2 差错控制编码的基本原理5.2 差错控制编码的基本原理一个码能检测e个错码，则要求其最小码dmin≥e+1 一个码能纠正t个错码，则要求其最小dmin≥2t+1 一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 dmin≥e+t+1 (e>t)（2）最小码距与检错和纠错能力的关系5.2 差错控制编码的基本原理5.2 差错控制编码的基本原理(a) 检e个错图5.2-2(a) 码距与检错纠错能力的关系A、B都为许用码； A发生e个错； B不能靠在球面上，否则收到B无法判断是否为错码； dmin≥e+15.2 差错控制编码的基本原理5.2 差错控制编码的基本原理1(b)纠正t个错码图5.2-2(b) 码距与检错纠错能力的关系A、B都为许用码； A、B都发生t个错； dmin≥2t+15.2 差错控制编码的基本原理5.2 差错控制编码的基本原理(c)纠正t个错码，检测e个错码图5.2-2(c) 码距与检错纠错能力的关系A、B都为许用码； 当误码数小于等于t时，可纠正误码； 当误码数大于t小于等于e时，不会落入另一码组的纠错范 围内。 dmin≥e+t+15.2 差错控制编码的基本原理5.2 差错控制编码的基本原理当码长n=7, P=10-3时，则有假设随机信道中发送“0”码与发送“1”码传错概率相等都为P,且P<<1,则在码长为n的码组中发生r个错误的概率为：4、误码率大概率事件5.2 差错控制编码的基本原理5.2 差错控制编码的基本原理设n=k+r 指一个码组中信息位所占比重，用η 表示 η=k/n=k/(k+r)，其中k为信息码元的数目，n为码长 编码效率是衡量纠错性能的一个重要指标，一般情况下，监督位越多，检纠错能力越强，但相应的编码效率也越低5、编码效率η一次课5.3 常用的简单编码 5.3 常用的简单编码 奇偶监督码 二维奇偶监督码 恒比码 正反码1、奇偶监督码1、奇偶监督码5.3 常用的简单编码 奇偶监督码：在信息码元后附加一位监督位，使得码组中 “1”的个数为偶数或奇数。null 最小码距dmin=2 只能检测出单个或奇数个错误，不能纠错 应用：以随机错误为主的计算机通信系统，难于对付突发错误 编码效率=k/n=k/(k+1)5.3 常用的简单编码 2、水平奇偶监督码2、水平奇偶监督码 将经过奇偶监督编码的码元序列按行排成方阵，每行为一组奇偶监督码，但发送时按列的顺序传输 接收端将码元排成发送时的方阵形式，再按行进行奇偶校验 能够发现某行上所有奇数个错误以及突发长度不大于方阵行数的突发错误 编码效率5.3 常用的简单编码 null表5-1 水平奇偶监督码null表5-2 水平奇偶监督码接收端出现突发误码示例结论：能够发现突发长度不大于方阵行数的突发错误3、水平垂直奇偶监督码3、水平垂直奇偶监督码 又称为方阵码、行列监督码、二维奇偶监督码。 将水平奇偶监督码推广到二维。即在水平监督基础上再对方阵中每一列进行奇偶校验，发送时按列的顺序传输 接收端将码元排成发送时的方阵形式，再分别按行、按列进行奇偶校验5.3 常用的简单编码 null 能够发现某行、某列上所有奇数个错误以及突发长度不大于方阵行数或列数的突发错误； 有可能检测出偶数个错误（在行上检测不出，但有可能在列上检测出），但当偶数个错误刚好构成矩形时，则检测不出 可纠正一些错误 5.3 常用的简单编码 null表5-3 水平垂直奇偶监督码发送顺序null表5-4 水平垂直奇偶监督码接收端纠错示例例如：当码组中仅在一行有奇数个错误时，能够确定错误位置，并纠正它。√√√√√√√√√√√√√××××null表5-5 水平垂直奇偶监督码接收端检错示例011构成矩形的偶数个误码检测不出。√√√√√√√√√√√√√00√√√√null表5-6 水平垂直奇偶监督码接收端检错示例01有可能检测出偶数个误码。√√√√√√√√√√√00√√1√√××null4、ISBN国际图书统一编号 International Standard Book Number无误码，若不能被11整除，有误码5.3 常用的简单编码 null5.3 常用的简单编码 能被11整除，无误码。5.4 线性分组码 （重点）5.4 线性分组码 （重点） (1) 分组码： 先将信息码分组，然后给每组信码附加若干监督码的编码称为分组码，用符号(n,k)表示，k是信息码的位数，n是编码组总位数，又称为码长，r=n-k为监督位数。 (2) 代数码： 建立在代数学基础上的编码，称为代数码。例如奇偶校验码。 1、基本概念5.4 线性分组码5.4 线性分组码 (3) 线性码： 线性码中信息位和监督位是按一组线性方程构成的。线性码是一种代数码。奇偶监督码是最简单的线性码。 (4) 线性分组码： 信息码分组后，附加的监督码和信息码由一些线性代数方程联系着的编码称为线性分组码。null2、线性分组码的性质任意两个许用码组之和（逐位模2和）仍为一许用码组，即具有封闭性。 最小码距=非零码的最小码重（1的个数）。（因为线性分组码中必有一个全0码组）5.4 线性分组码3、线性分组码的编码原理3、线性分组码的编码原理以汉明码为例来说明编码原理。汉明码是一种设计用来纠正一位错码且编码效率较高的线性分组码。（7，4）汉明码的编码效率为： 5.4 线性分组码（1）回忆奇偶监督偶校验码（1）回忆奇偶监督偶校验码 发送端编码：将一位监督码元附加在信息码元后，使得码元中“1”码元个数为偶数。 接收端译码： 计数接收码组中“1”码元个数是否为偶数，即计算：S=an-1+ an-2+……+ a0 （模2加）（5.4-1） S=0认为没错，S=1认为有错。 （5.4-1）式称为监督方程/监督关系式，S称为校正子/校验子/伴随式5.4 线性分组码null 监督位增加到2位：有两个监督方程，两个校验子； 两个校验子组合有四种（如00表示无错，01、10、11则可表示一位错码的三种可能位置） 监督位增加到r位：可指示一位错码的（2r-1）个可能位置 对于（n，k)分组码，若希望用r=n-k个监督位构造出的r个监督关系式来指示一位错码的n种可能位置，则要求： 可以这样来考虑2r-1≥n 即2r ≥k+r+1 （5.4-2）5.4 线性分组码null欲纠正一位错码，由（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 线性分组码null表5-9 S1S2S3的八种组合与一位错码的对应关系5.4 线性分组码nullS1= 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。这就意味着这四个码元构成偶数监督关系，即：null（3）发端编码的原则： 信息码元a6 、a5 、a4、a3来源于待编码的信息序列； 监督码元 a2 、a1、 a0的取值应根据信息码元按监督关系式来决定，即使前面三式中的S1、 S2 、S3均为0(000表示无错码）：5.4 线性分组码nulla2 = 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 线性分组码null表5-10 许用码组null该汉明码的编码效率较高 R=k/n=4/7≈57% 该码的最小码距为3，能纠正一个错码或检测两个错码 设收到码组0000011，按监督方程计算可得：S1=0，S2=1，S3=1；再根据校正子组合与一位错码位置的对应关系，可知错码发生在a3位，并加以纠正。00010115.4 线性分组码（4）监督矩阵（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 线性分组码nullH称为线性码监督矩阵可化简为： H·AT=0T 或A·HT=05.4 线性分组码null r×n阶矩阵 H确定了编码时监督码元与信息码元的关系 把具有[P·Ir]形式的H矩阵称为典型形式的监督矩阵，其中P为r ×k阶矩阵, Ir为r ×r阶单位方阵 当H不是典型阵时，可变换为典型阵。由典型阵构成的码组称为系统码，非典型阵构成的码组称为非系统码 H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关监督矩阵H特点5.4 线性分组码null上式右部前面矩阵就是监督矩阵H中的P矩阵。(5) 生成矩阵同样，监督码生成方程（5.4-5）式也可写成矩阵形式，即(5.4-7)5.4 线性分组码null其中Q=PT可见，Q为k ×r阶矩阵。或写成5.4 线性分组码null生成矩阵G：在Q矩阵的左边加上一个k ×k阶矩阵， 即5.4 线性分组码nullk ×n阶矩阵 编码方法完全由生成矩阵G确定 把具有[Ik·Q]形式的G矩阵称为典型形式的生成矩阵，其中，Ik为k×k阶单位方阵，Q为k ×r阶矩阵 由典型生成矩阵产生的分组码一定是系统码 G矩阵的各行应线性无关，每行均为许用码组生成矩阵G特点5.4 线性分组码null[例5-2 ]已知（6，3）汉明码的生成矩阵如下， (1)列出所有许用码组; (2)最小码距d0; (3)检错纠错能力 (4)编码效率5.4 线性分组码null（1）null（3）（4）（2）null设（7,4）线性码的生成矩阵G为：当信息位为0001时， （1）试求其后的监督位。 （2）监督矩阵H5.4 线性分组码null解： （1）null（2）监督矩阵H 根据生成矩阵和监督矩阵的关系： G= [Ik·Q]，H=[P·Ir] 其中P=QT，可得监督矩阵H为：null错误矩阵/错误图样E： 设发送码组为A，接收码组为B，(6) 校正子与检错则错误矩阵 5.4 线性分组码null接收端计算校正子S，即 S=BHT=(A+E)HT=AHT+EHT=0+ EHT= EHT 可见校正子只与E有关，即错误图样与校正子之间有确定的关系，所以可从错误图样与校正子的关系表中确定错码位置，加以纠正。5.4 线性分组码null以（7，4）汉明码为例 设发送码组A=（0001011） 接收码组 B=（0000011） 则收端译码过程如下： ①计算校正子②查表得a3为错误位置，即可纠正（0001011）5.4 线性分组码null5.4 线性分组码4、（7，4）汉明码编译码仿真汉明码编译码仿真null设A1和 A2为码中任意两许用码组， 则有 A1·HT=0 A2·HT=0 于是A1·HT+ A2·HT=（ A1 + A2）·HT=0 即（ A1 + A2）必是该码中一许用码组[例5-3] 证明线性分组码的封闭性。（略）p319：9-65.4 线性分组码5.5 循环码5.5 循环码循环码是一种重要的线性分组码。这种码的编码和解码设备都不太复杂，且有较强的检（纠）错能力。 共n位。通常前k位为信息位，后r位为监督位。5.5.1 循环码的编码原理null循环码的特点： 封闭性； 循环性；即码中任一码组循环一位(将最右端的码元移到左端或反之）以后，仍为该码中的一个码组。5.5.1 循环码的编码原理null若(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 循环码的编码原理null表5-10一种（7，3）循环码的全部码字null把码长为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)= 1·x6+1 · x5+ 0 · x4 + 0 · x3 + 1 · x2 + 0 · x+1 = x6 + x5 + x2 +11、码多项式T(x)null码多项式与码组的关系： 本质上是一回事，仅是表示方法的不同而已。对于二进制码组，多项式的每个系数不是0就是1，x仅是码元位置的标志。因此，这里并不关心x的取值。0+0=0 0+1=1 1+0=1 1+1=0 0*0=0 0*1=0 1*1=15.5.1 循环码的编码原理null若一个整数m可以表示为:则在模n运算下，有m≡p（模n），同样对于多项式而言：则可以写为：F(x)≡R(x) （模N(x)）。即一任意多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)5.5.1 循环码的编码原理null例如码组（1100101）对应的码多项式可为： T7(x)= x6 + x5 + x2 +1 其被x3+1除得 x6 + x5 + x2 +1≡ 1 （模x3+1）5.5.1 循环码的编码原理null在循环码中，若T(x)是一个长为n的许用码组，则xi· T(x)在按模xn+1运算下，也是一许用码组。即若 xi· T(x)≡Ti(x) （模xn+1） 则Ti(x) 也是一许用码组，且为A(x)码组向左循环移位i次的结果。重要结论5.5.1 循环码的编码原理null例如A4=0111001，对应的码多项式为 ：A4向左循环移1位得A7=1110010，这相当于将A4(x)乘以x，即 A7向左循环移1位得A6=1100101，但若将A7(x)乘以x得到多项式为 对于(7，3)循环码的码多项式，其最高次数不能超过6，解决该问题的办法是对上式作模x7+1运算得余作为码多项式 null例如：其对应的码组为0101110，它正是表5-10中第3码字。结论：一个码长为n的(n，k)循环码，它必为按模xn+1运算的一个余式。5.5.1 循环码的编码原理null 循环码完全由其码组长度n和生成多项式g(x)所决定 问题：寻找构成生成矩阵的k个线性无关的许用码组2、循环码的生成多项式与生成矩阵5.5.1 循环码的编码原理null 生成多项式： 如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如(7,3)循环码中， 其它码多项式都是g(x)的倍式， 即 null（n，k)循环码中一定能找到这样一个码组：前面的k-1位都是0，而第k位及第n位为1，其它各位gi为0或1： （000…01gn-k-1gn-k-2 …g2 g11) 其对应的码多项式为g(x)，且 g(x)一定是码中唯一的一个n-k次多项式，这唯一的n-k次多项式g(x)称为码的生成多项式5.5.1 循环码的编码原理null也就是说，最高次方为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 循环码的编码原理null 例如： 上表中的编码为(7, 3)循环码，n = 7, k = 3, n – k = 4，其中唯一的一个(n – k) = 4次码多项式代表的码组是第二码组0010111，与它对应的码多项式即生成多项式为： g(x) = x4 + x2 + x + 1。 null5.5.1 循环码的编码原理nullg(x)， … …， xk-1g(x)都是许用码组，连同g(x)共k个许用码组，构成码的生成矩阵G(x)注：该生成矩阵并不是典型形式的，但可通过线性变换变换成典型的生成矩阵。5.5.1 循环码的编码原理null一旦生成多项式g(x)确定以后，该循环码的生成矩阵G(x)就可以确定，进而该循环码的所有码字就可以确定。生成矩阵G(x)的每一行都是一个码组。5.5.1 循环码的编码原理null[例5-4]试求表5-10 （7，3）循环码的生成多项式和生成矩阵。解：对（7,3）循环码，n=7，k=3, r=4 由上例已知生成多项式为：g(x)= x4+x2+x+15.5.1 循环码的编码原理将第1行与第3行模2加作为第1行，则有 为典型生成矩阵null[接上例]设信息码为101，求整个码组。解：整个码组A=[信息码]*G（典型的） 故 A=[1 0 1] =[1 0 1 1 1 0 0]5.5.1 循环码的编码原理null[例5-5] 已知循环码的生成多项式为 ， 当信息位为1000时，写出它的监督位和整个码组。 解：由生成多项式可知n-k=3，而k=4，所以n＝7null 第1行+第3行+第4行 第1行 第2行+第4行 第2行 非典型典型当信息位为1000时，整个码组为null监督位为 101null已知（7，4）循环码的全部码组为：试写出该循环码的生成多项式g(x)和生成矩阵G，并将G化成典型矩阵。5.5.1 循环码的编码原理null解：n=7，k=4，n-k=3 上述码组中的(n-k)=3次码多项式为第2组，它所对应的码多项式g(x)即为生成多项式：g(x)=x3+x+1。 生成矩阵为：null5.5.2 循环码的编码、解码方法1、编码方法（1）原理用码多项式来表示为： A =[ mk-1 mk-2 … m0 ar-1 … a1 a0] null设信息位对应的多项式为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 循环码的编码、解码方法null例如:信息码为110，它相当于m(x)＝x2+x。当n-k＝7-3＝4时， xn-k ·m（x）＝ x4 · (x2+x)= x6+x5 ，相当于1100000。 而希望的到得系统循环码多项式应当是 T(x) = xn-k ·m(x) + r(x)。 5.5.2 循环码的编码、解码方法null即余式r(x)=x2+1 于是，对应码组T(x)= xn-k m(x)+r(x）= x6+x5+ x2+1 编码为1100101[例题] 设（7，3）循环码的生成多项式为g(x)=x4+x2+x+1，待编码信息位为110，求对应循环码码组。解：m(x)=x2+x，xn-k m(x)=x4(x2+x)=x6+x55.5.2 循环码的编码、解码方法null于是，以多项式形式表示的系统循环码的生成矩阵为：其中,rn-i(x)是g(x)除xn-i (i=1,2,…，k)所得的余式。2、译码方法2、译码方法（1）目的—检错、纠错5.5.2 循环码的编码、解码方法5.5.2 循环码的编码、解码方法5.5.2 循环码的编码、解码方法判断接收到的码组多项式B(x)是否能被生成多项式g(x)整除作为依据 当传输中未发生错误时，B(x)=T(x)，则接收的码组B(x)必能被g(x)整除； 若传输中发生了错误， B(x)≠T(x) ，B(x)不能被g(x)整除 B(x)≠T(x) ，B(x)能被g(x)整除 不可检错误 （2）采用手段：null由接收到的码多项式B(x)计算校正子（伴随式）多项式S(x)；即求解B(x)整除g(x)的余式r(x) 由校正子S(x)确定错误图样E(x)； 将错误图样E(x)与B(x)相加，纠正错误。 （3）译码步骤5.5.2 循环码的编码、解码方法null 能检出全部的单个错误： 对应一位错码的错码多项式E(x)=xi，而多于一项的生成多项式g(x)=……+1，显然xi除以g(x)的余数不会等于0，也即能检测出全部单个错码。 能检出全部离散的二位错： 对应的错码多项式E(x)=xi+xj=xi(1+xj-i)，只要选取的g(x)不能除尽(xj-i+1)，且(n-k)>(j-i) 能检出全部的奇数个错码： 含有奇数项错码的多项式必不含(x+1)因子，只要选取的g(x)含有(x+1)因子5.5.4 循环码的检错能力null 能检测所有长度不超过(n-k)的突发错误： 突发长度不大于b的突发错误对应的错码多项式 为: E(x)=xi(eb-1xb-1+ eb-2xb-2+……+e1x+1)= xi E1(x) 由于g(x)除不尽xi； g(x)为n-k次多项式，只要E1(x)的次数b-1不超过(n-k-1)次， g(x)便除不尽E1(x)。也就是说，能检测长度不超过(n-k)的突发错误。5.5.4 循环码的检错能力null信道编码与信源编码有什么不同？纠错码能够检错或纠错的根本原因是什么？ 差错控制的基本工作方式有哪几种?各有什么特点？ 汉明码有哪些特点? 分组码的检(纠)错能力与最小码距有什么关系?检、纠错能力之间有什么关系? 什么叫做奇偶监督码?其检错能力如何? 什么是线性码?它具有哪些重要性质? 什么是循环码?循环码的生成多项式如何确定?