第5章-有噪信道编码

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

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

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

4、, 1u 信道输入序列为：信道输入序列为： 111, 000, 111, 111x 由于由于p的存在，使得传输出错，故信道输出为：的存在，使得传输出错，故信道输出为：111, 001, 001, 000y 根据译码规则，信道估值输出：根据译码规则，信道估值输出： 1, 0, 0, 0y 信道错误概率：假设信道离散无记忆，即信道错误概率：假设信道离散无记忆，即 3 1 ( / )(/) ii i p y xp yx 错误概率为：错误概率为： 223323 33 (1)32 e pC ppC pppp 重复编码的结果使错误概率下降。重复编码的结果使错误概率下降。 书书5-15-1式有问题式有问题

5、n书上例题5.2 【例例5.3】 逆重复码逆重复码 离散无记忆二进制对称信道，固有 误码率为p (p0.5)，信源输出序列为三位二进制数字。 编码规则：为提高传输效率，仅向信道发送一位，预先将信 源输出序列进行择多编码: 000000000111 0 1 0 1 0 0 1 1 101111001110 判决输出 接收 发送 原序列 pp 图5-3 逆重复编码传输示意图 译码规则：将接收的 一位符号重复三次译出， 即若接收到1就译码为 111，即若接收到0就译 码为000。 信源输出的三位符号中有两位或3位是1，信源序列编码为1， 若三位符号中有两位或3位是0，就将此信源序列编码为0。 1-p

6、 0 p 1 0 1 1-p p 计算差错概率pe ： 分二步进行： （1）先设p = 0，计算这种编码方法带来的 固有错误p 1 信道输入符号集X = 000,001,010,011,100,101,110,111 判决输出符号集Y = 000,111 译码规则 因为后验概率 则出错概率 111)111110101011( 000)100010001000( ， ， F F 4 1 )111111() 4 1 )000000() y yx x y yx x （ （ 4 3 4 1 1)111()( 4 3 4 1 1)000()( epyep epyep 假设8组输入序列是等概发送的，由于信

7、道的对称性，两 个估值序列也是等概分布的，则每个序列的平均错误概率 为 ， 误比特率 。 （2）再设p0，计算由于信道噪声引起的错误概率p2因 为每个序列有三位二进制数字，但只发送一位，这一位的 出错概率为p，故序列差错概率为p，误比特率 。 （3）总差错概率（误比特率）： 4 3 )111(5 . 0)000(5 . 0epep 4 1 4 3 3 1 1 p pp 3 1 2 ppppe 3 1 4 1 21 n【例例5.4】 奇偶校验码奇偶校验码 在信息序列后面加上一位校验位， 使之模2和等于1，这样的编码称为奇校验码；若使模2和等 于0，这样的编码就称为偶校验码，即每个码矢中1的个数

8、固定为奇数或偶数。 n关于奇偶校验关于奇偶校验 n奇偶校验原理奇偶校验原理：通过计算数据中“1”的个数是奇数还是偶 数来判断数据的正确性。在被校验的数据后加一位校验位 或校验字符用作校验码实现校验。 n校验位的生成方法 n奇校验奇校验：确保整个被传输的数据中“1”的个数是奇数个， 即载荷数据中“1”的个数是奇数个时校验位填“0”，否则 填“1”； n偶校验偶校验：确保整个被传输的数据中“1”的个数是偶数个， 即载荷数据中“1”的个数是奇数个时校验位填“1”，否则 填“0”。 n 使用奇偶校验码校验的特点：使用奇偶校验码校验的特点： n奇偶校验能够检测出信息传输过程中的部分误码（1位误码能检出，

9、2位 及2位以上误码不能检出），同时，它不能纠错。在发现错误后，只能 要求重发。但由于其实现简单，仍得到了广泛使用。 n 校验处理过程简单，但如果数据中发生多位数据错误就可能检测不出 来，更检测不到错误发生在哪一位；主要应用于低速数字通信系统中， 一般异步传输模式选用偶校验，同步传输模式选用奇校验。 信道编码的目的：提高传输可靠性。 有噪信道编码定理，即香农第二定理， 是信道编码的理论基础。 本章重点介绍通过信道编码通信系统 所能达到的极限性能，不涉及编码技 术的具体实现，以及两种常用的译码 准则。 信道编码就是按一定的规则给信源输出序列增加某 些冗余符号，使其变成满足一定数学规律的码序列 （

10、或 码字），再经信道进行传输。（具有纠错能 力） 信道译码就是按与编码器同样的数学规律去掉接收 序列中的冗余符号，恢复信源消息序列。 传输信道传输信道 插插 入入 冗冗 余余 信信 息息 抽抽 出出 冗冗 余余 信信 息息 编码编码 译码译码 还原序列还原序列发送序列发送序列 编码编码 译码译码 发送序列发送序列还原序列还原序列 传输信道传输信道 插插 入入 冗冗 余余 信信 息息 抽抽 出出 冗冗 余余 信信 息息 编码编码 译码译码 第5.1节 错误概率与译码规则 第5.2节 错误概率与编码方法 第5.3节 有噪信道编码定理 主要内容 n 前一章已经从理论上讨论了, 对于无噪无损信道 只要

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

12、特性 信道统计特性用信道传递矩阵来描述, 该矩阵确 定了哪些是正确传递概率, 哪些是错误传递概率. 译码规则译码规则 通信过程并非到信道输出端就结束, 还要经过译码过程(或判决过程) 才到达消息的终端(收信者). 第5.1节 错误概率与译码规则 例: 有一个BSC信道, 如右图 0 1 0 1 1/3 1/3 2/3 2/3 若收到“0”译作“0”, 收到“1” 译作“1”, 则平均错误概率为: 2 (0) (1|0)(1) (0|1) 3 E Ppppp 反之, 若收到“0”译作“1”, 收到“1”译作“0”, 则 平均错误概率为1/3. 可见, 错误概率与译码准则错误概率与译码准则 有关有

13、关. 第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种 译码规则. 译码规则的选择应该根据什么准则？ 译码规则的选择依据选择依据: 使平均错误概率最小. 译码准则可以为

14、: A: 和B: 11 22 33 ( ) () ( ) F ba F ba F ba 11 23 32 ( ) () ( ) F ba F ba F ba 1 2 3 0.50.30.2 0.20.30.5 0.30.30.4 a Pa a 例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

15、 () ( |)()1(|) ss Ejjjij jj Pp 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) ”或“最

