信息论与编码6.ppt

第6章率失真编码,内容提要数据压缩是信息传输和处理的重要研究内容，率失真理论研究的就是在允许一定失真的前提下，对信源的压缩编码。率失真信源编码定理（香农第三定理）指出：率失真函数R(D)就是在给定失真测度条件下，对信源熵可压缩的最低程度。本章只限于研究率失真理论最基本的内容，失真测度，率失真函数，率失真函数的定义域，值域，性质及定量计算。R(D)的计算很烦琐，文中通过二个例子介绍了几种特殊情况下R(D)的求法，一般情况只能用参数法求解。,第6章率失真编码,在允许一定失真的前提下，从提高传输效率的角度出发，可以对信源信息量事先进行压缩再予传输，这章要讨论的问题就是给定一个失真度，求出在平均失真小于给定值的条件下，信源所能压缩的最低程度，即率失真函数R(D)。,6.1失真测度与平均失真,【例6.1】汉明（Hamming）失真测度信源输出符号X=x1,x2,xK，信道输出符号Y=y1,y2,yK，约定失真测度上述约定可以用矩阵表示为式中dij0i,j=1,2,K为信源方发送符号xi而信宿方判为yj引起的失真度。,对于矢量传输情况，若信道的输入、输出均为N长序列X=X1X2XN，Y=Y1Y2YN，定义失真测度为（6-2）,【例6.2】平方误差失真测度信源输出符号X=0,1,2，信道输出符号Y=0,1,2，给出失真测度dij=(xi-yj)2i,j=0,1,2则失真测度矩阵为,【例6.3】绝对值误差失真测度信源输出符号X=0,1,2，信道输出符号Y=0,1,2，给出失真测度dij=xi-yji,j=0,1,2则失真测度矩阵为,2.平均失真,离散信源，经有扰信道传输，信道输出符号为Y=y1,y2,yJ，平均失真即对dij（i=1,2,I;j=1,2,J）求统计平均值，记为（6-4）,平均失真是对在给定信源分布q(x)条件下，通过有扰信道传输而引起失真的统计平均度量。,6.2.1率失真函数的定义,给定信源，即信源概率分布q(x)一定，给定失真测度矩阵d=dij，寻找信道，记它的转移概率矩阵为，要求满足（6-11）式中D是预先给定的失真度，上式称为保真度准则。,6.2信息率失真函数R(D),根据定理2.2，当信源q(x)一定时，平均互信息量I(X;Y)是信道转移概率函数p(yx)的型凸函数，这意味着可以关于p(yx)对平均互信息量I(X;Y)求得极小值，定义这个极小值为率失真函数R(D)，即：(6-12),式(4-12)的意义在于，选择p(yx)即选择某种编码方法在满足的前提下，使I(X;Y)达到最小值R(D)，这就是满足平均失真条件下的信源信息量可压缩的最低程度。,（1）D的最小值Dmin在给定的失真测度矩阵中，对每一个xi，找一个最小的dij，然后对所有的i=1,2,I求统计平均值，就是D的最小值，即(6-14),2.R(D)的定义域,6.2.2率失真函数的值域、定义域,1.R(D)的值域（参见图4-1）率失真函数的值域为0R（D）H（X）(6-13),图61R（D）的值域,求出计算Dmax的显式:j=1,2,J（6-18）,（2）D的最大值Dmax当R(D)达到其最小值Rmin（D）=0时，对应的失真最大，这种情况下D对应着R(D)函数定义域的上界值Dmax，如图4-1所示。=minD:I(X;Y)=0（6-15),【例6.7】一信源含有三个消息，概率分布为q1=0.2,q2=0.3,q3=0.5，失真测度矩阵为，求Dmin和Dmax。,由式(6-14)可求出Dmin=10.2+00.3+00.5=0.2,由式(6-18)可求出Dmax=min40.2+20.5,20.2+30.3,10.2+20.3+10.5=min1.8,1.3,1.3=1.3,6.2.3率失真函数的性质,率失真函数有如下几条性质:：,3.对于离散无记忆信源（DMS）R(N)(D)=NR(D),2.R(D)是D的连续、单调、减函数,1.R(D)是D的型凸函数分别给定两个失真度D1和D2（DminD1,D2Dmax），则下式成立：R(1D1+2D2)1R(D1)+2R(D2)（6-19）,6.3.1二种特殊情况下的求解,【例6.8】信源含两个消息x1=0，x2=1,其概率分布为,0.5，信道输出符号Y=y1=0，y2=1，失真测度为汉明（Hamming）失真测度，求率失真函数R(D)。,(1)根据式(6-14)和(6-18)可求出R(D)的定义域Dmin=0+0(1-)=0Dmax=min1-,=,(2)求R(D)的值域R(Dmin=0)=H(U)=-log-(1-)log(1-)=H2()R(Dmax)=R()=0,6.3率失真函数的计算,根据互信息量的表达式：I(X;Y)=H(X)H(X|Y)I(X;Y)=H2()H(X|Y)（6-32）又根据Fano不等式有H(X|Y)H2(pe)+pelog(21)则I(X;Y)H2()H2(pe)（6-33）,（3）在0D的范围内，计算R(D）,式中，pe为传输错误概率，又根据定义=H2()H2(pe),从而有R(D)=H2()H2(pe)=H2()H2(D),下面找出pe与D的关系记信道转移概率矩阵信道输入xi，输出yj，i，j=1，2，若ij，则认定传输出错，故pe=q(x1)p(y2|x1)+q(x2)p(y1|x2),根据d的对称性，假设一个反向信道(YX),反向信道的转移概率矩阵为，假设的反向信道应满足：(xiyj)0i,j=1,2,（4）上面是按照定义求出了R(D)，下面的问题是要真正找到这么一个信道转移概率矩阵为P的信道,使H（YX）=H2（D），从而R(D)=H2()-H2(D)，且P中的每一个元素p(yjxi)都满足p(yjxi)0i,j=1,2,由假设的反向信道计算平均失真，得=(y1)+(y2)D=D,计算条件熵：=-(1-D)log(1-D)-DlogD=H2(D)则平均互信息量I(X;Y)=H(X)-H(XY)=H2()-H2(D)，假设的(xy)确实在满足的条件下，使I(X;Y)=H2()-H2(D)。从而有,由上式知，满足失真条件。,（5）要找出正向信道，可由，反解出(yj)，j=1,2，再计算出。=（1-D）（y1）+D(y2)1-=D（y1）+（1-D）(y2)由上面方程组解出，再算出,【例6.9】信源分布，失真测度矩阵，计算率失真函数,(1)求出R(D)的定义域,（2)计算R(D)根据d的对称性，可假设信道转移概率矩阵,式中为待定常数。由假设的信道转移概率计算信息量,（6-34）,先算出(6-35)将式(6-35)代入式(6-34)得,即（6-36）,由假设的信道转移概率计算平均失真，得（6-37）,因为，由式(6-37)得考虑到，则,如图6-3所示：在的范围内，H2()是单调递增函数，有,根据式(6-36)，得从而,6.3.2R（D）的参数表示法,(2)由式(6-41)求；,(3)由式(6-40)求p(yjxi)；,(4)由式(6-43)求D；,(5)由式(6-44)求R(D)。,用参数法求R(D)，可按下述步骤进行：,（1）由式(6-42)求出；,用此法求解，有时候会出现(yj)0的情况碰到这种情况，就要令某一(y*j)=0，重复刚才的求解过程，这种情况下求得的R(D)是一折线，折点对应(y*j)=0，如图65所示。,【例6.10】仍考虑例6.8的输入概率分布q(x1)=，q(x2)=1，R(D)的情况称为保真度准则下的率失真编码定理，RR(D)的情况称之为逆定理。,6.4率失真信源编码定理,（3）如何求R(D)的定义域和值域,（2）平均失真对给定信源q(x)进行压缩编码，不同的编码方法对应不同的实验信道，可用信道转移概率p(yx)来描述该实验信道，用概率分布p(xy)=q(x)p(yx)对给定的失真测度求统计平均值就得到平均失真.,（1）失真测度可以理解为误码带来的代价，实际上发送同一符号而错成不同符号所带来的代价是不同的。,本章小结,本章介绍在允许一定失真条件下，对给定信源进行压缩编码,信息传输率