通信原理-第10章-差错控制编码-09-06-20课件.ppt

1、12 信源编码，目的是实现模拟信号数字化信源编码，目的是实现模拟信号数字化 信道编码，目的是提高数字通信的可靠性信道编码，目的是提高数字通信的可靠性 差错率是信噪比的函数差错率是信噪比的函数 信道编码，差错控制编码，抗干扰编码信道编码，差错控制编码，抗干扰编码 信道编码过程：信道编码过程：信息码元序列监督码元信息码元序列监督码元编码码组编码码组 信道译码过程：信道译码过程：编码码组编码码组检错或纠错检错或纠错信息码元序列信息码元序列3 10.1.1差错控制方式差错控制方式 10.1.2差错控制编码分类差错控制编码分类 10.1.3几种简单的检错码几种简单的检错码 10.1.4检错和纠错的基本原

2、理检错和纠错的基本原理4 常用的差错控制方式有三种：常用的差错控制方式有三种：前向纠错（前向纠错（FEC:forward error correction）发送能纠错的码，在译码时发送能纠错的码，在译码时自动发现并纠正传输中的错误自动发现并纠正传输中的错误 只需正向信道，实时性好只需正向信道，实时性好 编译码设备复杂编译码设备复杂，适合单向信道和一发多收系统，适合单向信道和一发多收系统 检错重发（检错重发（ARQ:automatic repeat request）发送端发出能够检错的码，接收端检验，接收端发出反馈应答信号，发送端发出能够检错的码，接收端检验，接收端发出反馈应答信号，发送端重新传

3、输发送端重新传输 直到正确接收为止直到正确接收为止 工作原理简单，正向信道工作原理简单，正向信道+反向信道，传输效率低反向信道，传输效率低 混合纠错（混合纠错（HEC:hybrid error correction）前向纠错方式和检错重发方式的结合与折衷前向纠错方式和检错重发方式的结合与折衷 外层先采用前向纠错，当前向纠错不能解决问题时，内层再采用检错外层先采用前向纠错，当前向纠错不能解决问题时，内层再采用检错重发重发。5（a）FEC方式方式 （b）ARQ方式方式 （c）HEC方式方式6 检检 错错 重重 发发 的的 三三 种种 方方 式式 停发等候重发停发等候重发返回重发返回重发选择重发选择

4、重发71010.1.2.1.2 差错控制编码分类差错控制编码分类在编码前先把信息序列分为在编码前先把信息序列分为k位一组（称为位一组（称为信息信息码码），然后附加），然后附加m位位监督码监督码，形成，形成n=k+m位的码组。位的码组。1、按信息码和附加监督码间的检验关系、按信息码和附加监督码间的检验关系 线性码：监督码是信息码的线性组合线性码：监督码是信息码的线性组合 非线性码：监督码是信息码的非线性组合非线性码：监督码是信息码的非线性组合2、按信息码和监督码间的约束方式、按信息码和监督码间的约束方式 分组码：监督码仅与本码组的信息码有关分组码：监督码仅与本码组的信息码有关 卷积码：监督码与之

5、前的若干个信息码组的码元有约束关系卷积码：监督码与之前的若干个信息码组的码元有约束关系81.奇偶监督码奇偶监督码 编码方法编码方法 把信息码元先分组，在每组最后加一位监督码元，使把信息码元先分组，在每组最后加一位监督码元，使该码组中该码组中1的数目为奇数或偶数的数目为奇数或偶数 奇数时称为奇校验码奇数时称为奇校验码 偶数时称为偶校验码偶数时称为偶校验码 偶校验码偶校验码 许用码组为许用码组为000，011，101，110 禁用码组为禁用码组为001，010，100，111 奇校验码奇校验码 禁用码组为禁用码组为000，011，101，110 许用码组为许用码组为001，010，100，1119

6、一般情况下：一般情况下：设码组长为设码组长为n，且为：，且为：则偶校验时有：则偶校验时有：奇校验时有：奇校验时有：译码方法译码方法(与编码方法相对应与编码方法相对应)不满足校验关系，传输一定错误！不满足校验关系，传输一定错误！奇偶校验只能发现奇数个奇偶校验只能发现奇数个(单个单个)错误，不能检测出错误，不能检测出偶数个错误。偶数个错误。编码方法简单且实用性强，适用于检测随机零星错码编码方法简单且实用性强，适用于检测随机零星错码 满足校验关系，传输一定准确吗？满足校验关系，传输一定准确吗？0321aaaannn0 110naaa1 110naaa102.二维奇偶监督码二维奇偶监督码 将奇偶校验码

