现代通信原理(11).ppt

1 现代通信原理 第十一章差错控制编码和线性分组码 2 单元概述 实际信道传输数字信号时 不可避免地会产生误码 差错控制编码的目的是用信道编码的方法检测和纠正误码 降低误比特率 在检错重发控制编码方式中 信道编码只是为了检测误码 而在前向纠错方式中 信道编码用于纠正误码 检错和纠错能力是用信息冗余度即由附加附加在信息中的监督码元来实现的 信息码元与监督码元之间建立某种检验关系 根据建立检验关系的方法不同 可以分为分组码和卷积码 线性分组码中信息码元和监督码元是用现行方程联系起来的 卷积码中它们是以卷积的方式联系起来 码距是确定纠错检错能力的重要度量 3 单元学习提纲 1 前向纠错 检错重发差错控制方法 2 检错和纠错的基本原理 3 分组码 卷积码 线性码 系统码的定义 4 码距的定义 它与检错 纠错能力的关系 5 线性分组码中监督方程 监督矩阵 生成方程 生成矩阵的含义 4 6 汉明码的特点及构造 7 循环码的特点及编码方法 8 纠正一位误码的循环码的一种译码方法 9 交织码纠正突发错误的原理 10 卷积码的编码方法 生成多项式与编码器的构造 5 11 卷积码的树状图 网格图的表示 12 卷积码维持比译码的基本原理和译码过程 13 纠错编码误比特率性能 编码增益的含义 14 纠错编码在卫星信道 移动通信等实际通信系统中的应用 6 第十一章差错控制编码和线性分组码 1 概述 数字通信系统是以电子方式传输信息的 接收方收到的数据应当就是发送方发送的数据 但这些电子信息都易受到干扰 太阳黑子活动 电源抖动或施工者用锄头对电缆的碰撞都会对传输产生不可预料的影响 为保证传输数据的完整性 通常采用一定的措施 如利用均衡器纠正信道参数 加大发送功率 扩展信道频带宽度等办法来减少加性干扰 采用上述方法仍难以满足要求时 必须采用差错控制措施 即用差错控制编码来检错和纠错 7 对于数据传输 人们主要关心的是信息码元的差错概率 即误码率Pe 在中等传输速率 1200 2400波特 下 采用一般的调制方法 对于干线有线载波信道 Pe约为10 4 10 6的数量级 对于无线短波通信 Pe只有10 2 10 3的数量级 对于传输速率更高的系统 误码性能还要差 在数据通信中 如计算机与计算机之间的数据传送 Pe要求低于10 9 这就需要加入纠错编码 8 从差错控制角度看 信道可以分为三类 1 随机信道 误码的出现是随机的 误码之间是统计独立的 如由正态分布白噪声引起的误码 称为随机误码 就具有这种性质 2 突发信道 误码是成串集中出现的 即在短促的时间区间存在大量误码 在较长的时间区间无误码出现 产生突发误码的主要原因是脉冲干扰 信道中的衰落现象也是产生突发误码的主要原因 3 混合信道 既存在随机误码又存在突发误码的信道称为混合信道 9 11 1差错控制编码的基本概念 1 检错重发方式 ARQ 2 前向纠错方式 FEC 3 混合纠错检错方式 HEC 4 反馈校验方式 IRQ 11 1 1差错控制方式 10 11 1 检错重发方式 ARQ 采用检错重发方式 发端经编码后发出能够发现错误的码 接收端收到后经检验如果发现传输中有错误 则通过反向信道把这一判断结果反馈给发送端 然后 发送端把信息重发一次 直到接收端确认为止 采用这种差错控制方法需要具备双向通道 一般在计算机数据通信中应用 检错重发方式分为三种类型 如图所示 图中ACK是确认信号 NAK是否认信号 12 1 停发等待重发 发对或发错 发送端均要等待接收端的回应 特点是系统简单 时延长 2 返回重发 无ACK信号 当发送端收到NAK信号后 重发错误码组以后的所有码组 特点是系统较为复杂 时延减小 3 选择重发 无ACK信号 当发送端收到NAK信号后 重发错误码组 特点是系统复杂 时延最小 13 14 2 前向纠错方式 FEC 发送端经编码发出能纠正错误的码 接收端收到这些码组后 通过译码能发现并纠正误码 前向纠错方式不需要反馈通道 特别适合只能提供单向信道的场合 特点是时延小 实时性好 但系统复杂 但随着编码理论和微电子技术的发展 编译码设备成本下降 加之有单向通信和控制电路简单的优点 在实际应用中日益增多 15 3 混合纠错检错方式 HEC 混合纠错检错方式是前向纠错方式和检错重发方式的结合 发送端发出的码不但有一定的纠错能力 对于超出纠错能力的错误要具有检错能力 这种方式在实时性和复杂性方面是前向纠错和检错重发方式的折衷 因而在近年来 在数据通信系统中采用较多 16 4 反馈校验方式 IRQ 反馈校验方式 IRQ 又称回程校验 收端把收到的数据序列全部由反向信道送回发送端 发送端比较发送数据与回送数据 从而发现是否有错误 并把认为错误的数据重新发送 直到发送端没有发现错误为止 优点 不需要纠错 检错的编译器 设备简单 缺点 需要反向信道 实时性差 发送端需要一定容量的存储器 IRQ方式仅适用于传输速率较低 数据差错率较低的控制简单的系统中 17 11 1 2差错控制编码的分类 1 按照差错控制编码的不同功能 可以分为检错码 仅能检测误码 纠错码 仅可以纠正误码 和纠删码 兼有纠错和检错功能 2 按照信息码元和附加的监督码元之间的检验关系可以分为线性码 信息码元和监督码元满足一组线性方程式 和非线性码 18 3 按照信息码元和监督码元之间的约束关系可以分为分组码和卷积码 分组码中 码元序列每n位分成一组 其中k个是信息码元 r n k个是监督码元 监督码元仅与本组的信息码元有关 卷积码中 编码后序列也编为分组 但监督码元不仅与本组信息码元有关 还与前面码组的信息码元有关 4 按照纠正错误的类型不同 可以分为纠正随机错误的码和纠正突发错误的码 19 5 按照构成差错控制编码的数学方法来分类 可以分为代数码 几何码和算术码 其中代数码建立在近代数学基础上 是目前发展最为完善的编码 其中线性码是是代数码的一个最重要的分支 6 按照每个码元的取值不同 可以分为二进制码和多进制码 20 11 1 4检错和纠错的基本原理 香农著名的信道编码定理指出 对于一个给定的有扰信道 若信道容量为C 只要发送端以低于C的速率R发送信息 则一定存在一种编码方法 使编码错误概率P随着码长n的增加 按指数下降到任意小的值 即可以通过增加冗余编码来降低误码率 纠错编码的的基本思想就是在被传送的信息码元中附加一些监督码元 在两者之间建立某种校验关系 当这种校验关系因传输错误而受到破坏时 可以被发现并予以纠正 这种检错和纠错能力是用信息量的冗余度来换取的 21 以一组二进制码为例 三位二进制码元有8个码组 如果用来表示天气的8种情况000 晴 001 雷 010 雹 011 阴 100 风 101 云 110 雨 111 雪 如果有一个误码 接收端以为是另一条信息 这种编码没有检错和纠错能力 如果这8种码组只用来传送4条信息 即只准使用其中的4种码组000 晴 011 阴 101 云 110 雨 如果有一位误码 不会在接收端产生误判 会检出错误 22 4个状态只用2位二进制码就可以表达 所增加的第3位 就称为监督码元 增加1位监督码元 只能检出1位误码 对于上例 如果有2位误码 将发生误判 如将000 晴 误传成101 云 要抗多位误码 就要增加监督码元的个数 即增加冗余度 23 码距与检错和纠错能力 定义 1 码重 码组中非零码元的个数 如001 码重为1 011 码重为2 2 码距 两个码组中对应码位上具有的不同二进制码元的个数定义为两个码组的距离 汉明距 简称码距 如111和000 码距为3 111和100码距为2 111和110码距为1 3 最小码距 对于许用的n个码组 各码组之间最小的码距称为最小码距 24 25 对于如图所示的3位二进制码 如果8个码组可用 000 001 010 011 100 101 110 111 各点之间最小相差1个边长 最小码距为1 如果只有4个码组可用 选 010 111 100 001 或 110 011 000 101 各点之间相差2个边长 最小码距为2 如果只有2个码组可用 分别选 111 000 100 011 110 001 101 010 各点之间相差3个边长 最小码距为3 26 码距与检错和纠错能力 如上所述 一种编码的最小码距直接关系到这种码的检错和纠错能力 因此最小码距是信道编码的一个重要参数 在一般情况下 对于分组码有如下结论 1 在一个码组内检测个e误码 要求最小码距dmin e 1 2 在一个码组内纠正个t误码 要求最小码距dmin 2t 1 3 在一个码组内纠正t个误码 同时检测e个 e t 误码 当误码数大于t时就不能纠错 只能检测e个误码 要求最小码距dmin t e 1 27 11 1 5几种实用的简单检错码 1 奇偶监督码这是一种最简单的检错码 又称奇偶校验码 在计算机数据通信中得到广泛应用 七单位国际5层字母表 美国信息交换码ASCII字母表中都用7比特码组表示128种字符 如字符A的编码为1000001 为了检查字符传输过程中是否有误 常在7比特码组后码组后加1位作为奇偶校验位 使得8位码组 一个字节 中的 1 的个数为奇数或偶数 如果为奇数 称为奇校验码 偶数时 称为偶校验码 编码规则是 首先将要传送的信息分成组 然后将各位二进制信息加监督位用模2和 选择正确的监督位 使模2和为 0 偶校验 为 1 奇校验 奇偶校验码只能发现奇数个误码 对检测突发错误不适用 28 2 水平奇偶监督码将经过奇偶监督编码的码元按行排成方阵 但传送时则按列进行的顺序传送 接收端仍将码元排成发送时的方形阵式 然后再进行奇偶校验 如 发送时按顺序传送111011100110000 10101 以此来抗突发性错误 29 3 水平垂直奇偶校验码在水平奇偶监督码的基础上 对方阵中的每一列也进行奇偶校验 发送时按列序顺次传送 接收端恢复成方阵后进行奇偶校验 如 传送顺序为111010110011100001 101011 它能发现某一行或某一列上所有奇数个误码 30 4 群计数码监督码组中 1 的个数构成所谓群计数码 例如一个码组的信息码元为1010111 其中有5个 1 用二进制表示为101 将它作为监督码元附加在信息码元之后 传输码组为1010111101 为了提高检突发错误的能力 也可以仿照水平奇偶方法 将信息排成方阵 按列发送 31 5 恒比码在恒比码中 每个码组中 1 或 0 的个数相同 因而称为等重码 检测时 只要计算每个码组中 1 的数目是否对 就能判断有无错误 我国电传机传输汉字电码的通信中 广泛采用五单位数字保护电码 每个码组长度为5 共有25 32种组合 其中 1 的个数为3的编码正好10个 分别代表阿拉伯数字 1 10 1 01011 2 11001 3 10110 4 11010 5 00111 6 10101 7 11100 8 01110 9 10011 10 01101 在国际ARQ电报通信系统中 它采用3个 1 4个 0 的恒比码 7中取3共有35个许用码组 分别代表26个字母及其它符号 32 11 2 5汉明 Hamming 码 汉明码是1950年由美国贝尔实验室汉明提出来的 是第一个设计用来纠正错误的线性分组码 汉明码被广泛用于数字通信和数据存储系统中 对于奇偶校验的偶校验 我们用下式作为作为监督方程 在接收端译码时 若S 0 就认为无错 若S 1 就认为有错 这里称S为校正子 校验子 又称伴随式 33 汉明 Hamming 码 在上例中 由于只有一位监督码元 一个监督方程 所以只能检错 无法纠错 汉明码 n k 是一种可用于纠单个随机错误的循环编码 一般汉明码的参数如下 码长n 2r 1信息位k 2r 1 r监督位r n k r是不小于3的任意正整数 因为要纠t位错误 dmin大于2t 1 最小汉明距离d 3下表是纠错一位的一般汉明码结构 34 纠错一位的一般汉明码结构 35 7 4 汉明码举例 对于 7 4 汉明码 码元为a6 a5 a4 a3 a2 a1 a0假设有三个相应的监督方程 在接收端根据校正子的取值组合能纠正某一位的错误 36 7 4 汉明码举例 如果传送a6 a5 a4 a3共4位数据 要求能自动纠正单个误码 须增加3位监督码a2 a1 a0 监督码的计算方程见下式 7位数据按a6 a5 a1 a0的顺序一起发送 在接收端按校正子 伴随式 的组合来判断在哪一位出现了错误 并实时纠正 将相应位取非 37 7 4 汉明码的编码器和译码器 1 38 7 4 汉明码的编码器 2 1 S1接通 S2掷向下端 输出数据位a6 a5 a4 a3的同时 反馈移位寄存器串行接收数据 延时等待推出监督位 2 4位数据发完后 断开S1 将S2掷向上端 开始送监督位 3 3位监督位送完后 开关又掷回原位 4 设监督位为n 反馈移位寄存器由n位的本原多项式设计 39 15 11 汉明码举例 对于 15 11 汉明码 码为a14 a13 a12 a3 a2 a1 a0假设有四个相应的监督方程 在接收端根据校正子的取值组合能纠正某一位的错误 40 15 11 汉明码举例 同理 如果传送a14 a13 a5 a4共11位数据 要求能自动纠正单个误码 须增加4位监督码a3 a2 a1 a0 监督码的计算方程见下式 15位数据按a14 a13 a1 a0的顺序一起发送 在接收端按校正子 伴随式 的组合来判断在哪一位出现了错误 并实时纠正 将相应位取非 41 11 2线性分组码 线性分组码定义 分组码中信息码元和监督码元是用线性方程联系起来的一种差错控制码 汉明码是线性分组码的一种 能纠一位误码 线性分组码有三个重要的运算式 监督矩阵 生成矩阵和校正子 42 11 2 2 1 监督矩阵 从上节汉明码的例子可以看出 线性分组码的监督方程可以用矩阵形式来表达 无误码时 下式成立 式中的系数矩阵称为监督矩阵 用H表示 如果用虚线分为两部分 左边为P矩阵 是一个r k阶矩阵 右边为Ir矩阵 是一个r r阶单位方阵 43 1 监督矩阵 设发送序列为A 则监督方程也可以写为 44 11 2 3 2 生成矩阵 已知监督方程和信号码元时可以按下式算出监督码元 式中用的是P矩阵 或者用下式来计算 式中的矩阵是P的转置矩阵 称为Q矩阵 45 2 生成矩阵 在Q的左边加一个k k阶单位方阵 就生成一个新的矩阵G 这个新矩阵G称为生成矩阵 因为可由它产生整个码组A 46 11 2 4 校正子 设发送码组A为一n列的行矩阵 矩阵中n个元素就是码组中的n个码元 发送码组在传输过程中出现了误码 接收端收到了B矩阵 也是一n列的行矩阵 设收发码组之差E B A 模2 称为错误图样 校正子S可以根据接收序列和H矩阵来计算 可见校正子只与错误图样有关 与发送序列无关 是一个信道参数 47 校正子 如果不出现误码 校正子S 0 如果有误码 通过计算校正子S来指示误码的位置和纠正误码 设发送的序列A 0001011 错误图样E 0001000 接收到的序列B 0000011 校正子可以由下式计算得到 011 指示a3有错误 48 11 3循环码 循环码是线性分组码中的一类 是以现代代数理论作为基础建立起来的 循环码的编码和译码设备相对简单循环码的检错和纠错能力较强 49 循环码的循环特性 循环码与其它线性分组码一样 设总长度为n 前k位是信息位 后r位是监督位 r n k 循环码中任意一许用码组经过循环移位后 将最右端的码元移至左端 所得到的码组仍是许用码组 如表所示 50 循环码的循环特性 一般来说 若 an 1 an 2 a0 是循环码的码组 则 an 2 an 3 a0 an 1 an 3 an 4 an 1 an 2 a0 an 1 a2 a1 也是该循环码的码组 51 循环码的循环特性 码组 an 1 an 2 a1 a0 也可以用一个多项式来表示A X an 1xn 1 an 2xn 2 a1x a0对于一个 7 3 循环码 任一码组可以表示为A X a6x6 a5x5 a4x4 a3x3 a2x2 a1x a0式中a6 a5 a1 a0是编码 x只是码元位置的标记 52 循环码的循环特性 对于一个循环码组 可以用下列码多项式来分别表示 A X an 1xn 1 an 2xn 2 a1x a0A X an 2xn 1 an 3xn 2 a1x2 a0 x an 1Ai X an i 1xn 1 an i 2xn 2 a0 xi an 1xi 1 an i我们来看下式 53 循环码的循环特性 式中采用模2加减 所以加法与减法是等效的 若被除式是xA X 许用码组 除式是xn 1 已知多项式 余式是A X 循环移一位的许用码组 若被除式是xiA X 许用码组 除式是xn 1 已知多项式 余式是Ai X 循环移i位的许用码组 54 循环码的循环特性 例如某循环码1100101 则A X X6 X5 X2 1 XA X X7 X6 X3 X 余数构成的码是1001011 正好是循环一位的结果 55 循环码的循环特性 例如某循环码1100101 则A X X6 X5 X2 X1 X2A X X8 X7 X4 X2 余数构成的码是0010111 正好是循环两位的结果 56 由此得到一个重要结论 若A x 是n阶循环码的一个许用码组 包括信息码元和监督码元 通过除以xn 1再取余数的方法可以找到其它的许用码组 57 首先要找到第一个许用码组A x 在循环码中 有一个许用码组比较特殊 就是全0码 即信息位全0时 监督位也取全0 通过这一点可以找出另一个许用码组 结论 除全0码组外 另一个n位循环码的许用码组 n k 若前k 1位全为零 则第k位 信息末位 和第n位 监督末位 必定为1 假若第k位不为1 将造成信息位全为零 而监督位不为0的情况 若第n位不为1 右移一位后 将使信息位全为0 而监督位不为0 58 循环码的生成多项式g x 这一个前k 1位为0 第k位和第n位为1的许用码组可以用一个码多项式g x 来标识 称为循环码的生成多项式 1 g x 是一个能除尽xn 1的n k阶多项式 2 要寻找生成多项式 必须对xn 1进行因式分解 这需要计算机来完成 3 在一些参考书上有因式分解的表格可以选用 59 循环码的监督多项式h x 设多项式h x 满足下式 h x g x xn 1就称h x 为监督多项式 60 X7 1因式分解构成的循环码生成多项式 61 由生成多项式得到生成矩阵 根据生成多项式可以求出生成矩阵G x 62 根据生成矩阵可以由信息码组求出传输码组 63 X7 1因式分解后构成的循环码特例 因式分解x7 1 x 1 x3 x 1 x3 x2 1 1 若取x 1为生成多项式 这是一种 7 6 码 有6个信息位 1个纠错位 这是一种偶校验码 2 若取 x3 x2 1 为生成多项式 这是由本原多项式构成的 7 4 的汉明码 能纠1位错码 3 若取 x3 x 1 x3 x2 1 为生成多项式 只有1位信息位 构成的是全1码或全0码 64 例题一 对于一 7 3 循环码 其生成多项式g x x3 x2 1 x 1 x4 x2 x 1生成矩阵G X 便可写成 65 例题一 这不是典型的生成矩阵形式 若将第一列加上第三列 则如下生成矩阵形式 66 例题一 假设信息码是111 生成序列为A X 假设信息码是110 生成序列为A X 和循环的结果一致 67 例题一 其它信息码的编码结果见下表 68 循环码编码器 循环码的编码电路 用硬件实现 可以采用除法电路 对于生成多项式为g x x4 x2 x 1的编码器 其硬件电路如图所示 69 循环码编码器 工作原理 举 7 3 循环码为例 1 首先将xn 1 x7 1 多项式展开 取最高幂为xn k x4 的一个组合项为g x 2 对应g x 有4级移位寄存器D1 D2 D3 D4 g x 多项式系数是1还是0表示该位上有无反馈线 3 当信息位输入时 控制器使Q1和Q3为正 Q2为0 开通门1和门3 此时电路除输出信息码之外 还送到除法电路进行运算 4 当信息位传完之后 控制电路将Q2为正 Q1 Q3为0 开通门2 使寄存器中的除法余项 监督码元 依此输出 70 举输入信息码110为例 输出码为1100101 71 循环码的解码