16、小错误概率译码准则最小错误概率译码准则”.也叫最大联合概率译也叫最大联合概率译 码准则。码准则。对每个输出符号均译成具有最大后验概率的那个输入符号，则信道错 误概率就能最小。 * , j aA bB i aA （1）联合概率 ()() (/)() (/) ijijijij P abP a P baP b P ab (/) ji P ba 其中称为前向概率，描述信道的噪声特性 有时也把 称为先验 概率，把 称为后验概率 ( ) i P a （2）输出符号的概率 11 ()( ) (/)() rr jijiij ii P bp a p bap ab （3）后验概率 () (/) () ij ij

17、j P ab P ab P b (/) ij P ab 1 (/)1 r ij i P ab 表明输出端收到任一符号，必定是输入端某一符号 输入所致 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, jjii jj iij P baP aP ba P a P

18、bP b aA aa bB p(a*|bj)p(ai|bj) 等效于最大联合概率译码准则等效于最大联合概率译码准则 最大似然译码准则最大似然译码准则(maximum likelihoodML准则准则) 前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从错误概率最小角度，该译码前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从错误概率最小角度，该译码 准则是最好的。准则是最好的。 在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道的转移概率，而不知道信源在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道的转移概率，而不知道信源 的分布，故无法计算全概率，故

19、无法采用最大后验概率译码准则进行译码。的分布，故无法计算全概率，故无法采用最大后验概率译码准则进行译码。 n如果输入符号等概发生, 则选择译码函数F(bj)=a*, 并满足 p(bj|a*)p(bj|ai) 该译码规则称为: 最大似然译码准则最大似然译码准则. 该准则表示 收到bj后, 在信道矩阵的第j列, 选择最大的值对应 输入符号a*作为译码输出. * (|) ()(|) ( ) ()() for, jjii jj iij P baP aP ba P a P bP b aA aa bB 平均错误概率 根据译码规则, 可进一步写出平均错误概率PE, 即 而平均正确概率为 , , ( |) (

20、)1 ()| () 1 ()() () ()() Ejjjjj YY jjijjj YX YY ijjij YXY Y Xa Pp e bp bp F bbp b p F b bp abp F b b p abP a bP ab 1 () EEjjj YY PPp F b bP a b 平均错误概率也可写成: , ( ) ( ) (|)( ()(|) ( ) ( ) ( ) 1 ) Eijjii Xa YXa Y i X jij Y i ie X i Ee X p baF ba Pp abp ba p a p a p a p PP r 如果先验概率p(ai)相等, 则: 平均错误概率 先对行求

