北邮,信息论课件chapter9

1、第第9 9章章 信息率失真函数信息率失真函数9.1 9.1 概概 述述 当信源信息以超过信道容量的速率传输时，必然产生差错或失真； 由于信道噪声的干扰，信息在传输过程中也会产生差错或失真； 信宿的灵敏度和分辨力都是有限的，无需要求在传输过程中信息绝对无失真； 允许信息有某些失真，这样可以降低信息传输速率，从而降低通信成本； 对信源无失真压缩的极限是熵，如果再继续压缩就要失真；结论：失真是不可避免的，有时甚至是必要的。 从信源的输出抽取重要信息并压缩冗余信息的装置称数据压缩算法； 通过压缩所得到的编码序列不能完全恢复原来信源的信息，是有失真信源编码； 总希望在不大于一定编码速率（即传送每信源符号

2、所需的平均的二进数字数）的条件下，使平均失真限制到最小；或者在平均失真不大于某个值的条件下，使编码速率限制到最小（限失真信源编码）； 从信息论的观点处理数据压缩的学科称为信息率失真理论，信息率失真理论是数据压缩的基本理论。9. 1. 1 9. 1. 1 系统模型系统模型 研究限失真编码的系统模型如图9. 1. 1所示。l 信源发出的消息X通过有失真的信源编码，通过理想无噪声信道传输，经译码器的输出为Y，由于编码有失真，所以Y不是X的精确复现。l 可以把信源编码器和信源译码器之间看成一个有噪声的信道，这个信道称做试验信道。 l 通过研究试验信道输入与输出之间的互信息来研究限失真信源编码。 图9.

3、 1. 1 限失真编码的系统模型设试验信道的输入X，符号集A=a1,an；信道的输出 Y，符号集B=b1,bm。 信源信源解码器信宿信源编码器 无噪信道试验信道9. 1. 2 9. 1. 2 失真测度失真测度 1单符号失真测度 ， 。 定义失真矩阵 （9. 1. 1）其中， 。如果规定 ，那么失真矩阵变为汉明失真矩阵 （9. 1.2）特点：对角线上元素全为零，其他元素都为1。),(yxdYyXx,),(.),(.),(.),(),(.),(1212111mnnmmbadbadbadbadbadbadd0),(jibadjijibadji10),(.01.11.1.011.10d2序列失真测度：

4、 设 ，其中 取自符号集A； ，其中 取自符号集B； 序列失真测度定义为： （9. 1.3）3平均失真 单符号平均失真： （9. 1.4） 序列平均失真： （9. 1.5）),.,(1Nxxx ix),.,(1Nyyy iyNiiiNyxdNyxd1),(1),(,( ,) ( ,)ijiji jDdp a b d a b 1111 ( ,)NNiiiiidE d x yDNN 9.2 9.2 离散信源信息率失真函数离散信源信息率失真函数 9 92 21 1信息率失真函数信息率失真函数定义信息率失真函数为： （ 97）其中PD为使平均失真不大于D的p(y|x)的集合。即，R(D)就是在满足保真

5、度准则下，X,Y的最小平均互信息。或 （ 98） );(min)()|(YXIDRDPxypijiijiijijipppppDRDPijplogmin)(9 92 22 R(D)2 R(D)的性质的性质 1 R(D)的定义域为： （ 99） 且 （ 910） （ 911）证：1） 定义域下界： 对x的每一取值 ，令对应最小的 条件概率p(bj|ai)为1 ,其余条件概率为零，就得到Dmin 。maxmin0DDDxyyxdxpD),(min)(minxyyxdxpD),()(minmaxyxyxdxypxpD，),()|()(yxyyxdxypxp，),(min)|()(),(min),(yx

6、dyxdyxyyxypyxdxp)|(),(min)(0),(min)(xyyxdxp)0),(yxdia(,)ijd a b 2）定义域上界：R(D)为平均互信息，所以R(D)0。在较大范围内 求极小值一定不大于在所含小范围内求的极小值，所 以D1D2 = R(D1) R(D2)，即R(D)是D的非增函数。 当XY独立时，R(D) I(X;Y)=0，当D继续增加，R(D) 仍然为0。所以，Dmax是使R(D)=0的最小平均失真。当 x,y独立时，p(x,y)=p(x)q(y) ，有 由于 已给定，而且对不同y，也可能有不同的值。所以，求 ，并使对应的q(y)=1，其余为0。这样就可使平均失真

7、最小。所以得到（ 911）式。 证毕。 maxmin( ) ( ) ( , )min( )( ) ( , )xyxyyxDp x q y d x yq yp x d x y，( ), ( , )p x d x yxyxdxp),()(xyyxdxp),()(min例例91 设试验信道输入符号 ，概率分别为1/3，1/3，1/3，失真矩阵如下所示，求Dmin和Dmax和相应的试验信道的转移概率矩阵。 解 = 1令对应最小 的 ,其它为0。可得对应Dmin 的转移概率矩阵为： 123 ,a aa123312321dxyyxdxpD),(min)(min) 1 , 2 , 3min()() 3 ,

