第8章差错控制编码

1、1第第8 8章章 差错控制编码差错控制编码8.1 引言引言8.2 纠错编码的基本原理纠错编码的基本原理8.3 常用的简单编码常用的简单编码8.4 线性分组码线性分组码8.5 循环码循环码第5章 差错控制编码2数字信号在传输过程中受到干扰的影响，使信号波形变坏，发生误码，可以采用一些方法解决。v 有效性信源编码v 可靠性信道编码第5章 差错控制编码30 、复习、复习v 模拟信源：在无线广播中，信源一般是一个语音源（话音或音乐）；在电视广播中，信源主要是活动图像的视频信号源。这些信源的输出都是模拟信号，所以称之为模拟源。v 信源编码：将模拟信息源的输出转化为数字信号，即A/D转换。v 信源编码目的

2、：提高通信有效性，减少原消息的冗余度。第5章 差错控制编码4差错出现原因v 外界噪声v 传输中码间串扰解决方法v 合理地设计基带信号，选择调制、解调方式，采用均衡技术，发送功率等因素，使误比特率降低。v 差错控制措施了。第5章 差错控制编码5 差错控制编码属信道编码，要求在满足有效性前提下，尽可能提高数字通信的可靠性。 差错控制编码是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号。例如奇偶校验。 差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。第5章 差错控制编码61、差错控制编码分类、差错控制编码分类第

3、5章 差错控制编码72、误码类型、误码类型v 随机误码v 突发误码错码出现是随机的、错码之间统计独立。由随机噪声引起存在随机误码的信道称为随机信道无记忆信道差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关例如：脉冲噪声，存储系统中磁带的缺陷或读写头接触不良引起，再例如用手机过涵洞，且无发射天线存在这种差错的信道称为突发信道有记忆信道3、错误图样、错误图样l例如：设发送数据序列为：00000000001111111111接收数据序列为： 01101001001111001001错误图样（差错序列）：发送数据序列与接收序列对应码位的模和则差错序列为： 0110100100000

4、0110110l可见发生了两个长度分别为和的突发差错，其错误图样分别为1101001和11011突发长度：指突发差错首位与末位之间的长度（中间可能有没错的码位）第5章 差错控制编码9l说明差错序列或错误图样中的“”表示对应码位没错，而“”表示有错实际信道很复杂，所出现的差错并不是单一的，往往是随机和突发差错并存，只不过以某种错误为主一般说来，纠正随机差错的编译码方法和设备比较简单，成本较低，效果较显著；而纠正突发差错的编译码方法和设备比较复杂，成本较高，效果也不如前者显著第5章 差错控制编码10 4、信道类型、信道类型v 随机信道v 突发信道v 混合信道第5章 差错控制编码115、差错控制方法

5、、差错控制方法v检错重发（ARQ） 停发等候重发 返回重发 选择重发v前向纠错（FEC）v反馈校验（IRQ）v混合方式（HEC）第5章 差错控制编码12（1）检错重发法（）检错重发法（ARQ） Automatic Repeat reQuest 收端在接收到的信码中发现错码时，就通知发端重发，直到正确接收为止。例如奇偶校验。 检错重发方式只用于检测误码，能够在接收单元中发现错误，但不一定知道该错误码的具体位置。 需具备双向信道。发发收收能够发现错误的码能够发现错误的码图图8.1-1（a) 检错重发（检错重发（ARQ)应答信号应答信号图图8.1-1（b) 检错重发（检错重发（ARQ)信信源源编码器

6、和缓编码器和缓冲存储器冲存储器重发控制重发控制双双向向信信道道解码器解码器指令产生器指令产生器输出缓冲输出缓冲存储器存储器收收信信者者正确时输出错误时删除判断有无错误第5章 差错控制编码14 停发等候重发停发等候重发2发送端：接收端：133123ACKACKNAK发现错误TITw停顿时间图图8.1-2 停发等候重发停发等候重发第5章 差错控制编码15发端在Tw时间内送出一个码组；收端收到后检查。如果未发现错误，则发回一个认可信号（ACK）给发送端，发送端收到ACK信号再发下一个码组若检测到错误，则发回一个否认信号（NAK），发送端收到NAK信号后重发前一码组，并再次等候ACK信号或NAK信号发

7、送两个码组之间有停顿时间TI，影响了传输效率第5章 差错控制编码16 返回重发返回重发其发送端不停地送出一个个连续码组，不再等候收端返回的ACK信号一旦收端发现错误并返回NAK信号，则发端从下一码组开始重发前面的N个码组N的大小取决于信号传递及处理所带来的延时第5章 差错控制编码17发送端：接收端：1 2 3 4 5 6 2 3 41 2 3 4 5 6 2 3 45 6 7 8 95 6 7 8 9发现错误NAK从码组2开始重发图图8.1-3 返回重发返回重发第5章 差错控制编码18 选择重发选择重发也是连续不断地发送码组，收端检测到错误后发回NAK信号。与返回重发不同的是，发端并不重发错误

8、码组后的所有码组，而只重发有错的那个码组第5章 差错控制编码19发送端：接收端：1 2 3 4 5 6 2 7 81 2 3 4 5 6 2 7 899发现错误NAK重发码组2图图8.1-4 选择重发选择重发第5章 差错控制编码20三者比较 选择重发传输效率最高，但成本最贵：控制机制复杂，发端和收端都要有数据缓冲器； 返回重发、选择重发需要全双工数据链路，而停发等候重发只要求半双工的数据链路。第5章 差错控制编码21（2）前向纠错法（）前向纠错法（FEC） Forward Error Correction发发收收能够纠正错误的码能够纠正错误的码图图8.1-5 前向纠错（前向纠错（FEC)信信源