21、和，除去译码规则中所 对应的概率，然后是各行之和 几点说明 1）当输入符号等概时，最大似然准则等价于 最大后验概率准则。 2）该准则可直接从信道传递矩阵中选定译码 函数，即收到bj后，译成信道矩阵p中第j列 中最大那个元素所对应的信源符号。 3）该准则本身不再依赖于先验概率p(ai)，但 当输入符号等概时，它使平均错误概率PE最 小。 4）当输入符号等概或先验概率未知时，采用 此准则。 复习和捋顺关系 n信道编码就是按一定的规则给信源输出序列增加某些冗余 符号，使其变成满足一定数学规律的码序列（或 码字）， 再经信道进行传输。（具有纠错能力） n信道译码就是按与编码器同样的数学规律去掉接收序列

22、中 的冗余符号，恢复信源消息序列。 n平均错误概率与两个因素有关 n1、信道的统计特性（传递矩阵） n2、译码规则 n主要内容和捋顺关系：主要内容和捋顺关系： n一、译码规则；一、译码规则； n二、如何选择译码规则；二、如何选择译码规则； n三、两种译码准则三、两种译码准则- -最大后验概率译码准则最大后验概率译码准则 n四、两种译码准则四、两种译码准则- -最大似然译码准则最大似然译码准则 一、译码规则； 定义译码规则译码规则: 输入符号集: A=ai, i=1,2,r; 输出符号集: B=bj, j=1,2,s; 译码规则译码规则: 设计函数F(bj), 它对于每个输出符号bj 确定一个唯

23、一的输入符号ai与其对应(单值函数). 即 F(bj)=ai 由于任何输出符号bj都可以译成任何输入符号ai, 即s个输出符 号中的每一个都可以译成r个输入符号中的任一个，所以有rs种 译码规则. 译码准则可以为: A: 和B: 11 22 33 ( ) () ( ) F ba F ba F ba 11 23 32 ( ) () ( ) F ba F ba F ba 1 2 3 0.50.30.2 0.20.30.5 0.30.30.4 a Pa a 例5.1: 有一离散单符号信 道，信道矩阵为 二、如何选择译码规则； n译码规则的选择应该根据什么准则？ n译码规则的选择依据选择依据: 使平均

24、错误概率最小. 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(|) ss Ejjjij jj Pp b P e bp bP a b 三、两种译码准则-最大后验概率 译码准则 最小错误概率译码准则 问题: 如何选择p(ai|bj)? 使p(e|bj)最小, 就应选 择pF(bj)|bj为

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

26、A 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, jjii jj iij P baP aP ba P a P bP b aA aa bB p(a*|bj)p(ai|bj) 四 、两种译码准则-最大似然译码 准则 最大似然译码准则最大似然译码准则(maximum likelih

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

28、j|a*)p(bj|ai) 该译码规则称为: 最大似然译码准则最大似然译码准则. 该准则表示 收到bj后, 在信道矩阵的第j列, 选择最大的值对应 输入符号a*作为译码输出. * (|) ()(|) ( ) ()() for, jjii jj iij P baP aP ba P a P bP b aA aa bB 平均错误概率 根据译码规则, 可进一步写出平均错误概率PE, 即 而平均正确概率为 , , ( |) ()1 ()| () 1 ()() () ()() Ejjjjj YY jjijjj YX YY ijjij YXY Y Xa Pp e bp bp F bbp b p F b bp

29、 abp F b b p abP a bP ab 1 () EEjjj YY PPp F b bP a b 平均错误概率也可写成: , ( ) ( ) (|)( ()(|) ( ) ( ) ( ) 1 ) Eijjii Xa YXa Y i X jij Y i ie X i Ee X p baF ba Pp abp ba p a p a p a p PP r 如果先验概率p(ai)相等, 则: 平均错误概率 先对行求和，除去译码规则中所 对应的概率，然后是各行之和 几点说明 1）当输入符号等概时，最大似然准则等价于 最大后验概率准则。 2）该准则可直接从信道传递矩阵中选定译码 函数，即收到bj

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

