无损信源编码.pptVIP

*第1页，共38页，星期日，2025年，2月5日信息熵和信源编码定理（1）1.信息熵计算公式x0,x1…..xr…x∈A={a1,a2…am}H0=log2mbitH1=-∑p(x)logp(x)H2=-∑p(x0)∑P(x1|x0)logP(x1|x0)…….Hk+1=-∑p(x0,x1..xk-1)∑P(xk|x0,x1..xk-1)logP(xk|x0,x1..xk-1)*第2页，共38页，星期日，2025年，2月5日信息熵和信源编码定理（2）H0?H1?….?Hk?…...H(x0,x1..xk-1)=-∑p(x0,x1..xk-1)logp(x0,x1..xk-1)极限熵H=LimHk=LimH(x0,x1..xk-1)/kk无限2.等长码的编码定理码字同样长有利于传输典型序列——ar出现Spr次.*第3页，共38页，星期日，2025年，2月5日信息熵和信源编码定理(3)当S趋于无限，非典型序列出现的概率趋于零。可只编这些序列，差错接近零。典型序列个数是N=S!/∏(Spr)！用斯斗林公式S!=(S/e)S√(2πS)每个信源符号所需码长是(S→∝)liml=lim(logN)/S=-∑prlogpr*第4页，共38页，星期日，2025年，2月5日熵和信信息源编码定理(4)S有限时有失真，可容忍时S已很大。很难实现。3.变长码的编码定理可分离的必要条件是异前置性。码树结构(根，叶，节，枝）R000111*第5页，共38页，星期日，2025年，2月5日信息熵和信源编码定理(5)一个长为li的码字占2L-li个长为L的码字。Kraft不等式：∑2L-li≤2L，∑2-li≤1可分离的充要条件。可推广到k进码。若li=?-logpi?-logpi≦l1-logpi,*第6页，共38页，星期日，2025年，2月5日信息熵和信源编码定理(6)∑2-li≦∑pi=1,可以编码,平均码长l，有-∑pilogpi≦l=∑lipi1-∑pilogpi,SH1≦Sl1+SH1,S→∝,l→H1,这就是变长码编码定理，得证。对于相关信源，可把一段（长S）序列作为一个符号，有mS个码字,进行编码。*第7页，共38页，星期日，2025年，2月5日赫夫曼编码（1）1.概述从仙农码到赫夫曼码例xia1a2a3a4a5pi0.40.30.20.050.05li22355码字00011001010010101Ra1(00)a2(01)a3(100)a4(10100)a5(10101)*第8页，共38页，星期日，2025年，2月5日赫夫曼编码(2)这是仙农码，非满树，可改进。平均码长l=2.5,H=1.95编码效率η=H/l=78%不先规定码长的费诺码0(a1,a4,a5)0(a1)001(a4,a5)0(a4)010