第四章 信息率失真 李伟.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第4章,率失真编码,内容提要,数据压缩是信息传输和处理的重要研究内容，率失真理论研究的就是在允许一定失真的前提下，对信源的压缩编码。率失真信源编码定理（香农第三定理）指出：率失真函数,R,(,D,),就是在给定失真测度条件下，对信源熵可压缩的最大程度。,本章只限于研究率失真理论最基本的内容，失真测度，率失真函数，率失真函数的定义域，值域，性质及定量计算。,R,(,D,),的计算很烦琐，一般情况只能用参数法求解。,第4章 信息率失真函数,1,失真测度,d,(,x,y,),给定离散信源 ，,信道,输出符号,y,j,引起的失真用,d,(,x,i,y,j,)（,i,=1,2,I,j,=1,2,J,）,表示，简记为,d,i j,，,将所有的,d,i j,列出来，可以得到下面的失真测度矩阵,(4-1),在允许一定失真的前提下，从提高传输效率的角度出发，可以对信源信息量事先进行压缩再予传输，这章要讨论的问题就是给定一个失真度，求出在平均失真小于给定值的条件下，信源所能压缩的最低程度，即率失真函数,R,(,D,)。,4.1 失真测度与平均失真,【,例4.1,】,汉明,（,Hamming）,失真测度,信源输出符号,X,=,x,1,x,2,x,K,，,信道输出符号,Y,=,y,1,y,2,y,K,，,约定失真测度,上述约定可以用矩阵表示为,式中,d,i,j,0,i,j,=1,2,K,为信源方发送符号,x,i,而信宿方判为,y,j,引起的失真度。,对于矢量传输情况，若信道的输入、输出均为,N,长序列,X,=,X,1,X,2,X,N,，,Y,=,Y,1,Y,2,Y,N,，,定义失真测度为,（4-2）,【,例,4,.2,】,平方误差失真测度,信源输出符号,X,=0,1,2，,信道输出符号,Y,=0,1,2,，,给出失真测度,d,i j,=(,x,i,-,y,j,),2,i,j,=0,1,2,则失真测度矩阵为,【,例,4,.3,】,绝对值误差失真测度,信源输出符号,X,=0,1,2，,信道输出符号,Y,=0,12,，,给出失真测度,d,i j,=,x,i,-,y,j,i,j,=0,1,2,则失真测度矩阵为,2.,平均失真,离散信源 ，经有扰信道,传输，信道输出符号为,Y,=,y,1,y,2,y,J,，,平均失真即对,d,i j,（,i,=1,2,I,;,j,=1,2,J,）,求统计平均值，记为,（4-4）,平均失真 是对在给定信源分布,p,(,x,),条件下，通过有扰信道传输而引起失真的统计平均度量。,4.2.1 率失真函数的定义,给定信源，即信源概率分布,p,(,x,),一定，给定失真测度矩阵,d,=,d,ij,，,寻找信道，记它的转移概率矩阵为,，要求满足,（4-,5,）,式中,D,是预先给定的失真度，上式称为,保真度准则,。,4.2 信息率失真函数,R,(,D,),注：其中的信道即为假想的信道，而非真实信道，它实质上是对应的某一种编码方法。,根据定理2.2，当信源,p,(,x,),一定时，平均互信息量,I,(,X,;,Y,),是信道转移概率函数,p,(,y,x,),的型凸函数，这意味着可以关于,p,(,y,x,),对平均互信息量,I,(,X,;,Y,),求得极小值，定义这个极小值为,率失真函数,R,(,D,),，,即：,(4-,6),式(4-,6),的意义在于，选择,p,(,y,x,),即选择某种编码方法在满足 的 前提下，使,I,(,X,;,Y,),达到最小值,R,(,D,)，这就是满足平均失真 条件下的信源信息量可压缩的最大程度。,（1）,D,的最小值,D,min,在给定的失真测度矩阵中，对每一个,x,i,，,找一个最小的,d,i j,，,然后对所有的,i,=1,2,I,求统计平均值，就是,D,的最小值，即,(4-,8),2.,R,(,D,),的定义域,4.2.2 率失真函数的值域、定义域,1.,R,(,D,),的值域,（,参见图,4-1）,率失真函数的值域为,0,R,（,D,）,H,（,X,）,(4-7),D,图41,R,（,D,）,的值域,D,max,0,D,min,H（,X,）,R,(,D,),求出计算,D,max,的显式:,j,=1,2,J,（4-10）2）D,的最大值,D,max,当,R,(,D,),达到其最小值,R,min,（,D,）=0,时，对应的失真最大，这种情况下,D,对应着,R,(,D,),函数定义域的上界值,D,max,，,如图,4-1,所示。,=,min,D,:,I,(,X,;,Y,)=0,（4-9),纵上所述，,R,(,D,),的定义域为：,D,min,D,D,max,，,式中,D,min,和,D,max,可分别由式（,4-,8,）和式（,4-1,0,）求出。,4.2.3 率失真函数,的性质,率失真函数有如下几条性质:：,3.对于离散无记忆信源（,DMS）,R,(,N,),(,D,)=,N R,(,D,),2.,R,(,D,),是,D,的连续、单调、减函数,1.,R,(,D,),是,D,的型凸函数,分别给定两个失真度,D,1,和,D,2,（,D,min,D,1,D,2,D,max,），,则下式成立：,R,(,1,D,1,+,2,D,2,),1,R,(,D,1,)+,2,R,(,D,2,),（,4-11,）,(2)求 ；,(3)求,p,(,y,j,x,i,),；,(4),求,D,；,求,R,(,D,),。,用参数法求,R,(,D,),，,可按下述步骤进行：,（1）,求 ；,4.3 率失真函数的计算,【例4.10】输入概率分布,q,(,x,1,)=,，,q,(,x,2,)=1,，,0.5,，,失真测度矩阵，用参数法求,R(D)。,解：(1)根据式,得,解出,(2)由式,得,解出,(3)由式,，得,(4)得,(5)得,=,D,ln,D,+(1-D),ln,(1-D)+,H,2,(,),=H,2,(,)-,H,2,(D,),（3）,如何求,R,(,D,),的定义域和值域,（2）,平均失真,对给定信源,p,(,x,),进行压缩编码，不同的编码方法对应不同的实验信道，可用信道转移概率,p,(,y,x,),来,描述该实验信道，用概率分布,p,(,x y,)=,p,(,x,),p,(,y,x,),对给定的失真测度求统计平均值就得到平均失真.,（1）,失真测度,可以理解为误码带来的代价，实际上发送同一符号而错成不同符号所带来的代价是不同的。,本 章 小 结,本章介绍在允许一定失真条件下，对给定信源进行压缩编码,信息传输率可压缩的最低下界谓之率失真函数,R,(,D,)。,重点讨论了以下几个问题,（5）,香农第三定理,保真度准则下的率失真编码定理，这是信息理论的重要定理之一。,（4）,求率失真函数,R,(,D,),在一般的离散无记忆情况下，可用书中介绍的参数法求解。当然一般离散信源的率失真函数的计算是相当困难和冗繁的，往往要借助计算机进行。,