31、果； 2）所有译码结果所对应的转移概率的和再乘以 1/r（或pi）为 正确概率, 其他矩阵元素的和再乘以1/r （或pi）为错误概率。 当输入分布等概时，最大似然译码准则和最大后验当输入分布等概时，最大似然译码准则和最大后验 概率准则是等价的。概率准则是等价的。 根据最大似然译码准则，我们可以直接从信道矩阵根据最大似然译码准则，我们可以直接从信道矩阵 的传递概率中去选定译码函数：就是说，收到的传递概率中去选定译码函数：就是说，收到 后，后， 译成信道矩阵的第译成信道矩阵的第j 列中最大的那个元素所对应的信源列中最大的那个元素所对应的信源 符号。符号。 j b 最大似然译码准则本身不再依赖于先验

32、概率。但是最大似然译码准则本身不再依赖于先验概率。但是 当先验概率为等概时，它使错误概率当先验概率为等概时，它使错误概率PE最小。如果先验最小。如果先验 概率不相等或不知道时，仍可以采用这个准则，但不一概率不相等或不知道时，仍可以采用这个准则，但不一 定能使定能使 PE 最小。最小。 如果知道先验概率，应该使用最大后验概率准则; 如果不知道先验概率，则只能用最大似然准则. 例题例题5.2.2 已知信道的转移概率矩阵为 现有两种译码规则： 规则A： 规则B： 设输入等概，求两种译码规则的错误概率。 1/21/31/6 1/61/21/3 1/31/61/2 33 22 11 )( )( )( x

33、yF xyF xyF 23 32 11 )( )( )( xyF xyF xyF 解：解：设判决函数为 ，根据平均错误概率 公式得 * ( )F ya 3/ )|()( * aa E axypAp 3/)3/ 16/ 1 () 6/ 13/ 1 () 3/ 16/ 1( 2/1 3/ )|()( * aa E axypBp 3/)2/ 16/ 1 () 2/ 13/ 1 () 3/ 16/ 1( 3/2 The fourteenth class-2014 书上P104 可见这两种方法得到同一结果，因为要得到后验概率，计算 步骤更多，所以可直接应用最大联合概率译码准则译码。 【例】信源分布【例】

34、信源分布 123 ()0.50.10.4 Xxxx p X 信道转移概率矩阵信道转移概率矩阵 0.50.30.2 0.10.70.2 0.30.30.4 P P ，信道输出符号，信道输出符号Y = y1，y2，y3。 （1）计算按最大后验概率准则）计算按最大后验概率准则译码的平均错误概率；译码的平均错误概率； （2）若信源等概分布，对其按极大似然译码准则译码，并求平均错误概率若信源等概分布，对其按极大似然译码准则译码，并求平均错误概率。 【解】（【解】（1）最大后验概率准则译码）最大后验概率准则译码 0.250.150.10 ()0.010.070.02 0.120.120.16 p xy 前

35、面同一例子求平均错误概率 平均错误概率：平均错误概率： 11 21 33 yx yx yx 0.250.150.10 ()0.010.070.02 0.120.120.16 p xy () 0.1 0.10.4 0.30.1 0.70.4 0.30.5 0.20.1 0.2 0.44 k e x xy pp x y （2）当信源等概分布，按极大似然函数译码准则译码，已给出信道转移概）当信源等概分布，按极大似然函数译码准则译码，已给出信道转移概 率矩阵为率矩阵为 0.50.30.2 0.10.70.2 0.30.30.4 P P 在矩阵的每列中选一最大值在矩阵的每列中选一最大值(矩阵中带下划线的

36、值矩阵中带下划线的值)，译码为，译码为 11 22 33 yx yx yx 平均错误概率：平均错误概率： 1 0.1 0.30.30.30.20.20.467 3 e p 第5.1节 错误概率与译码规则 例5.3: 0.30.2 0.20.3B 0. 0.5 0.5 030.34 Pfor 根据最大似然准则最大似然准则可选择译码函数为B: 11 23 32 ( ) () () F ba F ba F ba * , 1 ( | ) 3 1 (0.20.3)(0.30.3)(0.20.4)0.567 3 E Y Xa PP b a 若采用前述译码函数A, 则平均错误率为: * , 1 ( | )

37、3 1 (0.20.3)(0.30.3)(0.20.5)0.6 3 E Y Xa PP b a 可见 EE PP 0.30.2 0.20.5 0. 0.5 0.3 0.430.3 Pfor A 第5.1节 错误概率与译码规则 11 22 33 ( ) () ( ) F ba F ba F ba 123 * E 111 (),(),() 442 111 (0.30.2)(0.20.3)(0.30.4)0.6 442 i ijijie XYX P aP aP a PP aP b aF baP aP 若输入不等概, 仍可采用最大似然译码准则, 其概率 分布为: 第5.1节 错误概率与译码规则 输入不

38、是等概分布时，比较最大似然译码准则和最小错误概率译码准则输入不是等概分布时，比较最大似然译码准则和最小错误概率译码准则 若采用最小错误概率译码准则, 其联合矩阵p(aibj) 为: 0.1250.0750.05 ()0.050 0.1 .0750.125 50.150.2 ij P ab 所得译码函数为: C: 13 23 33 ( ) () () F ba F ba F ba 第5.1节 错误概率与译码规则 平均错误率为: * E (0.1250.05)(0.0750.075)(0.050.125)0.5 iji Y Xa PP a P b a 可见, . 所以输入非等概分布时最大似然 译码

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

40、件下X的平均不确定性； n根据 I(X;Y)=H(X)-H(X/Y)，信道疑义度又表示X经 信道传输信息量的损失； 82 Fano不等式不等式 )|()() 1log(YXHPHrP EE 证明： *, )(; )*(1 aXY jiE Y jE EbaPPbaPPP *, 1 1 log)*( 1 log)( ) 1log( 1 1 log)1 ( 1 log ) 1log()( aXY E Y j E ji E E E E E EE P baP P r baP rp P P P P rppH 倒数？ Y j j aXY ji ji YX ji ji baP baP baP baP bap

41、baPYXH )|*( 1 log)*( )|( 1 log)( )|( 1 log)()|( *, ,* ,* ,*,* (|)()log(1) 1 ()log( *)log (1) (|)( *|) (ln1) 1 ()1( *)1 (1) (|)( *|) ()()(1)() 1 EE EE ijj Y X aY ijj EE ijj Y X aY ijj E jijEj Y X aY X aYY H X YH PPr PP P abP a b rp a bP ab xx PP P abP a b rp a bP ab P P bP abPP b r ( *) (1)(1)0 j EEE

42、E P a b PPPP ,* 11 jj Y X aX aYX a P bP br (2) 如果判决出错（概率为 ）,错在r-1个 符号中的哪一个，其疑义度不会超log (r-1)。 物理意义 E P 进行一次判决后，关于X的疑义度可分成两项： (1) 是否判对，疑义度为H ( ) E P 费诺不等式示意图费诺不等式示意图 n信道疑义度信道疑义度 n 是信源熵是信源熵H(X)超超 过平均互信息过平均互信息I(X;Y) 的部分。的部分。 n若以若以H(X|Y)为纵坐为纵坐 标，标，PE为横坐标，为横坐标， 则函数则函数H(PE)+ PE log(n-1)随随PE变化变化 的曲线如图所示。的曲线

43、如图所示。 n由图可知，当信源、由图可知，当信源、 信道给定时，信道信道给定时，信道 疑义度疑义度H(X|Y)就给就给 定了译码平均错误定了译码平均错误 概率概率PE的下限。的下限。 注释注释 第5.2节 错误概率与编码方法 一般信道传输时都会产生错误, 而选择译码准则 并不会消除错误, 那么如何减少错误概率呢? 下边讨论通过编码方法来降低错误概率. 第5.2节 错误概率与编码方法 a1=0 a2=1 b1=0 b2=1 0.99 0.99 0.01 0.01 2 (0) (1|0)(1) (0|1)0.01 10 E Ppppp 例: 对于如下二元对称信道 若选择最佳译码规则 F(b1)=a

44、1 F(b2)=a2 对于一般传输系统(如数字通信), 这个概率已经相当 大了. 一般要求系统的错误概率在10-610-9范围内, 甚至更低. 简单重复编码 如何提高信道传输的正确率呢？可尝试下面的方法 实际经验告诉我们：只要在发送端把消息重复发几遍，也就 是增加消息的传输时间，就可使接收端接收消息时错误减小， 从而提高了通信的可靠性。 如在二元对称信道中，当发送消息（符号）0时，不是只发 一个0而是连续发三个0，同样发送消息（符号）1时也连续 发送三个1，这是一种最简单的编码方法，他它将长度n=1的 两个二元序列变换为两个长度n=3的二元序列，我们称这两 个长度为3的二元序列为码字，于是信道

45、输入端有两个码字 000和111，但在输出端，由于信道干扰的作用，码字中各个 码元（码符号）都可能发生错误，则有8个可能的输出序列， 如下面 简单重复编码 如何提高信道传输的正确率呢？可尝试下面的方法 没有使用的 码字 001 010 011 100 101 110 用作消息的 码字 000 111 输出端接收 序列 000 001 010 011 100 101 110 111 二元对称信道的三 次扩展信道 重复编码重复编码(n=3次次)：信道看成是信道看成是3次扩展，输出端由于各个干次扩展，输出端由于各个干 扰，各个码元都可能发生错误，则有扰，各个码元都可能发生错误，则有8个可能的输出序列

46、。个可能的输出序列。 n根据最大似然译码准则(假设输入时等概率的), 可得简单重复编码的译码规则为 F(1)= F(2)= F(3)= F(5)=1 F(4)= F(6)= F(7)= F(8)=8 3222 22 12345678 2223 1 3222 8 23 ppppppp ppppp pp pp pp p p pp pp pppp P 信道矩阵 简单重复编码 n根据这个规则计算得译码后的错误概率为 , , 32222223 324 () (|) 1 =(|) 1 () 2 33*10 (0.01) Eiji Y Xa ji Y Xa Ppp p M pppppppppppppp pp

47、pp 简单重复编码 简单重复编码 也可以采用“择多译码择多译码”, 即根据接收序列中0多还是 1多, 0多就判作0, 1多就判作1. 可得译码函数为： F(000)=000, F(001)=000, F(010)=000, F(011)=111 F(100)=000, F(101)=111, F(110)=111, F(111)=111 根据择多译码规则, 同样可得到 324 (3)(2) 33*100.01 E PPP pppp 个码元错误个码元错误 可见, 择多译码择多译码准则与最大似然译码最大似然译码准则是一致的. 简单重复编码 n与原来PE=10-2比较, 这种简单重复的编码方法已 把

48、译码错误概率降低了近两个数量级. n结论：结论：重复编码使重复编码使PE减小减小 n原因原因: 这种编码可以纠正码字中的一位码元出错, 译错的可能性变小了, 因此错误概率降低. 简单重复编码 n若重复更多次更多次可进一步降低错误率. 可算得 n可见, 当n很大时, 使PE很小是可能的. 但这又带来 了一个新问题, n很大时, 信息传输率会降低很多. 5 7 8 10 510 74 10 910 115 10 E E E E nP nP nP nP 简单重复编码 编码后信息传输率为 在上例中： M=2 当n=1时 R=1 当n=3时 R=1/3 当n=5时 R=1/5 . . 由此得PE和R的关

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

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

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

52、所有的码书计算其平均错 误概率。当n足够大时，此平均错误概率趋于零， 由此证明得至少有一种好码存在。 ),( 21n xxxx ),( 21n yyyy n k kk xypP 1 )|()|(xy 2 , 1 nR nnR X2 , 1 : 2 , 1 : nRn X )|(mmmPP Em m Em nR E PP 2 1 证明证明：离散无记忆信道离散无记忆信道X, p(y|x), Y，输入序列为，输入序列为 输出序列：输出序列： 转移概率：转移概率： 编码速率为编码速率为R，则消息的标号集为，则消息的标号集为 编码函数可看作下述映射：编码函数可看作下述映射： 译码函数为：译码函数为： 发

53、送发送m的条件下译码错误概率为：的条件下译码错误概率为： 译码的平均误组率为（消息等概）译码的平均误组率为（消息等概） 具体的证明过程-了解 从从 中独立随机地选取中独立随机地选取 个序列作为码字，个序列作为码字， 这相当于每个码字出现的概率为消息序列出现的概率这相当于每个码字出现的概率为消息序列出现的概率: n X nR 2 n k k xPP 1 )()(x X中任一元素独立等概地出现，中任一元素独立等概地出现， 这种编码方法称作这种编码方法称作随机编码随机编码。 译码规则：译码规则： （典型序列准则（典型序列准则译为联合典型序列的译为联合典型序列的x） 对给定的接受序列对给定的接受序列y

54、，若存在唯一的，若存在唯一的 使使 就将就将y译为译为m，即，即D(y)=m 。当。当 或者有两个或者有两个 以上以上m和和y构成联合典型序列时，就认为译码出错。构成联合典型序列时，就认为译码出错。 2 , 1 nR m )(),( XYG nm yx mm 就是任意特定消息被错误译码的概率。就是任意特定消息被错误译码的概率。 所以不失一般性可假设发送的是第一个消息。所以不失一般性可假设发送的是第一个消息。 译码错误概率为译码错误概率为 )ym1( )ym( 1 构成联合典型序列与的不是 构成联合典型序列不与即 mmPPP EE )Y:X( IRn)Y:X( InnR m m )Y:X( In

55、 m nc m m c EE )E(P )E(P;)E(P )E(P)E(PPP 33 1 3 1 1 11 222 20 因为随机码具有对称性，所以译码错误概率与送出的因为随机码具有对称性，所以译码错误概率与送出的 消息编号无关，也就是随机码集合消息编号无关，也就是随机码集合的平均错误概率的平均错误概率 R)Y;X( In )Y;X( InnR nR i )Y;X( In e )Y;X( In ni C nR i i C nR C e n C nR ni )(P )i ()XY(G),i (P)E(P );n()E(P)E(P )E(P)E(P )EEEE(P)(|)(gPP )XY(G),

