2017通信原理第11章 差错控制编码

《2017通信原理第11章 差错控制编码》由会员分享，可在线阅读，更多相关《2017通信原理第11章 差错控制编码（124页珍藏版）》请在金锄头文库上搜索。

1、本章内容 第11章差错控制编码 基本概念 差控方式编码原理码距码率性能简单实用码 奇偶监督恒比码正反码线性分组码 汉明码监督矩阵H 生成矩阵G循环码 生成多项式编译方法BCH码RS码卷积码 编译原理代数表述几何表述 11 1 概述 开销 这就好像我们运送一批玻璃杯一样 为了保证运送途中不出现打烂玻璃杯的情况 我们通常都用一些泡沫或海棉等物将玻璃杯包装起来 这种包装使玻璃杯所占的容积变大 原来一部车能装5000个玻璃杯的 包装后就只能装4000个了 显然包装的代价使运送玻璃杯的有效个数减少了 为保证运送途中不出现打碎灯泡的情况 有效性 可靠性 通信中的情况 开销 这就好像我们运送一批玻璃杯一样

2、为了保证运送途中不出现打烂玻璃杯的情况 我们通常都用一些泡沫或海棉等物将玻璃杯包装起来 这种包装使玻璃杯所占的容积变大 原来一部车能装5000个玻璃杯的 包装后就只能装4000个了 显然包装的代价使运送玻璃杯的有效个数减少了 针对乘性干扰 针对加性干扰 合理选择调制 解调方法 增大发射功率 采用均衡等措施 差错控制编码 信道类型 根据错码的不同分布规律分为 差错控制方式 差错控制方式 ARQ FEC 自动请求重发 缺点 工作在半双工状态 传输效率较低 3种自动要求重发 ARQ 系统 1 停止等待ARQ系统 系统需要双工信道 2 拉后ARQ系统 第5组 传输速率比第 1 种高 3 选择重发ARQ

3、系统 ARQ的主要缺点 码率较高 用较少的监督码元就能使误码率降到很低 检错的计算复杂度较低 检错用的编码方法和加性干扰的统计特性基本无关 能适应不同特性的信道 需双向信道来重发 不适用单向信道和一点到多点的通信系统 重发使得ARQ系统的传输效率降低 信道干扰严重时 将发生因反复重发而造成事实上的通信中断 不适用于要求实时通信的场合 例如电话通信 ARQ的主要优点 与前向纠错 FEC 方法相比 ARQ系统的原理方框图 11 2 纠错编码的基本原理 规则 使码组中 1 的个数为偶数 情形1 没有冗余 不能发现错误 情形2 加入冗余 可以发现错误 冗余 另外4个码组 许用码组 禁用码组 许用码组

4、禁用码组 也不能纠正错误 奇数个错码 这时 能够发现2个以下错码 或者纠正1位错码 综上所述 信息码元位数 编码后码字位数 不同的编码方法 检错或纠错能力也不同 分组码和系统码 编码后的每组长度为n k r 就是分组码 前面的例子 信息位与监督位关系 分组码的符号 分组码的结构 n k 码长 n 码组 码字 中的码元个数 码重 W 码组中 1 的数目 011011 的距离为3 码重和码距 码重为3 对于3位的编码组 可用3维空间来说明 4个许用码组之间 各顶点之间沿立方体各边行走的几何距离 码距 2 码距的几何意义 对于 n k 分组码 有以下结论 最小码距d0和检纠错能力的关系 检 个错码

5、要求 纠 个错码 要求 纠t个错码 同时检e个错码 要求 证明 11 3 纠错编码的性能 系统带宽和信噪比的矛盾 右图所示的某种编码性能 可见 不增大发送功率 就能降低误码率约一个半数量级 A点 B点 2PSK调制 可见 能节省功率2dB 称为编码增益 D点 2PSK调制 C点 因此 纠错码主要应用于功率受限而带宽不太受限的信道中 付出的代价是带宽增大 设编码前系统工作在图中C点 提高速率后Pe由C点升到E点 传输速率RB和信噪比Eb n0的关系 若希望提高RB 则必使Eb n0下降 误码率Pe增大 这时付出的代价仍是带宽增大 但采用纠错编码后 Pe仍可降到D点 11 4 简单的实用编码 11