9、源编编码码器器单单向向信信道道纠错译码器纠错译码器输出缓冲输出缓冲存储器存储器收收信信者者+第5章 差错控制编码22发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正不需要反馈信道，特别适合只能提供单向信道场合自动纠错，不要求检错重发，延时小，实时性好纠错码必须与信道的错误特性密切配合若纠错较多，则编、译码设备复杂，传输效率低第5章 差错控制编码23（3）信息反馈校验法（）信息反馈校验法（IRQ） Information Repeat reQuest接收端将接收到的信码原封不动地转发回发端，并与原发送信码相比较，若发现错误，发端再重发。数据信息数据信息发收图图

10、8.1-6 信息反馈法信息反馈法数据信息数据信息第5章 差错控制编码24收端把收到的数据序列全部经反向信道送回发端，发端比较发出和送回的数据序列，从而发现有否错误，如果有错误，发端将数据序列再次传送，直到发端没有发现错误。不需要纠错、检错的编、译码器，设备简单。需要和正向信道相同的反向信道，实时性差发端需要一定容量的存储器以存储发送码组仅适应于传输速率较低，信道差错率较低，具有双向传输线路及控制简单的系统第5章 差错控制编码25（4）混合纠错检错（）混合纠错检错（HEC） Hybrid Error CorrectionFEC与ARQ的结合发端发出同时具有检错和纠错能力的码，收端收到后，检查错误

11、情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发。在实时性和译码复杂性方面是FEC和ARQ的折衷。第5章 差错控制编码26发发收收能够发现和纠正错误的码能够发现和纠正错误的码图图8.1-7 混合纠错检错（混合纠错检错（HEC)应答信号应答信号第5章 差错控制编码27核心问题核心问题v 发现错误发现错误v 纠正错误纠正错误第5章 差错控制编码288 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理 在信息码序列中加监督码就称为差错控制编码，也叫纠错编码。不同的编码方法，有不同的检错和纠错能力，增加监督码元越多，检（纠）错能力越强。差错控制

12、编码原则上是降低编码效率来换取可靠性提高。（即误码率更小）。 第5章 差错控制编码29v理论依据：Shannon信道编码定理。v定理指出： 对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。1、纠错编码的理论依据、纠错编码的理论依据8 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理第5章 差错控制编码30nE(R )pen :R :E(R ) : 编编 码码 长长 度度信信 息息 发发 送送 速速 率率错错 误误 指指 数数P1C,E(R)2n 为为了了方方法法 ：但但方方

13、法法 ：E(R)nCC1C2图图8.2-1 误差指数曲线误差指数曲线8 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理第5章 差错控制编码312、纠错编码的基本思想、纠错编码的基本思想8 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理v 发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系v 以牺牲通信的有效性（信息传输速率）来提高可靠性v 码的检错和纠错能力是用信息量的冗余来换取的。一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。第5章 差错控制编码32v 码长：码字中码元的数目。v 码距：两个等长码字中对应码位

14、上不同二进制码元的位数定义两码字的距离，简称码距（d）。对于二进制称作这两个码字的汉明距离。如两码字“10011”与“11010”间码距为2。3、码距与检错和纠错能力的关系、码距与检错和纠错能力的关系niii 1dAB 8 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理（1）几个概念）几个概念第5章 差错控制编码33v 最小码距：在一个码字集合中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为dmin或d0v 码重：码字中非零码元的数目定义为该码字的重量，简称码重。如“10011”码字的码重为3。纠错码的抗干扰能力完全取决于许用码字之间的距纠错码的抗干扰能力完

15、全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。大，抗干扰能力就越强。8 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理第5章 差错控制编码34举例说明：假如要传送举例说明：假如要传送A、B两个消息两个消息编码一：消息A-“0”；消息B-“1”最小码距1若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力。8 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理第5章 差错控制编码35编码二：消息A-“00”；消息B-“11”最小码距2若传输中产生一位错码

16、，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力8 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理编码三：消息A-“000”；消息B-“111”最小码距3传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。在产生一位错码（错1位概率远远大于错2位、3位概率）情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。例如收到110，认为是111。这表明增加两位冗余码元后码具

17、有检出两位错码及纠正一位错码的能力。第5章 差错控制编码37一个码能检测e个错码，则要求其最小码dmine+1一个码能纠正t个错码，则要求其最小dmin2t+1一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 dmine+t+1 (et)（2）最小码距与检错和纠错能力的关系）最小码距与检错和纠错能力的关系8 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理第5章 差错控制编码38(a) 检检e个错个错图图8.2-2(a) 码距与检错纠错能力的关系码距与检错纠错能力的关系Ae1dminBA、B都为许用码；都为许用码；A发生发生e个错；个错；B不能靠在球面上不能靠在球面上，否则

18、收到，否则收到B无法无法判断是否为错码；判断是否为错码；dmine+18 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理第5章 差错控制编码391tABtdmin(b)纠正纠正t个错码个错码图图8.2-2(b) 码距与检错纠错能力的关系码距与检错纠错能力的关系A、B都为许用码；都为许用码；A、B都发生都发生t个错；个错；dmin2t+18 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理第5章 差错控制编码40ABtedmint(c)纠正纠正t个错码，检测个错码，检测e个错码个错码图图8.2-2(c) 码距与检错纠错能力的关系码距与检错纠错能力的关系A、B都为许用码；都为许用码；A发生发生e个错；个错；B发生发生t个错；个错； dmine+t+18 8.2 .2 差错控制编码的基本原理差错控制编码的基本原理第5章 差错控制编码41当码长n=7, P=10-3时，则有假设随机信道中发送“0”码与发送“1”码传错概率相等都为P,且P(j-i)v 能检出全部的奇数个错码：含有奇数项错码的多项式必不