压缩理论极限与基本途径4

第三章

理论极限与基本途径

课前回顾文氏图中，各种熵之间的关系？两圆互相离开，条件熵增大，相关性减弱。X、Y信源相互独立时课前回顾两圆互相重合，条件熵为零，联合熵等于单个信源的熵。X、Y信源完全相关时课前回顾1离散无记忆信源2联合信源3随机序列

4率失真理论本章内容3.3随机序列有记忆信源：源字X的各分量不是互相独立的

极限熵把n个信源符号当作一个n维随机矢量X，其联合概率为P(X),熵为：平均符号熵为:(3.3.1)(3.3.2)若把前n-1个符号作为条件,则可求得最后一个符号Xn的熵为:信息论中已证明：对于离散平稳信源X，如果它的H(X1)<∞,下述结论成立:与均为随n增大而单调不增函数;①当n增大(考虑更多的元素互相依从关系)时,熵值将会进一步降低;为极限熵或极限信息量,用H∞表示③(3.3.4)②(3.3.3)

基本途径之三—利用条件概率数据压缩的途径之三

对于离散有记忆平稳信源，

1)理论上，可通过它的条件概率计算极限熵；

2)实践中，可利用条件概率进行编码，阶越高越有利。数据压缩的途径之三

对于离散平稳信源，

1)理论上，可通过它的条件概率计算极限熵；

2)实践中，可利用条件概率进行编码，阶越高越有利。任意两个不同时刻，信源发出的符号的概率分布完全相同，与时间起点无关H∞的计算极其困难

假定信源平稳;

测得n足够大的条件概率以近似计算H∞;

假定信源的记忆有限。Xp只与其前面M个符号Xp-1,

Xp-2,…,

Xp-M有关M阶Markov链：表示这M+1个符号(Xp-M,

Xp-M+1,,

Xp-1,Xp)组成的序列。M=1→

一阶Markov链P(Xp|Xp-1,

Xp-2,Xp-3,,

Xp-M)=P(Xp|Xp-1)P(X)=P(X1)P(X2|X1)P(X3|X2)P(Xn|Xn-1)M→

M阶Markov链P(Xp|Xp-1,

Xp-2,Xp-3,,

Xp-M)P(X)=P(X1)P(X2|X1)P(X3|X2,X1)P(Xn|Xn-1,X

n-2,,Xn-M)得到平均符号熵HM+1M=1→2阶条件熵H2H(X|Y)

和

H(Y|X)M=0→1阶熵H1

(信源无记忆)H(X)0阶熵H0(信源的最大离散熵)简化:信源等概率分布,有m种取值H0=logm=R对于一般平稳信源，有：有时只能得到H1，甚至H0，传输更浪费。只能计算HM，只好用传送HM的手段，传输不经济。实际符号熵是H∞，理论上只要传送H∞的手段即可。未能完全掌握其概率分布（3.3-5）对于PCM编码的数据,其无失真压缩的理论极限为:(3.3-6)等长的PCM编码:传送

H0测得各符号出现的概率,并按无记忆信源考虑的统计编码传送

H1,获得信息变差

I01=H0-H1

(统计了信源概率后获得的信息)进一步考虑利用前一取样值进行预测(DPCM)传送H2,获得信息变差I02=H0–H2若利用前M-1个取样值进行预测传送HM,获得信息变差I0M=H0-HM表3.18幅典型黑白电视图象的实测熵值序号图像内容H(X0)H(X0|X1)H(X0|X2)H(X0|X5,X1)H(X0|X1,X2)1戴胸花的女郎6.41454.04404.08243.26613.25472双人6.22003.98483.83972.95832.96983教授7.21003.64563.53954男孩与玩具7.13255.02684.79785戴草帽的妇女7.00304.58824.32756船7.03844.93804.86522.70252.66777水池7.35695.19145.41128分辨率测试卡6.94125.43865.4716熵值计算时所选的相邻像素位置关系X2X1X0X3X1X5X2X4X0图像1~2:美国电影电视工程师协会(SMPTE)测试图像图像3~8:欧洲广播联盟(EBU