中职中专-数字通信技术电子ppt课件.ppt

第三章 差错控制编码 教学重点 1 理解差错控制编码的基本原理 2 理解三种差错控制方式 3 了解简单检纠错码 常用检纠错码差错控制的编码方法 掌握差错控制编码的基本原理 学时分配 教学难点 第三章差错控制编码 3 1概述 3 2简单的纠 检错编码 3 3常用的纠错编码 本章小结 3 1概述 一 差错类型 二 差错控制方式 三 纠错编码的基本原理 2 信源编码和信道编码的区别 信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码 1 差错控制编码又称信道编码 抗干扰编码或纠错码 它是提高数字信号传输可靠性的有效方法之一 信道编码是为了降低误码率 提高数字通信的可靠性而采取的编码 1 目的 信源编码是去掉信源的多余度 信道编码是按一定的规则加入多余度 信道编码是在发送端的信息码元序列中 以某种确定的编码规则 加入监督码元 以便在接收端利用该规则进行解码 从而发现错误 纠正错误 2 方式 1 差错类型 造成这种差错的类型有三种 一 差错类型 1 随机错误 也称独立错误 其特点是发生错误的码元互相独立 大多不会成片出现 2 突发错误 即一个错误出现往往影响后面的数据也出现错误 误码成片出现 错误之间有相关性 3 混合错误 随机错误和突发错误都占有相当的比例 2 纠检错码分类 1 根据编码的用途 可分成检错码和纠错码 检错码以检错为目的 不一定能纠错 而纠错码以纠错为目的 一定能纠错 2 按对信息码元处理的方法不同 又可分成分组码和卷积码 分组码的各码元仅与本组的信息元有关 卷积码中码元不仅与本组的信息元有关 而且还与前面若干组的信息码元有关 其中分组码又还可分成汉明码和循环码 常用的差错控制方式有3种 检错重发 前向纠错和混合纠错 1 检错重发方式 ARQ 二 差错控制方式 检错重发又称自动请求重传方式 记作ARQ 由发端送出能够发现错误的码 由收端判决传输中有无错误产生 如果发现错误 则通过反向信道把这一判决结果反馈给发端 然后 发端把收端认为错误的信息再次重发 从而达到正确传输的目的 检错重发特点是需要反馈信道 译码设备简单 对突发错误和信道干扰较严重时有效 但实时性差 主要应用在计算机数据通信中 2 前向纠错方式 FEC 前向纠错方式记作FEC 发端发送能够纠正错误的码 收端收到解码之后 不仅可以发现错误 而且能够判断错误码元所在的位置 并自动纠正 前向纠错的特点是单向传输 实时性好 传输效率高 但译码设备较复杂 这种纠错方式广泛应用于移动通信设备中 例如BP机 手机等 3 混合纠错方式 HEC 混合纠错方式记作HEC 是ARQ和FEC方式的混合 发送端同时送出具有检错和纠错能力的码 接收端收到信码之后 检查错误情况 如果误码较少 且在码的纠错能力以内 则自动进行纠正 如果超过了码的纠错能力 则经过反馈信道请求发送端重发 HEC方式具有自动纠错和检错重发的优点 可达到较低的误码率 特别适合于高速传输系统 例如卫星通信中 三 纠错编码的基本原理 下面我们以分组码为例说明纠错码检错和纠错的基本原理 分组码的结构如图3 1所示 1 分组码 图3 1分组码 分组码用 n k 表示 其中k是每组信息码元的数目 n是编码码组的码元总位数 又称为码组长度 简称码长 n k r为每个码组中的监督码元数目 简单地说 分组码是对每段k位长的信息组以一定的规则增加r个监督元 组成长度为n的码字 在二进制情况下 共有2k个不同的信息组 相应地可得到2k个不同的码字 称为许用码组 其余2n 2k个码字未被选用 称为禁用码组 两个等长码组之间相应位取值不同的数目称为这两个码组的汉明距离 简称码距 例如码字11000与10011之间的码距d 3 码字11011与11000之间的码距d 2 码组中任意两个码字之间距离的最小值称为码的最小码距 用d0表示 最小码距是码的一个重要参数 它是衡量码检错 纠错能力的依据 例如左边的三个码字 则三个码字的最小码距d0 1 2 检错和纠错的基本原理 以重复编码为例说明 为什么纠错码能检错和纠错 检纠错能力与最小码距d0的关系 假如要发送天气预报的消息 且天气只有晴 阴两种状态 可用表3 1中的3种编码来讨论它的编码方法和纠错能力 a序号编码用1位二进制表示阴晴二种状态 b c序号是各用二位二进制 三位二进制表示二种状态 故b c序号为重复编码 表3 1重复码的简单例子 在编码a中 两个码字中只有一位差别 即最小码距d0 1 若 1 晴 误传为 0 阴 或 0 阴 误传为 1 晴 则收端都不可能判别是否有错 因为所收到的码字都是预先约定好的码 允许用码 在这种情况下误码只能产生错误的预报 在编码b中 将a中代码再加一位重复监督码元 即晴用 11 阴用 00 表示 这两个码字的差别是两位不同 即许用码组中的最小码距d0 2 如果干扰使码字中仅一位传错 即出现 01 或 10 码 收端译码时 可发现在预约的二位编码中 并不存在这样的码字 这就是禁用码 这时收端认为传输过程中出现错误 这是 11 或是 00 中一位出错造成的 但错码到底是由哪个码字造成的 难以判断 可见 这种具有两位差别的码字具有检测一个错误的能力 但不能纠正 在编码c中 将b中编码再增加一位重复监督位 构成三位码 111 和 000 显然 这两个码字的差别是3位不同 即许用码组中的最小码距d0 3 当传输中码字受干扰而将 111 或 000 误传为 110 101 011 001 010 100 时 接收端认为是都传错了 因为这些码字都不是许用码字而是禁用码字 这些错误的码字可能是由于错一位造成的 也可能是由于错两位造成的 所以它可以发现两位错误 如果把出现的二个1或三个1时 判为1 否则判为0 此时该编码可以纠正单个错误码 检查出二个错误码 从例中可以看出 码的最小距离d0直接关系着码的检错和纠错能力 任一 n k 分组码 若要在码字内 1 检测e个随机错误 则要求最小距码d0 e 1 2 纠正t个随机错误 则要求最小码距d0 2t 1 3 纠正t个同时检测e t 个随机错误 则要求最小码距d0 t e 最小码距d0越大 纠 检错能力越强 3 编码效率 我们定义编码效率R来衡量有效性 其中 k是信息元的个数 n为码长 对纠错码的基本要求是 检错和纠错能力尽量强 编码效率尽量高 编码规律尽量简单 实际中要根据具体指标要求 保证有一定纠 检错能力和编码效率 并且易于实现 3 2简单的纠 检错编码 一 奇偶校验码 二 行列校验码 三 恒比码 一 奇偶校验码 奇偶校验码是在原信息码后面附加一个监督元 使得码组中 1 的个数是奇数或偶数 奇偶校验码又分为奇校验码和偶校验码 设码字A an 1 an 2 a1 a0 对偶校验码有 式中 an 1 an 2 a1为信息元 a0为监督元 接收端译码时 按上式将码组中的码元模二相加 若结果为 0 就认为无错 结果为 1 就可断定该码组经传输后有奇数个错误 奇校验码情况相似 只是码组中 1 的数目为奇数 即满足条件 奇校验码检错能力与偶校验码相同 奇偶校验码只能用来检查错码 无纠正错码的能力 二 行列校验码 行列校验码不仅对水平 行 方向的码元 而且对垂直 列 方向的码元也实施奇偶校验 这种码既可以逐行传输 也可以逐列传输 图3 2是行列校验码的一个例子 行和列均用偶校码 第6行 11列为校验位 如对应第4行第6列出错 1 变为 0 则所对应的行列不能满足偶校验的关系 从而知其是错码 行列校验码具有较强的检测能力 适于检测突发错误 还可用于纠错 它应用于CD VCD数字信号的差错控制编码中 图3 2行列校验码 三 恒比码 码字中1的数目与0的数目保持恒定比例的码称为恒比码 又称等重码 定1码 恒比码在检测时 只要计算接收码元中1的数目是否正确 就知道有无错误 目前我国电传通信中普遍采用3 2码 又称 5中取3 的恒比码 即每个码组的长度为5 其中3个 1 这时可能编成的不同码组数目等于从5中取3的组合数10 这10个许用码组恰好可表示10个阿拉伯数字 如表3 2所示 表3 23 2恒比码 每个汉字以四位十进制数来代表的 采用检错重传ARQ的差错控制方式 使用这种码后 我国汉字电报的差错率大为降低 3 3常用的纠错编码 一 线性分组码 二 循环码 四 码元交织 三 卷积码 一 线性分组码 在 n k 分组码中 若每一个监督码元都是码组中某些信息码元按模2加而得到 即监督码元是按线性关系相加得到的 则称为线性分组码 在这里以 7 4 分组码为例说明编码过程 1 基本概念 设有n 7的码字 编为 7 4 分组码 其中4个信息码元为a6a5a4a3 3个监督码元为a2a1a0 根据模2和关系和多重监督原则 列出 7 4 线性分组码的一致监督关系 由于r 7 4 3 显然这个一致监督关系是3个线性方程组 三个监督码元由下式产生 4位信息码分别取不同的组合 经上面3个线性方程组计算 可得到 7 4 线性分组码的全部码字 如表3 3所示 表3 3 7 4 线性分组码码字表 从上表可看出 上述 7 4 分组码16个许用码组中的最小码距d0 3 因此它能纠正一位错码或检查出二位错码 2 纠错原理 分组码能实现纠检错的原理 分组码是通过附加监督码元实现对信息码元的监督 两者之间存在由监督方程组建立的相互制约关系 当信息码元或监督码元在传输过程中发生错误时 方程组中与这些码元对应的相互制约的关系就会被破坏 于是在接收端很容易通过检验监督方程来发现错误 另外 由于分组码的一致监督关系是多重监督 每个信息码元都受到两个或两个以上监督元的监督 故不仅能够发现传输中的错误 当只有单个错误时 还能知道错误的位置并给以纠正 举例说明 令校验子s1 s2 s3分别为 根据一致监督关系 如果接收的码组没有错误 则s1 s2 s3 0 当码组在传输过程中发生单个错误时 在s1 s2 s3的计算结果中 将有一个或几个不为零 这样根据s1 s2 s3的不同数值 就可唯一地确定错误的位置 为此我们把s1 s2 s3称作校验子 以 7 4 码为例 根据s1 s2 s3的不同结果 可判断出具体的错误位置 如表3 4所示 表3 4校验子和错码位置关系 例如接收到的码字 0000011 按校验子方程有 s1 0 s2 1 s3 1 从表3 4可查出错码位置为a3 在二进制系统中 能准确地知道错码的位置 就等于能纠正错码 这是因为错码位置确定之后 只要把所在位置的码元经过一个逻辑 非 电路 就能把 0 变成 1 或把 1 变 0 从而完成纠错的任务 二 循环码 循环码是一种码字间具有循环性质的码组 循环是指将任一码字的各位闭合左移或右移后 生成的新码字仍是该码组中的另一个码字 循环码仍由信息码和监督码两部分组成 它也是一种线性分组码 同样用 n k 来表示其码长和信息位数 在表 3 5 所示的循环码组里 若将2号码字向右闭合移动一位就得到5号码字 5号码字向右闭合移动一位即得到7号码字 等等 表3 5循环码 循环码是根据多项式代数运算原理来实现编 解码的 常用码多项式表示码字 如表 3 5 第2号码字a6a5a4a3a2a1a0 0010111 因为其a4 a2 a1 a0等于1 则可用码多项式表示 循环码也是一种分组码 由信息位和监督位组成一个码字 即 1 循环码的编码 上式中 表示循环码的一个码字 为信息位 为信息码多项式 乘上 在码多项式运算中表示把码多项式左移 n k 位 例如表 3 5 中的第2号码字 信息码元为A x 001 但它们的权重位置在a6a5a4位置上 所以应该左移n k 7 3 4位 R x 为监督码多项式 第2号码字中的R X 0111 如何编出循环码呢 循环码的编码特点是循环码中的一个码字可以被一个xn k次幂的多项式整除 称这个xn k次幂的多项式为生成多项式 并用符号G x 表示 例3 1已知信息码元为110 编一个 7 3 循环码字 解 第一步 由信息码元列出对应的k 1 2次幂码多项式A x 即 第二步 将A x 左移n k 7 3 4位 求出x4 A x 第三步 查表并选用下式为生成多项式G x 第四步 进行除法运算 求余数R x 转换成下面格式 第五步 把信息位x4A X 与余式R X 合并 得 7 3 循环码为 前三位为信息码元 后四位 0101 为监督码元 利用生成多项式可以方便地生成一个循环码字 因为生成多项式可以对应构成一个由移位寄存器和模2相加器组成的运算电路 利用这个电路就可完成循环码的编码 由此可知 从编码原理可知 循环码多项式都可被生成多项式G x 整除 因此 只要将接收到的码字除以G x 观察余式R x 是否为零就可判断出传输中是否发生了错误 当R x 0时 说明传输中无错误 如R x 0 说明传输中有错误 2 循环码的检错与纠错 例如上例中 7号码字C7 1100101 由于a2误码 接收的时候C7 1100001 在第3位发生了错码 对应的码多项式 上例中的生成多项式 将接收到的码字除以生成多项式G x 得到的余式 说明传输中有错误 将其与产生误码的码字相加 便可得到正确的7号码字 从而完成了纠错的目的 在广播电视设备中应用的典型例子是循环多余校验码 CRCC 它是由k 82位信息码元和r 8位校验码元组成的 90 82 循环码 主要用于检错 卷积码是将信息序列分成长度为k0的一个一个子组 长为n0的每个子码组 叫作子码 包括k0个信息位 n0 k0个监督位 这n0 k0个监督元 不仅与本组的k0个信息元有关 而且也与前面若干个子组的信息元有关 本组的信息元不但决定本组的监督元 而且也参与决定以后若干组的监督元 三 卷积码 卷积码编码器主要由移位寄存器构成 如图3 3所示 1 编码器和监督元 图中D0 D1为两级移位寄存器 信息序列由左面输入 其顺序是高位在右 低位在左 每一单位时间送入编码器一个信息元 图3 3 3 1 2 卷积码编码器 图3 3 3 1 2 卷积码编码器 移位寄存器 的存储数据每个时刻右移一位 在输入信息为mj的第j时刻 D0的输出是其前一时刻的mj 1 D1移出的是再前一个时刻的信息mj 2 mj与mj 1 mj 2经两个模2加法器后 得到两个监督元Pj 1 Pj 2 即Pj 1 mj mj 1Pj 2 mj mj 2 在输出端 由旋转开关选择输出序列 每一时刻旋转一周 输出一个子码 第j时刻输出的子码为Cj Cj mj Pj1 Pj2 对j 1时刻 输入信息为mj 1 相应的监督元为Pj 1 1 mj 1 mjPj 1 2 mj 1 mj 1 输出相应的子码Cj mj 1 Pj 1 1 Pj 1 2 对于这种编码器 每个子码的信息位k0 1 码长n0 3 2 约束关系 卷积码的一个信息元mj 不但参与决定本子码的监督元 还要参与决定其后续子码的监督元 这表明 信息元使前后相继的子码之间产生了约束关系 也就是说 子码之间存在相关性 这种相关性是若干信息元通过改变移位寄存器的状态来实现的 由图3 4可看出 一个子码 j既与前面N 1个子码发生关联 而且还与其后面N 1个子码相关联 就像图中的各个虚线方框是一个套着一个的 正如一串不断的连环一样 所以通常又把卷积码称为连环码 图3 4卷积码子码之间的约束关系 卷积码的译码和编码过程相类似 卷积码接收到的各个子码之间存在着一定的约束关系 一组信息元不但影响着本子码的监督码元 同时还将影响着其后面若干子码的监督码元 即后面 N 1 个子码都含有本组的信息 我们可以充分利用后面 N 1 个子码来帮助本组信息的正确译码 这将使译码的正确率大大提高 3 卷积码的译码和纠错 码元交织是将顺序传送的码元序列按一定规律重新进行排列 以使突发误码分散到不相邻的样值中 这样使突发误码变成了随机误码 再用消除随机误码的前向自动纠错 FEC 技术消除随机误码 在接收端再按规定的规律恢复成原来顺序 四 码元交织 码元交织的特点是不需增加任何码元 就可实现对突发错误的校正或对突发与随机误码的校正 使用十分广泛 卷积码的译码和编码过程相类似 以 7 3 线性分组码为例 说明交织编码原理 7 3 分组码每个码字有7位 由3位信息码和4位监督码组成 它的编码矩阵如下 1 交织编码原理 2 约束关系 交织编码矩阵中的行为前向自动纠错FEC方式中的一个码字 它由3位信息位及4位监督位组成 矩阵中行的数目M称为交织深度 交织编码的过程是将FEC码字序列按行写入而按列读出 其交织编码输出序列为 a11b21c31 mM1a12b22c32 mM2a13b23c33 交织深度M越大 离散度越大 抗突发差错能力也越强 交织深度M越大 交织编码处理时间也越长 即是以时间为代价的 本章小结 一 差错控制方式 二 反映纠错编码的参数 三 奇偶校验码 四 分组码 五 码元交织技术 一 差错控制方式 信道编码又称为差错控制编码或纠错编码 错码分为三种 一是以随机 个别 独立出现的随机错码 二是短时间内大量出现的突发错码 三是随机错码和突发错码的混合称为混合错码 差错控制有三种方式 1 检错重传ARQ 2 前向纠错FEC 3 混合纠错HEC 在移动通信中用得较多的是前向纠错FCC差错控制方式 它的特点是无需反馈信道 实时性好 但编解码电路复杂 编码效率低 二 反映纠错编码的参数 反映纠错编码的参数有码距 最小码距 编码效率 码距d是指二个码字在对应位上码元取值不同的位数 最小码距d0是指所有码组中码距d的最小值