《信息论》第五章

《《信息论》第五章》由会员分享，可在线阅读，更多相关《《信息论》第五章（24页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章 信道编码信道编码1 错误概率与译码规则错误概率与译码规则 错误概率与编码方法错误概率与编码方法 信道编码定理信道编码定理本章主要内容2信道编码信道编码 目的：提高抗干扰能力，使差错率最小。目的：提高抗干扰能力，使差错率最小。 实质：增加冗余度，扩大信号空间，增大信实质：增加冗余度，扩大信号空间，增大信号间距离。号间距离。 重要意义：通过信道编码的方法，可以用不重要意义：通过信道编码的方法，可以用不可靠的信道实现可靠的传输。可靠的信道实现可靠的传输。信信 源源 编编 码码 器器信信 源源 译译 码码 器器信信 道道 编编 码码 器器信信 道道 译译 码码 器器信源信源信宿信宿信道信

2、道u uy yx x干扰干扰3 编码器：编码函数，完成映射编码器：编码函数，完成映射编码器的输入：编码器的输入：码字分别为：码字分别为： 编码后的信息传输率：码字长为编码后的信息传输率：码字长为 n n物理意义：每个码元所能携带的最大信息量。物理意义：每个码元所能携带的最大信息量。 好码：在相同的差错控制（纠错能力）下，好码：在相同的差错控制（纠错能力）下， 越大，则相应的码越好。越大，则相应的码越好。问题：问题：R R 能否无限制提高能否无限制提高? ? 如何衡量纠错能力？如何衡量纠错能力？4例：二元对称信道例：二元对称信道译码规则对错误概率的影响译码规则对错误概率的影响 译码器译码器A A

3、译码规则：译码规则： 接收符号接收符号译码译码译码译码0 00 01 11 1错误概率与译码规则错误概率与译码规则5分析分析则在此译码器下，平均错误概率为（设输入为等概则在此译码器下，平均错误概率为（设输入为等概 ）发发发发出符号出符号接收符号接收符号译码译码译码译码正确概率正确概率错误错误错误错误 概率概率0 0 0 00 01/31/30 01 11 1p pe e(0)(0) = 2/3= 2/31 11 11 11/31/31 10 00 0p pe e(1)(1) = 2/3 = 2/3 6 译码器译码器B B译码规则：译码规则：分析分析则在此译码器下，平均错误概率为（设输入为等概则

4、在此译码器下，平均错误概率为（设输入为等概 ）接收符号接收符号译码译码译码译码0 01 11 10 0发发发发出符号出符号接收符接收符z z号号译码译码译码译码正确概率正确概率错误错误错误错误 概率概率0 0 0 01 1p pe e(0)(0) = 1/3= 1/30 01 10 0p(0)= 2/3p(0)= 2/31 11 10 0p pe e(1)(1) = 1/3= 1/31 10 01 1p(1)= 2/3p(1)= 2/37结论：错误概率不仅与信道的统计特性有关，而且与结论：错误概率不仅与信道的统计特性有关，而且与 译译码规则有关。码规则有关。 我们来定义译码规则我们来定义译码规

5、则 设信道的输入符号集为设信道的输入符号集为X X= a ai i ，i i =1=1，2 2， ，r r ； 输出符号集为输出符号集为Y Y= = b bj j ，j j =1 =1，2 2， ，s s。 制定译码规则就是设计一个单值函数制定译码规则就是设计一个单值函数F F（b bj j），），它对于它对于 每一个输出符号每一个输出符号b bj j确定一个唯一的输入符号确定一个唯一的输入符号a ai i与其对应与其对应 。 即即 F F（b bj j）= = a ai ii i =1=1，2 2， ，r r j j =1 =1，2 2， ，s s 注：对于同一有噪信道共有注：对于同一有噪信

6、道共有 r r s s 种种译码规则可供选择。译码规则可供选择。8例例5.15.1：可设计译码准则可设计译码准则 译码准则译码准则 A A： 译码准则译码准则 B B：译码规则总数为：译码规则总数为： r r s s = = 27279目标：在目标：在 r r s s个规则中找到理想的一个。个规则中找到理想的一个。原则：使平均错误概率最小。原则：使平均错误概率最小。平均错误概率平均错误概率 P PE E 如何计算？如何计算？收到符号收到符号b bj j 条件下译码正确的条件概率为条件下译码正确的条件概率为10平均错误概率平均错误概率P PE E ： 条件错误概率条件错误概率 对输出空间对输出空

7、间Y Y 取统计平均取统计平均物理意义：译码后平均收到一个符号所产生的错误的大物理意义：译码后平均收到一个符号所产生的错误的大 小小要使要使P PE E 最小就应该选择最小就应该选择p p F F( (b bj j)|)|b bj j 为最大为最大 。11最大后验概率准则（最小错误概率准则）最大后验概率准则（最小错误概率准则）选择译码函数：选择译码函数：译码：将每一个输出符号译成具有最大后验概率译码：将每一个输出符号译成具有最大后验概率 的的 输入符号，则信道的错误概率此时最小。输入符号，则信道的错误概率此时最小。分析：分析：12则则最大后验概率准则可另表述为最大后验概率准则可另表述为选择译码

