差错控制编码.ppt

第7章差错控制编码 7 1差错控制编码的基本原理7 2简单控制编码7 3线性分组码和汉明码7 4循环码7 5卷积码7 6turbo码 传输ASCII码010001110100110001011010ILY010001110100011001011010IHY 7 1差错控制编码的基本原理 加性噪声 码间串扰都会产生误码 为提高系统抗干扰性能 可以加大发射功率 降低接收设备本身的噪声 合理选择调制 解调方法等 差错控制编码即是减少加性干扰造成错误判决的措施之一 差错控制编码 是在信息序列上附加上一些监督码元 利用这些冗余的码元 使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号 采用差错控制编码 即使仅能纠正 或检测 这种码组中1 2个错误 也可以使误码率下降几个数量级 一般说来 编码中增加的监督码元越多 检 纠 错的能力就越强 差错控制译码则利用这些规律性来鉴别传输过程是否发生错误 或进而纠正错误 1 差错控制的工作方式 反馈校验法 接收端将收到的信码原封不动地转发回发送端 发送端将其与原发送信码比较 如果发现错误 则重发 混合纠错 HEC 当收到少量的错码时 就在接收端直接纠正 当错码太多超过其纠错能力时 则采用差错重发方式 前向纠错法 接收端不仅能在收到的信码中发现有错码 还能够解定错码的位置 纠正错码 检错重发 ARQ 接收端在收到的信码中检测出 发现 错码时 即设法通知发送端重发 直到正确收到为止 既存在随机错误又存在突发错误的信道称为混合信道 突发错误 错码成串出现 在短促的时间区间内错误密集成群 而在这些短促的时间区间之间却又存在较长的无错码区间 以突发错误为的信道称为突发信道 脉冲干扰 信道中的衰落现象 随机错误 错误的位置是随机 且统计独立高斯白噪声 以随机错误为主的信道称为随机信道 2 差错控制编码的类别 按照编码的用途不同 差错控制编码可分为检错码 纠错码 纠删码 按照监督码元和信息码元的不同关系 差错控制编码可分为线性码和非线性码 按照对信息码元的处理方式不同 差错控制编码可分为分组码和卷积码 按照码组中的信息码元在编码前后的位置是否发生变化 差错控制编码分为系统码 非系统码 按照编码针对的不同干扰类型 差错控制编码可分为纠 检 随机 独立 错误码 纠 检 突发错误码和既能纠 检 随机错误 有纠 检 突发错误码 纠错编码分类示意图 3 差错控制编码的基本方法 最小码距 在码字集合中全体码字之间距离的最小数值用d0表示 4码间距离d及检错纠错能力 码长 码字中码元的数目 码重 码字中非0数字的数目 码距 两个等长码字之间对应位不同的数目 有时也称作这两个码字的汉明距离 用d表示 码组11010 码长N 5 码重w 3 码组11010 和10100 码距d 3 10100 11010 01110两个码组的模二相加得到的新码组的重量就是这两个码组之间的距离 码组集合000011101110的最小码距d0为 2 码距 纠错码的抗干扰能力完全取决于许用码字之间的距离 码的最小距离越大 抗干扰能力就越强 1 检测错误时 如果要检测e个错误 则dmin e 1 2 纠正错误时 如果要纠正t个错误 则dmin 2t 1 3 纠t个错误 同时检e个错误时 e t 则dmin t e 1 5 编码效率 是指码字的信息码元个数k与总的码长n的比值 即 7 2简单控制编码 7 7 2奇偶监督码偶监督码规则 在信息位后加上一位监督位 要求整个码字中 1 的个数为偶数 例如10110010 10100110不能确定 如果是奇监督 则要求整个码字中 1 的个数为奇数 例如10110011 10100010有错 奇偶监督码的编码可以用软件实现 也可用硬件电路实现 如果码组B无错 B A 则M 0 如果码组B有单个 或奇数个 错误 则M 1 二维奇偶监督码 它是将若干个信息码字按每个码字一行排列成矩阵形式 然后在每一行和每一列的码元后面附加一位奇 偶 监督码元 信息码元监督码元信息码元监督码元10110001101100011101001011010010001001110110011101101100011011001001100110011001监督码元1011000110110001 7 2 2二维奇偶监督码 7 3线性分组码和汉明码 7 3 1线性分组码的定义及性质 线性码有一个重要性质 就是它具有封闭性 即线性码中的任意两个码组之各仍为该码中的一个码组 所谓线性分组码 是指信息位和监督位满足一组线性方程 编码规则用一组线性方程来描述的分组码 分组码是一组固定长度的码组 可表示为 n k k个信息位被编为n位码组长度 而r n k个监督位的作用就是实现检错与纠错 信息位 n 监督位 r n k a6a5a4a3a2a1a0 1011 001 编码效率 k n 7 4 线性分组码 a0 a6 a4 a3 监督关系 a2 a6 a5 a4 a1 a6 a5 a3 线性分组码的生成矩阵和监督矩阵 输入 1011 a6a5a4a3a2a1a0 0 0 1 1011001 1111001 a2 a6 a5 a4 1 a1 a6 a5 a3 1 a0 a6 a4 a3 0 a5错 a0 a6 a4 a3 a2 a6 a5 a4 a1 a6 a5 a3 线性分组码的生成矩阵和监督矩阵 简记作H AT 0T或A HT 0 写成矩阵形式 接收端H AT 0T说明有错 线性分组码的生成矩阵和监督矩阵 a6a5a4a3a2a1a0 a6a5a4a3 可以根据生成矩阵写出编码 1011 001 G IkQ Q PT 汉明码是一种能够纠正单个错误的线性分组码 它有以下特点 1 最小码距dmin 3 可纠正一位错误 2 码长n与监督元个数r之间满足关系式 6 7 3汉明码 如果信息长度为5位 要求纠正1位错 需要增加的校验位是 对于 n k 线性分组码 由于它的监督码元数为r n k 只发生一位错误时 监督码元的应能指出所有n个码元位置上出错及全对共 n 1 中情况 2n k n 1 汉明码校验和与错误码元位置对应关系为 S1 a6 a5 a4 a2S2 a5 a4 a3 a1S3 a6 a4 a3 a0 a0 a1 假设某汉明码的监督关系为 a2 a3 已知某汉明码监督矩阵 试求 1 n k 2 验证1111001和0101011是否有错 若有错 请纠正之 3 若信息码元为1001 写出其相应的汉明码字 1 n 7 k 4 a3错误 正确的序列为1110001 S BHT A E HT EHT S1 a6 a4 a3 a2S2 a5 a4 a3 a1S3 a6 a5 a4 a0 S 当0101011 a2错误 正确的序列为0100011 3 1111001 2 信息码元1001 由监督矩阵H 对应的生成矩阵为 G IkQ IkPT A M G 1001 G 1001011 一对码字之间的海明距离是 A 码字之间不同的位数B 两个码字之间相同的位数C 两个码字的校验和之和D 两个码字的校验和之差 A 一个码的最小码距是所有不同码字的码距的 A 平均值B 最大值C 最小值D 任意值 如果要检查出d位错 那么码的最小码距是 A d 1B d 1C 2d 1D 2d l 如果信息长度为5位 要求纠正1位错 按照海明编码 需要增加的校验位是 A 3B 4C 5D 6 以太网中使用的校验码标准是 A CRC 12B CRC CCITTC CRC 16D CRC 32 C B B D 为了进行差错控制 必须对传送数据帧进行校验 在局域网中广泛使用的校验方法是 1 校验 CRC 16标准规定的生成多项式为G x X16 X15 X2 l 它产生的校验码是 2 位 接收端发现错误后采取的措施是 3 如果 9 5 CRC的生成多项式为G X X4 X 1 信息码字为10110 则计算出的CRC校验码是 4 1 A 奇偶 Parity B 海明 Hamming C 格雷 Gray D 循环冗余 CyclicRedundancy 2 A 2B 4C 16D 32 3 A 自动纠错B 报告上层协议C 自动请求重发D 重新生成原始数据 4 A 0100B 1010C 0111D 1111 D C C D 7 4循环码 7 4 1循环码的基本概念及码多项式 所谓循环码 是指任何一个码字循环右移一位后所得到的仍是一个合法码字 属于线性分组码 应用 局域网数据传输 循环码特点 编码电路简单 可以很容易的用带有反馈的移位寄存器来实现 码字的多项式描述 设码字A a0 a1 an 1 10111 A an 1xn 1 an 2xn 2 a1x a0 例如 1011 x3 x 1 可以用码字多项式 表示 x4 x2 x 1 g x 生成多项式 循环码的生成矩阵G可以写成 G 例如 g x x4 x2 x 1 则 7 4 2循环码的生成多项式及生成矩阵 7 4 3循环码的编码原理 步骤 1 写出码多项式m x 2 写出xn km x 3 用 生成多项式 G x 除 码多项式 m x 4 得余式R x 模2运算 5 写出消息码组 信息码在前 监督码在后 信息码0111 7 4 循环码组 生成多项式G x x3 x 1 码多项式m x x2 x 1 x7 4m x x5 x4 x3 用G x 除m x 得余式R x x 010 消息码组 0111 010 例计算信息码110的 7 3 循环码组 生成多项式G x x4 x2 x 1 步骤 码多项式m x x2 x 0 xn km x x4 x2 x x6 x5用 生成多项式 G x 除xn km x x4 x2 x 1除x6 x5 模2运算 得余式R x x2 1写出消息码组 信息码在前 监督码在后1100101 11110111 1100000信息码补n k个01011111110101111001010111101编码为1100101计算1001的CRC码组 g x 生成多项式G x x4 x2 x 1 7 3 循环码编码器 循环码的编码电路 1 x x2 x4 7 4 4循环码的译码原理 检错 将接收码组R x 用原生成多项式g x 去除 以余式r x 是否为零判别码组中有无错码 1 用生成多项式g x 除接收码组R x 得出r x 2 余式用查表的方法确定错码位置 3 纠正错码 T x 0111010 R x 0111000 g x x3 x 1 r x 010 a1出错 练习 7 4 循环码组1001101 是否有错 生成多项式g x x3 x 1 7 5卷积码 概念 卷积码和分组码有明显的区别 线性分组码无记忆性 卷积码则不同 每个 n k 码段 也称子码 n个码元不仅与该码段内的信息元有关 而且与前面m段的信息元有关 有时候也用1 3 1 2表示卷积码 a b c d代表寄存器的四种状态 1 树图 其中a 00b 10c 01d 11 输出00 00 00 11 11 01 10 00 11 10 01 输入为110输出为 110101 2 网格图例1输入为1101110输出为 11010100011001 卷积码图解法 状态图树图格图 2 1 2 码的状态图 2 1 2 码的树图 卷积码的译码 卷积码译码可分为 代数译码 代数译码是利用生成矩阵和监督矩阵来译码 最主要的方法是大数逻辑译码 概率译码 概率译码比较实用的有两种 维特比译码和序列译码 目前 概率译码已成为卷积码最主要的译码方法 维特比译码思路 把接收码字与所有可能的码字比较 选择一种码距最小的码字作为解码输出 GSM系统中的 2 1 4 卷积编码器 IS 95CDMA系统中的 2 1 8 卷积编码器 GSM移动台原理框图 交错码又称交织码 是一种能纠正突发错误的码 它是以交错的方法来构造码的 把纠随机错误的 n k 线性分组码的m个码字 排成m行的一个码阵 该码阵称为交错码阵 一个交错码阵就是交错码的一个码子 码阵在传输时按列的次序进行 这样可以突发错误变为随机错误加以纠正 7 6Turbo码 如何纠正连续多个错误 突发错误 a6a5a4a3a2a1a0b6b5b4b3b2b1b0c6c5c4c3c2c1c0d6d5d4d3d2d1d0 横向写入 纵向读出 a6a5a4a3a2a1a0b6b5b4b3b2b1b0c6c5c4c3c2c1c0d6d5d4d3d2d1d0 纵向写入 a6b6c6d6 a5b5c5d5 a4b4c4d4 a3b3c3d3 a2b2c2d2 a0b0c0d0 a1b1c1d1 a6b6c6d6 a