差错控制

第 7章 差错控制 差错控制的基本概念及原理 错和纠错的基本概念 单的差错控制编码 环码 明码 性分组码 本章节教学说明 本章重点学习差错控制基本原理、简单差错控制编码、汉明码、循环码 本章主要介绍检错和纠错的方法和原理 本章主要详细介绍了常用的差错控制方法的基本原理 本章节内容概述 差错控制基本思路 随机差错与突发差错 检错和纠错的基本原理 码距与检错和纠错的关系 简单的差错控制编码 汉明码 循环码 本章节学习重点、难点 检错和纠错的基本原理 简单的差错控制编码 汉明码 循环码 本章节学习目标 熟悉检错和纠错的基本思路和原理 熟悉掌握简单差错编码、汉明码、循环码的检错和纠错机制 理解汉明码、循环码的编码原理 本章节学习能力要素及基础要求 课前预习相关内容 能够运用差错控制的编码技术对数据进行检错和纠错 本章节学习方法建议 预习复习结合 课堂学习与课外学习结合 自学与探讨结合 课后作业与章节个人总结结合 寻求教师答疑与学习反馈结合 差错控制是提高数字通信可靠性的重要方法，是数字通信中必须具有的功能。 差错控制的基本概念及原理 差错控制的基本概念 造成误码的原因很多，但主要原因可以归结为两点：一是信道不理想造成的符号间干扰；二是噪声对信号的干扰。 差错即是误码。 差错控制的核心是抗干扰编码，或差错纠正编码，简称纠错编码。 差错控制的基本思路是：发送端在被传输的信息序列上附加一些码元（称为监督码元），这些附加码元与信息（指数据）码元之间存在某种确定的约束关系；接收端根据既定的约束规则检验信息码元与监督码元之间的这种关系是否被破坏，如传输过程中发生差错，则信息码元与监督码元之间的这一关系受到破坏，从而使接收端可以发现传输中的错误，乃至纠正错误。 随机差错与突发差错 数字信号在信道中传输，会受到各种不同的噪声干扰。噪声大体分为两类：随机噪声和脉冲噪声（突发噪声）。 随机差错又称独立差错，是指那些独立地、稀疏地和互不相关地发生的差错。 突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。 实际信道是复杂的，所出现的错误也不是单一的，而是随机错误和突发错误并存，只不过有的信道以某种错误为主而已，这两类错误形式并存的信道称为组合信道或复合信道。 差错控制方式 在数字通信系统中，差错控制方式一般可以分为 4种类型：检错重发（ 前向纠错（ 混合纠错检错（ 信息反馈（ 它们的系统构成如图7 图 7差错控制方式的基本类型 1检错重发 图 7检错重发差错控制系统工作原理 2前向纠错 在前向纠错系统中，发送端经编码发出能够纠正错误的码，接收端收到这些码组后，通过译码能自动发现并纠正传输中的错误。 3混合纠错 混合纠错方式是前向纠错方式和检错重发方式的结合。 4信息反馈 信息反馈又称回程校验。 它是收端把收到的数据序列全部由反向信道送回发端，发端比较发送的数据序列与送回的数据序列，从而发现是否有错误，对有错误的数据序列的原数据再次传送，直到发端没有发现错误为止。 上述几种差错控制方式应根据实际情况合理选用。 检错和纠错的基本概念 检错和纠错的基本原理 差错控制之所以具有检错和纠错能力，是因为在信息码之外附加了监督码，用来监督信息码在传输过程中是否存在差错，其对用户来说是多余的。 监督码的引入，降低了信道的传输效率。 码距与检错和纠错的关系 （ 1）在信道编码中，定义码组中非零码元的数目为码组的重量，简称码重。 （ 2）把两个码组中对应码位上具有不同二进制码元的位数定义为两码组的距离，简称码距。 （ 3）在一种编码中，任意两个许用码组间距离的最小值，即码组集合中任意两个元素之间的最小距离，称为这一编码的汉明（ 离，用 表示。 码距的几何表示法 （ 1）为检测 m e+1 图 7码距与检错和纠错能力的关系 （ 2）为纠正 求 m t +1 （ 3）为纠正 时检测 m e+t+1 (et) 编码效率 编码效率是指一个码组中信息位所占的比重，用 设码组长为 n，信息位长度为 k，监督位长度为 r，编码效率定义为 。 纠错编码的分类 按码组的功能分，有检错码和纠错码。 按监督码与信息码之间的关系分，有线性码和非线性码。 按对信息码元处理方法的不同分，有分组码和卷积码。 图 7分组码的结构 按照信息码元在编码后是否保持原来的形式不变分，可划分为系统码和非系统码。 按纠正差错的类型分，可分为纠正随机错误的码和纠正突发错误的码。 按照每个码元取值来分，可分为二进制码与多进制码。 简单的差错控制编码 奇偶监督码 奇偶监督码是一种最简单的检错码，又称奇偶校验码，在计算机数据传输中得到了广泛的应用。 一般情况下奇偶监督码的编码规则是：首先将要传输的信息分成组，然后将各位二元信息及附加监督位用模 2和相加，选择正确的监督位，保证模 2和的结果为 0（偶校验）或 1（奇校验）。 这种监督关系可以用公式表示。 设码组长度为 n，表示为（ 其中前 n1位（ 信息，第 ）为校验位，则偶校验时有 0 1 2 1 0na a a a 0 1 2 1na a a a 0 1 2 1 1na a a a 奇校验时有 0 1 1 1na a a 监督码元 监督码元 奇校验方式就是使分组数据和监督位加起来整个码组中的“ 1”的个数为奇数个；偶校验方式就是使分组数据和监督位加起来整个码组中的“ 1”的个数为偶数个。 水平奇偶监督码 信 息 码 元 监 督 码 元 1110011000 1 1101001101 0 1000011101 1 0001000010 0 1100111011 1 按列发按行分组排列 表 7偶监督码 信 息 码 元 监 督 码 元 1 0 10011000 1 1 0 01001101 0 1 1 00011101 1 0 1 01000010 0 1 0 00111011 1 按列发按行分组排列 表 7偶监督码 水平垂直奇偶监督码 信 息 码 元 监 督 码 元 1110011000 1 1101001101 0 1000011101 1 0001000010 0 1100111011 1 监督码元 0110110001 1 表 7平垂直奇偶监督码 汉明码 汉明码的诞生 线性码中的信息位和监督位是由一些线性代数方程联系着的，或者说，线性码是按一组线性方程构成的，故又称线性分组码。 汉明码的原理 如果希望用 要求 k+r+1 21r 2r 由此可见： r=3，则有 3个校正子 2、 们对应有 8种组合。 其中 000无错。 剩下 7种错误，刚好可以对应指示n = 4 + 3 = 7个位置的错误情况。 汉明码编码方法 6 5 4 2a a a a 6 5 3 1a a a a 3 6 4 3 0S a a a a S 1 S 2 S 3 错 码 位 置 2 S 3 错 码 位 置 001 a 0 101 a 4 010 a 1 110 a 5 100 a 2 111 a 6 011 a 3 000 错码 注： a 2 、 a 1 、 a 0 错码位可以随意和校正子 S 1 S 2 S 3中的 001 、010 、 100 对应 S 1 S 2 S 3 S 1 S 2 S 3错码位置 错码位置a 0a 1a 3a 4a 5a 6a 2错码0010101000111 0 11 1 01 1 10 0 0注 ： a 3 、 a 4 、 a 5 、 a 6 错码位也可以随意和校正子S 1 S 2 S 3 对应的情况交换注 ： a 2 、 a 1 、 a 0 错码位可以随 意 和 校 正 子 S 1 S 2 S 3 中的 001 、 010 、 1 0 0 对应 7 - 4 校正子与错码位置注： a 3 、 a 4 、 a 5 、 a 6 错码位也可以随意 和 校 正 子S 1 S 2 S 3 对应的情况交换 S 1 S 2 S 3 S 1 S 2 S 3错码位置 错码位置a 0a 1a 3a 4a 5a 6a 2错码0010101000111 0 11 1 01 1 10 0 0注 ： a 3 、 a 4 、 a 5 、 a 6 错码位也可以随意和校正子S 1 S 2 S 3 对应的情况交换注 ： a 2 、 a 1 、 a 0 错码位可以随 意 和 校 正 子 S 1 S 2 S 3 中的 001 、 010 、 1 0 0 对应 7 - 4 校正子与错码位置表 7正子与错码位置 信 息 位 监 督 位 信 息 位 监 督 位 a3 a0 a3 000 000 1000 111 0001 011 1001 100 0010 101 1010 010 0011 110 1011 001 0100 110 1100 001 0101 101 1101 010 0110 011 1110 100 0111 000 1111 111 表 77,4)汉明码的许用码组 汉明码编码效率 通常将码长 n = 的线性分组码称为汉明码，即 ( , )码。 其编码效率为 21r 21r 21r r121rk n r 线性分组码 监督矩阵 汉明码属于线性分组码，我们可以将汉明码中的 6 5 4 26 5 3 16 4 3 0000a a a aa a a aa a a a 改写成下面的方程组 6 5 4 3 2 1 06 5 4 3 2 1 06 5 4 3 2 1 01 1 1 0 1 0 0 01 1 0 1 0 1 0 01 0 1 1 0 0 1 0a a a a a a aa a a a a a aa a a a a a a 65432101 1 1 0 1 0 0 01 1 0 1 0 1 0 01 0 1 1 0 0 1 0 上式可以简记为 H 或 A 0 其中， 111010011010101011001H 6 5 4 3 2 1 0a a a a a a aA 000O =1 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 1H = P为 r r 具有 P形式的 监督矩阵 1 码 的个监督方程之后，抽取其系数构成的。 2它的行数为监督码的位数， 种形式的 码的信息码组均在前 码的标准形式。 ( , )nk n k r( , ), )3 码的任何一个许用码字进行相乘的结果必等于 0，若不属于许用码字，或有传输差错，且差错位数在 码纠错能力内，则运算结果将为非 0值，此时，可以纠错或检错重发。 4 列。 ( , ), )生成矩阵 62514031 1 1 01 1 0 11 0 1 1 对其两侧做矩阵转置，有 2 1 0 6 5 4 3 6 5 4 31111 1 01 0 10 1 1a a a a a a a a a a aQ 式中 k 矩阵 Q = P T。 1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1rG I Q 6 5 4 3 2 1 0 6 5 4 3a a a a a a a a a a a 6 5 4 3a a a a 称 它可以产生整个码组。 形式的生成矩阵称为典型生成矩阵。 生成矩阵 1 送端）中直接生成信息码和监督码组合的 码组。 ( , )2由 码字时，由于其构成为 形式，与 相对应，这种结构特征生成的 码中的前 后面 位全是监督元，如 码的全部码字，从高位数共 位，均为源编码信息码组。 rG I Q , )k r(7, 4)4k 校正子和检错 R = . R A = E （模 2） E = . R = A + E R 0 R S S = (A + E) A E S = E 校正子 1校正子 有关，而与传输的码字 校正子可以根据错误样图进行检错和纠错。 2 (n,k)码的不同码字，都有同样多种全部错误样图，即 2r1个。 是位数等于 线性分组码主要性质 （ 1）线性分组码具有封闭性，任意两个许用码组按位之和仍是一个许用码组。 （ 2）线性分组最小距离 等于非零码组最小重量 W。 循环码 循环码的循环特性 循环码是一种线性分组码，且为系统码，即前 码 组 编 号 信 息 位 监 督 位 码 组 编 号 信 息 位 监 督 位 000 0000 5 100 1011 2 001 0111 6 101 1100 3 010 1110 7 110 0101 4 011 1001 8 111 0010 表 7 7,3）循环码码组 循环码的多项式表示 1码多项式 121 2 1 0()x C x C x C x C 2模 ()( ) ( , ) Q p N 余 数商 为 整 数 ( 模 )若 则记为 ( ) ( ) 所有余数为 的一个同余类。 ( ) ( )()( ) ( )M x R x N x 式中， Q(x)为整式，余式 R(x)的幂t) 。 5常用的简单差错控制编码有奇偶监督码、水平奇偶监督码和二维奇偶监督码等。 6分组码是信息位和监督位用线性方程联系在一起的一类码。 在线性