通信原理-第10章-差错控制编码-40课件.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 检检 错错 重重 发发 的的 三三 种种 方方 式式 停发等候重发停发等候重发返回重发返回重发选择重发选择重发61010.1.2.1.2 差错控制编码分类差错控制编码分类在

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

5、码组的码元有约束关系71.奇偶监督码奇偶监督码 编码方法编码方法 把信息码元先分组，在每组最后加一位监督码元，使把信息码元先分组，在每组最后加一位监督码元，使该码组中该码组中1的数目为奇数或偶数的数目为奇数或偶数 奇数时称为奇校验码奇数时称为奇校验码 偶数时称为偶校验码偶数时称为偶校验码 偶校验码偶校验码 许用码组为许用码组为000，011，101，110 禁用码组为禁用码组为001，010，100，111 奇校验码奇校验码 禁用码组为禁用码组为000，011，101，110 许用码组为许用码组为001，010，100，1118一般情况下：一般情况下：设码组长为设码组长为n，且为：，且为：则偶

6、校验时有：则偶校验时有：奇校验时有：奇校验时有：译码方法译码方法(与编码方法相对应与编码方法相对应)不满足校验关系，传输一定错误！不满足校验关系，传输一定错误！奇偶校验只能发现奇数个奇偶校验只能发现奇数个(单个单个)错误，不能检测出错误，不能检测出偶数个错误。偶数个错误。编码方法简单且实用性强，适用于检测随机零星错码编码方法简单且实用性强，适用于检测随机零星错码 满足校验关系，传输一定准确吗？满足校验关系，传输一定准确吗？0321aaaannn0 110naaa1 110naaa92.二维奇偶监督码二维奇偶监督码 将奇偶校验码的若干码组排列成矩阵将奇偶校验码的若干码组排列成矩阵 每一码组写成一

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

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

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

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

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

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

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

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

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

16、码组成的信息码组矩阵为D D：011100110010101001Gmind111011101001110010100000D20 由式由式 ，得码组矩阵为：，得码组矩阵为：信息码组、编码码组及码重如下表所示：信息码组、编码码组及码重如下表所示：信息码组信息码组 编码码组编码码组 码重码重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

17、 0 1 4 1 1 1 1 1 1 0 0 0 3GDC000 011 110 101 101 110 011 000 111011101001110010100000011100110010101001 111011101001110010100000C21 由前表可知，非零码组的最小码重为：由前表可知，非零码组的最小码重为：所以最小码距为：所以最小码距为：因此，该码有纠因此，该码有纠1 1错，或检错，或检2 2错，或纠一错同时检一错错，或纠一错同时检一错的能力。的能力。3minW3mind22译码原理译码原理 由由 可知，可知，或写成或写成 设设 ，则有，则有 。任何线性分组码码组都应该

18、满足上述关系任何线性分组码码组都应该满足上述关系 信息码与监督码间的校验关系完全取决于信息码与监督码间的校验关系完全取决于H H矩阵称为矩阵称为校验矩阵校验矩阵或或监督矩阵，是译码的关键！监督矩阵，是译码的关键！mkkCDDPDDPDIPIDC,mm 0DPCDPC,mm0PDCITm，HPIT 0CH231010.3.3 循环码循环码10.3.1 循环码的特点及表达式循环码的特点及表达式 循环码是一种系统分组码，前循环码是一种系统分组码，前k位是信息码，后位是信息码，后r位是监位是监督码。不仅具有督码。不仅具有封闭性封闭性，还具有，还具有循环性循环性，即一许用码组，即一许用码组经循环移位后得

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

20、来描述。123121 cxcxcxcxcnnn)()()()()()(xcxcxcxcxcxcxnnnn111211 )()(xci)(xcxi)(1nx)(1nx)(xcxi25循环冗余编码循环冗余编码CRCn在数据链路层传送的帧中，广泛使用了循环冗余检验在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。的检错技术。n假设待传送的数据假设待传送的数据 M=1010001101（共（共k bit）。我们在）。我们在M的后面再添加供差错检测用的的后面再添加供差错检测用的 n bit 冗余码冗余码一起发送。一起发送。n冗余码的计算冗余码的计算用二进制的模用二进制的模 2 运算进行

21、运算进行 2n 乘乘 M 的运算，这相当于的运算，这相当于在在 M 后面添加后面添加 n 个个 0。得到的得到的(k+n)bit 的数除以事先选定好的长度为的数除以事先选定好的长度为(n+1)bit 的数的数 P，得出商是，得出商是 Q 而余数是而余数是 R，余数，余数 R 比除数比除数 P 至少要少至少要少1 个比特。个比特。2627v 冗余码的计算举例冗余码的计算举例n 设设 n=5,P=110101，M=1010001101模模 2 运算的结果运算的结果是：是：商商 Q=1101010110，余数，余数R=01110。将余数将余数 R 作为冗余码添加在数据作为冗余码添加在数据 M 的后面发送出去，的后面发送出去，即发送的数据是即发送的数据是101000110101110，或，或 2nM+R。281 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 1