第6章 信道编码.ppt

第六章信道编码 概述 在理论上 在无噪无损信道中 只要对信源的输出进行恰当的编码 总能以最大信息传输率C无错误地传输信息 但一般信道中总是存在噪声或干扰 信息传输会造成损失 那么在有噪信道中 怎么能使消息通过传输后发生的错误最少 而且无错误传输时可达到的最大信息传输率是多少 这就是本章要研究的内容 即通信的可靠性问题 香龙在1948年的文章中 提出并证明了这个极限信息率的存在 该定理被称为信道编码定理 也称为香龙第二定理 由于在有噪信道中 输入输出之间是统计依赖关系而不是确定关系 因此 信道输出要唯一地译成输入一般将无法避免差错 这时 根据信道输出确定信道输入的可靠程度就反映为错误概率 这一错误概率完全取决于信道的特性 且不可能为零 但是 香龙的研究证明 如果把要传送的消息在传送前事先进行编码 并在接收端采用适当的译码 则消息有可能得到无错误的传输 也就是说 通过不可靠的信道可以实现可靠的信息传输 一 信道编码的相关概念 1 信道编码在数字通信系统的地位和作用 数字信号在信道传输过程中 总会遇到各种干扰而使接收端收到的信号失真 这种失真称为差错 信道编码的作用就是尽量减少这种差错 提高通信系统的可靠性 2 衡量数字系统的技术标准 传输速率码元传输速率 每秒钟通过信道传输的码元数称为码元传输速率 比特传输速率 每秒钟通过信道传输的信息量称为比特传输速率 简称比特率 两者关系 采用二进制时 码元速率与比特速率在数值上是相等的 采用M进制时 比特率 码元传输速率 log2M 2 差错率码元差错率 指在传输的码元总数中发生差错的码元数所占的比例 简称误码率 用符号表示 3 可靠性不同的传输系统 对通信可靠性的要求是不一样的 比如 数字电话要求误码率在10 4 10 5 但计算机网的数据传输 却要求误码率在10 6 10 7 4 降低误码率的途径 一是降低信道本身所引起的误码率 二是采用信道编码 在数字通信系统中增加差错控制设备 比特速率与码元速率的转换及计算 用途 某些干扰大的信道上 其码元速率受到了限制 误码率Pe的计算 注意 计算误码率时 一定使用码元速率 3 信道编码基本思路 衡量信息传输可靠性的指标是差错率 而它只与信道的统计特性有关 要改变信道的统计特性成本太高 所以 可事先对信源编码器输出的符号序列按照某种规则进行编码 一般的方法是给信源序列加上一定的冗余度 这种编码谓之信道编码 编好的代码称为码字 将码字送入信道传输 而在信道输出端 信道译玛器根据编码规则对信道输出符号进行估值 尽量使这种估值接近实际输入码字 二 有噪信道编码定理该定理又称香农第二定理 定理指出 只要信息传输率R不大于信道容量C 则存在一种编码 可使信道输出端的错误概率任意小 而信息传输率可以无限地接近信道容量 证明略 三 纠错编码有噪信道编码定理出现后 引起了人们对信道编码的极大兴趣 但是 定理只是证明了这种特性 R C时PE0 的码的存在 还不能按其证明的方法得到这种好码 纠错编码作为提高传输可靠性的最主要措施之一 是本小节讨论的主要内容 广义的信道编码还包括 为特定信道设计的传输信号 如 NRZ码 HDB3码等都属于信道编码 1 前向纠错 FEC方式 若误码个数在码的纠错能力范围之内 译码器可自动发现并纠错特点 1 不需反馈信道 2 延时小 实时性好 3 设备较复杂能进行一对多点的通信 特别适合于移动通信 1 差错控制的基本工作方式 在信道译码时 能在译码器自动发现错误的码称为检错码 不仅能发现错误而且能自动纠正错误的码称为纠错码 2 检错重发 反馈重传 ARQ 发送端发出的是检错码 接收端译码时 若发现有错 通过反馈系统向发送端请求重传已发送的全部或部分码字 直到接收端认为没有错误为止 检错重发系统有以下几种 A 停发 等候重发 若收到码组后经检测 无错误 回送ACK 认确信号 给发端 发端收到后接着发下组 若收端检测有错误时 回送NAK 否认信号 请求重发本组 直至正确 B 返回重发 无停顿地送出多个码组 再检查错误重发 3 混合纠错 HEC方式 有一定的前向纠错能力 对超出纠错能力的错误有检测能力 并作检错重发 这种方式能使通信系统的误码率很低 得到了广泛应用 2 纠错码分类 1 根据信息码元与效验码元之间是否存在线性关系可分为线性码和非线性码 线性码的效验码元是若干位信息码元的线性组合 而非线性码的效验位与信息位不满足线性关系 线性码特点 具有良好的数学结构 编译码比较简单 性能优于同样纠错能力的非线性码 2 根据不同的分组及映射方式 纠错码又可以分成 分组码和卷积码两大类 分组码 是把信息序列以每k个码元分为一组 然后通过编码器把这k个信息元按一定规则产生r个多余的校验元 输出码序列每组长为n k r 每一码字的r个校验元只与本分组的k个信息元有关 而与别的分组的信息位无关 记为 n k n表示码长 k表示信息元位数 卷积码 信息序列以每k0个 通常较小 码元分段 编码器输出该段的效验元r n0 k0不仅本段的k0个信息元有关 而且还与其前面m段的信息元有关 称为卷积码 记为 n0 k0 m 称m为编码存贮 该码的信息元与校验元是线性关系 3 码字的描述 研究编码技术的目的之一就是寻找编码效率高且纠错能力强的编码方法 为了准确描述码的纠 检错能力 要用到以下几个基本概念 1 二元分组码 将信源编码器的输出序列进行分组 分组长度为k 则可以有M 2k个不同的信息组 每个信息组用一个n长的码字来表示 n k 故共有2k个不同的码字 人们把2k个码字的集合称为二元分组码 2 码字C的数学表示 C Cn 1 Cn 2 C1 C0 编码效率或信息率 R k n表示信息位所占的比重 衡量编码性能的重要指标 3 许用码组与禁用码组 许用码组 2k 23 8禁用码组 2n 2k 27 23 128 8 120 7 3 线性分组码R k n 3 7 43 1 几个基本概念 汉明距离 距离 在 n k 线性码中 两个码字U V之间对应码元位上取值不同的个数 称为码字U V之间的汉明距离 例如 7 3 码的两个码字U 0011101 V 0100111 它们之间第2 3 4和6位不同 因此 码字U和V的距离为4 线性分组码的一个码字对应于n维线性空间中的一点 码字间的距离即为空间中两对应点的距离 4 线性分组码的最小距离 检错和纠错能力 最小距离 dmin 在 n k 线性码的码字集合中 任意两个码字间距离最小值 叫做码的最小距离 若C i 和C j 是任意两个码字 则码的最小距离表示为如 3 2 码 n 3 k 2 共有22个码字 000 011 101 110 显然dmin 2 码的最小距离是衡量码的抗干扰能力 检 纠错能力 的重要参数 码的最小距离越大 码的抗干扰能力就越强 汉明重量 码字重量 W 码字中非0码元符号的个数 称为该码字的汉明重量 在二元线性码中 码字重量就是码字中含 1 的个数 最小重量 Wmin 线性分组码CI中 非0码字重量最小值 叫做码CI的最小重量 Wmin min W V V CI V 0 2 最小距离与检 纠错能力一般地说 线性码的最小距离越大 意味着任意码字间的差别越大 则码的检 纠错能力越强 检错能力 如果一个码能检出长度 l个码元的任何错误图样 称码的检错能力为l 纠错能力 如果码能纠正长度 t个码元的任何错误图样 称码的纠错能力为t 最小距离与检错能力 n k 线性码能够发现L个错误的充要条件是码的最小距离为dmin L 1 上式表明 由于接收字R与其它任何码字U的距离都大于0 则说明接收字R不会因发生错误变为其它码字 因而必能发现错误 两球的重叠区域内 几何意义 例如 只有一个校验元的奇偶校验码 表示为 n n 1 分组码 以偶校验为例 这种码的编码规则为 添加的校验元要保证每个码字中 1 的个数为偶数 比如 3 2 偶校验码 合法码字为22 4个 000 011 101 110 该码组最小距离为2 所以能发现一个差错 现象一 若发出000 而收到是010 显然010为非法码字 说明收到的码字有差错 可是并不能纠正 现象二 若发出还是000 但收到的是011 由于011为合法码字 于是接收端无法发现 最小距离与纠错能力 n k 线性码能纠t个错误的充要条件是码的最小距离为 上式表明 如果接收字R中错误个数t t 那么 此时译码是正确的 码字中的错误可以被纠正 球体以内的错误均可纠正 几何意义 最小距离与检 纠错能力 n k 线性码能纠t个错误 并能发现L个错误 L t 的充要条件是码的最小距离为dmin t L 1 几何意义 以简单直观的 n 1 重复码为例 说明码的最小距离与纠错能力之间的关系 当 n k 线性码的最小距离dmin给定后 可按实际需要灵活安排纠错的数目 例如 对dmin 6的码 可只用于检5个错误 也可用来纠正2个错误 或者用来纠2检3错 检 纠错能力的安排 练习与作业 1 简述信道纠错编码的思路及其目的 2 差错控制系统的基本工作方式有哪些 3 检错码和纠错码两者有什么不同 4 试述码的距离 汉明距离 和重量 汉明重量 的概念 线性分组码的最小距离有何实际意义 5 设某二元码为C 11100 01001 10010 00111 1 计算此码的最小距离dmin 2 此码能纠正几位码元的错误 5 编码信道的一般模型 注意 1 信源编码器的输出二进制序列各符号彼此无关 信道编码器的输出二进制序列各符号具有相关性 2 在上述的有噪信道中 传输信息发生的差错率与哪些因素有关呢 信道统计特性 编码方法 译码规则 1 差错与差错图样 差错的基本形式 A 随机错误 数据序列中 前后码元之间是否发生错误彼此无关 此时 通常把产生这种错误的信道称为无记忆信道或随机信道 B 突发性错误 错误之间有相关性 错误是成串出现的 此时 通常把产生这种错误的信道为突发差错信道 设发送的是n个码元长的序列信道中的干扰也用二进制序列表示为 通过信道传输到达接收端的序列为 若将有错误的各位取值为1 无错的各位取值为0 那么 接收序列R就是C与E序列模2相加的结果 此时 就称E为信道的错误图样 例6 1 发送序列C 1111100000 收到序列R 1001010000 可以看出 第二 三 五 六位产生的错误 因此 信道的错误图样E的二 三 五 六位取值为1 其它各位取值为0 即E 0110110000 用式子可表示成 发送序列C 1111100000 错误图样E 0110110000接收序列R 1001010000 2 错误概率 差错率 和信道统计特性 我们已经知道 信道统计特性可由信道矩阵来表示 同时 可以通过信道矩阵求出错误概率 所以 错误概率与信道统计特性有关 0 1 1 0 0 9 0 9 0 1 0 1 若输入符号概率相等 则PE 0 9 例6 2 3 错误概率和译码规则 经过前面的分析知道 错误概率与信道统计特性有关 但是 通信的过程并不是信息传输到信道输出端就结束了 还要经过译码过程才能到达信宿 所以 译码过程和译码规则对系统的错误概率影响很大 译码规则的定义 例6 3 设有一个二元对称信道 其输入符号为等概率分布 如图 0 1 1 0 0 9 0 9 0 1 0 1 若译码规则 00 11错误概率 PE 0 9 若译码规则 01 10错误概率 PE 0 1 可见 错误概率既与信道统计特性有关 也与译码规则有关 例6 4 设有一信道 其信道矩阵为 根据此信道矩阵 可以设计以下两种不同的译码规则 r s 3 总共可以设计出rs 27种译码规则 当然 在所有的译码规则中 并不是每一种译码规则都是合理的 因此 译码规则的选择应该根据什么准则 一个很自然的准则当然就是要使错误概率最小 1 基本概念 译码器的条件正确概率可表示为 译码器的条件错误概率可表示为 5 最大后验概率译码准则 译码后的平均错误概率为 其中 P yj 是接收符号yj的概率 与译码方法无关 2 最大后验概率译码准则 只要设计 或选择 某种译码规则 使条件错误概最小 也就是要选择条件正确概率最大 这就是最大后验译码准则 又称为最小错误概率译码 即满足下式 规则物理含义 在译码时 对于每一个输出符号均译成具有最大后验概率的那个输入符号 则信道译码平均错误概率最小 其不足之处 通常情况下 已知信道转移概率和输入符号的先验概率 而后验概率不易获得 需要进行烦琐的计算 故使用起来不方便 6 极大似然译码准则 该译码规则的优点 1 译码函数可直接从信道矩阵的传递概率中去选定 当收到yj后 译成信道矩阵P第j列中最大的转移概率所对应的输入符号xi 此时 可使平均错误概率PE达到最小 2 当输入符号等概率时 前述两个规则是等价的 根据贝叶斯定律 式 6 2 5 又可写成 当输入符号的先验概率相等 上式就变换成为 由此 获得了较实用的译码规则 极大似然译码准则 根据上述译码准则 可以计算平均错误概率 X x 的理解 对输入符号集X中 除去x 以外的所有元素求和 如果输入为等概率分布 即 则上式写成 PE公式表明 在输入等概率的情况下 译码的平均错误概率可用信道矩阵中的元素求和来表示 求和是除去每列中对应于的那一项后 矩阵中其余元素之和 例6 5 试求例6 4中 两种译码规则对应的平均错误概率 假设其输入为