第5章-有噪信道编码

1、第第5章章有噪信道编码有噪信道编码 前一章已经从理论上讨论了在无噪无损信道上，只要对信源进行适当的编码, 总能以最大信息传输率C （信道容量）无差错的传输信息。 但是一般信道总存在噪声或干扰, 信息传输会造成损失，那么在有噪信道中怎么能使消息通过传输后发生的错误最少？在有噪信道中无错误传输的可达的最大信息传输率是多少？这就是本章所要研究的问题，即研究通信的可靠性问题。第第5章章 有噪信道编码有噪信道编码 内容提要本章介绍了信道编码和译码的基本概念，介绍了两种常用的译码准则：最大后验概率译码准则和极大似然译码准则,还介绍了在这两种译码准则下错误概率的计算方法。本章还介绍了信道编码定理以及信息论中

2、的一个重要不等式Fano不等式。5 51 1 信道编码的基本概念信道编码的基本概念 将信道用图5-1所示的模型表示。信道编码器信道信道译码器uxyX X图5-1 信道模型 信源输出序列u，经信道编码器编成码字x = f (u) 并输入信道，由于干扰，信道输出y，信道译码器对y估值得 = F (y) 。 X X信源编码以提高传输效率传输效率作为主要考虑因素，信道编码以提高传输可靠性传输可靠性作为主要考虑因素。这一章讨论信道编码的一些基本概念及信道编码定理。【例】给定二元对称信道，信道固有错误概率为【例】给定二元对称信道，信道固有错误概率为p（p 0.5）01011 - p1 - ppp编码规则：

3、为提高可靠性，每个信道符号重复三次发送。编码规则：为提高可靠性，每个信道符号重复三次发送。译码规则：择多译码，即信宿方收到的三个符号中有两个或三个为译码规则：择多译码，即信宿方收到的三个符号中有两个或三个为1，就将此，就将此次接收符号判决为次接收符号判决为1；若三个符号中有两个或三个为；若三个符号中有两个或三个为0，就将此次接，就将此次接收符号判决为收符号判决为0。下面为重复编码传输示意图，计算错误概率下面为重复编码传输示意图，计算错误概率pe。书上例题5.1信源输出序列为：信源输出序列为：1, 0, 1, 1u 信道输入序列为：信道输入序列为：111, 000, 111, 111x 由于由于

4、p的存在，使得传输出错，故信道输出为：的存在，使得传输出错，故信道输出为：111, 001, 001, 000y 根据译码规则，信道估值输出：根据译码规则，信道估值输出：1, 0, 0, 0y 信道错误概率：假设信道离散无记忆，即信道错误概率：假设信道离散无记忆，即31( / )(/)iiip y xp yx 错误概率为：错误概率为：22332333(1)32epC ppC pppp重复编码的结果使错误概率下降。重复编码的结果使错误概率下降。书书5-15-1式有问题式有问题n书上例题5.2【例例5.3】 逆重复码逆重复码 离散无记忆二进制对称信道，固有误码率为p (p0.5)，信源输出序列为三

5、位二进制数字。编码规则：为提高传输效率，仅向信道发送一位，预先将信源输出序列进行择多编码:00000000011101010011101111001110判决输出接收发送原序列pp图5-3 逆重复编码传输示意图 译码规则：将接收的一位符号重复三次译出，即若接收到1就译码为111，即若接收到0就译码为000。信源输出的三位符号中有两位或3位是1，信源序列编码为1，若三位符号中有两位或3位是0，就将此信源序列编码为0。1-p0 p 1011-p p 计算差错概率pe ：分二步进行： （1）先设p = 0，计算这种编码方法带来的固有错误p1信道输入符号集X = 000,001,010,011,100