6、 4 1奇偶监督码 偶监督码 奇监督码 适用 检测随机出现的零星差错 编码规则 只一位监督码元 不知错码位置 很高 只有一位监督位 码率 编出的码字应为 若收到10011 检测结果为 根据偶数监督规则 有错 若收到00011 检测结果为 奇偶监督码不能检出偶数个错 解 认为无错 11011 11 4 2二维奇偶监督码 编码规则 方阵码 检测方法 计算接收码组中 1 的数目 可知是否有错 11 4 3恒比码 适用 用于电报传输系统或其他键盘设备产生的字母和符号 编码规则 等重码 个许用码组 可分别用来代表26个英文字母及其他符号 11 4 4正反码 编码规则 设码长n 10 即信息位k 5 监督

7、位r 5 监督位数与信息位数相同 能纠错 编码效率低 50 译码方法 00000 校验码组和错码的关系 无错 信息位中有奇数个 1 校验码组 00000 发送码组为1100111001 纠检能力 n k 线性分组码 11 5 线性码 按照一组线性方程构成的代数码 即每个码字的监督码元是信息码元的线性组合 基本概念 代数码 建立在代数学基础上的编码 正反码 效率50 太低 纠正1位错 最少增加多少监督位 构造出以最小多余度代价换取最大抗干扰能力的好码 纠错编码任务 汉明码 能纠正1位错 编码效率较高 监督关系式 若S 0 认为无错 偶监督时 若S 1 认为有错 若要构造具有纠错能力的 n k 码

8、 则需增加督码元的数目 当 成立时 构造的线性分组码称为汉明码 校正子 构造原理 只有一位监督元 检错 汉明码的 能纠1位错码的高效线性分组码 7 4 汉明码 可以其他假设 由表可见 仅当一位错码的位置在a2 a4 a5或a6时 校正子S1为1 否则S1为0 同理 A 移项运算解出监督位 A 接收端译码 检错纠错过程 以上构造的线性分组码 称为汉明码 最小码距 当n很大r很小时 Rc 1 编码效率 汉明码特点 d0 3 纠1或检2 r是不小于3的任意正整数 答 最小码距 故能纠1或检2 d0 3 线性分组码的一般原理 将前面 7 4 汉明码的监督方程 改写为 表示成如下矩阵形式 H 监督矩阵

9、简记为 H A a6a5a4a3a2a1a0 0 000 监督矩阵 或 转置 转置 T r n PIr r k阶矩阵 r r阶方阵 典型监督矩阵 H矩阵的性质 H的行数等于监督位的数目r H的每行中 1 的位置表示相应码元之间存在的监督关系 H的各行应该是线性无关的 否则得不到r个线性无关的监督关系式 若一矩阵能写成典型阵形式 PIr 则其各行一定是线性无关的 将上面汉明码例子中的监督位公式 改写成矩阵形式 G 生成矩阵 或者写成 P阵 式中 Q为一个k r阶矩阵 它为P的转置 即 Q PT P阵 Q阵 将Q的左边加上1个k k阶单位方阵 就构成矩阵 生成矩阵 或者 因此 若找到了码的G 则编

10、码的方法就完全确定了 具有 IkQ 形式的称为典型生成矩阵 由典型G得到的码称为系统码 称为 典型生成矩阵 信息位不变 监督位在后 由它可以产生整个码组 即有 k n G矩阵的性质 G矩阵的各行是线性无关的 由式 可看出 任一码组A都是G的各行的线性组合 G共有k行 若它们线性无关 则可以组合出2k种不同的码组A 它恰是有k位信息位的全部码组 G和H的关系 校正子与错误图样 设发送码组为一个n列的行矩阵A 接收码组的行矩阵B 错码矩阵 错误图样 模2 A B E 在接收端 若能求出错误图样E就能恢复出发送码组A 即 任一发送码组A都应满足式 对于接收码组B 可通过计算 来进行检测 将B A E

11、代入上式 可得 0 因此 可根据S是否为0判断接收码组是否出错 由以上分析可知 n k 线性分组码译码的三个步骤 2 由S找到错误图样E 3 由公式A B E得到译码器译出的码组 n k 线性分组码译码的三个步骤 封闭性 A1和A2 A1 A2 证明 若A1和A2是两个码组 则有 A1 HT 0和A2 HT 0 将两式相加 有 A1 HT A2 HT A1 A2 HT 0 最小距离 证毕 线性分组码的性质 根据性质 线性分组码计算最小码距 只需找最小码重 无需两两码组比较 完备性 汉明码中 伴随式的非零形式与错误图样一一对应 且伴随式的图样除全0外为个 正好等于码长 最充分利用了监督位所提供的

