第6章 有噪信道编码定理12

幻灯片 1 第第 6 6 章章 有噪信道编码定理有噪信道编码定理 幻灯片 2 在无噪无损信道上 只要对信源的输出进行适当的编码 总能以最大信息传输率在无噪无损信道上 只要对信源的输出进行适当的编码 总能以最大信息传输率 C C 信道容量 无差错地传输信息 但一般信道中总存在噪声或干扰 信息传输会 信道容量 无差错地传输信息 但一般信道中总存在噪声或干扰 信息传输会 造成损失 那么在有噪信道中怎么能使消息通过传输后发生的错误最少 在有噪造成损失 那么在有噪信道中怎么能使消息通过传输后发生的错误最少 在有噪 信道中无错误传输的可达的最大信息传输率是什么 信道中无错误传输的可达的最大信息传输率是什么 这就是本章所要研究的内容 即研究通信的可靠性问题 这时香农在这就是本章所要研究的内容 即研究通信的可靠性问题 这时香农在 19481948 年的文年的文 章中提出并证明了的信道编码定理 也称香农第二定理 章中提出并证明了的信道编码定理 也称香农第二定理 幻灯片 3 6 16 1 错误概率和译码规则错误概率和译码规则 在有噪信道中传输消息时会发生错误的 为了减少错误 提高可靠性 首先就要分析在有噪信道中传输消息时会发生错误的 为了减少错误 提高可靠性 首先就要分析 错误概率与哪些因素有关 有没有办法加以控制 能控制到什么程度等问题 错误概率与哪些因素有关 有没有办法加以控制 能控制到什么程度等问题 错误概率与信道统计特性有关 信道的统计特性可由信道的传递矩阵来描述 当确定错误概率与信道统计特性有关 信道的统计特性可由信道的传递矩阵来描述 当确定 了输入和输出对应关系后 也就确定了信道矩阵中哪些是正确传递概率 哪些是错误了输入和输出对应关系后 也就确定了信道矩阵中哪些是正确传递概率 哪些是错误 传递概率 传递概率 但通信过程一般并不是在信道输出端就结束了 还要经过译码过程 或判决过程 才但通信过程一般并不是在信道输出端就结束了 还要经过译码过程 或判决过程 才 到达消息的终端 收信者 到达消息的终端 收信者 因此译码过程和译码规则对系统的错误概率影响很大 因此译码过程和译码规则对系统的错误概率影响很大 幻灯片 4 错误概率既与信道的统计特性有关 也与译码的规则有关 错误概率既与信道的统计特性有关 也与译码的规则有关 定义译码规则 设离散单符号信道的输入符号集为定义译码规则 设离散单符号信道的输入符号集为 A ai i 1 2 r 输出符号集为 输出符号集为 B bj j 1 2 s 制定译码规则就是设计一个函数 制定译码规则就是设计一个函数 F bj 它对于每一个输出符号 它对于每一个输出符号 bj 确定一个唯一的输入符号确定一个唯一的输入符号 ai 与其对应 单值函数 与其对应 单值函数 即 即 F bj ai i 1 2 r j 1 2 s 幻灯片 5 译码规则的选择应该根据什么准则 一个很自然的准则当然就是要使平均错误概率为译码规则的选择应该根据什么准则 一个很自然的准则当然就是要使平均错误概率为 最小 最小 为了选择译码规则 首先必须计算平均错误概率 为了选择译码规则 首先必须计算平均错误概率 平均错误概率平均错误概率 PEPE 表示经过译码后平均接收到一个符号所产生的错误大小 应是条件错表示经过译码后平均接收到一个符号所产生的错误大小 应是条件错 误概率误概率 P eP e bj bj 对对 Y Y 空间取平均值 空间取平均值 e e 表示除了表示除了 F bj F bj aiai 以外的所有输入符号的集以外的所有输入符号的集 合 合 PEPE E p e E p e bj bj 收到符号收到符号 bjbj 条件下译码的正确概率为条件下译码的正确概率为 P F bj P F bj bj bj P aiP ai bj bj P eP e bj bj 1 1 P aiP ai bj bj 1 1 P F bj P F bj bj bj s 1j jj bepbp 幻灯片 6 如何设计译码规则如何设计译码规则 F bj F bj aiai 使 使 PEPE 最小最小 s 1j jj bepbp PE E p e bj 由于上式由于上式 PE 的表达式中右边是非负项之和 可以选择译码规则使每一项为最小 即的表达式中右边是非负项之和 可以选择译码规则使每一项为最小 即 得得 PE 最小 因为最小 因为 p bj 与译码规则无关 所以只要设计译码规则与译码规则无关 所以只要设计译码规则 F bj ai 使条件 使条件 错误概率错误概率 P e bj 为最小 为最小 幻灯片 7 最大后验概率准则最大后验概率准则 如果采用一种译码函数 对于每一个输出符号均已成具有最大后验概率的那个输入符如果采用一种译码函数 对于每一个输出符号均已成具有最大后验概率的那个输入符 号 则信道错误概率就能最小 号 则信道错误概率就能最小 P eP e bj bj 最小 就是最小 就是 P F bj P F bj bj bj 为最大 即选择译码函数 为最大 即选择译码函数 F bj F bj a a a a A A bj Bbj B 并使之满足条件并使之满足条件 P a P a bj bj P ai P ai bj bj ai Aai A aiai a a 这种译码规则称为这种译码规则称为 最大后验概率准则最大后验概率准则 或或 最小错误概率准则最小错误概率准则 幻灯片 8 最大后验概率准则利用贝叶斯定律就可以表示为选择译码函数最大后验概率准则利用贝叶斯定律就可以表示为选择译码函数 F bj F bj a a a a A A bj Bbj B 使满足 使满足 P bjP bj a a p a p a P bjP bj ai ai p ai p ai ai Aai A aiai a a j iij j j bP aPabP bP aPabP 幻灯片 9 最大似然译码准则最大似然译码准则 若最大后验概率准则中输入符号的先验概率若最大后验概率准则中输入符号的先验概率 p ai p ai 均相等 则上式均相等 则上式 6 7 6 7 可写成选择可写成选择 译码函数译码函数 F bj F bj a a a a A A bj Bbj B 并满足 并满足 P bjP bj a a P bjP bj ai ai ai Aai A aiai a a 这样定义的译码规则称为最大似然译码准则 这样定义的译码规则称为最大似然译码准则 幻灯片 10 在输入符号等概率时 这两个译码准则是等价的 在输入符号等概率时 这两个译码准则是等价的 根据最大似然译码准则可以直接从信道矩阵的传递概率中去选定译码函数 就是说 根据最大似然译码准则可以直接从信道矩阵的传递概率中去选定译码函数 就是说 收到收到 bjbj 后 译成信道矩阵后 译成信道矩阵 P P 的第的第 j j 列中最大那个元素所对应的信源符号 列中最大那个元素所对应的信源符号 最大似然译码准则本身不再依赖于先验概率最大似然译码准则本身不再依赖于先验概率 p ai p ai 但是当先验概率为等概率分布时 但是当先验概率为等概率分布时 它使错误概率它使错误概率 PEPE 最小 如果先验概率不相等或不知道时 仍可以采用这个准则 但不最小 如果先验概率不相等或不知道时 仍可以采用这个准则 但不 一定能使一定能使 PEPE 最小 最小 幻灯片 11 平均错误概率平均错误概率 PEPE 根据译码准则 可以进一步推得平均错误概率根据译码准则 可以进一步推得平均错误概率 PE PE 平均正确概率为平均正确概率为 经过简化经过简化 YaX Y jij Y X jij Y j bapbapbapbepbp Y j Y jjEE bapbbFpp1p aX Y iijE apabpp i e X i Y jij X iij X baY iE pap abFabpapabpapp j 对应的 幻灯片 12 平均错误概率平均错误概率 PEPE 令令 就是某个输入符号就是某个输入符号 aiai 传输所引起的错误概率 传输所引起的错误概率 如果先验概率均相等 如果先验概率均相等 p ai p ai 1 r 1 r 则得 则得 i e p Y jij i e abFabpp X i e aX Y ijE p r 1 abp r 1 p 幻灯片 13 在等先验概率分布情况下 译码错误概率可用信道矩阵中的元素在等先验概率分布情况下 译码错误概率可用信道矩阵中的元素 P bj ai 求和表示 求和表示 式式 6 15 求和是除去每列对应于求和是除去每列对应于 F bj a 的那一项后 先对列求和 然后求各列之和 的那一项后 先对列求和 然后求各列之和 而式而式 6 16 是先对行求和 然后求各行之和 是先对行求和 然后求各行之和 幻灯片 14 采用最小错误概率准则采用最小错误概率准则 1 1 aXY ji Y j YX ji Y jj YX ji Y jj j Y jjj Y jE baPbaPbaP bbFPbaPbbFP bPbbFPbePbPP 幻灯片 15 例题例题 4 03 03 0 5 03 02 0 2 03 05 0 P 已知信道矩阵已知信道矩阵 译码函数译码函数 B 译码函数译码函数 A 33 22 11 abF abF abF 23 32 11 abF abF abF 幻灯片 16 例题例题 2 015 0 15 0 125 0 075 0 05 0 05 0 075 0 125 0 jib aP jij baPbaP 33 32 31 abF abF abF 译码函数译码函数 C jjijj bPbaPbaPbP 例题例题 6 2 可知输入不是等概率分布时最大似然译码准则可知输入不是等概率分布时最大似然译码准则 的平均错误概率不是最小 的平均错误概率不是最小 幻灯片 17 费诺不等式费诺不等式 平均错误概率平均错误概率 PEPE 与译码规则 译码函数 有关 而译码规则又由信道特性来决定 与译码规则 译码函数 有关 而译码规则又由信道特性来决定 由于信道中存在噪声 导致输出端发生错误 并使接收到输出符号后 对发送的是什由于信道中存在噪声 导致输出端发生错误 并使接收到输出符号后 对发送的是什 么符号还存在不确定性 么符号还存在不确定性 可见 可见 PEPE 与信道疑义度与信道疑义度 H X Y H X Y 是有一定关系的 因此可得是有一定关系的 因此可得 H X Y H X Y H PE H PE PEPE log r 1 log r 1 幻灯片 18 虽然虽然 PEPE 与译码规则有关 但是不管采用什么译码规则该不等式都是成立的 与译码规则有关 但是不管采用什么译码规则该不等式都是成立的 H PE H PE 是错误概率是错误概率 PEPE 的熵 表示产生错误概率的熵 表示产生错误概率 PEPE 的不确定性 的不确定性 幻灯片 19 费诺不等式 说明 费诺不等式 说明 接收到接收到 Y Y 后关于后关于 X X 的平均不确定性可分为两部分 第一部分是指接收到的平均不确定性可分为两部分 第一部分是指接收到 Y Y 后是否产生后是否产生 PEPE 错误的不确定性错误的不确定性 H PE H PE 第二部分表示当错误第二部分表示当错误 PEPE 发生后 到底是哪个输入符号发送而造成错误的最大不确定性 发生后 到底是哪个输入符号发送而造成错误的最大不确定性 为为 PEPE log r 1 log r 1 其中 其中 r r 是输入符号集的个数 是输入符号集的个数 若以若以 H X Y H X Y 为纵坐标 为纵坐标 PEPE 为横坐标 函数为横坐标 函数 H PE H PE PEPE log r 1 log r 1 随随 PEPE 变化的曲线如变化的曲线如 图图 6 26 2 从图中可知当信源 信道给定 信道疑义度从图中可知当信源 信道给定 信道疑义度 H X Y H X Y 就给定了译码错误概率的下限 就给定了译码错误概率的下限 幻灯片 20 6 26 2 错误概率与编码方法错误概率与编码方法 消息通过有噪信道传输时会发生错误 而错误概率与译码规则有关 但当一般信道给消息通过有噪信道传输时会发生错误 而错误概率与译码规则有关 但当一般信道给 定即信道矩阵给定 不论采用什么译码规则 定即信道矩阵给定 不论采用什么译码规则 PEPE 总不会等于或趋于零 除特殊信道外 总不会等于或趋于零 除特殊信道外 一般要求系统的错误概率在的一般要求系统的错误概率在的 10 610 6 10 910 9 范围内 有的甚至要求更低的错误概率 范围内 有的甚至要求更低的错误概率 幻灯片 21 例题例题 99 0 01 0 01 0 99 0 一个二元对称信道一个二元对称信道 选用最佳译码规则选用最佳译码规则 11 00 22 11 abF abF 输入等概率 2 1001 0 E P 幻灯片 22 实际经验说明 只要在发送端把消息重复发几遍 也就是增加消息的传输时间 就可实际经验说明 只要在发送端把消息重复发几遍 也就是增加消息的传输时间 就可 使接收端接收消息使错误减小 从而提高了通信的可靠性 使接收端接收消息使错误减小 从而提高了通信的可靠性 这是一种最简单的重复编码 这种信道可以看作是这是一种最简单的重复编码 这种信道可以看作是 N N 次无记忆扩展信道 简单重复编次无记忆扩展信道 简单重复编 码方法可以纠正一位码元的错误 译错的可能性变小了 因此错误概率降低 码方法可以纠正一位码元的错误 译错的可能性变小了 因此错误概率降低 也可以采用也可以采用 择多译码择多译码 的译码规则 即根据输出端接收序列中的译码规则 即根据输出端接收序列中 0 0 多还是多还是 1 1 多 如果多 如果 有二个以上是有二个以上是 0 0 则译码器就判决为 则译码器就判决为 0 0 如果有两个以上是 如果有两个以上是 1 1 则判决为则判决为 1 1 幻灯片 23 例题例题 重复编码将长度重复编码将长度 n 1n 1 的两个二元序列变成长度的两个二元序列变成长度 n 3n 3 的二元序列 信道输入端有两个码的二元序列 信道输入端有两个码 字字 000000 和和 111111 输出端 由于信道干扰 可能发生错误 输出端 由于信道干扰 可能发生错误 8 8 个可能的输出 个可能的输出 这样的信道看成三次无记忆扩展信道 这样的信道看成三次无记忆扩展信道 其输入是在其输入是在 8 8 个可能出现长度为个可能出现长度为 3 3 的二元序列中选取两个作为消息 许用码字 的二元序列中选取两个作为消息 许用码字 幻灯片 24 续续 信道矩阵为信道矩阵为 3 3 2 2 2 2 2 2 2 2 2 2 2 2 3 3 87654321 2 1 p p pp pp pp pp pp pp pp pp pp pp pp pp p p P 88 87 86 15 84 13 12 11 F F F F F F F F 最大似然译码准则最大似然译码准则 幻灯片 25 平均错误概率平均错误概率 01 0 1033 2 1 1 423 32222223 33 pppp pppppppppppppp P M PaPP aCY ij aCY ijiE 择多译码准则择多译码准则 88 87 86 15 84 13 12 11 F F F F F F F F 01 0 1033ppCpC 23 4232 2 3 33 3 pppp P E 个码元的概率错个码元的概率错 幻灯片 26 发现发现 10 8 7 5 10511 109 1047 105 E E E E Pn Pn Pn Pn 当当 n 重复次数 很大时 重复次数 很大时 PE 很小是可能的 很小是可能的 但是一个新问题出现了 但是一个新问题出现了 n 很大时 信息传输率就会降低 很大时 信息传输率就会降低 幻灯片 27 信息传输率信息传输率 编码后信道的信息传输率 也称码率 表示为编码后信道的信息传输率 也称码率 表示为 比特 比特 码符号 码符号 若传输每个码符号平均需要若传输每个码符号平均需要 t t 秒钟 则编码后单位时间传输的信息量秒钟 则编码后单位时间传输的信息量 比特 比特 秒 秒 此时 此时 M M 是输入消息 许用码字 的个数 是输入消息 许用码字 的个数 logMlogM 表示消息集在等概率条件下每个消息表示消息集在等概率条件下每个消息 码字 携带的平均信息量 比特 码字 携带的平均信息量 比特 N N 是编码后码字的长度 码元的个数 是编码后码字的长度 码元的个数 n logM R nt logM R t 幻灯片 28 运用重复编码方法可计算得出运用重复编码方法可计算得出 PEPE 和和 R R 的关系 表明 尽管可使的关系 表明 尽管可使 PEPE 降低很多 但同时降低很多 但同时 也使传输率降得很低 也使传输率降得很低 11 1 11 1 211 5 1 5 1 25 3 1 3 1 23 11 log 1 t t t t RRMn RRMn RRMn R n M Rn 幻灯片 29 思考思考 N N 增大 增大 PEPE 降低 降低 R R 降低降低 能不能有好办法 能不能有好办法 从理论上 根据香农第二定理 就是有噪信道编码定理可知 能找到一种更好的编码从理论上 根据香农第二定理 就是有噪信道编码定理可知 能找到一种更好的编码 方法 使得方法 使得 PEPE 相当低 而相当低 而 R R 却保持在一定水平 却保持在一定水平 幻灯片 30 例题例题 通过例子可以看出错误概率与编码方法有很大关系 通过例子可以看出错误概率与编码方法有很大关系 采用增大采用增大 n n 并适当增大 并适当增大 M M 和合适的编码方法 既能使和合适的编码方法 既能使 PEPE 降低 又能使信息传输率不降低 又能使信息传输率不 减少 减少 011 101 110 000 001 010 100 000 2 1028 2 E P 2 102 E P 幻灯片 31 为什么为什么 为什么上述编码的平均错误概率不同呢 为什么上述编码的平均错误概率不同呢 引入码字距离引入码字距离 幻灯片 32 码字距离码字距离 长度为长度为 n n 的两个符号序列 码字 的两个符号序列 码字 i i 和和 j j 之间的距离是指之间的距离是指 i i 和和 j j 之间对应位之间对应位 置上不同码元的个数 用符号置上不同码元的个数 用符号 D i D i j j 表示 这种码字距离通常称为汉明距离 表示 这种码字距离通常称为汉明距离 一般在信道编码中码字常用一般在信道编码中码字常用 C cn 1cn 2 c0 C cn 1cn 2 c0 表示 对于二元信道 即对于二元码 表示 对于二元信道 即对于二元码 汉明距离可表达成下述关系式 若令汉明距离可表达成下述关系式 若令 0 1 0 1 0 1 0 1 则则 CiCi 和和 CjCj 的汉明距离为的汉明距离为 D Ci D Ci Cj Cj 式中 式中 为模二和运算 为模二和运算 k i c 0n2n1n iiiii ccccC k j c 0n2n1n jjjjj ccccC n 1k ji kk cc 幻灯片 33 最小距离最小距离 在某一码在某一码 C C 中 任意两个码字的汉明距离的最小值称为该码中 任意两个码字的汉明距离的最小值称为该码 C C 的最小距离 即的最小距离 即 dmin min D Ci dmin min D Ci Cj Cj CiCi Cj Cj CiCi CjCj C C 在任一码在任一码 C C 中 码的最小距离中 码的最小距离 dmindmin 与该码的译码错误概率有关 与该码的译码错误概率有关 上述距离定义是适合任意多元信道和多元码的 但一般常用的是二元离散对称信道和上述距离定义是适合任意多元信道和多元码的 但一般常用的是二元离散对称信道和 二元码 二元码 幻灯片 34 表表 6 16 1 码码 A A码码 B B码码 C C码码 D D码码 E E 码字码字000 111 000 011 101 110 000 001 100 010 00000 01101 10111 11010 000 001 010 011 100 101 110 111 消息数消息数 M M24448 码的最小距码的最小距 离离 d d minmin 32131 信息传输率信息传输率1 32 32 32 51 R R 错误概率错误概率 PEPE 最大似然最大似然 3 10 42 10 22 28 10 27 8 10 43 10 2 幻灯片 35 通过五种码组的计算 在表通过五种码组的计算 在表 6 16 1 中可以看出 中可以看出 dmindmin 越大 越大 PEPE 越小 在越小 在 M M 相同的情况相同的情况 下也有下也有 dmindmin 越大 越大 PEPE 越小 越小 码码 C C 中最小距离越大 受干扰后 越不容易把一个码字传错 成为另一码字 因而错中最小距离越大 受干扰后 越不容易把一个码字传错 成为另一码字 因而错 误概率小 若码误概率小 若码 C C 的最小距离小 受干扰后很容易把一码字变成另一码字 因而错误的最小距离小 受干扰后很容易把一码字变成另一码字 因而错误 概率大 概率大 在编码选码字时 要使码字之间的距离越大越好 在编码选码字时 要使码字之间的距离越大越好 幻灯片 36 用汉明距离表示最大似然译码准则用汉明距离表示最大似然译码准则 选择译码函数选择译码函数 F j F j a a a a C C j j YnYn 使满足使满足 D a D a j j D i D i j j i i C C i i a a 即满足即满足 D a D a j j Dmin i Dmin i j j i i C C i i a a 上式又称为最小距离译码准则 上式又称为最小距离译码准则 在二元对称信道中最小距离译码准则等于最大似然译码准则 在任意信道中也可采用在二元对称信道中最小距离译码准则等于最大似然译码准则 在任意信道中也可采用 最小距离译码准则 但它不一定等于最大似然译码准则 最小距离译码准则 但它不一定等于最大似然译码准则 幻灯片 37 汉明距离表示平均译码错误概率汉明距离表示平均译码错误概率 在二元对称无记忆信道中 平均译码错误概率也可用汉明距离来表示 在二元对称无记忆信道中 平均译码错误概率也可用汉明距离来表示 设输入码字数为设输入码字数为 M M 并设输入等概率分布 并设输入等概率分布 平均译码错误概率 平均译码错误概率 或者或者 其中其中 ij ij n Dn j i D aC Y ijE pp M 1 p M 1 p j j n Dn j D Y ijE pp M 1 1p M 1 1p j j aDD 幻灯片 38 在二元信道中最大似然译码准则可表述为 当收到在二元信道中最大似然译码准则可表述为 当收到 j 后 译成与之距离 汉明距离 后 译成与之距离 汉明距离 为最近的输入码字为最近的输入码字 a 也就是把 也就是把 j 译成与它最相邻的那个发送码字译成与它最相邻的那个发送码字 a 可使平均 可使平均 错误概率错误概率 PE 达到最小 如图达到最小 如图 6 8 所示 所示 幻灯片 39 汉明距离表示平均译码错误概率的公式汉明距离表示平均译码错误概率的公式 6 25 6 25 说明 在说明 在 M M 和和 n n 不变的情况下 即保持不变的情况下 即保持 一定信息传输率一定信息传输率 R R 的前提下 选择不同的编码方法 可取得不同的的前提下 选择不同的编码方法 可取得不同的 Dij D Dij D j j 和和 而使 而使 PEPE 不同 不同 所以可以选择这样的编码方法 对选择的每一个码字所以可以选择这样的编码方法 对选择的每一个码字 a a 都与某一特定接收序列都与某一特定接收序列 j j 的的 距离尽可能近 距离尽可能近 尽量小 又使其他码字尽量小 又使其他码字 i i a a 与这接收序列与这接收序列 j j 的距离的距离 尽可能地远 尽可能地远 D i D i j j 尽量大 尽量大 应尽量设法使选取的应尽量设法使选取的 M M 个码字中任意两两不同码字的距离个码字中任意两两不同码字的距离 D i D i k k 尽量大 就尽量大 就 可以做到保持一定信息传输率可以做到保持一定信息传输率 R R 而使 而使 PEPE 尽可能地小 尽可能地小 j j aDD j aD 幻灯片 40 在有噪信道中 传输的平均错误概率在有噪信道中 传输的平均错误概率 PEPE 与各种编 译码方法有关 与各种编 译码方法有关 编码可采用选择编码可采用选择 M M 个消息所对应的码字之间最小距离个消息所对应的码字之间最小距离 dmindmin 尽可能增大的编码方法 尽可能增大的编码方法 译码采用将接收序列译码采用将接收序列 j j 译成与之距离最近的那个码字译成与之距离最近的那个码字 a a 的译码规则 则只要码长的译码规则 则只要码长 n n 足够长时 合适地选择足够长时 合适地选择 M M 个消息所对应的码字 就可以使错误概率很小 而信息传输个消息所对应的码字 就可以使错误概率很小 而信息传输 率保持一定 率保持一定 幻灯片 41 6 46 4 有噪信道编码定理有噪信道编码定理 有噪信道编码定理又称为香农第二定理 是信息论的基本定理之一 有噪信道编码定理又称为香农第二定理 是信息论的基本定理之一 定理定理 6 46 4 设离散无记忆信道设离散无记忆信道 X p y x Y X p y x Y P y x P y x 为信道传递概率 其信道容量为为信道传递概率 其信道容量为 C C 当信息传输率 当信息传输率 R R C C 时 只要码长时 只要码长 n n 足够长 总可以在输入足够长 总可以在输入 XnXn 符号集中找到符号集中找到 M M 2nR 2nR 个码字组成的一组码个码字组成的一组码 2nR n 2nR n 和相应的译码规则 使译码的平均错误概率任意小和相应的译码规则 使译码的平均错误概率任意小 PE 0 PE 0 幻灯片 42 有噪信道编码定理方法中的基本思路有噪信道编码定理方法中的基本思路 连续使用信道多次 即在连续使用信道多次 即在 n n 次无记忆扩展信道中讨论 以便使大数定律有效 次无记忆扩展信道中讨论 以便使大数定律有效 随即地选取码字 也就是在随即地选取码字 也就是在 XnXn 和符号序列集中随机地选取经常出现的高概率序列作为和符号序列集中随机地选取经常出现的高概率序列作为 码字 码字 采用最大似然译码准则 也就是将接收序列译成与其距离最近的那个码字 采用最大似然译码准则 也就是将接收序列译成与其距离最近的那个码字 在随机编码的基础上 对所有的码字计算其平均错误概率 当在随机编码的基础上 对所有的码字计算其平均错误概率 当 n n 足够大时 此平均错足够大时 此平均错 误概率趋于零 由此证明得至少有一种好码存在 误概率趋于零 由此证明得至少有一种好码存在 幻灯片 43 定理定理 6 56 5 有噪信道编码逆定理 定理有噪信道编码逆定理 定理 6 46 4 的逆定理 设离散无记忆信道的逆定理 设离散无记忆信道 X p y x Y X p y x Y 其信道容量为其信道容量为 C C 当信息传输率 当信息传输率 R CR C 则无论码长则无论码长 n n 多长 总也找不到一种编码 多长 总也找不到一种编码 M M 2nR n2nR n 是译码错误概率任意小 是译码错误概率任意小 幻灯片 44 定理定理 6 66 6 对于限带高斯白噪声加性信道 噪声功率为对于限带高斯白噪声加性信道 噪声功率为 PnPn 带宽为 带宽为 w w 信号平均功率受限为 信号平均功率受限为 PsPs 则 则 当当 R C R C 总可以找到一种信道编码在信道中以信息传输率 码率 总可以找到一种信道编码在信道中以信息传输率 码率 R R 传输信息 而使平均错误概率任意小 传输信息 而使平均错误概率任意小 当当 R R C C 找不到任何信道编码 在信道中以 找不到任何信道编码 在信道中以 R R 传输信息而使平均错误概率任意小 传输信息而使平均错误概率任意小 n s p p 1Wlog 幻灯片 45 任何信道的信道容量是一个明确的分界点 当取分界点以下的信息传输率时 任何信道的信道容量是一个明确的分界点 当取分界点以下的信息传输率时 PEPE 以以 指数趋于零 当取分界点以上的信息传输率时 指数趋于零 当取分界点以上的信息传输率时 PEPE 以指数趋于以指数趋于 1 1 因此 在任何信道 因此 在任何信道 中信道容量是可达的 最大的可靠信息传输率 中信道容量是可达的 最大的可靠信息传输率 幻灯片 46 香农第二定理也只是个存在定理 说明错误概率趋于零的好码是存在的 香农第二定理也只是个存在定理 说明错误概率趋于零的好码是存在的 但从实际观点看 定理是不令人满意的 因为在定理的证明过程中 是完全但从实际观点看 定理是不令人满意的 因为在定理的证明过程中 是完全 随机地随机地 选择一组码的 选择一组码的 这个码是完全无规律的 因此这码无法具体构造和译码 当这个码是完全无规律的 因此这码无法具体构造和译码 当 n n 很大时 这码构成的译很大时 这码构成的译 码表 式码表 式 6 646 64 阵列 就非常庞大 也就无法使用和实现 阵列 就非常庞大 也就无法使用和实现 尽管如此 信道编码定理仍然具有根本性的重要意义 有助于指导各种通信系统的设尽管如此 信道编码定理仍然具有根本性的重要意义 有助于指导各种通信系统的设 计 有助于评价各种通信系统及编码的效率 计 有助于评价各种通信系统及编码的效率 幻灯片 47 6 56 5 联合信源信道编码定理联合信源信道编码定理 香农第二定理说明在任意信道中进行数据传输 必须使信息传输率小于信道容量 即香农第二定理说明在任意信道中进行数据传输 必须使信息传输率小于信道容量 即 R R C C 才能可靠地传输数据 香农第一定理指出要进行无失真数据压缩必须 才能可靠地传输数据 香农第一定理指出要进行无失真数据压缩必须 R R H H 联合这两个定理 会有个问题 若信源通过信道传输 要做到有效和可靠 无错 联合这两个定理 会有个问题 若信源通过信道传输 要做到有效和可靠 无错 误 地传输 是否误 地传输 是否 H H C C 是充分和必要的条件 是充分和必要的条件 幻灯片 48 从香农的两个定理看出 要做到有效和可靠地传输信息 可以将通信系统设计成两部从香农的两个定理看出 要做到有效和可靠地传输信息 可以将通信系统设计成两部 分的组合 即信源编码和信道编码两部分 分的组合 即信源编码和信道编码两部分 首先 通过信源编码 用尽可能少的信道符号来表达信源 也就是对信源数据用最有首先 通过信源编码 用尽可能少的信道符号来表达信源 也就是对信源数据用最有 效的表达方式表达 尽可能减少编码后的数据的剩余度 效的表达方式表达 尽可能减少编码后的数据的剩余度 然后 针对信道 对信源编码后所得的数据独立地设计信道编码 也就是适当增加一然后 针对信道 对信源编码后所得的数据独立地设计信道编码 也就是适当增加一 些剩余度 使能纠正和克服信道中引起的错误和干扰 些剩余度 使能纠正和克服信道中引起的错误和干扰 这两部分编码是分别独立考虑的 这两部分编码是分别独立考虑的 幻灯片 49 两部分独立编码的方法在实际通信系统设计中有重要的意义 实际中都是数字通信系两部分独立编码的方法在实际通信系统设计中有重要的意义 实际中都是数字通信系 统 信道是共同公用的数字信道 一般为二元信道 针对各自信源的不同特点 进行统 信道是共同公用的数字信道 一般为二元信道 针对各自信源的不同特点 进行 不同的数据压缩 用最有效的二元码来表达这些不同的信源 而对于共同传输的数字不同的数据压缩 用最有效的二元码来表达这些不同的信源 而对于共同传输的数字 信道而言 输入端只是一系列二元码 信道编码只需针对信道特性而进行 不用考虑信道而言 输入端只是一系列二元码 信道编码只需针对信道特性而进行 不用考虑 不