通信原理第11章差错控制编码.ppt

第第1111章章 差错控制编码差错控制编码11.1 概述概述11.2 纠错编码的基本原理纠错编码的基本原理11.3 常用的简单编码常用的简单编码11.4 线性分组码线性分组码第11章 差错控制编码0 0、复习、复习v 模拟信源：在无线广播中，信源一般是一个语音源（话音或音乐）；在电视广播中，信源主要是活动图像的视频信号源。这些信源的输出都是模拟信号，所以称之为模拟源。v 信源编码：将模拟信息源的输出转化为数字信号，即A/D转换。v 信源编码目的：提高通信有效性，减少原消息的冗余度。11.1 11.1 概述概述第11章 差错控制编码差错出现原因v 外界噪声v 传输中码间串扰解决方法v 合理地设计基带信号，选择调制、解调方式，采用均衡技术，发送功率等因素，使误比特率降低。v 差错控制措施。11.1 11.1 概述概述信号在数字信道传输过程中受到干扰的影响，使信号波形变坏，发生误码，可以采用一些方法解决。第11章 差错控制编码 差错控制编码属信道编码，要求在满足有效性前提下，尽可能提高数字通信的可靠性。差错控制编码是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号。例如奇偶校验。差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。11.1 11.1 概述概述第11章 差错控制编码vv 按功能分：检错码和纠错码按功能分：检错码和纠错码vv 按监督码元与信息码元关系分：按监督码元与信息码元关系分：线性码线性码与非线性码与非线性码vv 按信息码元与监督码元之间的约束关系不同分：按信息码元与监督码元之间的约束关系不同分：分组分组码码与卷积码与卷积码vv 按信息码元在编码后是否保持原来的信号形式分：系按信息码元在编码后是否保持原来的信号形式分：系统码与非系统码统码与非系统码vv 按纠正差错的类型分：纠正随机错误的码与纠正突发按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码错误的码vv 按码元的取值分：二进制码与多进制码按码元的取值分：二进制码与多进制码1 1、差错控制编码分类、差错控制编码分类11.1 11.1 概述概述第11章 差错控制编码2 2、误码类型、误码类型v 随机误码v 突发误码错码出现是随机的、错码之间统计独立。由随机噪声引起存在随机误码的信道称为随机信道无记忆信道差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关例如：脉冲噪声，存储系统中磁带的缺陷或读写头接触不良引起，再例如用手机过涵洞，且无发射天线存在这种差错的信道称为突发信道有记忆信道11.1 11.1 概述概述3 3、错误图样、错误图样l例如：设发送数据序列为：00000000001111111111接收数据序列为：01101001001111001001错误图样（差错序列）：发送数据序列与接收序列对应码位的模和则差错序列为：01101001000000110110l可见发生了两个长度分别为和的突发差错，其错误图样分别为1101001和11011突发长度：指突发差错首位与末位之间的长度（中间可能有没错的码位）第11章 差错控制编码l说明差错序列或错误图样中的“”表示对应码位没错，而“”表示有错实际信道很复杂，所出现的差错并不是单一的，往往是随机和突发差错并存，只不过以某种错误为主一般说来，纠正随机差错的编译码方法和设备比较简单，成本较低，效果较显著；而纠正突发差错的编译码方法和设备比较复杂，成本较高，效果也不如前者显著11.1 11.1 概述概述第11章 差错控制编码 4 4、信道类型、信道类型v 随机信道v 突发信道v 混合信道11.1 11.1 概述概述第11章 差错控制编码5 5、差错控制方法、差错控制方法v检错重发（ARQ）停发等候重发 返回重发 选择重发v前向纠错（FEC）v反馈校验（IRQ）v检错删除（ECD）v混合方式（HEC）11.1 11.1 概述概述第11章 差错控制编码（1 1）检错重发法（）检错重发法（ARQARQ）Automatic Repeat reQuestAutomatic Repeat reQuest 收端在接收到的信码中发现错码时，就通知发端重发，直到正确接收为止。例如奇偶校验。检错重发方式只用于检测误码，能够在接收单元中发现错误，但不一定知道该错误码的具体位置。需具备双向信道。11.1 11.1 概述概述发发收收能够发现错误的码能够发现错误的码图图11.1-1（a)检错重发（检错重发（ARQ)应答信号应答信号图图11.1-111.1-1（b)b)检错重发（检错重发（ARQ)ARQ)信信源源编码器和缓编码器和缓冲存储器冲存储器重发控制重发控制双双向向信信道道解码器解码器指令产生器指令产生器输出缓冲输出缓冲存储器存储器收收信信者者正确时输出错误时删除判断有无错误第11章 差错控制编码 停发等候重发停发等候重发2发送端：接收端：133123ACKACKNAK发现错误TITw停顿时间图图11.1-2 11.1-2 停发等候重发停发等候重发11.1 11.1 概述概述第11章 差错控制编码发端在Tw时间内送出一个码组；收端收到后检查。如果未发现错误，则发回一个认可信号（ACK）给发送端，发送端收到ACK信号再发下一个码组若检测到错误，则发回一个否认信号（NAK），发送端收到NAK信号后重发前一码组，并再次等候ACK信号或NAK信号发送两个码组之间有停顿时间TI，影响了传输效率11.1 11.1 概述概述第11章 差错控制编码 返回重发返回重发(拉回重发拉回重发)其发送端不停地送出一个个连续码组，不再等候收端返回的ACK信号一旦收端发现错误并返回NAK信号，则发端从下一码组开始重发前面的N个码组N的大小取决于信号传递及处理所带来的延时11.1 11.1 概述概述第11章 差错控制编码发送端：接收端：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开始重发11.1 11.1 概述概述图图11.1-3 11.1-3 返回重发返回重发第11章 差错控制编码 选择重发选择重发也是连续不断地发送码组，收端检测到错误后发回NAK信号。与返回重发不同的是，发端并不重发错误码组后的所有码组，而只重发有错的那个码组11.1 11.1 概述概述第11章 差错控制编码发送端：接收端：1 2 3 4 5 6 2 7 81 2 3 4 5 6 2 7 899发现错误NAK重发码组2图图11.1-4 11.1-4 选择重发选择重发11.1 11.1 概述概述第11章 差错控制编码三者比较 选择重发传输效率最高，但成本最贵：控制机制复杂，发端和收端都要有数据缓冲器；返回重发、选择重发需要全双工数据链路，而停发等候重发只要求半双工的数据链路。11.1 11.1 概述概述第11章 差错控制编码（2 2）前向纠错法（）前向纠错法（FECFEC）Forward Error CorrectionForward Error Correction发发收收能够纠正错误的码能够纠正错误的码图图11.1-5 11.1-5 前向纠错（前向纠错（FEC)FEC)信信源源编编码码器器单单向向信信道道纠错译码器纠错译码器输出缓冲输出缓冲存储器存储器收收信信者者+11.1 11.1 概述概述第11章 差错控制编码发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正不需要反馈信道，特别适合只能提供单向信道场合自动纠错，不要求检错重发，延时小，实时性好纠错码必须与信道的错误特性密切配合若纠错较多，则编、译码设备复杂，传输效率低11.1 11.1 概述概述第11章 差错控制编码（3 3）信息反馈校验法（）信息反馈校验法（IRQIRQ）Information Repeat reQuestInformation Repeat reQuest接收端将接收到的信码原封不动地转发回发端，并与原发送信码相比较，若发现错误，发端再重发。数据信息数据信息发收图图11.1-6 信息反馈法信息反馈法数据信息数据信息11.1 11.1 概述概述第11章 差错控制编码收端把收到的数据序列全部经反向信道送回发端，发端比较发出和送回的数据序列，从而发现有否错误，如果有错误，发端将数据序列再次传送，直到发端没有发现错误。不需要纠错、检错的编、译码器，设备简单。需要和正向信道相同的反向信道，实时性差发端需要一定容量的存储器以存储发送码组仅适应于传输速率较低，信道差错率较低，具有双向传输线路及控制简单的系统11.1 11.1 概述概述第11章 差错控制编码（4 4）检错删除（）检错删除（ECDECD）Error Correction DeletionError Correction Deletion接收端发现错码之后，立即将其删除，不要求重发。适用在少数特定系统中，发送码元中包含大量多余度，删除部分接受码元并不影响使用。设备复杂度低，不需要缓冲存储装置。11.1 11.1 概述概述第11章 差错控制编码（5 5）混合纠错检错（）混合纠错检错（HECHEC）Hybrid Error CorrectionHybrid Error CorrectionFEC与ARQ的结合发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发。在实时性和译码复杂性方面是FEC和ARQ的折衷。11.1 11.1 概述概述第11章 差错控制编码发发收收能够发现和纠正错误的码能够发现和纠正错误的码图图11.1-7 混合纠错检错（混合纠错检错（HEC)应答信号应答信号11.1 11.1 概述概述第11章 差错控制编码核心问题核心问题v 发现错误发现错误v 纠正错误纠正错误11.1 11.1 概述概述第11章 差错控制编码11.2 11.2 差错控制编码的基本原理差错控制编码的基本原理 在信息码序列中加监督码就称为差错控制编码，也叫纠错编码。不同的编码方法，有不同的检错和纠错能力，增加监督码元越多，检（纠）错能力越强。差错控制编码原则上是降低传输效率来换取可靠性提高。（即误码率更小）。第11章 差错控制编码v理论依据：Shannon信道编码定理。v定理指出：对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。1 1、纠错编码的理论依据、纠错编码的理论依据11.2 11.2 差错控制编码的基本原理差错控制编码的基本原理第11章 差错控制编码2 2、纠错编码的基本思想、纠错编码的基本思想11.2 11.2 差错控制编码的基本原理差错控制编码的基本原理v 发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系v 以牺牲通信的有效性（信息传输速率）来提高可靠性v 码的检错和纠错能力是用信息量的冗余来换取的。一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。第11章 差错控制编码v 码长：码字中码元的数目。v 码距：两个等长码字中对应码位上不同二进制码元的位数定义两码字的距离，简称码距（d）。对于二进制称作这两个码字的汉明距离。如两码字“10011”与“11010”间码距为2。3 3、码距与检错和纠错能力的关系、码距与检错和纠错能力的关系11.2 11.2 差错控制编码的基本原理差错控制编码的基本原理（1 1）几个概念）几个概念第11章 差错控制编码v 最小码距：在一个码字集合中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为dmin或d0v 码重：码字中非零码元的数目定义为该码字的重量，简称码重。如“10011”码字的码重为3。纠错码的抗干扰能力完全取决于许用码字之间的距纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。大，抗干扰能力就越强。11.2 11.2 差错控制编码的基本原理差错控制编码的基本原理第11章 差错控制编码举例说明：假如要传送举例说明：假如要传送A A、B B两个消息两个消息编码一：消息A-“0”；消息B-“1”最小码距1若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力。11.2 11.2 差错控制编码的基本原理差错控制编码的基本原理第11章 差错控制编码编码二：消息A-“00”；消息B-“11”最小码距2若传输中产生一位错码，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力11.2 11.2 差错控制编码的基本原理差错控制编码的基本原理编码三：消息A-“000”；消息B-“111”最小码距3传输中产生一位甚至两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。在产生一位错码（错1位概率远远大于错2位、3位概率）情况下，收端可根据“最大似然”法则进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。例如收到110，认为是111。这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。第11章 差错控制编码一个码能检测e个错码，则要求其最小码dmine+1一个码能纠正t个错码，则要求其最小dmin2t+1一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 dmine+t+1 (et)（2 2）最小码距与检错和纠错能力的关系）最小码距与检错和纠错能力的关系11.2 11.2 差错控制编码的基本原理差错控制编码的基本原理第11章 差错控制编码(a)(a)检检e e个错个错图图11.2-2(a)11.2-2(a)码距与检错纠错能力的关码距与检错纠错能力的关系系Ae1dminBA A、B B都为许用码；都为许用码；A A发生发生e e个错；个错；B B不能靠在球面上，不能靠在球面上，否则收到否则收到B B无法判断无法判断是否为错码；是否为错码；d dminmine+1e+111.2 11.2 差错控制编码的基本原理差错控制编码的基本原理第11章 差错控制编码1tABtdmin(b)(b)纠正纠正t t个错码个错码图图11.2-2(b)11.2-2(b)码距与检错纠错能力的关码距与检错纠错能力的关系系A A、B B都为许用码；都为许用码；A A、B B都发生都发生t t个错；个错；d dminmin2t+12t+111.2 11.2 差错控制编码的基本原理差错控制编码的基本原理第11章 差错控制编码ABtedmint(c)(c)纠正纠正t t个错码，检测个错码，检测e e个错码个错码图图11.2-2(c)11.2-2(c)码距与检错纠错能力的关码距与检错纠错能力的关系系A A、B B都为许用码；都为许用码；A A发生发生e e个错；个错；B B发生发生t t个错；个错；d dminmine+t+1e+t+111.2 11.2 差错控制编码的基本原理差错控制编码的基本原理第11章 差错控制编码当码长n=7,P=10-3时，则有假设随机信道中发送“0”码与发送“1”码传错概率相等都为P,且P1,则在码长为n的码组中发生r个错误的概率为：4 4、误码率、误码率大概率事件大概率事件11.2 11.2 差错控制编码的基本原理差错控制编码的基本原理第11章 差错控制编码设n=k+r指一个码组中信息位所占比重，用 表示=k/n=k/(k+r)，其中k为信息码元的数目，n为码长5 5、编码效率、编码效率11.2 11.2 差错控制编码的基本原理差错控制编码的基本原理第11章 差错控制编码v 奇偶监督码v 二维奇偶监督码v 恒比码v 正反码vISBNISBN国际图书统一编号国际图书统一编号11.3 11.3 常用的简单编码常用的简单编码 第11章 差错控制编码1 1、奇偶监督码、奇偶监督码 parity checkparity check11.3 11.3 常用的简单编码常用的简单编码 奇偶监督码：在信息码元后附加一位监督位，使得码组中奇偶监督码“1”的个数为偶数或奇数。第11章 差错控制编码v 最小码距dmin=2v 只能检测出单个或奇数个错误，不能纠错v 应用：以随机错误为主的计算机通信系统，难于对付突发错误v 编码效率=k/n=k/(k+1)11.3 11.3 常用的简单编码常用的简单编码 第11章 差错控制编码v 又称为方阵码、行列监督码、二维奇偶监督码。v 将水平奇偶监督码推广到二维。即在水平监督基础上再对方阵中每一列进行奇偶校验，发送时按列的顺序传输v 接收端将码元排成发送时的方阵形式，再分别按行、按列进行奇偶校验2 2、水平垂直奇偶监督码、水平垂直奇偶监督码11.3 11.3 常用的简单编码常用的简单编码 第11章 差错控制编码46v 能够发现某行、某列上所有奇数个错误以及突发长度不大于方阵行数或列数的突发错误；v 有可能检测出偶数个错误（在行上检测不出，但有可能在列上检测出），但当偶数个错误刚好构成矩形时，则检测不出v 可纠正一些错误v 11.3 11.3 常用的简单编码常用的简单编码 第11章 差错控制编码THANK YOUSUCCESS2023/2/447可编辑表表11-3 11-3 水平垂直奇偶监督码水平垂直奇偶监督码发送顺序表表11-4 11-4 水平垂直奇偶监督码接收端纠错示例水平垂直奇偶监督码接收端纠错示例011例如：当码组中仅在一行有奇数个错误时，能例如：当码组中仅在一行有奇数个错误时，能够确定错误位置，并纠正它。够确定错误位置，并纠正它。表表11-5 11-5 水平垂直奇偶监督码接收端检错示例水平垂直奇偶监督码接收端检错示例011构成矩形的偶数个误码检测不出。构成矩形的偶数个误码检测不出。00 表表11-6 11-6 水平垂直奇偶监督码接收端检错示例水平垂直奇偶监督码接收端检错示例01有可能检测出偶数个误码。有可能检测出偶数个误码。001第11章 差错控制编码523 3、恒比码、恒比码v 每个码组中含“1”和“0”的个数的比例恒定，又称等重码v 能检测出所有1个和奇数个错误，并能部分检测出偶数个错误（成对交换错则检测不出）v 简单，适应于对字母或符号进行编码11.3 11.3 常用的简单编码常用的简单编码 表表11-7 11-7 保护电码保护电码（是一种五中取三码）（是一种五中取三码）数字数字电码电码数字数字电码电码00 1 1 0 150 0 1 1 110 1 0 1 161 0 1 0 121 1 0 0 171 1 1 0 031 0 1 1 080 1 1 1 041 1 0 1 091 0 0 1 1第11章 差错控制编码4 4、正反码、正反码v 监督位数目与信息位数目相同，且监督码元与信息码元或者相同或者相反，取决于信息序列中“1”的个数。v 电报通信用的正反码的码长n=10。信息位k=5，监督位r=5。11.3 11.3 常用的简单编码常用的简单编码 第11章 差错控制编码v 码组中信息位有奇数个“1”，监督码元与信息码元相同；v 码组中信息位有偶数个“1”，监督码元与信息码元相反。11.3 11.3 常用的简单编码常用的简单编码（1 1）正反码编码规则）正反码编码规则第11章 差错控制编码v 将接收码组中信息位与监督位按位模2加，得到合成码组v 产生校验码组：v 接收码组中信息码元有奇数个“1”，则校验码组=合成码组，否则校验码组=合成码组的反码v 按照校验码组中“1”的个数进行判决及纠错（表11-8）11.3 11.3 常用的简单编码常用的简单编码（2 2）接收端解码规则）接收端解码规则校验码组组成校验码组组成误码情况误码情况全为全为0无误码无误码4个个“1”，1个个“0”信息码有一个错码，位置对应信息码有一个错码，位置对应校验码组中校验码组中“0”的位置的位置1个个“1”，4个个“0”监督码有一个错码，位置对应监督码有一个错码，位置对应校验码组中校验码组中“1”的位置的位置其它其它错码多于错码多于1个个表表11-8 11-8 正反码检错纠错判决规则正反码检错纠错判决规则第11章 差错控制编码58(1)(1)若接收码组为若接收码组为11001110011100111001合成码组为合成码组为11001 11001=0000011001 11001=00000因码组中信息码元有奇数个因码组中信息码元有奇数个“1 1”，校验码，校验码=00000=00000判决为无错传输判决为无错传输(2)(2)若接收码组为若接收码组为10001110011000111001 合成码组合成码组10001 11001=0100010001 11001=01000 因码组中信息码元有偶数个因码组中信息码元有偶数个“1 1”，则校验码组为，则校验码组为1011110111；说明信息码元中第二位错码，给以纠正为说明信息码元中第二位错码，给以纠正为1 11 10011100100111001 例例11-111-1 假设发送码组为假设发送码组为11001110011100111001，分析各种，分析各种正反码判决纠错情况。正反码判决纠错情况。11.3 11.3 常用的简单编码常用的简单编码(3)(3)若接收码组为若接收码组为11001010011100101001：合成码组合成码组1000010000；因码组中信息码元有奇数个因码组中信息码元有奇数个“1 1”，则校验码组为，则校验码组为10000 10000 说明监督码元中第一位错码说明监督码元中第一位错码(4)(4)若接收码组为若接收码组为10011110011001111001：合成码组合成码组0101001010；因码组中信息码元有奇数个因码组中信息码元有奇数个“1 1”，则校验码组为，则校验码组为0101001010，说明错码多于说明错码多于1 1个个码长为码长为1010的正反码能够纠正的正反码能够纠正1 1位差错，并能位差错，并能检测所有检测所有2 2位及以下的错码。位及以下的错码。第11章 差错控制编码5 5、ISBNISBN国际图书统一编号国际图书统一编号International Standard Book NumberInternational Standard Book NumberISBN 7-118-02481-3中国中国出出版版公公司司书书名名编编号号校校验验位位无误码，若不能被11整除，有误码11.3 11.3 常用的简单编码常用的简单编码 第11章 差错控制编码 7 1 1 8 0 2 4 7 1 1 8 0 2 4 8 1 38 1 37*10+1*9+1*8+8*7+0*6+2*5+4*4+8*3+1*2+3*17*10+1*9+1*8+8*7+0*6+2*5+4*4+8*3+1*2+3*1=198=198（模（模1111）=0=011.3 11.3 常用的简单编码常用的简单编码 能被11整除，无误码。第11章 差错控制编码5 5、ISBNISBN国际图书统一编号国际图书统一编号International Standard Book NumberInternational Standard Book Number11.3 11.3 常用的简单编码常用的简单编码 早期的早期的ISBNISBN号由号由1010位十进制数字组成，位十进制数字组成，20072007年起全世年起全世界的界的ISBNISBN号统一升级为号统一升级为1313位，简称位，简称“ISBN-13ISBN-13”。ISBN-13的编码结构组成 第11章 差错控制编码11.3 11.3 常用的简单编码常用的简单编码 每个每个ISBNISBN号码的前号码的前1212位与最后一位校验位之间有通过固定算法位与最后一位校验位之间有通过固定算法形成的约束关系。若它们之间不满足这个约束关系，则该形成的约束关系。若它们之间不满足这个约束关系，则该ISBNISBN号码对应号码对应的图书必为非法出版物。校验位的具体算法包括：的图书必为非法出版物。校验位的具体算法包括：9 7 8 7 3 0 2 1 3 2 3 1(1)1 3 1 3 1 3 1 3 1 3 1 3(2)9+21+8+21+3+0+2+3+3+6+3+3=82(3)MOD10=2(4)10-2=8第11章 差错控制编码11.4 11.4 线性分组码线性分组码(1)分组码：先将信息码分组，然后给每组信码附加若干监督码的编码称为分组码，用符号(n,k)表示，k是信息码的位数，n是编码组总位数，又称为码长，r=n-k为监督位数。(2)代数码：建立在代数学基础上的编码称为代数码。例如奇偶校验码。v1 1、基本概念基本概念第11章 差错控制编码(3)线性码：线性码中信息位和监督位是按一组线性方程构成的。线性码是一种代数码。(4)线性分组码：信息码分组后，附加的监督码和信息码由一些线性代数方程联系着的编码称为线性分组码。11.4 11.4 线性分组码线性分组码第11章 差错控制编码2 2、线性分组码的性质、线性分组码的性质v任意两个许用码组之和（逐位模2和）仍为一许用码组，即具有封闭性。v最小码距=非零码的最小码重（1的个数）。v有零码（信息码元和监督码元均为零的码组）11.4 11.4 线性分组码线性分组码第11章 差错控制编码以汉明码为例来说明编码原理。汉明码是一种设计用来纠正一位错码且编码效率较高的线性分组码，已广泛应用于数字通信和数据存储系统中，本节将以（7，4）汉明码为例进行讲述。3 3、线性分组码的编码原理线性分组码的编码原理11.4 11.4 线性分组码线性分组码第11章 差错控制编码v 发送端编码：将一位监督码元附加在信息码元后，使得码元中“1”码元个数为偶数。v 接收端译码：计数接收码组中“1”码元个数是否为偶数，即计算：S=an-1+an-2+a0（模（模2 2加）加）（11.4-111.4-1）S=0认为没错，S=1认为有错。（11.4-1）式称为监督方程/监督关系式，S称为校正子/校验子/伴随式（1 1）回忆奇偶监督偶校验码）回忆奇偶监督偶校验码11.4 11.4 线性分组码线性分组码第11章 差错控制编码v 监督位增加到2位：有两个监督方程，两个伴随式；v 两个伴随式组合有四种（00表示无错，01、10、11表示一位错码的三种可能位置）v 监督位增加到r位：可指示一位错码的（2r-1）个可能位置v对于（n，k)分组码，若希望用r=n-k个监督位构造出的r个监督关系式来指示一位错码的n种可能位置，则要求：2 2r r-1n -1n 即即2 2r r k+r+1 k+r+1 （11.4-211.4-2）可以这样来考虑11.4 11.4 线性分组码线性分组码第11章 差错控制编码欲纠正一位错码，由（11.4-2）式知r 3。取r=3，则n=k+r=7设7位码元为：a6a5 a0；三个伴随式：S1、S2、S3；可规定S1S2S3的八种组合与一位错码的对应关系（也可规定为另一种对应关系）：构造一（构造一（n n，k)k)分组码，分组码，k=4k=4并能纠正一位错码并能纠正一位错码(2)(2)汉明码的构造汉明码的构造11.4 11.4 线性分组码线性分组码第11章 差错控制编码表表11-9 S11-9 S1 1S S2 2S S3 3的八种组合与一位错码的对应关系的八种组合与一位错码的对应关系11.4 11.4 线性分组码线性分组码第11章 差错控制编码S1S2S3错码位置错码位置0 0 0无错码无错码0 0 1a00 1 0a11 0 0a20 1 1a31 0 1a41 1 0a51 1 1a6信息码信息码监督码监督码a6 a5a4 a3a2 a1 a0FS S1 1=a=a2 2+a+a4 4+a+a5 5+a+a6 6FS S2 2=a=a1 1+a+a3 3+a+a5 5+a+a6 6FS S3 3=a=a0 0+a+a3 3+a+a4 4+a+a6 6(11.4-(11.4-3)3)监督方程监督方程:第11章 差错控制编码（3 3）发端编码的原则：发端编码的原则：v 信息码元a6、a5、a4、a3来源于待编码的信息序列；v 监督码元 a2、a1、a0的取值应根据信息码元按监督关系式来决定，即使前面三式中的S1、S2、S3均为0：11.4 11.4 线性分组码线性分组码第11章 差错控制编码Fa a2 2=a=a4 4+a+a5 5+a+a6 6Fa a1 1=a=a3 3+a+a5 5+a+a6 6Fa a0 0=a=a3 3+a+a4 4+a+a6 6v 给定信息位后，根据上式算出各监督位，该编码的所有码组如表11-10：(11.4-(11.4-4)4)Fa a6 6+a+a5 5+a+a4 4+a+a2 2=0=0Fa a6 6+a+a5 5+a+a3 3+a+a1 1=0=0Fa a6 6+a+a4 4+a+a3 3+a+a0 0=0=0(11.4-(11.4-5)5)11.4 11.4 线性分组码线性分组码第11章 差错控制编码表表11-10 11-10 （7 7，4 4）汉明编码的许用码组）汉明编码的许用码组第11章 差错控制编码v该汉明码的编码效率较高 R=k/n=4/757%v该码的最小码距为3，能纠正一个错码或检测两个错码v收到码组0000011，按照（7，4）汉明码进行分析，判断是否有误，如果有，如何更正？按监督方程计算可得：S1=0，S2=1，S3=1；再根据校正子组合与一位错码位置的对应关系，可知错码发生在a3位，并加以纠正。0000001 101101111.4 11.4 线性分组码线性分组码第11章 差错控制编码（4 4）监督矩阵）监督矩阵沿（7，4）汉明码出发，式（11.4-4）可改写成：1 a6+1 a5+1 a4+0 a3+1 a2+0 a1+0 a0=01 a6+1 a5+0 a4+1 a3+0 a2+1 a1+0 a0=01 a6+0 a5+1 a4+1 a3+0 a2+0 a1+1 a0=0写成矩阵形式：(11.4-6)(11.4-6)11.4 11.4 线性分组码线性分组码第11章 差错控制编码H称为线性码监督矩阵可化简为：HAT=0T 或AHT=011.4 11.4 线性分组码线性分组码第11章 差错控制编码v rn阶矩阵v 监督矩阵H确定了编码时监督码元与信息码元的关系v 把具有PIr形式的H矩阵称为典型形式的监督矩阵，其中P为r k阶矩阵,Ir为r r阶单位方阵v H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关监督矩阵H特点11.4 11.4 线性分组码线性分组码第11章 差错控制编码上式右部前面矩阵就是监督矩阵H中的P矩阵。(5)(5)生成矩阵生成矩阵（11.4-5）式也可写成矩阵形式，即(11.4-7)(11.4-7)11.4 11.4 线性分组码线性分组码第11章 差错控制编码其中Q=PT可见，Q为k r阶矩阵。或写成11.4 11.4 线性分组码线性分组码第11章 差错控制编码生成矩阵G：在Q矩阵的左边加上一个k k阶矩阵，即11.4 11.4 线性分组码线性分组码第11章 差错控制编码vk n阶矩阵v编码方法完全由生成矩阵G确定v把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中，Ik为kk阶单位方阵，Q为k r阶矩阵vG矩阵的各行应线性无关，每行均为许用码组生成矩阵G特点11.4 11.4 线性分组码线性分组码第11章 差错控制编码例11-2 已知（6，3）汉明码的生成矩阵如下，(1)列出所有许用码组;(2)最小码距d0;(3)检错纠错能力(4)编码效率11.4 11.4 线性分组码线性分组码第11章 差错控制编码（1 1）信息码信息码编码码字编码码字码重码重0 0 00 0 0 0 0 000 0 10 0 1 1 1 030 1 00 1 0 0 1 130 1 10 1 11 0 141 0 01 0 0 1 0 131 0 11 0 1 0 1 141 1 01 1 0 1 1 041 1 1 1 1 1 0 0 03第11章 差错控制编码（3 3）（4 4）（2 2）第11章 差错控制编码设（设（7,47,4）线性码的生成矩阵）线性码的生成矩阵G G为：为：当信息位为当信息位为00010001时，时，（1 1）试求其后的监督位。）试求其后的监督位。（2 2）监督矩阵）监督矩阵H11.4 11.4 线性分组码线性分组码第11章 差错控制编码解：解：（1 1）第11章 差错控制编码（2 2）监督矩阵）监督矩阵H H根据生成矩阵和监督矩阵的关系：根据生成矩阵和监督矩阵的关系：G=IG=Ik kQQ，H=PH=PI Ir r 其中其中P=QP=QT T，可得监督矩阵，可得监督矩阵H H为：为：第11章 差错控制编码v错误矩阵/错误图样E：设发送码组为A，接收码组为B，(6)(6)校正子与检错校正子与检错则错误矩阵 11.4 11.4 线性分组码线性分组码第11章 差错控制编码v接收端计算校正子S，即S=BHT=(A+E)HT=AHT+EHT=0+EHT=EHT 可见校正子只与E有关，即错误图样与校正子之间有确定的关系，接收端译码器的任务就是从校正子确定错误图样，然后从接收的码字中减去错误图样。11.4 11.4 线性分组码线性分组码第11章 差错控制编码v以（7，4）汉明码为例设发送码组A=（0001011）接收码组 B=（0000011）则收端译码过程如下：计算校正子查表得a3为错误位置，即可纠正（0001011）11.4 11.4 线性分组码线性分组码第11章 差错控制编码1.1.1.1.信信信信道道道道编编编编码码码码与与与与信信信信源源源源编编编编码码码码有有有有什什什什么么么么不不不不同同同同？纠纠纠纠错错错错码码码码能能能能够够够够检检检检错错错错或或或或纠错的根本原因是什么？纠错的根本原因是什么？纠错的根本原因是什么？纠错的根本原因是什么？2.2.2.2.差错控制的基本工作方式有哪几种差错控制的基本工作方式有哪几种差错控制的基本工作方式有哪几种差错控制的基本工作方式有哪几种?各有什么特点？各有什么特点？各有什么特点？各有什么特点？3.3.3.3.检检检检(纠纠纠纠)错能力与最小码距有什么关系错能力与最小码距有什么关系错能力与最小码距有什么关系错能力与最小码距有什么关系?4.4.4.4.(7,4)(7,4)(7,4)(7,4)汉明码有哪些特点汉明码有哪些特点汉明码有哪些特点汉明码有哪些特点?5.5.5.5.什么叫做奇偶监督码什么叫做奇偶监督码什么叫做奇偶监督码什么叫做奇偶监督码?其检错能力如何其检错能力如何其检错能力如何其检错能力如何?p371p371：11-1,2,611-1,2,6作作 业业第11章 差错控制编码THANK YOUSUCCESS2023/2/494可编辑