通信原理樊昌信版第11章差错控制编码课件.ppt

1,第11章 差错控制编码,11.1 概述,11.2 纠错编码的基本原理,11.3 纠错编码的性能,11.4 简单的实用编码,11.5 线性分组码,11.6 循环码,2,11.1 概述,数字信号在传输过程中受到干扰的影响，使信号波形变坏，发生误码，可以采用一些方法解决。,有效性信源编码 可靠性信道编码,3,0、复习,模拟信源：在无线广播中，信源一般是一个语音源（话音或音乐）；在电视广播中，信源主要是活动图像的视频信号源。这些信源的输出都是模拟信号，所以称之为模拟信源。,信源编码：将模拟信息源的输出转化为数字信号，即A/D转换。,信源编码目的：提高通信有效性，减少原消息的冗余度。,4,差错出现原因 外界噪声 传输中码间串扰,解决方法 合理地设计基带信号、调制/解调方式、采用均衡技术、发送功率等因素，使误比特率降低。 差错控制措施。,5,差错控制编码属信道编码，要求在满足有效性前提下，尽可能提高数字通信的可靠性。 差错控制编码是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号。例如奇偶校验。 差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。,6,按功能分：检错码和纠错码 按监督码元与信息码元关系分：线性码与非线性码 按信息码元与监督码元之间的约束关系分：分组码与卷积码按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码,1、差错控制编码分类,7,2、误码类型,随机误码、突发误码,随机误码错码出现是随机的、错码之间统计独立 由随机噪声引起存在随机误码的信道称为随机信道无记忆信道,8,突发误码,差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关。例如：脉冲噪声；存储系统中磁带的缺陷或读写头接触不良引起的；用手机过涵洞。存在这种差错的信道称为突发信道/有记忆信道。,9,3、信道类型,随机信道：错码的出现是随机的 突发信道：错码是成串集中出现的混合信道：既存在随机错码又存在突发错码,10,4、差错控制方法,检错重发前向纠错反馈校验检错删除,11,（1）检错重发 Error Detection retransmission,收端在接收到的信码中发现错码时，就通知发端重发，直到正确接收为止。如奇偶校验。 检错重发方式只用于检测误码，能够在接收单元中发现错误，但不一定知道该错误码的具体位置。 需具备双向信道。,12,（2）前向纠错（FEC） Forward Error Correction,发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正。,13,不需要反馈信道，特别适合只能提供单向信道场合。自动纠错，不要求检错重发，延时小，实时性好。若纠错较多，则编、译码设备复杂，传输效率低。,（2）前向纠错（FEC） Forward Error Correction,14,（3）反馈 (feedback) 校验 (checkout),接收端将接收到的信码原封不动地转发回发端，并与原发送信码相比较，若发现错误，发端再重发。,15,不需要纠错、检错的编、译码器，设备简单。需要反向信道，实时性差。发端需要一定容量的存储器以存储发送码组。仅适应于传输速率较低，信道差错率较低，具有双向传输线路及控制简单的系统。,（3）反馈 (feedback) 校验 (checkout),16,（4）检错删除,发现错误后，删除，不需重发。适合少数特定系统中，发送码元中有大量多余度，删除部分接收码元不影响应用。,核心问题：发现错误、纠正错误,17,5、差错控制编码,常称为纠错编码 (Error-Correcting Coding)监督码元：前述除第3种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，称为监督码元。 不同的编码方法，有不同的检错或纠错能力。,18,编码效率(简称码率) ：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n 就是码率。冗余度：监督码元数(n-k) 和信息码元数 k 之比。理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。,19,6、自动要求重发(ARQ)系统 Automatic Repeat reQuest,20,停止等待ARQ系统,2,发送端：,接收端：,TI,Tw,停顿时间,6、自动要求重发(ARQ)系统,21,发端在Tw时间内送出一个码组；收端收到后检查。如果未发现错误，则发回一个认可信号(ACK) 给发送端，发送端收到ACK信号再发下一个码组若检测到错误，则发回一个否认信号(NAK)，发送端收到NAK信号后重发前一码组，并再次等候ACK信号或NAK信号发送两个码组之间有停顿时间TI，影响了传输效率。半双工状态。,22,拉后ARQ系统,其发送端不停地送出一个个连续码组，不再等候收端返回的ACK信号一旦收端发现错误并返回NAK信号，则发端从下一码组开始重发前面的N个码组N的大小取决于信号传递及处理所带来的延时,6、自动要求重发(ARQ)系统,23,选择重发ARQ系统,也是连续不断地发送码组，收端检测到错误后发回NAK信号。发端并不重发错误码组后的所有码组，而只重发有错的那个码组。,6、自动要求重发(ARQ)系统,24,ARQ的主要优点：和前向纠错方法相比监督码元较少即能使误码率降到很低，即码率较高；检错的计算复杂度较低；检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。,6、自动要求重发(ARQ)系统,25,ARQ的主要缺点：需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。因为重发而使ARQ系统的传输效率降低。在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。在要求实时通信的场合，例如电话通信，往往不允许使用ARQ法。,6、自动要求重发(ARQ)系统,26,11.2 纠错编码的基本原理,在信息码序列中加监督码就称为差错控制编码，也叫纠错编码。不同的编码方法，有不同的检错和纠错能力，增加监督码元越多，检 (纠) 错能力越强。差错控制编码原则上是降低编码效率来换取可靠性提高。（即误码率更小）。,27,设有一种由3位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，则可以表示8种不同天气，如：000（晴） 001（云） 010（阴） 011（雨） 100（雪） 101（霜）110（雾） 111（雹）其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。,1、分组码基本原理：举例说明,28,若在上述8种码组中只准许使用4种来传送天气，如：000晴 011云 101阴 110雨接收端却有可能发现码组中的一个错码。若 000 中错了一位，则接收码组将变成 100 或 010 或 001。这3种码组都是不准使用的，称为禁用码组。接收端在收到禁用码组时，就认为发现了错码。这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是许用码组。也能检测3个错码，000变成了111。,29,2、检错和纠错 000晴 011云 101阴 110雨上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组 100 时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成 100。要能够纠正错误，还要增加多余度。例如，若规定许用码组只有两个：000(晴)，111 (雨)，其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。,30,2、检错和纠错 000=晴 111=雨 例如，当收到禁用码组 100 时，若当作仅有一个错码，则可以判断此错码发生在“1”位，从而纠正为 000 （晴）。因为 111 （雨）发生任何一位错码时都不会变成 100这种形式。 若假定错码数不超过两个，则存在两种可能性：000 错1位和 111 错2位都可能变成 100，因而只能检测出存在错码而无法纠正错码。,31,3、分组码的结构,将信息码分组，为每组信息码附加若干监督码的编码称为分组码 。分组码包括信息位和监督位。监督码元仅监督本码组中的信息码元。,32,分组码的一般结构,分组码的符号：(n, k)n码组的总位数，又称为码组的长度(码长)k 码组中信息码元的数目 n k r 码组中的监督码元数目,编码效率: 指一个码组中信息位所占比重,33,码重：码组中“1”的个数目称为码组的重量，简称码重。码距：两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。如：000晴 011云 101阴 110雨 4个码组之间，任意两个的距离均为2。最小码距：某种编码中各个码组之间距离的最小值称为最小码距(d0)。如上面的编码的最小码距d0 = 2。,4、分组码的码重和码距,34,5、码距的几何意义,每个码组的3个码元的值(a1, a2, a3)就是此立方体各顶点的坐标。而上述码距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离。由此图可以直观看出，上例中4个准用码组之间的距离均为2。,35,6、码距和检纠错能力的关系,一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力。,为检测e个错码，要求最小码距 d0 e + 1,36,检e个错,A、B都为许用码；A发生e个错；B不能靠在球面上，否则收到B无法判断是否为错码；dmine+1,若要求检测e个错码，则最小码距d0至少应不小于( e + 1) 。反之，若一种编码的最小码距为d0，则将能检测(d0 - 1)个错码。,37,为了纠正t个错码，要求最小码距d0 2t + 1,【证】图中码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，反之判决为码组B。这样，就能够纠正两位错码。,38,1,纠正t个错码,A、B都为许用码；A、B都发生t个错；dmin2t+1,为纠正t个错码，同时检测e个错码，要求最小码距:,39,先分析上图所示的例子。图中d0=5。按照检错能力公式e =d01 ，最多能检测4个错码；按照纠错能力公式，能纠正2个错码。但是，不能同时作到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地“纠正”了。这就是说，检错和纠错公式不能同时成立或同时运用。,40,为了在纠正t 个错码的同时，能够检测e 个错码，就需要如图所示，使某一码组（码组A）发生e 个错误之后所处的位置，与其它码组（码组B）的纠错圆圈至少距离等于1，避免将落在该纠错圆上从而发生错误地“纠正”。由此图可以直观看出，要求最小码距：,41,11.3 纠错编码的性能,1、系统带宽和信噪比的矛盾,为减少错误码元数量，需在信息码元序列中加入监督码元，使发送序列增长，冗余度增大。若保持信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起噪声功率增大，使信噪比下降，又使系统接收端错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。,42,第11章差错控制编码,2、编码性能举例,若接收信噪比等于7dB， 未采用纠错编码时误码率约为810-4，(A点) 采用 纠错编码后:误码率降至约410-5(B点) 不增大发送功率就能降低误码率约一个半数量级。,编码和误码率关系,43,第11章差错控制编码,2、编码性能举例,若接收信噪比等于7dB， 未采用纠错编码时误码率约为810-4，(A点) 采用 纠错编码后:误码率降至约410-5(B点) 不增大发送功率就能降低误码率约一个半数量级。,编码和误码率关系,2PSK,44,若保持误码率在10-5，未采用编码时，约需要信噪比9.5 dB (C点)。在采用这种编码时，约需要信噪比7.5 dB (D点)。可以节省功率2 dB。通常称这2 dB为编码增益。上面两种情况付出的代价是带宽增大。,编码和误码率关系,2PSK,45,第11章差错控制编码,传输速率和Eb/n0的关系,提高传输速率，采用编码以保持误码率不变；付出的代价仍是带宽增大。,对于给定的传输系统,2PSK,式中，RB为码元速率。,46,奇偶监督码二维奇偶监督码恒比码正反码,11.4 简单的实用编码,47,1、奇偶监督码,奇偶监督码：在信息码元后附加一位监督位，使得码组中奇偶监督码“1”的个数为偶数或奇数。,偶数监督码,奇数监督码,式中a0为监督位，其他位为信息位。,48,只能检测出奇数个错误，不能纠错。 应用：以随机错误为主的计算机通信系统，难于对付突发错误。 编码效率=k/n=k/(k+1),偶数监督码,奇数监督码,49,2、二维奇偶监督码（方阵码）,将奇偶监督码推广到二维。即在水平监督基础上再对方阵中每一列进行奇偶校验，发送时按列的顺序传输。,又称为方阵码、行列监督码、水平垂直奇偶监督码。,接收端将码元排成发送时的方阵形式，再分别按行、按列进行奇偶校验。,50,能够发现某行、某列上所有奇数个错误以及突发长度不大于方阵行数或列数的突发错误； 有可能检测出偶数个错误（在行上检测不出，但有可能在列上检测出），但当偶数个错误刚好构成矩形时，则检测不出。可纠正一些错误。,52,例如：当码组中仅在一行有奇数个错误时，能够确定错误位置，并纠正它。,0,1,1,构成矩形的偶数个误码检测不出。,0,0,0,1,有可能检测出偶数个误码。,0,0,1,55,3、恒比码,每个码组中含“1”和“0”的个数的比例恒定，又称等重码。这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错码。主要优点是简单，适于用来传输电传机或其他键盘设备产生的字母和符号。,表 我国五单位保护电码表,（是一种五中取三码）,57,4、正反码,它是一种简单的能够纠正错码的编码。监督位数目与信息位数目相同，且监督码元与信息码元或者相同或者相反，取决于信息序列中“1”的个数。 电报通信用的正反码的码长n=10。信息位k=5，监督位r=5。,58,码组中信息位有奇数个“1”，监督码元与信息码元相同； 码组中信息位有偶数个“1”，监督码元与信息码元相反。,（1）正反码编码规则,信息位为11001，则码组为1100111001；信息位为10001，则码组为1000101110。,59,将接收码组中信息位与监督位按位模2加，得到合成码组。 产生校验码组： 接收码组中信息码元有奇数个“1”，则校验码组=合成码组，否则校验码组=合成码组的反码。 按照校验码组中“1”的个数进行判决及纠错（表11-2）。,（2）接收端解码规则,表11-2 正反码检错纠错判决规则,61,(1)若接收码组为1100111001(无错)合成码组为11001 11001=00000码组中信息码元有奇数个“1”，校验码=00000判决为无错传输(2)若接收码组为1000111001 合成码组10001 11001=01000 码组中信息码元有偶数个1, 校验码组10111； 信息码元第二位错码，给以纠正为1100111001,例:假设发送码组为1100111001，分析各种正反码判决纠错情况。,(3)若接收码组为1100101001： 合成码组11001 01001 =10000； 因码组中信息码元有奇数个“1”，则校验码组为10000 说明监督码元中第一位错码,发送码组为1100111001,63,(4)若接收码组为1001111001： 合成码组10011 11001 =01010；因码组中信息码元有奇数个“1”，则校验码组为01010，说明错码多于1个,码长为10的正反码能够纠正1位差错，并能检测所有2位及以下的错码。,发送码组为1100111001,