12、信息 循环码 西安电子科技大学通信工程学院 课件制作 曹丽娜 它除了具有线性分组码的一般性质外 还具有循环性 11 6 表中的第2码组向右移一位即得到第5码组 7 3 循环码 11 6 1循环码原理 表中的第6码组向右移一位即得到第3码组 码字 1100101 的多项式可表示为 码多项式 多项式的系数就是码组中的各码元 x仅是码元位置标记 n 7时 码字 码组 的多项式表示 1 码多项式的按模运算 一般说来 若一个整数m可以表示为 Q为整数 m p 模n 则在模n运算下 有 码多项式的按模运算 或 则 码多项式系数之间的加法和乘法 按模2运算 解运算过程 即有 则有 余式 因为 A x 是A

13、x 代表的码组向左循环移位i次的结果 循环码的码多项式 则余式A x 也是该编码中的一个许用码组 循环码组 码长n 7 i 3时 有 0101110 1100101 左移i位 3 由上述分析可见 2 循环码的生成矩阵G 生成矩阵G可由k个线性无关的码组构成 引思 如何寻找这k个线性无关的码组 因此 用这 个线性无关的码组可构成该循环码的生成矩阵G 即 生成多项式 g x 是xn 1的因式 g x 的性质 g x 必有一常数项a0 1 g x 的次数为n k次 且唯一 否则 循环右移1位出现k连0 线性分组码不可能信息位全0 监督位不全为0 若2个 由封闭性得两者和为码组 连0个数至少多出2位

14、a0 an k线性分组码不可能 后面说明 r n k 7 3 4 解 码组中唯一一个4次码多项式代表的 或 此循环码多项式A x n k k 1 n 1 任一循环码多项式A x 都是g x 的倍式 可以写成 而生成多项式g x 本身也是一个码组 即有 A x g x A x h x g x 码组A x 是一个 n k 次多项式 故xkA x 是一个n次多项式 xkA x 在模 xn 1 运算下也是一个码组 故可写成 左端分子和分母都是n次多项式 故Q x 1 将和代入上式 化简后得到 A x g x A x h x g x 求 7 3 循环码的生成多项式g x 将 x7 1 进行因式分解 解

15、n k 即有 或 11 6 2循环码的编解码方法 1 循环码的编码 设信息码 an 1an 2 an k 的多项式为 m x an 1xk 1 an 2xk 2 an k 其最高次数为k 1 则循环码的多项式为 A x A x m x g x 即 1 xn k乘m x 得xn km x 2 xn km x 除以g x 将信元左移 n k 位 附上 n k 个0 预留给监督码元 得到余式r x 作为监督码元 即得循环码的码多项式 系统循环码的编码步骤 3 作A x xn km x r x 通常是非系统码 n k k 1 n 1 k 1 r n 1 最高次数 2 循环码的解码 目的 检错和纠错 若

16、能除尽 则无错 若除不尽而有余项 则表示在传输中发生错误 11 6 3截短循环码 例 构造一个能够纠正1位错码的 13 9 码 可由 15 11 循环码的码组中选出前两信息位均为 0 的码组 构成一个新的码组集合 在发送时不发送这两位 0 于是发送码组成为 13 9 截短循环码 截短目的 在设计纠错编码方案时 若找不到合适的码长n及信息位k时 可以把循环码的码长截短以得到符合要求的编码 截短方法 设给定一个 n k 循环码 它共有2k种码组 现使其前i 0 i k 个信息位全为 0 于是它变成仅有2k i种码组 然后从中删去这i位全 0 的信息位 最终得到一个 n i k i 的线性码 截短循环码 截短循环码性能 循环码截短前后至少具有相同的纠错能力 并且编解码方法仍和截短前的方法一样 11 6 4BCH码 解决了生成多项式与纠错能力的关系问题 可以在给定纠错能力要求的条件下寻找到码的生成多项式 BCH码的重要性 BCH码的分类 多个 汉明码是能够纠正单个随机错误的码 可以证明 具有循环性质的汉明码就是能纠正单个随机错误的本原BCH码 BCH码的性能 码长n与监督位 纠错个数t之间的关