8、1 , 2min()() 3 , 2 , 1min()(321apapap）jibad,(1)|(ijabp = 5/3上式中第2项最小，所以令 ， 。可得对应Dmax 的转移概率矩阵为： 100010001xyyxdxpD),()(minmax 3)(2)(1)(min321apapap123, () 2() 1() 2,p ap ap a 123 () 3() 3() 1p ap ap a 21p b（ ）130p bp b（ ） （ ）0100100102R(D) 是关于D的下凸函数 设D1,D2为任意两个平均失真， ，那么 （ 926） 证 当信源分布给定后， 可以看成试验信道转移概率

9、 的函数，即 ， ，且有 10)()1 ()()1 (2121DRDRDDR)(DR)|(xyp)/()|(min)(1)|(11xypIxypIDRDPxyp)/()|(min)(2)|(22xypIxypIDRDPxyp1111( )( | ) ( , )( | )Dxyp x p y x d x yDp y xP，2222( )( | ) ( , )( | )Dxyp x py x d x yDpy xP，令 ，那么 ， = 证毕。 210)1 (DDD)|()1 ()|()|(210 xypxypxypyxyxyxdxypxypxpyxdxypxpD，),()|()1 ()|()(),

10、()|()(210021)1 (DDD0)|(0DPxyp00120()min ( | )( | )( | )(1)( | )( | )R DI p y xI py xIp y xpy xp y xD)()1 ()()|()1 ()|(2121DRDRxypIxypI3、R(D)是(Dmin,Dmax)区间的连续和严格递减函数证 R(D)为凸函数 = 连续 严格递减 R(D)为非增函数又不是常数关于信息率失真函数的解释关于信息率失真函数的解释 （1）在信道给定情况下：希望输入与输出之间的互信息最大；在信源给定情况下：满足失真要求的传输所需要的最小信道容量或传输速率，达到降低信道的复杂度和通信成

11、本的目的。关于信息率失真函数的解释关于信息率失真函数的解释 （2）根据R（D）为单调减函数的性质，如果我们固定平均互信息，选择信道的转移概率使平均失真最小，可以得到同样的R（D）函数曲线，唯一的差别就是变量之间作用交换。这时就得到“失真率函数”（distortion-rate function）。 失真率函数定义为( / ): ( ( / )( )min( ( / )p y x I p y xRD Rd p y x9.3 限失真信源编码定理 设信源X发出长度为N的序列，而码字仅有M个，即仅对M个信源序列进行编码。设信源的熵为H，如果 ，那么当N足够长时就存在无失真信源编码。令 ，就有 。但如果

12、 ，编码就会产生失真。这就是限失真信源编码要解决的问题。由于压缩了码率，可以提高信息传输速率，从而减小了通信的成本。2NHM 2(log)/RMNRHRH9.3.1码率的压缩限失真信源编码系统 9.3.1码率的压缩 例例9.3.1 设信源X，符号集为a1,a2,a2n，等概分布pi=1/2n，i=1,2n，给定失真测度为 ，设计一种单符号压缩算法使得平均失真D=1/2并求压缩后的码率R。jijidij019.3.1码率的压缩 解：失真测度为汉明测度，实际上要求误码率为1/2。设Y为X的压缩编码，符号集为b1,b2,bn，下面为压缩算法和对应的试验信道转移概率矩阵：)2.(.) 1,.,1(nn

13、jbanibaYXnjii，nnnnnbbbbaaaaa1212121.1.01.10.0010.0.0.0100.01. 恢复算法和对应条件概率矩阵：(1,., ).iiYXba in12121211000001000100010nnnnny xaaaaabbbb(1,., )iiXXaa in122122100001100010nnnnaaaaaaaa 试验信道转移概率矩阵：9.3.1码率的压缩 平均失真 算法满足要求。 的概率分布为： 所以 2,111( ) ( / ) ( , )1222nx ynnDp x p y x d x ynn1jb j (， ，n) 12/1.2/1nnnnn

14、2/ ) 1( 12log212log21)(nnnnnnnYH1( )log2log(1)2nRH Ynnn 对于一个n元等概率无记忆信源，如果具有对称失真测度，则 0 1ijijdij 1log()0(1)()0DnnH DDnnR D其他1/21211( )log( )loglog(21)2(21)22nRHnnn 本题中： 1( )2RR9. 3.2 9. 3.2 限失真信源编码定理限失真信源编码定理限失真信源编码定理限失真信源编码定理-仙农第三编码定理 任意给定 ，总存在一种信源编码，使得 ，且平均失真 ； 反之，如果RR(D)，就不可能存在使平均失真 的编码。0)(DRR DDii

15、）该定理是非构造性的，它仅指出了编码的存在性，并未给出编码的实际方法。iii）定理的含义是：在给定的保真度准则下，可对信源进行压缩，所需的编码速率（或每信源符号所需的比特数）RR(D),即R(D)是满足D准则下传送每信源符号所需最小的比特数。 因此，R(D)是衡量在给定失真测度下数据压缩有效性的标准。码率越接近R(D)，就说明编码越有效，而实际上，编码复杂度或代价也就越高。9.3.3 限失真信源信道编码定理定理9.3.2 设离散无记忆信源的信息率失真函数为(比特/秒)，离散无记忆信道的容量为C（比特/秒），若满足 则信源序列通过信道传输后的平均失真 ；若CR(D) ，则信源序列通过信道传输后的

16、平均失真大于D。()CR DD9.4 离散信源信息率失真函数的计算例9.4.1 一个二元信源，符号集A=0,1，概率为p(0)=p1=p，p(1)=p2=1-p，其中p1/2；试验信道输出符号集B=0,1，失真测度函数为汉明失真，求R(D)函数。解：)()0(1001 00110 minpHRPDD试验信道汉明失真矩阵为0)()(1010 );1min(),()(minmaxmaxpRDRPpppyxdxpDXY试验信道)()();()()()|()|()()|()();()0, 1() 1, 0(),(),(0,maxDHpHYXIDHPHYXHFanoYXHpHYXHXHYXIPyxpyx

17、pyxdyxpDpDDEEyx不等式，根据时，平均失真度为一般情况下，pDpDDHpHDR00)()()( 图9.4.1 二元信源的R(D)函数曲线 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5P = 0 .5P = 0 .3P = 0 .1P = 0 .21 .00 .20 .40 .60 .8R ( D )（ 比 特 / 符 号 ）1 .20D9.5 连续信源信息率失真函数设时间离散连续信源X，概率密度为p(x)，试验信道转移概率p(y|x)，输出为q(y)。定义平均失真为 dxdyyxdxypxpdxdyyxdyxpyxdED),()|()(),(),(),(信息率失真函数

18、与性质对所有试验信道集合PD，在满足失真度DD*时，信息率失真函数定义为： 其中 )|(min);(inf)(*)|()|(xypIYXIDRDDPxypPxyp* ( | ):DPp y xDD。 信息率失真函数与性质R(D)函数有以下性质：（1）非负性；（2） 区间是单调递减函数；（3） 区间是下凸函数； max0DDmax0DD与离散情况不同的是，在D=0时，R(D)并不连续。在D0时，R(D) ，趋近信源的绝对熵。对离散情况，H(X)是R(0)的上界；对连续情况，h(X)不是R(0)的上界，因为h(X)还可能为负。9.6.1离散时间无记忆高斯信源平方误差测度定理9.6.1 一个无记忆任

19、意均值、方差为的高斯信源，在平方误差准则下的信息率失真函数为： 其中, ,且222211log0()max(0,log)220DR DDDDmax0DD22max)(infdxyxxpD2)(),(yxyxd 图94 高斯信源的R（D）函数 0 . 2 0 . 4 0 . 6 0 . 8 1 . 0 0 . 21 . 21 . 00 . 80 . 60 . 40 . 0R ( D )（比特/ 自由度）D/2（1）此R(D)函数是在均方准则下推出的，不适用其他准则；（2）R(D)函数是高斯信源实现平均失真小于等于D的有损编码可达到的最低速率。（3） 称为有损压缩的信噪比；当信源功率给定，平均失真

20、越大，信噪比越小，所需码率也越小。高斯信源R(D)函数的注释D/2（4）当D=0时，R(D)= ；当D= 时，R(D)=0。这说明，对于连续信源，当平均失真为0时，所需要的信息率为无限大。5）高斯信源失真率函数 (9. 62）其中，R为编码器的码率，单位为比特/符号。D（R）表示，当高斯信源有损压缩的码率为R时，可以达到的最小平均失真。所以对于任意码率为R的高斯信源有损编码器，其平均失真D，满足 (9. 63）2RRD222)(RD222例961 一个均值为零的离散时间高斯信源作为限失真信源编码器的输入，该编码器是一个量化器，输出256个量化电平，输出信噪比SNR用输入信号的均方值与均方误差的

21、比来量度；（1）求编码器的码率；（2）SNR能否达到49dB？ 解 （1）编码器的码率： 比特/信源符号； 8256log2R（2）SNR不能达到49dB。解释如下： 根据 (9. 63），有RDSNR222dBdB4916.483010. 01602lg1082 9.6.2 独立并联高斯信源一个多维离散时间高斯信源 ，其中，X1、X2、XN是N个独立零均值、方差为 的高斯随机变量 ，称这种信源为独立并联高斯信源，其中各Xi为子信源。 设每个子信源的失真测度为均方失真，即 ，i=1，N；独立并联高斯信源 的失真测度为 12NNX XXX2i(iiidx y2- )NX1( , ) (1/ )(

22、NNiiidNx yx y2- )设信源 的信息率失真函数为 ，各并联信源的信息率失真函数为 ，i=1，N；那么 NX()R D()iiR D21( , )(1/)()NNNiiiDE dNE xyx y1(1/)NiiND(/)()(1/)min(;)DNNpPR DNIy xXY结论 这是因为，对于每个 ， 的最大值就是 。 222,iiiiBBDB()iiR DiD2i图95 平均失真分配的倒注水原理。 1 2 3 4 5 6B0信 源 序 号421262i2322252其中，K 为满足 的子信源的个数，满足此条件的称为被使用的子信源。所求函数为 Bi221()1/(2)log(/)Ni

23、iiR DND22,1/(2)log(/)iiiBNB222:iiiiBiBBN DKNDBBiii/)(2,2注：（1）如果对总失真有要求，那么重点处理功率大的信号；（2）如果总失真允许较大，功率小的信号可以不予处理；（3）只有满足 的子信源对R（D）有贡献。 将每个子信源的方差按大小顺序排序，得 Bi222221iNii在平均失真从0逐渐增大的过程中，从对所有子信源的全部使用开始，按方差大小的顺序，逐个从被使用的子信源集合中排除，直至所有子信源都不被使用，此时对应最大的平均失真，为所有子信源方差的和，对应的R(D)=0。例9.6.1 一个二维独立高斯信源（X1X2），其中X1 、X2均值都为零，方差分别为2和4，采用均方失真测度，求该信源的R(D)函数。如果 X1、X2都使用，根据(9. 6. 14）和 (9. 6. 12），有 和 ，得 ， 2/2DB 2B2DDDDDR22log214log412log41)(如果仅使用X2，有22 DB42 B32 D12log21224log41)(DDDR6422m