6、,101,110,111判决输出符号集Y = 000,111译码规则因为后验概率 则出错概率 111)111110101011(000)100010001000(，FF41)111111()41)000000()y yx xy yx x（43411)111()(43411)000()(epyepepyep假设8组输入序列是等概发送的，由于信道的对称性，两个估值序列也是等概分布的，则每个序列的平均错误概率为 ，误比特率 。（2）再设p0，计算由于信道噪声引起的错误概率p2因为每个序列有三位二进制数字，但只发送一位，这一位的出错概率为p，故序列差错概率为p，误比特率 。（3）总差错概率（误比特率）

7、：43)111(5 . 0)000(5 . 0epep4143311ppp312ppppe314121n【例例5.4】 奇偶校验码奇偶校验码 在信息序列后面加上一位校验位，使之模2和等于1，这样的编码称为奇校验码；若使模2和等于0，这样的编码就称为偶校验码，即每个码矢中1的个数固定为奇数或偶数。n关于奇偶校验关于奇偶校验 n奇偶校验原理奇偶校验原理：通过计算数据中“1”的个数是奇数还是偶数来判断数据的正确性。在被校验的数据后加一位校验位或校验字符用作校验码实现校验。n校验位的生成方法 n奇校验奇校验：确保整个被传输的数据中“1”的个数是奇数个，即载荷数据中“1”的个数是奇数个时校验位填“0”，

8、否则填“1”；n偶校验偶校验：确保整个被传输的数据中“1”的个数是偶数个，即载荷数据中“1”的个数是奇数个时校验位填“1”，否则填“0”。n 使用奇偶校验码校验的特点：使用奇偶校验码校验的特点：n奇偶校验能够检测出信息传输过程中的部分误码（1位误码能检出，2位及2位以上误码不能检出），同时，它不能纠错。在发现错误后，只能要求重发。但由于其实现简单，仍得到了广泛使用。n 校验处理过程简单，但如果数据中发生多位数据错误就可能检测不出来，更检测不到错误发生在哪一位；主要应用于低速数字通信系统中，一般异步传输模式选用偶校验，同步传输模式选用奇校验。信道编码的目的：提高传输可靠性。有噪信道编码定理，即香

9、农第二定理，是信道编码的理论基础。本章重点介绍通过信道编码通信系统所能达到的极限性能，不涉及编码技术的具体实现，以及两种常用的译码准则。信道编码就是按一定的规则给信源输出序列增加某些冗余符号，使其变成满足一定数学规律的码序列（或 码字），再经信道进行传输。（具有纠错能力）信道译码就是按与编码器同样的数学规律去掉接收序列中的冗余符号，恢复信源消息序列。传输信道传输信道插插入入冗冗余余信信息息抽抽出出冗冗余余信信息息编码编码译码译码还原序列还原序列发送序列发送序列编码编码译码译码发送序列发送序列还原序列还原序列传输信道传输信道插插入入冗冗余余信信息息抽抽出出冗冗余余信信息息编码编码译码译码第5.1

10、节 错误概率与译码规则第5.2节 错误概率与编码方法第5.3节 有噪信道编码定理主要内容n 前一章已经从理论上讨论了, 对于无噪无损信道只要对信源进行适当的编码, 总能以信道容量无差错的传递信息。n 但是一般信道总会存在噪声和干扰, 那么在有噪信道中进行无错传输可以达到的最大信息传输率是多少呢？这就是本章所要讨论的问题。n 本章的核心是香农第二定理。第五章 有噪信道编码 第5.1节 错误概率与译码规则 有噪信道传输消息是会发生错误的. 为了减少错误, 提高通信可靠性, 就必须 1) 分析错误概率与哪些因素哪些因素有关; 2) 有没有办法控制, 如何控制; 3) 能控制到什么程度等问题. 前边已

11、经讨论过, 错误概率与信道的统计特性有关, 但并不是唯一相关的因素, 译码方法的选择也会影响错误率。 信道统计特性信道统计特性信道统计特性用信道传递矩阵来描述, 该矩阵确定了哪些是正确传递概率, 哪些是错误传递概率. 译码规则译码规则 通信过程并非到信道输出端就结束, 还要经过译码过程(或判决过程)才到达消息的终端(收信者).第5.1节 错误概率与译码规则例: 有一个BSC信道, 如右图 01011/31/32/32/3若收到“0”译作“0”, 收到“1”译作“1”, 则平均错误概率为:2(0) (1|0)(1) (0|1)3EPpppp反之, 若收到“0”译作“1”, 收到“1”译作“0”,

12、 则平均错误概率为1/3. 可见, 错误概率与译码准则错误概率与译码准则有关有关. 第5.1节 错误概率与译码规则n极端的例子-书P103，图5.4-强噪信道译码规则定义译码规则译码规则:输入符号集: A=ai, i=1,2,r;输出符号集: B=bj, j=1,2,s;译码规则译码规则: 设计函数F(bj), 它对于每个输出符号bj确定一个唯一的输入符号ai与其对应(单值函数). 即F(bj)=ai译码规则的选择依据由于任何输出符号bj都可以译成任何输入符号ai, 即s个输出符号中的每一个都可以译成r个输入符号中的任一个，所以有rs种译码规则. 译码规则的选择应该根据什么准则？译码规则的选择

13、依据选择依据: 使平均错误概率最小.译码准则可以为: A: 和B:112233( )()( )F baF baF ba112332( )()( )F baF baF ba1230.50.30.20.20.30.50.30.30.4aPaa例5.1:有一离散单符号信道，信道矩阵为平均错误概率有了译码规则F(bj)=ai以后, 条件正确概率条件正确概率: 收到bj译码为ai的概率pF(bj)|bj=p(ai|bj) 条件错误概率条件错误概率: 收bj后推测发出除ai之外符号的概率p(e|bj)=1-p(ai|bj)=1-pF(bj)|bj平均错误译码概率平均错误译码概率:11() ( |)()1(

14、|)ssEjjjijjjPp b P e bp bP a b最小错误概率译码准则问题: 如何选择p(ai|bj)? 使p(e|bj)最小, 就应选择pF(bj)|bj为最大, 即选择译码函数F(bj)=a*，并使之满足条件: p(a*|bj)p(ai|bj) aia* 如果采用这样一种译码函数，它对于每一个输出符号均译成具有最大后验概率的那个输入符号，则信道错误概率就能最小；即收到符号bj以后译成具有最大后验概率的输入符号a*. 该译码准则称为“最大后验概率译码准则最大后验概率译码准则(MAP，Maximum a Posteriori) ”或“最小错误概率译码准则最小错误概率译码准则”.也叫最

