信息论第四章失真率函数(课堂PPT).ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第4章,率失真编码,1,内容提要,数据压缩是信息传输和处理的重要研究内容，率失真理论研究的就是在允许一定失真的前提下，对信源的压缩编码。率失真信源编码定理（香农第三定理）指出：率失真函数,R,(,D,),就是在给定失真测度条件下，对信源熵可压缩的最低程度。,本章只限于研究率失真理论最基本的内容，失真测度，率失真函数，率失真函数的定义域，值域，性质及定量计算。,R,(,D,),的计算很烦琐，文中通过二个例子介绍了几种特殊情况下,R,(,D,),的求法，一般情况只能用参数法求解。,第4章 率失真编码,2,信息率失真函数,R,(,D,),香农,1959,年提出,在允许一定,失真度,D,的情况下，,信源输出的,信息率可压缩为,R,(,D,),值,数据压缩的理论基础,I,(,X,;,Y,),H,(,X,),、,H,(,Y,/,X,),的二元函数,固定,H,(,Y,/,X,),，改变,H,(,X,),得,I,(,X,;,Y,),最大值,信道容量,固定,H,(,X,),，改变,H,(,Y,/,X,),得,I,(,X,;,Y,),最小值,率失真函数,第4章 率失真编码,3,1,失真测度,d,(,x,y,),给定离散信源 ，,信道,输出符号,y,j,引起的失真用,d,(,x,i,y,j,)（,i,=1,I,j,=1,J,）,表示，简记为,d,i j,，,将所有的,d,i j,列出来，可以得到下面的失真测度矩阵,(4-1),在允许一定失真的前提下，从提高传输效率的角度出发，可以对信源信息量事先进行压缩再予传输，这章要讨论的问题就是给定一个失真度，求出在平均失真小于给定值的条件下，信源所能压缩的最低程度，即率失真函数,R,(,D,)。,4.1 失真测度与平均失真,4,【,例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）,5,【,例,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,1,2,，,给出失真测度,d,i j,=,x,i,-,y,j,i,j,=0,1,2,则失真测度矩阵为,6,2.,平均失真,离散信源 ，经有扰信,道传输，信道输出符号为,Y,=,y,1,y,2,y,J,，,平均失真即对,d,i j,（,i,=1,2,I,;,j,=1,2,J,）,求统计平均值，记为,（4-4）,平均失真 是对在给定信源分布,q,(,x,),条件下，通过有扰信道传输而引起失真的统计平均度量。,7,平均失真说明：,是在,平均意义,上，对系统失真的总体描述,是信源统计特性,p,(,x,i,),的函数,是信道统计特性,p,(,y,j,/,x,i,),的函数,是规定失真度,d,(,x,i,y,j,),的函数,若保持,p,(,x,i,),、,d,(,x,i,y,j,),不变，则平均失真度就是信道特性,p,(,y,j,/,x,i,),的函数,8,N,次扩展信道,对于矢量传输情况，若信道的输入、输出符号均为,N,长序列,X=X,1,，,X,k,X,N,Y=Y,1,，,Y,k,Y,N,，,平均失真定义为,（4-,5,）,（,4-5,）式表明了离散无记忆,N,次扩展信道的输入输出符号之间平均失真等于单个符号,x,ki,y,kj,之间失真统计值的总和。,9,若矢量信源是原离散无记忆信道的,N,次扩展，且矢量信道也是原离散无记忆信道的,N,次扩展，则每个,对一位信源信道所取的均值相等，即,从而，,10,4.2.1 率失真函数的定义,给定信源，即信源概率分布,q,(,x,),一定，给定失真测度矩阵,d,=,d,ij,，,寻找信道，记它的转移概率矩阵为,，要求满足,（4-11）,式中,D,是预先给定的失真度，上式称为,保真度准则,。,4.2 信息率失真函数,R,(,D,),11,根据定理2.2，当信源,q,(,x,),一定时，平均互信息量,I,(,X,;,Y,),是信道转移概率函数,p,(,y,x,),的型凸函数，这意味着可以关于,p,(,y,x,),对平均互信息量,I,(,X,;,Y,),求得极小值，定义这个极小值为,率失真函数,R,(,D,),，,即：,(4-12),式(4-12)的意义在于，选择,p,(,y,x,),即选择某种编码方法在满足 的 前提下，使,I,(,X,;,Y,),达到最小值,R,(,D,)，,这就是满足平均失真 条件下的信源信息量可压缩的最低程度。,12,补充：试验信道,(,D,允许信道,),P,D,1.,定义：,固定信源,(,H,(,X,),时，,满足失真度,准则,的所有转移概率,p,(,y,/,x,),的集合,2.,单符号信源、单符号信道的试验信道,3.,N,次扩展信源、,N,次扩展信道的,P,D,(,N,),4.2 信息率失真函数,R,(,D,),13,（1）,D,的最小值,D,min,在给定的失真测度矩阵中，对每一个,x,i,，,找一个最小的,d,i j,，,然后对所有的,i,=1,2,I,求统计平均值，就是,D,的最小值，即,(4-14),2.,R,(,D,),的定义域,4.2.2 率失真函数的值域、定义域,1.,R,(,D,),的值域（,参见图,4-1）,率失真函数的值域为,0,R,（,D,）,H,（,X,）,(4-13),D,图41,R,（,D,）,的值域,D,max,0,D,min,H（,X,）,R,(,D,),14,求出计算,D,max,的显式:,j,=1,2,J,（4-18）,（2）D,的最大值,D,max,当,R,(,D,),达到其最小值,R,min,（,D,）=0,时，对应的失真最大，这种情况下,D,对应着,R,(,D,),函数定义域的上界值,D,max,，,如图,4-1,所示。,=,min,D,:,I,(,X,;,Y,)=0,（4-15),纵上所述，,R,(,D,),的定义域为：,D,min,D,D,max,，,式中,D,min,和,D,max,可分别由式（,4-14,）和式（,4-18,）求出。,15,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-19,）,16,4.3.1二种特殊情况下的求解,【,例,4,.8,】信源含两个消息,x,1,=0,，,x,2,=1,其概率分布为,0.5,，,信道输出符号,Y,=,y,1,=0,，,y,2,=1,，,失真测度为汉明（,Hamming,）,失真测度，求率失真函数,R,(,D,),。,(1),根据式,(4-14),和,(4-18),可求出,R,(,D,),的定义域,D,min,=0,+0,(1,-,)=0,D,max,=min 1,-,=,(2),求,R,(,D,),的值域,R,(,D,min,=0)=,H,(,U,)=,-,log,-,(1,-,)log(1,-,)=,H,2,(,),R,(,D,max,)=,R,(,)=0,4.3 率失真函数的计算,17,根据熵的性质,H（XY）,H(X),H(XY)，,又算出,H(X)=-,log,-(1-,)log(1,-,)=,H,2,(,),将这两个结果代入平均互信息量的表达式,I(X;Y)=H(X)-H(XY)，,得到,I(X;Y),H,2,()-H(XY)（4-32）,（3）在,0,D,的范围内，计算,R,(,D,）,对于汉明失真测度，失真测度矩阵为,平均失真,在,R,(,D,),的定义中，要求满足 ，取等号 ，则,H,（,XY,）,=,H,2,（,X,Y,）,=,H,2,p,(,X,Y,)=,H,2,(,D,),将这一结果代入式（,4-32,），得,I,（,X,；,Y,）,H,2,(,),-,H,2,(,D,),根据定义,=,H,2,(,),-,H,2,(,D,),18,根据,d,的对称性，假设一个反向信道(,Y,X,),反向信道的转移概率矩阵为，假设的反向信道应满足：,(,x,i,y,j,),0,i,j,=1,2,（4）上面是按照定义求出了,R,(,D,)，,下面的问题是要真正找到这么一个信道转移概率矩阵为,P,的信道，使,H,（,Y,X,）=,H,2,（,D,），,从而,R,(,D,)=,H,2,(,)-,H,2,(,D,)，,且,P,中的每一个元素,p,(,y,j,x,i,),都满足,p,(,y,j,x,i,),0,i,j,=1,2,19,由假设的反向信道计算平均失真，得,=,(,y,1,)+,(,y,2,)D=D,计算条件熵：,=-(1-,D,)log(1-,D,)-,D,log,D,=,H,2,(,D,),则平均互信息量,I,(,X,;,Y,)=,H,(,X,)-,H,(,X,Y,)=,H,2,(,)-,H,2,(,D,)，,假设的,(,x,y,),确实在满足 的条件下，使,I,(,X,;,Y,)=,H,2,(,)-,H,2,(,D,)。,从而有,由上式知 ，满足失真条件 。,20,（5）要找出正向信道，可由 ，,反解出,(,y,j,)，,j,=1,2,，,再计算出 。,=,（,1-,D,）,（,y,1,）,+,D,(,y,2,),1-,=D,（,y,1,）,+,（,1-,D,）,(,y,2,),由上面方程组解出，,再算出,21,【,例,4,.,9,】,信源分布 ，失真测度矩阵为:,，计算率失真函数,(1)求出,R,(,D,),的定义域,（2)计算,R,(,D,),根据,d,的对称性，可假设信道转移概率矩阵 ,式中 为待定常数。,由假设的信道转移概率计算信息量,（4-33）,22,先算出,(4-34),将式(,4-34),代入式,(4-33,)得,即 （4-35）,23,由假设的信道转移概率计算平均失真，得,（4-36）,因为 ，由式(,4-36,)得,考虑到 ，则,如图4-3所示：在 的范围,内，,H,2,(,),是单调递增函数，有,H,2,(,),图 4-3,H,2,(,)-,曲线,0,1,0.5,24,根据式(,4-35,)，得,从而,25,4.3.2,R,（,D,）,的参数表示法,(2)由式(,4-40,)求 ；,(3)由式(,4-39,)求,p,(,y,j,x,i,),；,(4),由式(,4-42,)求,D,；,(5),由式(,4-43,)求,R,(,D,),。,用参数法求,R,(,D,),，,可按下述步骤进行：,（1）由式(,4-41,),求 ；,26,用此法求解，有时候会出现,(,y,j,)0,的情况,碰到这种情况，就要令某一,(,y,*,j,)=0，,重复刚才的求解过程，这种情况下求得的,R,(,D,),是一折线，折点对应,(,y,*,j,)=0，,如图45所示。,图4-5,(,y,*,j,)0,的情况,D,0,对应,(,y,*,j,)=0,R,(,D,),【例4.10】仍考虑例4.8的输入概率分布,q,(,x,1,)=,，,q,(,x,2,)=1,，,R,(,D,),时，,只要信源序列长度,L,足够长，,必存在一种编码方式,C,，,使译码后的失真,且当,L,时，,0,反之,若,R,R,(,D,),则必可设计一种编码方式,满足,若系统,R,R,(,D,),则无法满足 要求,2.,逆定理,若已规定满足失真度准则,则对所有设计均有,R,R,(,D,),3.,R,R,(,D,),与 不能同时满足,34,4.4,限失真信源编码定理,(,续,),说明,4.,任何设计所得到的工作点,必,在,率失真函数曲线,R,(,D,),上面,R,Q,与,R,1,之比,理论上存在的最大可能压缩比,二、香农信息论,三个基本概念,信源熵、信道容量、率失真函数，都是,临界值,三个编码定理,无失真信源编码、限失真信源编码、信道编码，都是,存在性定理,END,0,D,1,D,max,D,R,(,D,),H,(,X,),R,1,R,Q,Q,35,（3）,如何求,R,(,D,),的定义域和值域,（2）,平均失真,对给定信源,q,(,x,),进行压缩编码，不同的编码方法对应不同的实验信道，可用信道转移概率,p,(,y,x,),来,描述该实验信道，用概率分布,p,(,x y,)=,q,(,x,),p,(,y,x,),对给定的失真测度求统计平均值就得到平均失真.,（1）,失真测度,可以理解为误码带来的代价，实际上发送同一符号而错成不同符号所带来的代价是不同的。,本 章 小 结,本章介绍在允许一定失真条件下，对给定信源进行压缩编码,信息传输率可压缩的最低下界谓之率失真函数,R,(,D,)。,重点讨论了以下几个问题,36,（5）,香农第三定理,保真度准则下的率失真编码定理，这是信息理论的重要定理之一。,（4）,求率失真函数,R,(,D,),本章通过两个例子讨论了两种特殊情况下,R,(,D,),的求法，在一般的离散无记忆情况下，可用书中介绍的参数法求解。当然一般离散信源的率失真函数的计算是相当困难和冗繁的，往往要借助计算机进行。,37,38,