信息论失真率函数.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第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,(,Dmax,)=,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页,