15、大联合概率译也叫最大联合概率译码准则。码准则。对每个输出符号均译成具有最大后验概率的那个输入符号，则信道错误概率就能最小。 *,jaA bBiaA（1）联合概率()() (/)() (/)ijijijijP abP a P baP b P ab(/)jiP ba其中称为前向概率，描述信道的噪声特性有时也把 称为先验概率，把 称为后验概率( )iP a（2）输出符号的概率11()( ) (/)()rrjijiijiiP bp a p bap ab（3）后验概率()(/)()ijijjP abP abP b(/)ijP ab1(/)1rijiP ab 表明输出端收到任一符号，必定是输入端某一符号输

16、入所致n我们一般已知信道传递概率p(bj|ai)与输入符号先验概率p(ai), 所以根据贝叶斯定律, 上式也可以写成n一般p(bj) 0.这样最大后验概率准则就表示为: 选择译码函数F(bj)=a*,使满足p(bj|a*)p(a*)p(bj|ai)p(ai), 也即p(a*bj)p(aibj).最大联合概率译码准则最大联合概率译码准则*(|) ()(|) ( )()()for,jjiijjiijP baP aP ba P aP bP baA aa bBp(a*|bj)p(ai|bj)等效于最大联合概率译码准则等效于最大联合概率译码准则最大似然译码准则最大似然译码准则(maximum likel

17、ihoodML准则准则)前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从错误概率最小角度，该译码前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从错误概率最小角度，该译码准则是最好的。准则是最好的。在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道的转移概率，而不知道信源在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道的转移概率，而不知道信源的分布，故无法计算全概率，故无法采用最大后验概率译码准则进行译码。的分布，故无法计算全概率，故无法采用最大后验概率译码准则进行译码。 n如果输入符号等概发生, 则选择译码函数F(bj)=a*,并满足p(bj|a*

18、)p(bj|ai)该译码规则称为: 最大似然译码准则最大似然译码准则. 该准则表示收到bj后, 在信道矩阵的第j列, 选择最大的值对应输入符号a*作为译码输出.*(|) ()(|) ( )()()for,jjiijjiijP baP aP ba P aP bP baA aa bB平均错误概率 根据译码规则, 可进一步写出平均错误概率PE, 即而平均正确概率为,( |) ()1 ()| ()1 ()() ()()()EjjjjjYYjjijjjYX YYijjijYXYY XaPp e bp bp F bbp bp F b bp abp F b bp abP a bP ab 1 ()EEjjjY

19、YPPp F b bP a b 平均错误概率也可写成:,( )( )(|)()(|) ( )( )( )1)EijjiiXa YXa YiXjijYiieXiEeXp baF baPp abp ba p ap ap a pPPr如果先验概率p(ai)相等, 则:平均错误概率先对行求和，除去译码规则中所对应的概率，然后是各行之和几点说明1）当输入符号等概时，最大似然准则等价于最大后验概率准则。2）该准则可直接从信道传递矩阵中选定译码函数，即收到bj后，译成信道矩阵p中第j列中最大那个元素所对应的信源符号。3）该准则本身不再依赖于先验概率p(ai)，但当输入符号等概时，它使平均错误概率PE最小。4

20、）当输入符号等概或先验概率未知时，采用此准则。复习和捋顺关系n信道编码就是按一定的规则给信源输出序列增加某些冗余符号，使其变成满足一定数学规律的码序列（或 码字），再经信道进行传输。（具有纠错能力）n信道译码就是按与编码器同样的数学规律去掉接收序列中的冗余符号，恢复信源消息序列。n平均错误概率与两个因素有关n1、信道的统计特性（传递矩阵） n2、译码规则n主要内容和捋顺关系：主要内容和捋顺关系：n一、译码规则；一、译码规则；n二、如何选择译码规则；二、如何选择译码规则；n三、两种译码准则三、两种译码准则- -最大后验概率译码准则最大后验概率译码准则n四、两种译码准则四、两种译码准则- -最大似

21、然译码准则最大似然译码准则一、译码规则；定义译码规则译码规则:输入符号集: A=ai, i=1,2,r;输出符号集: B=bj, j=1,2,s;译码规则译码规则: 设计函数F(bj), 它对于每个输出符号bj确定一个唯一的输入符号ai与其对应(单值函数). 即F(bj)=ai由于任何输出符号bj都可以译成任何输入符号ai, 即s个输出符号中的每一个都可以译成r个输入符号中的任一个，所以有rs种译码规则. 译码准则可以为: A: 和B:112233( )()( )F baF baF ba112332( )()( )F baF baF ba1230.50.30.20.20.30.50.30.30

22、.4aPaa例5.1:有一离散单符号信道，信道矩阵为二、如何选择译码规则；n译码规则的选择应该根据什么准则？n译码规则的选择依据选择依据: 使平均错误概率最小.n平均错误概率如何计算？平均错误概率有了译码规则F(bj)=ai以后, 条件正确概率条件正确概率: 收到bj译码为ai的概率pF(bj)|bj=p(ai|bj) 条件错误概率条件错误概率: 收bj后推测发出除ai之外符号的概率p(e|bj)=1-p(ai|bj)=1-pF(bj)|bj平均错误译码概率平均错误译码概率:11() ( |)()1(|)ssEjjjijjjPp b P e bp bP a b三、两种译码准则-最大后验概率译码