7、的若干码组排列成矩阵将奇偶校验码的若干码组排列成矩阵 每一码组写成一行每一码组写成一行 m个码组个码组m行行 m个监督位构成了一监督位列个监督位构成了一监督位列 按列的方向增加第二维校验位按列的方向增加第二维校验位 n个监督位构成了一监督位行个监督位构成了一监督位行NoImageNoImageNoImage检错能力检错能力 检出所有行和列中的奇数个检出所有行和列中的奇数个差错差错 能检出大多数偶数个差错能检出大多数偶数个差错 检测突发错码也有一定的适检测突发错码也有一定的适应能力应能力方阵码，交织码方阵码，交织码113.重复码重复码 重复码是在每位信息码元之后，再简单重复多次的编码；重复码是在

8、每位信息码元之后，再简单重复多次的编码；接收端译码时采用多数表决法接收端译码时采用多数表决法。4.恒比码恒比码 从固定码长的码组中选择那些从固定码长的码组中选择那些1和和0的比例恒定的码组作的比例恒定的码组作为许用码组，如五单位保护电码等。为许用码组，如五单位保护电码等。5.ISBN国际统一图书编号国际统一图书编号2007年作了修改年作了修改1210.1.4 10.1.4 检错与纠错的基本原理检错与纠错的基本原理 差错编码的基本思想是在被传输的信息中附加监差错编码的基本思想是在被传输的信息中附加监督码，用督码，用信息的冗余度信息的冗余度来实现检错和纠错。来实现检错和纠错。例如：例如：00000

9、0、001001、010010、011011、100100、101101、110110、111111用用来传递信息，则无法检错；来传递信息，则无法检错；000000、011011、101101、110110用来传递信息可以检一位错，但用来传递信息可以检一位错，但无法纠错；无法纠错；000000、111111用来传递信息可以检一位或两位错码，还可用来传递信息可以检一位或两位错码，还可以纠一位错码。以纠一位错码。可见，码组间的差异与纠检错能力十分重要。可见，码组间的差异与纠检错能力十分重要。13 定义定义1：码组中非零码元的数目称为码组的重量，简称码组中非零码元的数目称为码组的重量，简称码重。码重

10、。定义定义2：两码组中对应码位上具有不同码元的数目称为两码组中对应码位上具有不同码元的数目称为两码组的距离，简称码距，又叫汉明距。两码组的距离，简称码距，又叫汉明距。最小汉明距离最小汉明距离dmin决定纠检错能力决定纠检错能力 例例 8种码组种码组000000、001001、010010、011011、100100、101101、110110、111111均均为许用码组时，最小码距为为许用码组时，最小码距为1 在选在选4种码组种码组000000、011011、101101、110110为许用码组情况下，最为许用码组情况下，最小码距为小码距为2 采用采用2种许用码组种许用码组000000、111

11、111时，最小码距为时，最小码距为314下图为码距的几何解释下图为码距的几何解释三种编码组合，其汉明距分别为三种编码组合，其汉明距分别为1，2，3。15 对于分组码，一般有如下结论：对于分组码，一般有如下结论：(1)(1)在一个码组内检测在一个码组内检测e e个误码，要求个误码，要求 ；(2)(2)在一个码组内纠正在一个码组内纠正t t个误码，要求个误码，要求 ；(3)(3)在一个码组内纠正在一个码组内纠正t t个误码，同时检测个误码，同时检测 个误个误码，要求码，要求 。差错控制编码提高了通信系统的可靠性，也降低了有效差错控制编码提高了通信系统的可靠性，也降低了有效性。性。为衡量有效性，定义

