信息论与编码2012.ppt

1、Wisdom in the mind is better than money in the hand,信息论与编码基础,香农三大定理 简介,一、香农第一定理,二、香农第二定理,三、香农第三定理,无失真信源编码,有噪离散信道编码,保真度准则下的信源编码,信息论与编码基础,香农三大定理 简介,一、香农第一定理,二、香农第二定理,三、香农第三定理,信息论与编码基础,香农三大定理 简介,1、信源编码器,a、模型,单符号信源无失真编码器,码符号,码字,码长,信息论与编码基础,香农三大定理 简介,N次扩展信源无失真编码器,1、信源编码器,a、模型,信息论与编码基础,香农三大定理 简介,b、举例,1）AS

2、CII信源编码器,1、信源编码器,信息论与编码基础,香农三大定理 简介,1、信源编码器,2）摩尔斯电码,b、举例,信息论与编码基础,香农三大定理 简介,3）中文电报信源编码器,“中”,“0022”,“01101 01101 11001 11001”,1、信源编码器,b、举例,信息论与编码基础,香农三大定理 简介,c、分类,等长码,变长码,中文电报,莫尔斯电码,有失真编码,无失真编码,I(S;C) H(S),I(S;C) = H(S),惟一可译码,非惟一可译码,若某一种码的任意一串有限长的符号序列只能 被惟一地译成所对应的信源符号。,1、信源编码器,信息论与编码基础,香农三大定理 简介,d、指标

3、,1) 平均码长,code/sign,code/N-sign,1、信源编码器,信息论与编码基础,香农三大定理 简介,2) 编码后的信息传输率,bit/code,bit/code,d、指标,1、信源编码器,信息论与编码基础,香农三大定理 简介,3) 编码效率,d、指标,1、信源编码器,信息论与编码基础,香农三大定理 简介,例：二元DMS进行无失真编码,H(S) = H(3/4,1/4) = 0.811(bit/sign),N=1,(code/sign),(bit/code),信息论与编码基础,香农三大定理 简介,例：二元DMS进行无失真编码,H(S) = H(3/4,1/4) = 0.811(b

4、it/sign),N=2,0,10,110,111,(code/2-sign),(bit/code),信息论与编码基础,香农三大定理 简介,例：二元DMS进行无失真编码,H(S) = H(3/4,1/4) = 0.811(bit/sign),N=3,(bit/code),N=4,(bit/code),随着N的增加，平均码长减小，有效性逐步提高； 当N趋于无穷时，平均码长可以无限制地减小吗？,信息论与编码基础,香农三大定理 简介,2、香农第一定理（可变长无失真信源编码定理）,信息论与编码基础,香农三大定理 简介,表述二：若RH(S)，就存在惟一可译变长编码；若RH(S)， 惟一可译变长编码不存在

5、，不能实现无失真编码。其中,2、香农第一定理（可变长无失真信源编码定理）,信息论与编码基础,香农三大定理 简介,说明：,1）通过对扩展信源进行可变长编码，可以使平均码长无限趋近 于极限熵值，但这是以编码复杂性为代价的。,2）无失真信源编码的实质：对离散信源进行适当的变换，使变换后新的符号序列信源尽可能为等概率分布，从而使新信源的每个码符号平均所含的信息量达到最大。,3）香农第一定理仅是一个存在性定理，没有给出更有效的信源 编码的实现方法。,2、香农第一定理（可变长无失真信源编码定理）,信息论与编码基础,香农三大定理 简介,总结：,信源编码器模型,性能指标,香农第一定理（无失真信源编码定理）,平

6、均码长、信息传输率、编码效率,信息论与编码基础,香农三大定理 简介,一、香农第一定理,二、香农第二定理,三、香农第三定理,有效性 可靠性 矛盾,X,信息论与编码基础,香农三大定理 简介,1、错误概率,误码率,误字率,p = 0.01,PE = P(a1)P(b2|a1)+P(a2)P(b1|a2),= p + (1-)p = 0.01,错误概率与哪些因素相关？,信息论与编码基础,香农三大定理 简介,2、常用判决准则,a、MAP准则（Maximum a Posteriori）,对于所有的,信息论与编码基础,香农三大定理 简介,b、ML准则（Maximum Likelihood）,若输入符号等概时

7、,似然比,2、常用判决准则,a、MAP准则（Maximum a Posteriori）,信息论与编码基础,香农三大定理 简介,例1 重复编码,(n,1),信息论与编码基础,香农三大定理 简介,n=5,PE 10-5,n=7,PE 410-7,n=9,PE 10-8,R = logM/n,bit/code,R = logM/5,R = logM/7,R = logM/9,可靠性增强,有效性减小,矛盾,例1 重复编码,(n,1),信息论与编码基础,香农三大定理 简介,例2 （5，2）线性码,PE = 7.8*10-4 ， R = 0.4,信息论与编码基础,香农三大定理 简介,例2 （5，2）线性码