23、准则最小错误概率译码准则问题: 如何选择p(ai|bj)? 使p(e|bj)最小, 就应选择pF(bj)|bj为最大, 即选择译码函数F(bj)=a*，并使之满足条件: p(a*|bj)p(ai|bj) aia* 如果采用这样一种译码函数，它对于每一个输出符号均译成具有最大后验概率的那个输入符号，则信道错误概率就能最小；即收到符号bj以后译成具有最大后验概率的输入符号a*. 该译码准则称为“最大后验概率译码准则最大后验概率译码准则(MAP，Maximum a Posteriori) ”或“最小错误概率译码准则最小错误概率译码准则”.也叫最大联合概率译也叫最大联合概率译码准则。码准则。对每个输出

24、符号均译成具有最大后验概率的那个输入符号，则信道错误概率就能最小。 *,jaA bBiaAn我们一般已知信道传递概率p(bj|ai)与输入符号先验概率p(ai), 所以根据贝叶斯定律, 上式也可以写成n一般p(bj) 0.这样最大后验概率准则就表示为: 选择译码函数F(bj)=a*,使满足p(bj|a*)p(a*)p(bj|ai)p(ai), 也即p(a*bj)p(aibj).最大联合概率译码准则*(|) ()(|) ( )()()for,jjiijjiijP baP aP ba P aP bP baA aa bBp(a*|bj)p(ai|bj)四 、两种译码准则-最大似然译码准则最大似然译码

25、准则最大似然译码准则(maximum likelihoodML准则准则)前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从错误概率最小角度，该译码前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从错误概率最小角度，该译码准则是最好的。准则是最好的。在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道的转移概率，而不知道信源在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道的转移概率，而不知道信源的分布，故无法计算全概率，故无法采用最大后验概率译码准则进行译码。的分布，故无法计算全概率，故无法采用最大后验概率译码准则进行译码。 n如果输入符号等概发生, 则选

26、择译码函数F(bj)=a*,并满足p(bj|a*)p(bj|ai)该译码规则称为: 最大似然译码准则最大似然译码准则. 该准则表示收到bj后, 在信道矩阵的第j列, 选择最大的值对应输入符号a*作为译码输出.*(|) ()(|) ( )()()for,jjiijjiijP baP aP ba P aP bP baA aa bB平均错误概率 根据译码规则, 可进一步写出平均错误概率PE, 即而平均正确概率为,( |) ()1 ()| ()1 ()() ()()()EjjjjjYYjjijjjYX YYijjijYXYY XaPp e bp bp F bbp bp F b bp abp F b b

27、p abP a bP ab 1 ()EEjjjYYPPp F b bP a b 平均错误概率也可写成:,( )( )(|)()(|) ( )( )( )1)EijjiiXa YXa YiXjijYiieXiEeXp baF baPp abp ba p ap ap a pPPr如果先验概率p(ai)相等, 则:平均错误概率先对行求和，除去译码规则中所对应的概率，然后是各行之和几点说明1）当输入符号等概时，最大似然准则等价于最大后验概率准则。2）该准则可直接从信道传递矩阵中选定译码函数，即收到bj后，译成信道矩阵p中第j列中最大那个元素所对应的信源符号。3）该准则本身不再依赖于先验概率p(ai)，

28、但当输入符号等概时，它使平均错误概率PE最小。4）当输入符号等概或先验概率未知时，采用此准则。两种准则使用要点MAP准则-最大后验概率准则最大后验概率准则 1）由转移概率矩阵的每行分别乘 p(x)，得到联合概率矩阵； 2）对于每一列（相当于 y 固定）找一个最大的概率对应的X 作为译码结果； 3）所有译码结果所对应的联合概率的和为正确概率，其他矩阵元素的和为错误概率。ML准则 -最大似然译码准则最大似然译码准则1）对转移概率矩阵中每列选择最大的一个元素对应的x作为译码结果；2）所有译码结果所对应的转移概率的和再乘以 1/r（或pi）为 正确概率,其他矩阵元素的和再乘以1/r （或pi）为错误概

29、率。 当输入分布等概时，最大似然译码准则和最大后验当输入分布等概时，最大似然译码准则和最大后验概率准则是等价的。概率准则是等价的。 根据最大似然译码准则，我们可以直接从信道矩阵根据最大似然译码准则，我们可以直接从信道矩阵的传递概率中去选定译码函数：就是说，收到的传递概率中去选定译码函数：就是说，收到 后，后，译成信道矩阵的第译成信道矩阵的第j 列中最大的那个元素所对应的信源列中最大的那个元素所对应的信源符号。符号。jb 最大似然译码准则本身不再依赖于先验概率。但是最大似然译码准则本身不再依赖于先验概率。但是当先验概率为等概时，它使错误概率当先验概率为等概时，它使错误概率PE最小。如果先验最小。

