香农三大定理详解.ppt

1、信息论与编码基础,香农三大定理 简介,一、香农第一定理,二、香农第二定理,三、香农第三定理,无失真信源编码,有噪离散信道编码,保真度准则下的信源编码,信息论与编码基础,香农三大定理 简介,一、香农第一定理,二、香农第二定理,三、香农第三定理,信息论与编码基础,香农三大定理 简介,1、信源编码器,a、模型,单符号信源无失真编码器,码符号,码字,码长,信息论与编码基础,香农三大定理 简介,N次扩展信源无失真编码器,1、信源编码器,a、模型,信息论与编码基础,香农三大定理 简介,b、举例,1）ASCII信源编码器,1、信源编码器,信息论与编码基础,香农三大定理 简介,1、信源编码器,2）摩尔斯电码,

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

3、定理 简介,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(bit/sign),N=2,0,10,110,111,(code/2-sign),(bit/code),信

4、息论与编码基础,香农三大定理 简介,例：二元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)， 惟一可译变长编码不存在，不能实现无失真编码。其中,2、香农第一定理（可变长无失真信源编码定理）,信息论与编码基础,香农三大定理

5、 简介,说明：,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）,若输入符号等概时,似然比,2、常用判决准则,a、MAP准则（Maximum a Posteriori）,信息论与编码

7、基础,香农三大定理 简介,例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）线性码,信息论与编码基础,香农三大定理 简介,3、香农第二定理（有噪信道编码定理）,表述二： 若在信息传输

8、率R不大于信道容量C（即RC），则存在一种编码，当码长n足够大时，它可以使信道输出端的错误概率任意小，而信息传输率无限接近C；如果RC，则不可能找到一种编码，使输出端错误概率任意小。,信息论与编码基础,香农三大定理 简介,3、香农第二定理（有噪信道编码定理）,信息论与编码基础,香农三大定理 简介,说明：,1、定理纠正了人们传统固有的可靠性和有效性矛盾的观点， 为信道编码理论和技术的研究指明了方向。,2、定理仅指出编码的存在性，未给出编码的具体方法。,3、定理指出：RC是可靠传输的必要条件，但并未指出编码 序列无限长是可靠传输的必要条件。,3、香农第二定理（有噪信道编码定理）,AWGN 1)Tu

9、rbo码：1/2码率，BPSK，65536随机交织， 18次迭代，Pe=10-5, Eb/N0 = 0.7dB 2)非规则LDPC码：N = 107, 1/2码率， Pe=10-5, Eb/N0 = 0.0045dB,4、香农进一步证明：R=C时，任意小的差错概率也是可以达 到的。,证明基本条件：1）随机编码 2）码长 3）最大似然译码,信息论与编码基础,香农三大定理 简介,一、香农第一定理,三、香农第三定理,二、香农第二定理,不大于一定编码速率的条件下，使平均失真限 制到最小；,在平均失真不大于某个值的条件下，使编码 速率限制到最小,信息论与编码基础,香农三大定理 简介,信息率失真理论,1、

10、失真度与信息率失真函数,a、系统模型,信息论与编码基础,香农三大定理 简介,b、失真测度,1）单符号失真测度,设,定义失真矩阵,信息论与编码基础,香农三大定理 简介,1、失真度与信息率失真函数,如果规定,，那么失真矩阵为,N=3时，失真度如图,信息论与编码基础,香农三大定理 简介,1、失真度与信息率失真函数,b、失真测度,2)序列失真测度,设序列,定义序列失真测度为,信息论与编码基础,香农三大定理 简介,1、失真度与信息率失真函数,b、失真测度,3)平均失真,单符号平均失真,序列平均失真,信息论与编码基础,香农三大定理 简介,1、失真度与信息率失真函数,b、失真测度,c、信息率失真函数,信息论

11、与编码基础,香农三大定理 简介,1、失真度与信息率失真函数,信息论与编码基础,香农三大定理 简介,信息论与编码基础,香农三大定理 简介,信息率失真函数性质,1）当D0时,R(D)无意义,2）存在一个Dmax，使D Dmax时,R(D)=0,3）R(0)=H(X),4）在0D Dmax范围内,R(D)是正的、连续的下凸函数,二、香农第三定理（保真度准则下的信源编码定理）,信息论与编码基础,香农三大定理 简介,表述二：,信息论与编码基础,香农三大定理 简介,二、香农第三定理（保真度准则下的信源编码定理）,几点讨论,1）R(D)确定是保真度准则条件下，信源信息率压缩的下限。,2）R(D)在实际工程中可以作为衡量各种压缩编码方法性能 优劣的一种标尺。,3）是一种存在定理，其实际应用有待于进一步研究：,a)如何计算符合实际信源的信息率失真函数R(