差错控制编码PPT课件.ppt

1 本章内容目的要求 教学要求 了解差错控制编码的基本方法和基本原理 掌握线性分组码的一般构造原理及汉明码 循环码 卷积码的概念 内容提要 差错控制的基本方式及信道编码的概念 检错码 线性分组码 卷积码 重点 汉明码的生成矩阵 监督矩阵的计算 循环码的生成矩阵 监督矩阵的计算 难点 卷积码的原理 共4学时 12 11 1 2 9 1 9 412 12 3 4 9 5 9 6 2 9 1概述 信源编码和信道编码信源编码目的 提高数字信号的有效性 模拟信号数字化 信道编码目的 降低误码率 提高数字通信的可靠性信道编码方法 在信息序列上附加上一些监督码元 发现和纠正错误 3 差错控制方式 图9 1差错控制方式 4 1 检错重发方式 计算机通信 检错重发 ARQ 的优点主要表现在 1 只需要少量的冗余码 就可以得到极低的输出误码率 2 有一定的自适应能力 某些不足主要表现在 1 需要反向信道 故不能用于单向传输系统 并且实现重发控制比较复杂 2 通信效率低 不适合严格实时传输系统 5 2 前向纠错发送端经信道编码后可以发出具有纠错能力的码字 接收端译码后不仅可以发现错误码 而且可以判断错误码的位置并予以自动纠正 3 混合纠错方式混合纠错方式是前向纠错方式和检错重发方式的结合 6 9 2检错与纠错原理 一 纠错编码的分类 1 按照信道编码的不同功能 可以将它分为检错码和纠错码 2 按照信息码元和监督码元之间的检验关系 可以将它分为线性和非线性码 3 按照信息码元和监督码元之间的约束方式不同 可以将它分为分组码和卷积码 4 按照信息码元在编码后是否保持原来的形式 可以将它分为系统码和非系统码 5 按照纠正错误的类型不同 可以将它分为纠正随机错误码和纠正突发错误码 7 二 检错与纠错编码的基本原理1 分组码表示为 n k n表示码组的长度 k信息的长度 r n k表示监督位长度 几个概念 码长n 码字中码元的数目 码重w 码字中非0数字的数目 码距d 两个等长码字之间对应位不同的数目 有时也称作这两个码字的汉明距离 8 例 3位二进制数构成的码组表示天气 如不要检 纠 错 传输4种不同的信息 用两位码组就够了 这两位码代表所传信息 称为信息位 多增加的称为监督位 9 例 三位二进制码的三种编码方法 三位二进码共有8种可能的组合 000 001 010 011 100 101 110 111 a 若8个码组均用于表示不同的信息 任一位或一位以上的错误都会变成另一码组 所以无法检错和纠错 b 若将8个码组分成许用和禁用两类 许用码组 000 011 101 110禁用码组 111 100 010 001因任何一位误码 都会变成禁用码组 所以可检出一位误码 c 若只用000 111两个码组 其余为禁用码组 则可发现两位及以下的误码 并纠正一位误码 10 最小码距 在码字集合中全体码字之间距离的最小数值 纠错码的抗干扰能力完全取决于许用码字之间的距离 码的最小距离越大 说明码字间的最小差别越大 抗干扰能力就越强 分组码的最小汉明距离为d0 11 2 检错和纠错能力 1 当码字用于检测错误时 如果要检测e个错误 则d0 e 1 2 当码字用于纠正错误时 如果要纠正t个错误 则d0 2t 1 3 若码字用于纠t个错误 同时检e个错误时 e t 则d0 t e 1 12 三 编码效率和基本要求 编码效率R可以用下式表示 基本要求 检错和纠错能力强编码效率高编码规律简单 13 9 3简单分组码 1奇偶监督码可以表示成为 n n 1 如果是奇监督码 在附加上一个监督元以后 码长为n的码字中 1 的个数为奇数个 如果是偶监督码 在附加上一个监督元以后 码长为n的码字中 1 的个数为偶数个 偶监督码有 奇监督码 奇偶效验码码组间最小距离dmin 2 14 奇偶监督码的编码可以用软件实现 也可用硬件电路实现 如果码组B无错 B A 则M 0 如果码组B有单个 或奇数个 错误 则M 1 编码效率 R n 1 n 15 2 水平奇偶监督码 表9 1水平奇偶监督码 m个码组分别以各自码组为单位作奇效验或偶效验 然后以各码组的最高位 次高位 依次发送 当突发的错误数小于m个时 每个码组中的误码个数小于2个 通过奇偶效验可以检出 16 3行列监督码行列监督码又称水平垂直一致监督码或二维奇偶监督码 有时还被称为矩阵码 二维奇偶监督码适于检测突发错码 二维奇偶监督码不仅可用来检错 还可用来纠正一些错码 图9 2 66 50 行列监督码 17 4 群计数码 计算码组中信息位 1 的个数 将计算值作为监督位 可检出除 0 变 1 1 变 0 成对出现之外的所有错误 5 恒比码 恒比码又称等重码 该码的码字中1和0的位数保持恒定的比例 具体情况见表9 3 18 表9 33 2恒比码 目前我国电传通信中普遍采用3 2码 国际上通用的ARQ电报通信系统中 采用3 4码即7中取3码 19 9 4线性分组码 一 基本概念分组码是一组固定长度的码组 可表示为 n k 通常它用于前向纠错 在编码时 k个信息位被编为n位码组长度 而n k个监督位的作用就是实现检错与纠错 这样 一个k比特信息的线性分组码可以映射到一个长度为n码组上 20 二 汉明码 Hamming 具有下列特点的线性分组码称之为汉明码 码长 n 2r 1 信息位 k 2r 1 r 监督位 r n k最小码距dmin 3 纠错能力t 1记为 n k 2r 1 2r 1 r 汉明码的编码效率 若S 0 则无错 若S 1就认为有错 监督方程 21 二 汉明码 Hamming 现以 7 4 分组码为例来说明线性分组码的特点 设其码字为A a6a5a4a3a2a1a0 其中前4位是信息元 后3位是监督元 可用下列线性方程组来描述该分组码 产生监督元 22 表9 5校正子与错码位置的关系 23 表9 6 7 4 码的码字表 汉明码的编码效率 24 设信息码组a6a5a4a3 0101a2 a6 a5 a4 0 1 0 1a1 a6 a5 a3 0 1 1 0a0 a6 a5 a4 0 0 1 1发送 a6a5a4a3a2a1a0 0101101若接收时有一位 a5 位出错 a6a5a4a3a2a1a0 0001101S1 a6 a5 a4 a2 0 0 0 1 1S2 a6 a5 a3 a1 0 0 1 0 1S3 a6 a5 a3 a0 0 0 0 0 0根据效验子S1S2S3 110 可判断误码发生在a5 25 三 监督距阵 监督矩阵H将 7 4 码的三个监督方程式可以重新改写为如下形式 上式可以记作 HAT 0T或AHT 0 其中 26 监督矩阵的性质 1 H由码元间的监督关系唯一确定 2 H的行向量相互独立 当采用系统码结构时 具有形式其中Ir是r r单位阵 3 若发 A 收到 R 则有误码 27 若把监督方程补充为下列方程 四 生成距阵 28 可改写为矩阵形式 2020 1 7 29 30 这里G称为生成矩阵 利用它可以产生整个码组 这时Q PT 如果在Q矩阵的左边在加上一个k k的单位矩阵 就形成了一个新矩阵G 31 设发送码组A an 1 an 2 a1 a0 在传输过程中可能发生误码 接收码组B bn 1 bn 2 b1 b0 则收发码组之差定义为错误图样E 也称为误差矢量 即 其中E en 1 en 2 e1 e0 且 9 23 五 伴随式 校正子 S和检错 32 表9 7 7 4 码S与E的对应关系 则接收端利用接收到的码组B计算校正子 S BHT A E HT AHT EHT EHT因此 校正子仅与E有关 即错误图样与校正子之间有确定的关系 33 六 线性分组码的性质 线性分组码的主要性质如下 具有封闭性 也就是说 任意两许用码之和仍为一许用码 有零码 有负元满足结合律和交换律码组间的最小码距等于非零码的最小码重 34 9 5循环码 循环码是线性分组码的一个重要子集 是目前研究得最成熟的一类码 它有许多特殊的代数性质 特点 循环码中任一许用码组经过循环移位后 所得到的码组仍然是许用码组 描述 许用循环码A an 1an 2 a1a0 可以将它的码多项式表示为 一 循环特性 35 表9 8 7 3 循环码 如果一种码的所有码多项式都是多项式g x 的倍式 则称g x 为该码的生成多项式 在 n k 循环码中任意码多项式A x 都是最低次码多项式的倍式 如表9 8的 7 3 循环码中 36 二 生成多项式及生成矩阵 其它码多项式都是g x 的倍式 即 37 循环码的生成矩阵常用多项式的形式来表示 38 例如 7 3 循环码 n 7 k 3 r 4 其生成多项式及生成矩阵分别为 39 进行矩阵行运算 r1 r3mod2得到 40 可以证明生成多项式g x 具有以下特性 1 g x 是一个常数项为1的次多项式 2 g x 是的一个因式 3 该循环码中其它码多项式都是g x 的倍式 41 为了便于对循环码编译码 通常还定义监督多项式 令 其中g x 是常数项为1的r次多项式 是生成多项式 h x 是常数项为1的k次多项式 称为监督多项式 同理 可得监督矩阵H 9 5 3监督多项式及监督矩阵 42 是h x 的逆多项式 例如 7 3 循环码 g x x4 x3 x2 1 则 其中 43 9 5 4编码方法 在编码时 首先要根据给定的 n k 值选定生成多项式g x 即应在xn 1的因式中选一个r n k次多项式作为g x 设编码前的信息多项式m x 为 循环码的码多项式可表示为 图9 2 7 3 循环码的编码电路 P321 44 9 5 5译码方法和电路 图9 4单个错误出现在接收码组首位的 7 3 循环码译码电路 循环码的译码可以分三步进行 1 由接收到的码多项式B x 计算校正子 伴随式 多项式S x 2 由校正子S x 确定错误图样E x 3 将错误图样E x 与B x 相加 纠正错误 45 9 6 1基本概念 9 6卷积码 卷积码中编码后的n个码元不仅与当前段的k个信息有关 而且也与前面 N 1 段的信息有关 编码过程中相互关联的码元为nN个 因此 这N段时间内的码元数目nN通常被称为这种码的约束长度 由于与前面m段规定时间内的信息位有关 这里的m N 1通常用 n k m 表示卷积码 46 图9 5卷积码 2 1 2 编码器 例如 卷积码的n 2 k 1 m 2 因此 它的约束长度nN n m 1 2 3 6 47 假如输入的信息为D 11010 为了使信息D全部通过移位寄存器 还必须在信息位后面加3个零 表列出了对信息D进行卷积编码时的状态 描述卷积码的方法 图解表示和解析表示 卷积码的译码方法可分为代数译码和概率译码两大类 48 起始状态 各级移位寄存器清零 即S1S2S3为000 S1等于当前输入数据 而移位寄存器状态S2S3存储以前的数据 输出码字C由下式确定 表9 6 2 1 2 编码器的工作过程 49 1 树图 图10 9 2 1 2 码的树图 9 6 2卷积码的图解表示 50 2 状态图 图9 10 2 1 2 码的状态图 51 3 网格图 图9 11 2 1 2 码的格图 52 1 维特比译码 图9 12维特比译码网格图 9 6 3卷积码的译码 53 2 序列译码 当m很大时 可以采用序列译码法 其过程如下 译码先从码树的起始节点开始 把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较 沿着差异最小的分支走向第二个节点 在第二个节点上 译码器仍以同样原理到达下一个节点 以此类推 最后得到一条路径 若接收码组有错 则自某节点开始 译码器就一直在不正确的路径中行进 译码也一直错误 因此 译码器有一个门限值 当接收码元与译码器所走的路径上的码元之间的差异总数超过门限值时 译码器判定有错 并且返回试走另一分支 经数次返回找出一条正确的路径 最后译码输出 54 作业 55 9 7网格编码调制 TCM 网络编码调制 TrellisCodedModulation