30、如果先验概率不相等或不知道时，仍可以采用这个准则，但不一概率不相等或不知道时，仍可以采用这个准则，但不一定能使定能使 PE 最小。最小。如果知道先验概率，应该使用最大后验概率准则;如果不知道先验概率，则只能用最大似然准则.例题例题5.2.2已知信道的转移概率矩阵为现有两种译码规则：规则A： 规则B：设输入等概，求两种译码规则的错误概率。1/21/31/61/61/21/31/31/61/2332211)()()(xyFxyFxyF233211)()()(xyFxyFxyF解：解：设判决函数为 ，根据平均错误概率公式得*( )F ya3/ )|()(*aaEaxypAp3/)3/ 16/ 1 (

31、) 6/ 13/ 1 () 3/ 16/ 1(2/13/ )|()(*aaEaxypBp3/)2/ 16/ 1 () 2/ 13/ 1 () 3/ 16/ 1(3/2The fourteenth class-2014书上P104可见这两种方法得到同一结果，因为要得到后验概率，计算步骤更多，所以可直接应用最大联合概率译码准则译码。【例】信源分布【例】信源分布123()0.50.10.4Xxxxp X信道转移概率矩阵信道转移概率矩阵0.50.30.20.10.70.20.30.30.4P P，信道输出符号，信道输出符号Y = y1，y2，y3。（1）计算按最大后验概率准则）计算按最大后验概率准则译

32、码的平均错误概率；译码的平均错误概率；（2）若信源等概分布，对其按极大似然译码准则译码，并求平均错误概率若信源等概分布，对其按极大似然译码准则译码，并求平均错误概率。【解】（【解】（1）最大后验概率准则译码）最大后验概率准则译码0.250.150.10()0.010.070.020.120.120.16p xy前面同一例子求平均错误概率平均错误概率：平均错误概率：112133yxyxyx0.250.150.10()0.010.070.020.120.120.16p xy()0.1 0.10.4 0.30.1 0.70.4 0.30.5 0.20.1 0.20.44kex xypp x y （2

33、）当信源等概分布，按极大似然函数译码准则译码，已给出信道转移概）当信源等概分布，按极大似然函数译码准则译码，已给出信道转移概率矩阵为率矩阵为0.50.30.20.10.70.20.30.30.4P P在矩阵的每列中选一最大值在矩阵的每列中选一最大值(矩阵中带下划线的值矩阵中带下划线的值)，译码为，译码为112233yxyxyx平均错误概率：平均错误概率：10.1 0.30.30.30.20.20.4673ep 第5.1节 错误概率与译码规则例5.3: 0.30.20.20.3B0.0.50.5030.34Pfor根据最大似然准则最大似然准则可选择译码函数为B:112332( )()()F ba

34、F baF ba*,1( | )31(0.20.3)(0.30.3)(0.20.4)0.5673EY XaPP b a若采用前述译码函数A, 则平均错误率为:*,1( | )31(0.20.3)(0.30.3)(0.20.5)0.63EY XaPP b a 可见EEPP 0.30.20.20.50.0.50.30.430.3Pfor A第5.1节 错误概率与译码规则112233( )()( )F baF baF ba 123*E111(),(),()442 111(0.30.2)(0.20.3)(0.30.4)0.6442iijijieXYXP aP aP aPP aP b aF baP aP

35、若输入不等概, 仍可采用最大似然译码准则, 其概率分布为:第5.1节 错误概率与译码规则输入不是等概分布时，比较最大似然译码准则和最小错误概率译码准则输入不是等概分布时，比较最大似然译码准则和最小错误概率译码准则若采用最小错误概率译码准则, 其联合矩阵p(aibj)为:0.1250.0750.05()0.0500.1.0750.12550.150.2ijP ab 所得译码函数为: C:132333( )()()F baF baF ba第5.1节 错误概率与译码规则平均错误率为: *E(0.1250.05)(0.0750.075)(0.050.125)0.5ijiYXaPP a P b a可见,

36、 . 所以输入非等概分布时最大似然译码准则获得的平均错误概率不是最小的.EEPP第5.1节 错误概率与译码规则5.3 费诺费诺(Fano)不等式不等式1. 信道疑义度（损失熵）2. 费诺(Fano)不等式平均错误概率Pe与译码规则(译码函数)有关，而译码规则又由信道特性来决定。由于信道中存在噪声，导致输出端发生错误，并使接收端输出符号后，对发送的是什么符号还存在不确定性。可以， Pe与信道疑义度具有一定的关系，就是下面要讲的费诺不等式5.3.1 信道疑义度（回忆）信道疑义度（回忆）n设信道的输入与输出分别为X、Y，定义条件熵H(X/Y)为信道疑义度。n信道疑义度的含义：n信道疑义度表示接收到

37、Y 条件下X的平均不确定性；n根据 I(X;Y)=H(X)-H(X/Y)，信道疑义度又表示X经信道传输信息量的损失；82 Fano不等式不等式)|()() 1log(YXHPHrPEE证明：*,)(; )*(1aXYjiEYjEEbaPPbaPPP*,11log)*(1log)() 1log(11log)1 (1log) 1log()(aXYEYjEjiEEEEEEEPbaPPrbaPrpPPPPrppH倒数？YjjaXYjijiYXjijibaPbaPbaPbaPbapbaPYXH)|*(1log)*()|(1log)()|(1log)()|(*,*,*,*,*(|)()log(1)1()l

38、og( *)log(1) (|)( *|)(ln1)1()1( *)1(1) (|)( *|)()()(1)()1EEEEijjY X aYijjEEijjY X aYijjEjijEjY X aY X aYYH X YH PPrPPP abP a brp a bP abxxPPP abP a brp a bP abPP bP abPP br( *)(1)(1)0jEEEEP a bPPPP ,*11jjY X aX aYX aP bP br (2) 如果判决出错（概率为 ）,错在r-1个符号中的哪一个，其疑义度不会超log (r-1)。 物理意义EP进行一次判决后，关于X的疑义度可分成两项：

39、 (1) 是否判对，疑义度为H ( ) EP费诺不等式示意图费诺不等式示意图n信道疑义度信道疑义度 n 是信源熵是信源熵H(X)超超过平均互信息过平均互信息I(X;Y)的部分。的部分。n若以若以H(X|Y)为纵坐为纵坐标，标，PE为横坐标，为横坐标，则函数则函数H(PE)+ PE log(n-1)随随PE变化变化的曲线如图所示。的曲线如图所示。n由图可知，当信源、由图可知，当信源、信道给定时，信道信道给定时，信道疑义度疑义度H(X|Y)就给就给定了译码平均错误定了译码平均错误概率概率PE的下限。的下限。 注释注释第5.2节 错误概率与编码方法 一般信道传输时都会产生错误, 而选择译码准则并不会

40、消除错误, 那么如何减少错误概率呢? 下边讨论通过编码方法来降低错误概率.第5.2节 错误概率与编码方法a1=0a2=1b1=0b2=10.990.990.010.012(0) (1|0)(1) (0|1)0.01 10EPpppp例: 对于如下二元对称信道若选择最佳译码规则F(b1)=a1F(b2)=a2对于一般传输系统(如数字通信), 这个概率已经相当大了. 一般要求系统的错误概率在10-610-9范围内, 甚至更低.简单重复编码 如何提高信道传输的正确率呢？可尝试下面的方法实际经验告诉我们：只要在发送端把消息重复发几遍，也就是增加消息的传输时间，就可使接收端接收消息时错误减小，从而提高了

41、通信的可靠性。如在二元对称信道中，当发送消息（符号）0时，不是只发一个0而是连续发三个0，同样发送消息（符号）1时也连续发送三个1，这是一种最简单的编码方法，他它将长度n=1的两个二元序列变换为两个长度n=3的二元序列，我们称这两个长度为3的二元序列为码字，于是信道输入端有两个码字000和111，但在输出端，由于信道干扰的作用，码字中各个码元（码符号）都可能发生错误，则有8个可能的输出序列，如下面简单重复编码 如何提高信道传输的正确率呢？可尝试下面的方法没有使用的码字001010011100101110用作消息的码字000111输出端接收序列000001010011100101110111二元

42、对称信道的三次扩展信道重复编码重复编码(n=3次次)：信道看成是信道看成是3次扩展，输出端由于各个干次扩展，输出端由于各个干扰，各个码元都可能发生错误，则有扰，各个码元都可能发生错误，则有8个可能的输出序列。个可能的输出序列。n根据最大似然译码准则(假设输入时等概率的), 可得简单重复编码的译码规则为F(1)= F(2)= F(3)= F(5)=1F(4)= F(6)= F(7)= F(8)=832222212345678222313222823pppppppppppppp pp pp pp pp pp ppppP信道矩阵简单重复编码n根据这个规则计算得译码后的错误概率为,3222222332

43、4() (|)1=(|)1()233*10 (0.01)EijiY XajiY XaPpppMpppppppppppppppppp简单重复编码简单重复编码也可以采用“择多译码择多译码”, 即根据接收序列中0多还是1多, 0多就判作0, 1多就判作1. 可得译码函数为：F(000)=000, F(001)=000, F(010)=000, F(011)=111F(100)=000, F(101)=111, F(110)=111, F(111)=111根据择多译码规则, 同样可得到324(3)(2)33*100.01EPPPpppp个码元错误个码元错误可见, 择多译码择多译码准则与最大似然译码最大

44、似然译码准则是一致的. 简单重复编码n与原来PE=10-2比较, 这种简单重复的编码方法已把译码错误概率降低了近两个数量级. n结论：结论：重复编码使重复编码使PE减小减小n原因原因: 这种编码可以纠正码字中的一位码元出错, 译错的可能性变小了, 因此错误概率降低.简单重复编码n若重复更多次更多次可进一步降低错误率. 可算得n可见, 当n很大时, 使PE很小是可能的. 但这又带来了一个新问题, n很大时, 信息传输率会降低很多.5781051074 10910115 10EEEEnPnPnPnP简单重复编码编码后信息传输率为 在上例中： M=2 当n=1时 R=1 当n=3时 R=1/3 当n

45、=5时 R=1/5 . .由此得PE和R的关系, 如右图. 它表明:尽管PE降低很多, 但也使信息传输率降得很低.logMRnM为输入信息（许用码字）的个数。logM表示消息集在等概率条件下每个消息（码字）携带的平均信息量（比特）。n是编码后码字的长度（码元的个数）The fifteenth class-2014复习上一次课主要内容n一、费诺(Fano)不等式n二、降低错误概率的方法5.3 费诺费诺(Fano)不等式不等式1. 信道疑义度2. 费诺(Fano)不等式平均错误概率Pe与译码规则(译码函数)有关，而译码规则又由信道特性来决定。由于信道中存在噪声，导致输出端发生错误，并使接收端输出符

46、号后，对发送的是什么符号还存在不确定性。可以， Pe与信道疑义度具有一定的关系，就是下面要讲的费诺不等式香农第二定理n这显然是一个矛盾, 有没有解决的办法, 能不能找到一种更好的编码方法, 使PE相当低, 而R却保持在一定水平呢？这就是香农第二定理, 即有噪信道编码定理. n在上图中, 也给出了香农第二定理的PE和R的关系值, 其中为任意小的数.设离散无记忆信道设离散无记忆信道X, p(y|x), Y，其信道容量为，其信道容量为C。当信。当信息传输率息传输率RC时，只要码长时，只要码长n 足够长，总可以在输入符足够长，总可以在输入符号集号集 中找到中找到 个码字组成的一组码个码字组成的一组码

47、和相应的译码规则，使译码的错误概率任意小。和相应的译码规则，使译码的错误概率任意小。nX)2(nRM ),2(nnR与信源编码定理的证明类似，构造编码方法。与信源编码定理的证明类似，构造编码方法。第三节 有噪信道编码定理(香农第二定理)基本思路证明有噪信道编码定理n香农对有噪信道编码定理证明方法的基本思路是：n连续使用信道多次，即在n次无记忆扩展信道中讨论，以便使大数定律有效；n随机地选取码书，也就是在Xn的符号序列集中随机地选取经常出现的高概率序列作为码字；n采用最大似然译码准则，也就是将接收序列译成与其距离最近的那个码字；n在随机编码的基础上，对所有的码书计算其平均错误概率。当n足够大时，

48、此平均错误概率趋于零，由此证明得至少有一种好码存在。),(21nxxxx),(21nyyyynkkkxypP1)|()|(xy2 , 1 nRnnRX2 , 1 :2 , 1 :nRnX)|(mmmPPEmmEmnREPP21证明证明：离散无记忆信道离散无记忆信道X, p(y|x), Y，输入序列为，输入序列为输出序列：输出序列：转移概率：转移概率：编码速率为编码速率为R，则消息的标号集为，则消息的标号集为编码函数可看作下述映射：编码函数可看作下述映射：译码函数为：译码函数为：发送发送m的条件下译码错误概率为：的条件下译码错误概率为：译码的平均误组率为（消息等概）译码的平均误组率为（消息等概）

49、具体的证明过程-了解从从 中独立随机地选取中独立随机地选取 个序列作为码字，个序列作为码字，这相当于每个码字出现的概率为消息序列出现的概率这相当于每个码字出现的概率为消息序列出现的概率:nXnR2nkkxPP1)()(xX中任一元素独立等概地出现，中任一元素独立等概地出现，这种编码方法称作这种编码方法称作随机编码随机编码。译码规则：译码规则： （典型序列准则（典型序列准则译为联合典型序列的译为联合典型序列的x） 对给定的接受序列对给定的接受序列y，若存在唯一的，若存在唯一的使使就将就将y译为译为m，即，即D(y)=m 。当。当 或者有两个或者有两个以上以上m和和y构成联合典型序列时，就认为译码

50、出错。构成联合典型序列时，就认为译码出错。2 , 1 nRm)(),(XYGnmyxmm 就是任意特定消息被错误译码的概率。就是任意特定消息被错误译码的概率。所以不失一般性可假设发送的是第一个消息。所以不失一般性可假设发送的是第一个消息。译码错误概率为译码错误概率为)ym1()ym(1构成联合典型序列与的不是构成联合典型序列不与即mmPPPEE)Y:X( IRn)Y:X( InnRmm)Y:X( InmncmmcEE)E(P)E(P;)E(P)E(P)E(PPP3313111122220 因为随机码具有对称性，所以译码错误概率与送出的因为随机码具有对称性，所以译码错误概率与送出的消息编号无关，

51、也就是随机码集合消息编号无关，也就是随机码集合的平均错误概率的平均错误概率R)Y;X( In)Y;X( InnRnRi)Y;X( Ine)Y;X( InniCnRiiCnRCenCnRni)(P)i ()XY(G),i (P)E(P);n()E(P)E(P)E(P)E(P)EEEE(P)(|)(gPP)XY(G),(E,.i),XY(G),i (E3322313112212321112212221yx11xx1yy1x21yx再具体一些说，就是：再具体一些说，就是：为了使为了使R大，可使大，可使 I(X:Y) 极大化，即以极大化，即以C代替。代替。若若RC-3 ，随着，随着 n 趋于无穷大，上

52、面的错误概率趋于趋于无穷大，上面的错误概率趋于0。因为因为RC-3 ，上面的错误概率趋于，上面的错误概率趋于0，所以必定存在一种，所以必定存在一种码，当码，当 n 足够大时，其译码错误概率为足够大时，其译码错误概率为0。 Shannon第二定理另一种形式！有噪信道编码定理信道编码定理，即Shannon第二定理。-书上的证明方法！ P1065 53 3 信道编码定理信道编码定理定理定理5.1 对于任何离散无记忆信道DMC，存在信息传输率为R，长为n的码，当n 时，平均差错概率 pe exp- nE (R)0，式中E (R) 为可靠性函数，E ( R )在0 R C的范围内为正。 1 随机编码方法

53、 信道输入符号集A=a1,a2,ak,选用长为n的定长码，共可构成k n个矢量，设有M个消息待传（M k n），每次随机地从k n个矢量中抽出M个矢量构成一个码集C（允许重复取）C = x1 , , x m , , x M共可构成k nM个这样的码集。由随机编码的构造方法，得到任何一个码字的概率相同，且相互独立。 上述定理也称有噪信道编码定理信道编码定理，即Shannon第二定理。 2Gallager上界因为上述按随机编码方法构成的码集是等概分布的，按照最大似然译码准则译码，在发送码矢xk时，要得到正确译码须满足 ，即 （5-5） kmppmkx xy yx xy y1mkppx xy yx

54、xy y01mkppx xy yx xy y定义示性函数MmppppImkmkk, 2 , 1)()(1)()(0)(x xy yx xy yx xy yx xy yy y则发送码矢xk判错的概率为 （5-6） kkkepIpx xy yy yx xy y书上错的书上错的根据式(5-5)，当0 , 1时，下式成立mkmkkmkmppppppx xy yx xy yx xy yx xy yx xy yx xy y当当10用示性函数Ik (y)表示上式，即 （5-7） kikmkppIx xy yx xy yy y将式(5-7)代入式(5-6)，得kmkmkkeppppx xy yx xy yx

55、xy yx xy y式中0 , 1，因为 , 都是任意数，可取 ，则有 （5-8） 11kmmkkeppp1111x xy yx xy yx xGallager上界上界3 随机编码错误概率上界随机编码错误概率上界 Gallager限仅给出发送码矢xk时的错误概率上界，还要对全部码矢求平均，下面对上述的随机编码集合求平均。 对于随机编码，各码字等概且独立，有，对式(5-8)求统计平均值，得平均错误概率上界 MmmMmqq11x xx xx xx x, keMmpqpMx xx xx xx xx xx x,e,11 y yx xx xx xy yx xy yx xx xx xkmmkMppqqqM

56、1111211, y yx xx xx xy yx xx xy yx xkmkmmmkkpqpq1111(5-9) 后面一项 ，因为0 1，而x 是x的型凸函数，由型凸函数的定义知：函数均值 均值函数，即有 (5-10)mkmmmpqx xx xy yx x11kmmmkmmmpqpqmm1111x xy yx xx xy yx xx xx x因为 xm (m = 1,2, M) 都通过同一信道传输，故p(y yxm)值相同，记为p(y yx)，代入式（510）得 (5-11) kmmmpqm11x xy yx xx x 11)1(x xy yx xx xpqM 将式(5-11)代回式(5-9

57、)，得 （512） 1111) 1(x xy yx xx xy yx xx xy yx xpqMpqpkkke y yx xx xy yx x111) 1(pqM平均错误概率的平均错误概率的一个上界一个上界4离散无记忆信道DMC的错误概率上界 对于n维离散无记忆信道DMC，有 ，对于随机编码 ，将这两个关系式代入式(5-12)，有niiixypp1)(x xy y niixqq1)(x x 1111111111)()()()(1yyxxNNNeNNxypxqxypxqMp NiyxiiiiixypxqM1111)()(1（513） 序列x = x1, xi, , xn 中的 xi,取自同一符号

58、A=a1,a2,ak，故分布q(xi)相同, yxyxiiixypxqxypxqii111111)()()()(（514） 将式（514）代入式（513），得 （515） nyxexypxqMp 111)()(1nyxxypxqM 111)()(5 可靠性函数E (R ) 信息传输率 ，则式(515)可写为： (5-16) RneMnMRlnnyxxypxqRneeep 111)()(ln记10, ),()()(ln0111 qExypxqyx则式(5-16)可写成 pe exp -n -R + E0 (, q ) (5-17) 对式(5-17)右边求极小值，即对指数-R + E0 (, q )求极大值,记这个极大值为则式(5-17)可写为pe exp -n E (R ) 称E (R )为可靠性函数可靠性函数,也称随机编码指数，它与信道转移概率p(yx)有关。 RqEREq),(maxmax010 在0 R C的范围内，E (R )是下降的、下凹的正值函数，说明E (R )有界，这样，当 时，有exp -nE (R ) 0，从而pe C时, 则无论码长n多长, 总找不到一种编码(2nR,n)使信道输出端的平均错误译码概率达到任意小.