12、编码效率为衡量有效性，定义编码效率 。k k是编码前码组中的码元数，即信息码元数是编码前码组中的码元数，即信息码元数；n n是编码后码组中的码元数，它包含了校验码元是编码后码组中的码元数，它包含了校验码元。1min ed12min td)(tee1minetdnkR/c1610.2 10.2 线性分组码线性分组码 线性码组中的监督码是信息码元的线性组合。线性码组中的监督码是信息码元的线性组合。线性码具有封闭性，即任意两个许用码组之和（模线性码具有封闭性，即任意两个许用码组之和（模2加），结果仍为一许用码组。加），结果仍为一许用码组。设设n位分组码用位分组码用 表示，表示，k位信息码用位信息码用

13、 表示，记该码组为表示，记该码组为(n,k)码。码。将码组和信息码组用行矩阵表示出来，则有：将码组和信息码组用行矩阵表示出来，则有：nccc,21kddd,21nccc,21Ckddd,21D17 kmkmmnkkkkkkkkdhdhdhcdhdhdhcdhdhdhcdcdcdc 221122221212121211112211n=k+m，n：编码以后的位数：编码以后的位数k：编码以前的位数，即：编码以前的位数，即信息码信息码m=n-k：监督位或校验位：监督位或校验位18 写成矩阵形式，有写成矩阵形式，有 ，G为生成矩阵为生成矩阵(k*n)，且：，且：设设 则则GDCmkkkmmhhhhhhh

14、hh212221212111100000100001G100000100001kImkkkmmhhhhhhhhh212221212111P mkkCDDPDDPDIPIDC,k行行k+m=n列列19 与监督位或校验位相对应与监督位或校验位相对应 编码的根据编码的根据 译码的根据，检纠错的根据译码的根据，检纠错的根据矩阵矩阵P如何选择？如何选择？编码前信息码组有编码前信息码组有k位码元，位码元，k位码元共有位码元共有 种组合种组合 编码后码组有编码后码组有n位码元，位码元，n位码元共有位码元共有 种组合，种组合，矩阵矩阵P可有多种选择可有多种选择 较强的检错或纠错能力较强的检错或纠错能力 实现方

15、法尽可能简单且编码效率高实现方法尽可能简单且编码效率高 在数学上已经证明在数学上已经证明 线性码的最小码距正好等于非零码的最小码重线性码的最小码距正好等于非零码的最小码重 为了估算线性码的差错控制能力应首先求出码组的最为了估算线性码的差错控制能力应首先求出码组的最小码距小码距k22nkn22 20例例10-110-1已知已知(6,3)(6,3)码的生成矩阵为码的生成矩阵为G G，试求：，试求：(1)(1)编码码组编码码组和各码组的码重；和各码组的码重；(2)(2)最小码距最小码距 及其差错控制及其差错控制能力。能力。解解(1)(1)由由3 3位码组成的信息码组矩阵为位码组成的信息码组矩阵为D

16、D：NoImageNoImageNoImage21 由式由式 ，得码组矩阵为：，得码组矩阵为：信息码组、编码码组及码重如下表所示：信息码组、编码码组及码重如下表所示：信息码组信息码组 编码码组编码码组 码重码重W 信息码组信息码组 编码码组编码码组 码重码重W0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 30 0 1 0 0 1 1 1 0 3 1 0 1 1 0 1 0 1 1 40 1 0 0 1 0 0 1 1 3 1 1 0 1 1 0 1 1 0 40 1 1 0 1 1 1 0 1 4 1 1 1 1 1 1 0 0 0 3GDCNoImage22 由

17、前表可知，非零码组的最小码重为：由前表可知，非零码组的最小码重为：所以最小码距为：所以最小码距为：因此，该码有纠因此，该码有纠1 1错，或检错，或检2 2错，或纠一错同时检一错错，或纠一错同时检一错的能力。的能力。NoImageNoImage23译码原理译码原理 由由 可知，可知，或写成或写成 设设 ，则有，则有 。任何线性分组码码组都应该满足上述关系任何线性分组码码组都应该满足上述关系 信息码与监督码间的校验关系完全取决于信息码与监督码间的校验关系完全取决于H H矩阵称为矩阵称为校验矩阵校验矩阵或或监督矩阵，是译码的关键！监督矩阵，是译码的关键！mkkCDDPDDPDIPIDC,mm 0DP

18、CDPC,mm0PDCITm，HPIT 0CH24 则则 B A=E E=en-1 en-2 e0 错误图样错误图样 也可写作也可写作 B=A+Eiiiiiababe当当1025错误图样与校正子之间有确定的关系错误图样与校正子之间有确定的关系TTTTTEHEHAHHEABHS）（26 验证验证3个接收码组是否发生差错？个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？然后再指出发生错码的码字中，哪位有错？100101010110001011H1011101B1101012B1100003B2700011

19、THBSB1无错10122THBSB2错11033THBSB3错2）S2=H 第1列 E=1 0 0 0 0 0 第1位错同理 S3=H 第3列 E=0 0 1 0 0 0 第3位错TEHS 2810.3 10.3 循环码循环码10.3.1 循环码的特点及表达式循环码的特点及表达式 循环码是一种系统分组码，前循环码是一种系统分组码，前k位是信息码，后位是信息码，后r位是监位是监督码。不仅具有督码。不仅具有封闭性封闭性，还具有，还具有循环性循环性，即一许用码组，即一许用码组经循环移位后得到另一个许用码组。经循环移位后得到另一个许用码组。设设 是一个循环码组，则可将之表示为：是一个循环码组，则可将

20、之表示为：上式称为码多项式。上式称为码多项式。nccc,21Cnnncxcxcxc 2211)(29 码组码组C移位移位1次得到的仍是码组，它可写成：次得到的仍是码组，它可写成：不难验证：不难验证：类似地，码组类似地，码组C经经i次移位后，得到的新的码组次移位后，得到的新的码组 是是 除以除以 的余式。的余式。也就是说，在模也就是说，在模 意义下，意义下，若若c(x)是码多是码多项式，则项式，则 都是码多项式。都是码多项式。循环码的编码过程也可用多项式来描述循环码的编码过程也可用多项式来描述。123121 cxcxcxcxcnnn)()()()()()(xcxcxcxcxcxcxnnnn111

21、211 )()(xci)(xcxi)(1nx)(1nx)(xcxi30循环冗余编码循环冗余编码CRCn在数据链路层传送的帧中，广泛使用了循环冗余检验在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。的检错技术。n假设待传送的数据假设待传送的数据 M=1010001101（共（共k bit）。我们在）。我们在M的后面再添加供差错检测用的的后面再添加供差错检测用的 n bit 冗余码冗余码一起发送。一起发送。n冗余码的计算冗余码的计算用二进制的模用二进制的模 2 运算进行运算进行 2n 乘乘 M 的运算，这相当于的运算，这相当于在在 M 后面添加后面添加 n 个个 0。得到的得到

22、的(k+n)bit 的数除以事先选定好的长度为的数除以事先选定好的长度为(n+1)bit 的数的数 P，得出商是，得出商是 Q 而余数是而余数是 R，余数，余数 R 比除数比除数 P 至少要少至少要少1 个比特。个比特。3132v 冗余码的计算举例冗余码的计算举例n 设设 n=5,P=110101，M=1010001101模模 2 运算的结果运算的结果是：是：商商 Q=1101010110，余数，余数R=01110。将余数将余数 R 作为冗余码添加在数据作为冗余码添加在数据 M 的后面发送出去，的后面发送出去，即发送的数据是即发送的数据是101000110101110，或，或 2nM+R。33

23、v循环冗余检验的原理说明循环冗余检验的原理说明 1101010110 Q 商 除数 P 110101 101000110100000 2nM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数34v循环冗余检验的原理说明循环冗余检验的原理说明n 只要得出的余数只要得出的余数 R 不为不为 0，就表示检测到了，就表示检测到了差错差错。n 但这种检测方法并不能确定究竟是哪一个或哪几个比特但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。出现了差错。n 一旦检

24、测出差错，就一旦检测出差错，就丢弃丢弃这个出现差错的帧。这个出现差错的帧。n 只要经过严格的挑选，并使用位数足够多的除数只要经过严格的挑选，并使用位数足够多的除数 P，那，那么出现检测不到的差错的概率就很小很小。么出现检测不到的差错的概率就很小很小。351 1 0 0 1 1发送数据比特序列CRC校验码比特序列1 0 0 1带CRC校验码的发送数据比特序列1 1 0 0 1 1 1 0 0 11 1 0 0 11 1 0 0 11 1 0 0 11 1 0 0 101 0 0 0 0 136引引 言言 卷积码是非分组码。卷积码是非分组码。它充分利用了各组之间的相关性，信息码的码它充分利用了各组

25、之间的相关性，信息码的码长长 k和卷积码的码长和卷积码的码长n 都比较小。都比较小。卷积码的性能在许多实际应用情况下优于分组卷积码的性能在许多实际应用情况下优于分组码，而且设备也较简单。码，而且设备也较简单。通常它更适用于前向纠错，在高质量的通信设通常它更适用于前向纠错，在高质量的通信设备中已得到广泛应用。备中已得到广泛应用。37 卷积码中编码后的卷积码中编码后的n个码元不仅与当前个码元不仅与当前段的段的k个信息有关，而且也与前面（个信息有关，而且也与前面（N-1）段的信息有关，编码过程中相互关联的码段的信息有关，编码过程中相互关联的码元为元为nN个。因此，这个。因此，这N段时间内的码元数段时

26、间内的码元数目目nN通常被称为这种码的约束长度。通常被称为这种码的约束长度。由于与前面由于与前面m段规定时间内的信息位段规定时间内的信息位有关，这里的有关，这里的mN-1通常用（通常用（n，k，m）表示卷积码表示卷积码。38 例如：例如：卷积码的卷积码的n=2，k=1，m=2，因，因此，它的约束长度此，它的约束长度nN=n(m+1)=23=6。m1m2输入输出1b2b3b1C2C39 假如输入的信息为假如输入的信息为D=11010，为了使信，为了使信息息D全部通过移位寄存器，还必须在信息位后全部通过移位寄存器，还必须在信息位后面加面加3个零。表列出了对信息个零。表列出了对信息D进行卷积编码时进行卷积编码时的状态。的状态。描述卷积码的方法：图解表示和解析表示。描述卷积码的方法：图解表示和解析表示。卷积码的译码方法可分为代数译码和概率卷积码的译码方法可分为代数译码和概率译码两大类。译码两大类。3123211bbCbbbC