56、(E ,.i),XY(G),i (E 3 3 2 2 3 1 3 11 2 2 1 2 3211 1 2 2122 2 1yx 1 1xx1y y1x 21yx 再具体一些说，就是：再具体一些说，就是： 为了使为了使R大，可使大，可使 I(X:Y) 极大化，即以极大化，即以C代替。代替。 若若RC-3 ，随着，随着 n 趋于无穷大，上面的错误概率趋于趋于无穷大，上面的错误概率趋于0。 因为因为RC-3 ，上面的错误概率趋于，上面的错误概率趋于0，所以必定存在一种，所以必定存在一种 码，当码，当 n 足够大时，其译码错误概率为足够大时，其译码错误概率为0。 Shannon第二定理另一种形式！ 有

57、噪信道编码定理信道编码定理，即Shannon第二定理。 -书上的证明方法！ P106 5 53 3 信道编码定理信道编码定理 定理定理5.1 对于任何离散无记忆信道DMC，存在信息 传输率为R，长为n的码，当n 时，平均差错概率 pe exp- nE (R)0，式中E (R) 为可靠性函数，E ( R )在0 R C的范围内为正。 1 随机编码方法 信道输入符号集A=a1,a2,ak,选用长为n的定长码，共可 构成k n个矢量，设有M个消息待传（M k n），每次随机地 从k n个矢量中抽出M个矢量构成一个码集C（允许重复取） C = x1 , , x m , , x M 共可构成k nM个这

58、样的码集。 由随机编码的构造方法，得到任何一个码字的概率相同， 且相互独立。 上述定理也称有噪信道编码定理信道编码定理，即Shannon第二定理。 2Gallager上界 因为上述按随机编码方法构成的码集是等概分布的，按照最 大似然译码准则译码，在发送码矢xk时，要得到正确译码须 满足 ，即 （5-5） kmpp mk x xy yx xy y 1 m k p p x xy y x xy y 01 m k p p x xy y x xy y 定义示性函数 Mm pp pp I mk mk k , 2 , 1 )()(1 )()(0 )( x xy yx xy y x xy yx xy y y

59、y 则发送码矢xk判错的概率为 （5-6） kkke pIpx xy yy yx x y y 书上错的书上错的 根据式(5-5)，当0 , 1时，下式成立 mk mk km k m pp pp p p x xy yx xy y x xy yx xy y x xy y x xy y 当 当 1 0 用示性函数Ik (y)表示上式，即 （5-7） ki k m k p p I x xy y x xy y y y 将式(5-7)代入式(5-6)，得 km k m kke p p pp x xy y x xy y x xy yx x y y 式中0 , 1，因为 , 都是任意数，可取 ，则有 （5-8

60、） 1 1 km mkke ppp 1 1 1 1 x xy yx xy yx x Gallager上界上界 3 随机编码错误概率上界随机编码错误概率上界 Gallager限仅给出发送码矢xk时的错误概率上界，还要对全 部码矢求平均，下面对上述的随机编码集合求平均。 对于随机编码，各码字等概且独立，有， 对式(5-8)求统计平均值，得平均错误概率上界 M m mMm qq 1 1 x xx xx xx x, keMm pqp M x xx xx xx x x xx x , e , 1 1 y yx xx x x xy yx xy yx xx xx x km mkM ppqqq M 1 1 1