信息论与编码基础.ppt
信息论与编码基础,香农三大定理简介,一、香农第一定理,二、香农第二定理,三、香农第三定理,无失真信源编码,有噪离散信道编码,保真度准则下的信源编码,信息论与编码基础,香农三大定理简介,一、香农第一定理,二、香农第二定理,三、香农第三定理,信息论与编码基础,香农三大定理简介,1、信源编码器,a、模型,单符号信源无失真编码器,码符号,码字,码长,信息论与编码基础,香农三大定理简介,N次扩展信源无失真编码器,1、信源编码器,a、模型,信息论与编码基础,香农三大定理简介,b、举例,1）ASCII信源编码器,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、指标,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(bit/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)，惟一可译变长编码不存在，不能实现无失真编码。其中,2、香农第一定理（可变长无失真信源编码定理）,信息论与编码基础,香农三大定理简介,说明：,1）通过对扩展信源进行可变长编码，可以使平均码长无限趋近于极限熵值，但这是以编码复杂性为代价的。,2）无失真信源编码的实质：对离散信源进行适当的变换，使变换后新的符号序列信源尽可能为等概率分布，从而使新信源的每个码符号平均所含的信息量达到最大。,3）香农第一定理仅是一个存在性定理，没有给出更有效的信源编码的实现方法。,2、香农第一定理（可变长无失真信源编码定理）,信息论与编码基础,香农三大定理简介,总结：,信源编码器模型,性能指标,香农第一定理（无失真信源编码定理）,平均码长、信息传输率、编码效率,信息论与编码基础,香农三大定理简介,一、香农第一定理,二、香农第二定理,三、香农第三定理,有效性 可靠性 矛盾,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）,信息论与编码基础,香农三大定理简介,例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、香农第二定理（有噪信道编码定理）,表述二：若在信息传输率R不大于信道容量C（即RC），则存在一种编码，当码长n足够大时，它可以使信道输出端的错误概率任意小，而信息传输率无限接近C；如果RC，则不可能找到一种编码，使输出端错误概率任意小。,信息论与编码基础,香农三大定理简介,3、香农第二定理（有噪信道编码定理）,信息论与编码基础,香农三大定理简介,说明：,1、定理纠正了人们传统固有的可靠性和有效性矛盾的观点，为信道编码理论和技术的研究指明了方向。,2、定理仅指出编码的存在性，未给出编码的具体方法。,3、定理指出：RC是可靠传输的必要条件，但并未指出编码序列无限长是可靠传输的必要条件。,3、香农第二定理（有噪信道编码定理）,AWGN1)Turbo码：1/2码率，BPSK，65536随机交织，18次迭代，Pe=10-5,Eb/N0=0.7dB2)非规则LDPC码：N=107,1/2码率，Pe=10-5,Eb/N0=0.0045dB,4、香农进一步证明：R=C时，任意小的差错概率也是可以达到的。,证明基本条件：1）随机编码 2）码长 3）最大似然译码,信息论与编码基础,香农三大定理简介,一、香农第一定理,三、香农第三定理,二、香农第二定理,不大于一定编码速率的条件下，使平均失真限 制到最小；,在平均失真不大于某个值的条件下，使编码 速率限制到最小,信息论与编码基础,香农三大定理简介,信息率失真理论,1、失真度与信息率失真函数,a、系统模型,信息论与编码基础,香农三大定理简介,b、失真测度,1）单符号失真测度,设,定义失真矩阵,信息论与编码基础,香农三大定理简介,1、失真度与信息率失真函数,如果规定,，那么失真矩阵为,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(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),