8、,信息论与编码基础,香农三大定理 简介,要兼顾通信的有效性和可靠性是有可能的。但这种兼顾的极限在哪里呢？有没有可能在保证一定的有效性前提下使可靠性达到最佳，或者使得有效性与可靠性同时达到最佳呢？ 香农指出，这是完全可能的。有可能在传输错误Pe 无穷小的同时，信息传输率R可无限接近信道容量C.,信息论与编码基础,香农三大定理 简介,3、香农第二定理（有噪信道编码定理）,表述二： 若在信息传输率R不大于信道容量C（即RC），则存在一种编码，当码长n足够大时，它可以使信道输出端的错误概率任意小，而信息传输率无限接近C；如果RC，则不可能找到一种编码，使输出端错误概率任意小。,信息论与编码基础,香农三

9、大定理 简介,3、香农第二定理（有噪信道编码定理）,信息论与编码基础,香农三大定理 简介,说明：,1、定理纠正了人们传统固有的可靠性和有效性矛盾的观点， 为信道编码理论和技术的研究指明了方向。,2、定理仅指出编码的存在性，未给出编码的具体方法。,3、定理指出：RC是可靠传输的必要条件，但并未指出编码 序列无限长是可靠传输的必要条件。,3、香农第二定理（有噪信道编码定理）,AWGN 1)Turbo码：1/2码率，BPSK，65536随机交织， 18次迭代，Pe=10-5, Eb/N0 = 0.7dB 2)非规则LDPC码：N = 107, 1/2码率， Pe=10-5, Eb/N0 = 0.00

10、45dB,4、香农进一步证明：R=C时，任意小的差错概率也是可以达 到的。,证明基本条件：1）随机编码 2）码长 3）最大似然译码,信息论与编码基础,香农三大定理 简介,一、香农第一定理,三、香农第三定理,二、香农第二定理,不大于一定编码速率的条件下，使平均失真限 制到最小；,在平均失真不大于某个值的条件下，使编码 速率限制到最小,信息论与编码基础,香农三大定理 简介,信息率失真理论,1、失真度与信息率失真函数,a、系统模型,信息论与编码基础,香农三大定理 简介,b、失真测度,1）单符号失真测度,设,定义失真矩阵,信息论与编码基础,香农三大定理 简介,1、失真度与信息率失真函数,如果规定,，那

11、么失真矩阵为,N=3时，失真度如图,信息论与编码基础,香农三大定理 简介,1、失真度与信息率失真函数,b、失真测度,2)序列失真测度,设序列,定义序列失真测度为,信息论与编码基础,香农三大定理 简介,1、失真度与信息率失真函数,b、失真测度,3)平均失真,单符号平均失真,序列平均失真,信息论与编码基础,香农三大定理 简介,1、失真度与信息率失真函数,b、失真测度,c、信息率失真函数,信息论与编码基础,香农三大定理 简介,1、失真度与信息率失真函数,信息论与编码基础,香农三大定理 简介,信息率失真函数性质,1）当D0时,R(D)无意义,2）存在一个Dmax，使D Dmax时,R(D)=0,3）R

12、(0)=H(X),4）在0D Dmax范围内,R(D)是正的、连续的下凸函数,二、香农第三定理（保真度准则下的信源编码定理）,信息论与编码基础,香农三大定理 简介,表述二：,信息论与编码基础,香农三大定理 简介,二、香农第三定理（保真度准则下的信源编码定理）,几点讨论,1）R(D)确定是保真度准则条件下，信源信息率压缩的下限。,2）R(D)在实际工程中可以作为衡量各种压缩编码方法性能 优劣的一种标尺。,3）是一种存在定理，其实际应用有待于进一步研究：,a)如何计算符合实际信源的信息率失真函数R(D)？,b)如何寻找最佳编码方法才能达到信息压缩的极限值R(D)？,二、香农第三定理（保真度准则下的信源编码定理）,信息论与编码基础,香农三大定理 简介,信息论与编码基础,香农三大定理 简介,信息论与编码基础,香农三大定理 简介,香农第二定理（有噪信道编码定理）,R C,信息率失真函数,香农第三定理（保真度准则下的信源编码定理）,R R(D),RH(S),香农第一定理（可变长无失真信源编码定理）,信道容量,信源熵,香农 公式,信息论“三大定理”总结,香农信息论的三个基本概念信源熵、信道