通讯原理差错编码控制.ppt

第十一章差错控制编码 主要内容纠错编码的原理线性分组码循环码 重点检错 纠错的概念分组码的结构汉明码循环码 11 1概述 11 2纠错编码的原理 11 3常用的简单编码 11 4线性分组码 11 5循环码 作业 11 6卷积码 习题11 1 5 7 14 作业 11 1概述 检错重发法 11 1 2差错控制的方法 11 1 1编码的目的 提高信号抗加性干扰的能力 干扰种类 加性克服方法 差错控制编码 加性干扰的特征 突发信道 出现错码成串集中 混合信道 前两者中和 乘性克服方法 均衡器 随机信道 出现错码是随机的 相互间统计独立 反馈校验法 前向纠错方法 定义 误码率标准 CCITT建议的误码率标准 检错重发法 在接收端检测出错码时 通知发端重发信号 直到接收正确为止 此方法只能判断是否有错码 不能判断具体的错码位置 所以 只能检错不能纠错 且需要双向通道 前向纠错方法 在收端检测出错码时 可以确定错码的位置 并予纠正 此方法只需要单向通道 实时性好 但设备复杂 反馈校验法 接收端将收到的信号原封不动的发回发端 由发端将其与原发信号相比较 如果有错则重发 这种方法需双向通道 效率低 但设备简单 在信息码序列中加监督码元 也称纠错码 自动请求重发系统 ARQ 11 1 3差错控制编码的原理 不同的编码方法 有不同的检错或纠错能力 监督码元越多 检 纠错能力越强 由于信息码元是随机序列 收端无法预知信号状态 因而无法判别接收码是否有错 增加了监督码元之后 监督码和信息码之间存在一种逻辑关系 因此 收端可以利用这种逻辑关系发现或纠正存在的错码 自动请求重发系统 ARQ 工作过程 3 重发控制器收到重发命令时 控制输入缓冲储存器重发一次当前码组 否则发送后一码组 2 收端解码器检测出错码时由指令发生器产生重发命令传给发端 同时发出删除命令 删除输出缓冲器内容 1 收发正常时 重发控制与指令发生器不工作 优点 1 监督码少 占总码的 20 2 对各种信道有一定的适应能力 3 成本及复杂性低 缺点 1 需要双向通道2 干扰大时系统可能处于重发循环中 效率降低3 实时性差 11 2纠错编码的基本原理 11 2 1分组码的概念 11 2 2分组码参数 例 天气预报 11 2 1分组码的概念 特征 分组码中的监督码元仅监督本码组中的信息码元 分组码定义 将信息码分组 为每组信息码后附加若干监督码元形成的码集合 分组码检错 纠错能力的体现 结论 虽然接收码组有错 但接收端无法识别 讨论 建立分组码A 错1位 错2位 结论 只能检测出1位错码 但不能纠正 禁用码组 非信息码组 许用码组 有效信息码组 结论 能纠正1位错码 或检测出2位错码 建立分组码B 错1位 错2位 k 码组中信息码元的数目 n 码组的总位数 又称为码组长度 r n k 码组中监督码元的数目 结构 符号 n k 码长n k r k个信息位 r个监督位 码组重量 码组中 1 的数目 11 2 2分组码参数 码距d 两个码组对应位数值不同的码元个数称为码组间的汉明距离 码距与码集合检 纠错能力的关系 例 码组 a2a1a0 110 b2b1b0 010 码距的几何概念 码距是1 最小码距d0 码集合中任意两两码组间距离的最小值 010 110 000 100 101 001 011 111 选许用码组 000011110101 令n 3 共有8个码组 沿立方体各边行走 4个码组的距离均为2个边长 d0 2 检测e个错码 要求最小码距 纠正t个错码 要求最小码距 纠正t个错码 同时检测e个错码 要求最小码距 码距与码集合检 纠错能力的关系 A B 例 A 00000 B 11111 d0 5 结论 e 4或t 2或e 3 t 1 d 1 d 2 d 3 11 3常用的简单编码 11 3 1奇偶监督码 11 3 2正反码 奇数监督码 偶数监督码 监督码元1位 使码组中 1 的个数为奇 监督码元1位 使码组中 1 的个数为偶 只能检测奇数个错码 二维奇偶监督码 矩阵码 能检测部分偶数个错码 生成规则 许用码组写成一行 包括信息码和1位监督码 设共有m行 第m 1行为按列增加的监督码 构成监督码行 例 11 3 1奇偶监督码 一维奇偶监督码 例 监督方程 监督方程 例 一维偶数监督码 错1位 检验满足 检验不满足 只能检错 不能纠错 2 当同时出错 则按行按列均不能检测出有错 能检测部分偶数个错码适用于突发信道 若仅一行有奇数个错码时 可通过列确定错码位置并纠正 1 设和发生错码 按行无法检测出错 而按列可检测 a2a1a0000011101110000 例 二维偶数监督码 通式 结论 方阵码除对构成矩形四角的错码无法检测外 其余均能检测 特征 具有纠正1位错码 检测2位和大部分2位以上错码的能力 定义 信息码位数与监督码位数相同 编码规则 1 当信息位中有奇数个 1 时 监督位是信息位的重复 2 当信息位中有偶数个 1 时 监督位是信息位的反码 10001 例 若信息码为11001 11 3 2正反码 则正反码为1100111001 1000101110 1 将接收码组中信息码和监督码对应按位模2加 得合成码组 2 根据接收码组中信息码含 1 的奇偶情况 由合成码组生成校验码组 3 根据校验码组的值依表判断错码情况 并予检 纠错 译码规则 1 为奇校验 合成 1 为偶校验 例 例 发1100111001 1 收无错 信息码中含奇数个 1 2 收有错 为1000111001 合成码组 11001 11001 00000 译码判决 校验码组 合成码组 00000 判断接收无错码 合成码组 10001 11001 01000 信息码中含偶数个 1 查表知信息码第二位错 特征 编码效率低 11 4线性分组码 11 4 1汉明码的编码原理 11 4 2一般线性分组码的编码原理 11 4 3线性码分组码的数学描述 11 4 1汉明码的编码原理 定义 能纠正一位错码 且编码效率较高的线性分组码 问题 在正反码中 为纠正一位错码 其监督码位数与信息码位数一样多 能否减少监督码位数但纠错能力不变 如何实现纠错 思路 分组码 n k 只可能出现n个一位错码事件 若某种逻辑组合具有n个状态 就能利用这种逻辑组合描述一位错码事件并予纠正 例 分析偶数监督码 寻找逻辑组合 汉明码 监督方程 则接收时解码是在计算 只能表示出错不能描述错码位置 一位监督码对应一个监督方程 结论 若增加监督码元 建立多个监督方程 多个校正子就能形成逻辑组合描述错码位置 汉明码 确定监督码元位数r 确定监督关系表 建立监督方程 建立编码方程 分组码 n k 共需n 1个状态描述无错及n个有错事件 为提高编码效率 r取最小值 例 已知 7 4 码 r 3 共有3个监督方程 构成3个校正子S1S2S3 例 例 已知 7 4 汉明码 求码组集合 解 监督方程 编码方程 k 4 信息码组有16个 r 3 例 汉明码的监督方程为 矩阵表达式 11 4 2一般线性分组码的编码原理 矩阵方程 记为 H 监督矩阵 A 码组向量 思路 确定编码矩阵方程 构造生成矩阵 又 根据监督方程确定了编码方程 两边同取转置 构造生成矩阵 称G为典型生成矩阵 含单位阵 编码矩阵方程 特点 信息位不变 监督位附加于其后 定义系统码 由典型生成矩阵得出的码组A 生成矩阵 G中每行均为一个码组 且线性无关 译码运算 当 S为校正子 说明S与E间有确定的线性关系 若E的数目有限 能与S一一对应 则说明S能描述错码的位置 具有纠错能力 11 4 3线性码分组码的数学描述 令发码组为A 收码组为B 错码图样E B A 收发码组的关系 令B E A 例 发码组A 1100010 收码组B 1000010 译码运算 例 7 4 汉明码 a5错 含义 错码图样E 0100000 只有一位错码 定义 线性码中任意两个码组之和仍为这种码中的一个码组 证 设A1 A2为线性码中两个许用码组 两式相加 是许用码组 推广 1 两个码组间的距离必是另一码组的重量 2 除0码组之外 码组的最小重量是码集合的最小距离 线性分组码具有封闭性 11 5循环码 11 5 1码多项式 11 5 2循环码的特性 11 5 3循环码的编码方法 码多项式的按模运算 11 5 1码多项式 码多项式 定义 以码组中各码元为系数的多项式 T x an 1xn 1 an 2xn 2 a1x a0 设多项式F x 除数为N x 模N x 运算 注 多项式按模N x 运算过程中 其系数按模2加运算 系数为二进制 只能取0或1 x仅为码元位置的标记 例 R x 余式 例 1100101 T x x6 x5 x2 1 例 解 记为 余式 定理 若T x 对应一个码长为n的许用码组 证 令 T x 的系数是T x 中系数向左循环移位i次的结果 11 5 2循环码的特性 码集合中任意一个码组 左移或右移一位得到的新码组必是该码集合中另一码组 循环码的定义 循环码的码多项式 则xiT x 按模xn 1运算后余式T x 仍为许用码组 例 例 7 3 循环码 码组为 1100101 求码多项式T x 验证x3T x 按模x7 1运算后余式仍是一个许用码组 解 T x an 1xn 1 an 2xn 2 a1x a0 T x x6 x5 x2 1 x3T x x9 x8 x5 x3 余式T x 对应码组为 0101110 是T x 码组左移三位 循环码的生成矩阵G 11 5 3循环码的编码方法 思路 确定编码矩阵方程 构造生成矩阵 码生成多项式g x 循环码的监督矩阵H 码生成多项式g x 的求解 例 G是G x 的系数矩阵 循环码的检 纠错能力 与n k的值相关 循环码的编码方法 循环码生成矩阵G的数学描述 已知 7 4 汉明码 G中每行均为一个码组 且线性无关是线性分组码的共性 循环码是线性分组码成员之一 其G除满足上述特性外 每行之间必须满足循环性 循环码每个码组对应一个码多项式 以最简方式寻找k个线性无关的码多项式就能建立G x 码生成多项式g x 定义 g x 是幂次为 n k 的码多项式 唯一性 分析循环码 循环码 n k 的形成方法是在信息码后加监督码且保持移位循环的特征 除全零码组外 权值最小的信息码组为00 001 且监督位a0不可能为零 否则循环数次后码组前k位均为零 而监督位不为零的情况 这不符合监督码的定义 结论 信息码组00 001对应的码多项式必为 n k 次幂 且常数项不等于零 信息码组00 001唯一 码多项式唯一 且幂次最低 记为g x 与g x 线性无关的k 1个码多项式为xg x xk 1g x 可组成生成矩阵G x 码生成多项式g x 的求解 定理 g x 是xn 1的一个 n k 次因子 证 g x 是幂次最低的码多项式 任意一个码多项式T x 都是g x 倍数 令T x h x g x 余式为码组 xkg x xn 1 T x xn 1 xkg x T x 模2加 xkg x h x g x xk h x g x 得证 例 已知 7 3 循环码 求码组集合 监督矩阵H 解 n 7 x7 1 x 1 x6 x5 x4 x3 x2 x 1 x 1 x3 x2 1 x3 x 1 g1 x x 1 x3 x2 1 x4 x2 x 1 g2 x x 1 x3 x 1 x4 x3 x2 1 取g x g1 x x4 x2 x 1 A a6a5a4a3a2a1a0 监督方程 d0 4t 1 非系统码 循环码的编码方法 思路 已知信息码组多项式m x 建立T x 编码步骤为 1 生成xn km x 2 生成 xn km x g x 求余式r x 3 生成循环码多项式T x T x xn km x r x 例 m x 101建立 7 3 循环码 解 xn km x 1010000 g x x4 x2 x 1 r x x3 x2 T x x6 x4 x3 x2 码组为1011100系统码 非系统码 b c d a 输入 输出 开关S S同时上下 7 3 循环码编码 11 6卷积码 11 6 1卷积码的图形描述 11 6 2卷积码的解析描述 k 信息码元n 码组长度N 约束长度 符号 n k N 定义 线性非分组码 特点 相邻数个码组的编码相互约束 本码组编码不仅与自身的k位信息码有关 还与前面 N 1 个码组的信息段有关 11 6 1卷积码的图形描述 输入序列m1m2 mj 输出序列 y1jy2jy3jy1jy2jy3j y1j y2j y3j 输入输出序列速度匹配关系 移位寄存器 树状图 网格图 状态图 3 1 3 卷积码的编码器 输出序列的变化规律 树状图 0 001 011 010 100 1 110 1 000 000 000 111 111 001 011 010 100 101 110 000 111 001 110 0 1 0 111 0 1 a a b a b c 101 d b a c d a b c d a m1m2 00 b m1m2 01 c m1m2 10 d m1m2 11 寄存器初态 m3 m3 m3 m3 00 11 01 10 11 00 10 01 m1m200 网格图 000 b c d a 010 110 111 101 000 111 001 特点 相同状态的节点合并 100 011 3 1 3 卷积码 初态 上支路实线下支路虚线 从第N个节点开始图形重复出现 2N 1种 状态图 特点 状态稳定后的转移