8、函数选择译码函数 使成立使成立最大似然译码准则最大似然译码准则（最大后验概率准则最大后验概率准则特例）特例） 设输入符号的先验概率等概，选择译码函数设输入符号的先验概率等概，选择译码函数使成立使成立译码：当收到译码：当收到 b bj j 后后，译成信道矩阵中第，译成信道矩阵中第 j j 列中最大列中最大 的元素所对应的信源符号。的元素所对应的信源符号。13最大后验概率准则最大后验概率准则：依赖于先验概率：依赖于先验概率p p( (a ai i) )和信道和信道 传递概率传递概率p p( (b bj j| |a ai i) )选定译码函数。选定译码函数。最大似然译码准则最大似然译码准则：直接从信

9、道矩阵的传递概：直接从信道矩阵的传递概 率中去选定译码函数。率中去选定译码函数。当先验概率当先验概率p p( (a ai i) )为等概率分布时，最大似然译码为等概率分布时，最大似然译码 准则与最大后验概率准则等价。准则与最大后验概率准则等价。平均错误概率平均错误概率P PE E与译码规则（译码函数）有关。与译码规则（译码函数）有关。 而译码规则又由信道特性来决定。而译码规则又由信道特性来决定。费诺不等式费诺不等式 HH（X X | | Y Y） HH（P PE E）+ + P PE E log (log (r r1)1)14重复发送重复发送大数判决规则大数判决规则 信息数据 编码编码 1编码

10、编码 2000000000000000000000001000000111001001001010000111000010010010011000111111011011011100111000000100100100101111000111101101101 110111111000110110110111111111111111111111错误概率与编码方法错误概率与编码方法15编码编码1 1：将每个码元重复三次：将每个码元重复三次 纠正任一位上的错误纠正任一位上的错误设码字记为设码字记为 由编码方法知由编码方法知“择多译码择多译码”规则的依据规则的依据： 连续出现两个错误的连续出现两个错

11、误的 概率概率 远远小于出现一个错误的概率。远远小于出现一个错误的概率。 16编码编码2 2：将每个码字重复三次：将每个码字重复三次 纠正任一位上的错误纠正任一位上的错误 纠正连续三位和三位以下码元的错误纠正连续三位和三位以下码元的错误由编码方法知由编码方法知例例 发送的码字为发送的码字为 0 1 0 0 1 0 0 1 00 1 0 0 1 0 0 1 0干扰后收到为干扰后收到为 0 1 1 1 0 0 0 1 00 1 1 1 0 0 0 1 0此时此时17以上这两种重复码编码后的信息传输率相同为以上这两种重复码编码后的信息传输率相同为但纠错能力不同，平均但纠错能力不同，平均错误概率错误概

12、率不同。不同。如何选择编码规则呢？如何选择编码规则呢？例：对例：对 4 4个等概消息编码个等概消息编码M = 4 第种M = 4 第种0 0 0 0 1 1 1 0 1 1 1 00 0 0 0 0 1 0 1 0 1 0 018M = 4 第种0 0 0 0 1 1 1 0 1 1 1 0最大似然译码规则下，计算平均错误概率最大似然译码规则下，计算平均错误概率P PE E= =？0.010.990.990.0119M = 4 第种 0 0 0 0 0 1 0 1 0 1 0 020在选择编码规则时，要使码字之间的最小距离在选择编码规则时，要使码字之间的最小距离D Dminmin越越大大越好。

13、越好。结论：错误概率与编码方法有关。结论：错误概率与编码方法有关。21码码 A码码 B码码 C码码 D码码 E 码码字000 111000 011 101 110000 001 010 10000000 01101 10111 11010000 001 010 011 100 101 110 111 码码字长长度 n33353 消息数 M24448 码码的最小距离 Dmin32131 信息传输传输 速率R （比特/符号）1/32/32/32/51错误错误 概率PE （最大似然译码译码 ）310-4210-22.2310-27.810-4310-222能不能找到一种编码方法使能不能找到一种编码方

14、法使P PE E相当低（可靠性高），而相当低（可靠性高），而R R却保持在却保持在 一定水平（有效性较高）呢？一定水平（有效性较高）呢？定理定理5.1 5.1 香农第二定理（信道编码定理）香农第二定理（信道编码定理） 设某信道有设某信道有r r个输入符号，个输入符号，s s个输出符号，信道容量为个输出符号，信道容量为C C。 当信息传输率当信息传输率R RC C时，只要码长时，只要码长n n足够长，总可以在输入足够长，总可以在输入 的集合中找到的集合中找到MM个码字（代表个码字（代表MM个等可能性的消息）组成个等可能性的消息）组成 的一个码（的一个码（ MM22n n( (C -C -) )，而，而 是一任意小的正数是一任意小的正数 ）和相应的）和相应的 译码规则，使信道输出的错误概率译码规则，使信道输出的错误概率P PE E任意小。任意小。 定理定理5.2 5.2 （信道编码逆定理）设某信道有（信道编码逆定理）设某信道有r r个输入，个输入，s s个输个输 出，信道容量为出，信道容量为C C，令，令 为任意小的正数。若选用码字个数为任意小的正数。若选用码字个数 M = M = 2 2n n( (C +C +) )，则无论则无论n n多大也不能找到一种编码，使译码错多大也不能找到一种编码