信息论与编码

1、信息率失真函数信息率失真函数 第第4 4章章24.14.1 平均失真和平均失真和信息率失真函数信息率失真函数4.24.2 离散信源和连续信源的离散信源和连续信源的R(D)计算计算内内 容容34.14.1 平均失真和平均失真和 信息率失真函数信息率失真函数44.1.1 4.1.1 失真函数失真函数 n假如某一信源假如某一信源X,输出样值输出样值xi , xia1,a2,an,经过有失真的经过有失真的信源编码器输出后变成信源编码器输出后变成yj , yj b1, b2,bm,如果如果: xi yj 没有失真没有失真 xi yj 产生失真产生失真n失真的大小失真的大小,用一个量来表示用一个量来表示,

2、即失真函数即失真函数d(xi,yj),以衡量用以衡量用yj代替代替xi所引起的失真程度。所引起的失真程度。n失真函数定义为：失真函数定义为：jijijiyxyxyxd00),(5失真函数失真函数n将所有的将所有的d(xi,yj)排列起来排列起来,用矩阵表示为用矩阵表示为:),(),(),(),(1111mnnmbadbadbadbadd失真矩阵n例：设信源符号序列为例：设信源符号序列为X=0,1,接收端收到符号序接收端收到符号序列为列为Y= 0,1,2,规定失真函数为规定失真函数为 d(0,0)d(1,1)= 0 d(0,1)d(1,0)= 1 d(0,2)d(1,2)= 0.55 . 001

3、5 . 010d失真矩阵62)(),(jijiyxyxdn失真函数形式可以根据需要任意选取失真函数形式可以根据需要任意选取,最常用的最常用的有有:|),(jijiyxyxd| / |),(ijijixyxyxd其他, 1, 0)(),(jijijiyxyxyxdn均方均方失真失真:n绝对绝对失真失真:n相对相对失真失真:n误码误码失真失真:适于连续信源适于离散信源失真函数失真函数7n汉明失真矩阵汉明失真矩阵 011101110dn对于二元对称信源对于二元对称信源(m=n),X=0,1,Y=0,1,汉明失真汉明失真矩阵矩阵:0110d8 失真函数的定义可推广到序列编码情况，如果假定失真函数的定义

4、可推广到序列编码情况，如果假定离散信源输出符号序列离散信源输出符号序列 ，其中，其中L长符号长符号序列样值序列样值 ，经信源编码后，输出符号，经信源编码后，输出符号序 列序 列 ， 其 中， 其 中 L 长 符 号 序 列 样长 符 号 序 列 样值值 ，则失真函数定义为：，则失真函数定义为： 12(,)LXXXX 其中其中d(xil，yjl)是信源输出是信源输出L长符号样值长符号样值 中的第中的第l个个符号符号xil时，编码输出时，编码输出L长符号样值长符号样值 中的第中的第l个符号个符号yjl的失真函数。的失真函数。 11( ,)(,)LLijiljlldd xyLx y 12( ,)LY

5、Y YY 12(,)jjjjLyyyy12(,)iiiiLxxxx ixiy 94.1.2 4.1.2 平均失真平均失真 nxi和和yj都是随机变量都是随机变量,所以失真函数所以失真函数d(xi,yj)也是随机也是随机变量变量,限失真时的失真值只能用数学期望表示限失真时的失真值只能用数学期望表示n将失真函数的数学期望称为将失真函数的数学期望称为平均失真平均失真：jjiijiibadabpapD),()|()(n失真函数失真函数d(xi,yj)：q描述了某个信源符号通过传输后失真的大小描述了某个信源符号通过传输后失真的大小n平均失真平均失真 ：q是是对给定对给定信源信源分布分布p(xi)经过某一

6、转移概率分布为经过某一转移概率分布为p(yj/xi)的的有失真信源编码器后产生失真的总体量度有失真信源编码器后产生失真的总体量度,是从是从总体总体上描上描述整个系统的失真。述整个系统的失真。D10n如果假定离散信源输出符号序列如果假定离散信源输出符号序列XX1X2 Xl Xn, 经信源编码后经信源编码后,输出符号序列输出符号序列Y=Y1YlYm, 则则平均失平均失真真定义为定义为1111 (,)LLLLLijlllDE d xyDLL dxdyyxdyxpDxy),(),(11平均失真为：平均失真为：),()/()(11jiinimjjibadabpapD 信源信源X经过有失真的信源编码器输出

7、经过有失真的信源编码器输出Y，其结构如下：，其结构如下：信源编码器信源编码器XY,.,21naaaX ,.,21mbbbY )/(ijxyp把上面的信源编码器看成是有干扰的假想信道，这样就可以把上面的信源编码器看成是有干扰的假想信道，这样就可以用分析信道传输的方法来分析信源编码问题。用分析信道传输的方法来分析信源编码问题。假想信道假想信道XY,.,21naaaX ,.,21mbbbY )/(ijxyp4.1.3 4.1.3 信息率失真函数信息率失真函数R(D)124.1.3 4.1.3 信息率失真函数信息率失真函数R(D)n无论是无噪信道还是有噪信道无论是无噪信道还是有噪信道: n RCq总能

8、找到一种编码使在信道上能以任意小的错误概率总能找到一种编码使在信道上能以任意小的错误概率,以任以任意接近意接近C的传输率来传送信息的传输率来传送信息n RCq就必须对信源压缩就必须对信源压缩,使其压缩后信息传输率使其压缩后信息传输率R小于信道容量小于信道容量C,但同时要保证压缩所引入的失真不超过预先规定的限度。但同时要保证压缩所引入的失真不超过预先规定的限度。n信源编码器的目的是使编码后所需的信息传输率信源编码器的目的是使编码后所需的信息传输率R尽量尽量小，然而小，然而R越小，引起的平均失真就越大。给出一个失越小，引起的平均失真就越大。给出一个失真的限制值真的限制值D，在满足平均失真，在满足平

9、均失真 D的条件下，选择的条件下，选择一种编码方法使信息率一种编码方法使信息率R尽可能小。尽可能小。D13信息率失真函数信息率失真函数R(D)n若平均失真度若平均失真度 不大于我们所允许的失真不大于我们所允许的失真,即即DDD n则称此为则称此为保真度准则保真度准则n当信源当信源p(xi)给定给定,单个符号失真度单个符号失真度d(xi,yj) 给定时给定时,选择选择不同的试验信道不同的试验信道p(yj|xi), 相当于不同的编码方法相当于不同的编码方法,其所其所得的平均失真度不同。得的平均失真度不同。n试验信道试验信道DDDD满足保真度准则14D允许试验信道允许试验信道 n 若若p(xi)和和

10、d(xi，yj)已定，选择信道，使其满足保真已定，选择信道，使其满足保真度准则，凡满足要求的这种信道称为度准则，凡满足要求的这种信道称为D允许试验信道。允许试验信道。n 满足这种要求的信道有多个，则可给出满足下式满足这种要求的信道有多个，则可给出满足下式条件的所有转移概率分布条件的所有转移概率分布pij，它们构成了一个信道集，它们构成了一个信道集合合PD(/):1,2, ;1,2,DjiPp yxDDin jm15信息率失真函数信息率失真函数R(D)nR(D)：q在限定失真为在限定失真为D的条件下信源输出的最小信息速率。的条件下信源输出的最小信息速率。 ( )min ( ; )DPR DI X

11、 Yn在信源给定后在信源给定后, 在满足一定失真的情况下在满足一定失真的情况下,使信源必须传输使信源必须传输给收信者的给收信者的信息传输率信息传输率R尽可能地小。尽可能地小。n若从接收端来看若从接收端来看,就是在满足保真度准则下就是在满足保真度准则下,寻找再现信源寻找再现信源消息所必须获得的消息所必须获得的最低平均信息量最低平均信息量。即在满足保真度准。即在满足保真度准则的条件下寻找平均互信息则的条件下寻找平均互信息I(X,Y)的最小值。的最小值。16信息率失真函数信息率失真函数nPD是所有满足保真度准则的试验信道集合是所有满足保真度准则的试验信道集合,因而可因而可以在集合以在集合PD中寻找某

12、一个信道中寻找某一个信道pij,使使I (X,Y)取极小取极小值。值。n离散无记忆信源离散无记忆信源(|)( )min( ) (|)log()ijDjiijipPijjp baR Dp a p bap b17n例已知编码器输入的概率分布为例已知编码器输入的概率分布为p(x)=0.5 ,0.5n信道矩阵信道矩阵8 . 02 . 04 . 06 . 0ijpn求互信息)|()()(ijijixypxpyxp11122122()0.3()0.2()0.1()0.4p x yp x yp x yp x y6 . 0)(4 . 0)(21ypyp32)(41)|(31)|(43)|(22122121yx

13、pyxpyxpyxp(|)(; )()log0.125/( )jiijijip yxI X Yp x ybitp y符18n编码器输入的概率分布为编码器输入的概率分布为p(x)=0.5 ,0.5n信道矩阵信道矩阵8 . 02 . 01 . 09 . 0ijpn求互信息求互信息符号/397. 0)()|(log)();(bitypyxpyxpYXIijijijin可见当可见当p(x)一定时一定时,I (X,Y)随随p(yj|xi)而变。而变。n因为因为p(x)分布一定时分布一定时,信道受干扰不同所能传递的信息信道受干扰不同所能传递的信息量是不同的。量是不同的。n当当p(x)一定时一定时,I (X

14、,Y)是关于是关于p(yj|xi)的下凸函数。的下凸函数。n因此当改变因此当改变p(yj|xi)时时,I (X,Y)有一极小值。有一极小值。19平均互信息平均互信息n平均互信息平均互信息I(X;Y)： q信源的概率分布信源的概率分布p(xi)的上凸函数。的上凸函数。q信道传递概率信道传递概率p(yj|xi)的下凸函数。的下凸函数。);(max)(YXICixpn信道容量：信道容量： n信息率失真函数：信息率失真函数： );(min)(YXIDRDP20信道容量信道容量q假定信道固定的前提下假定信道固定的前提下,选择一种试验信源使选择一种试验信源使信息传信息传输率最大。输率最大。q它所反映的是信

15、道传输信息的能力它所反映的是信道传输信息的能力,是信道可靠传送是信道可靠传送的最大信息传输率。的最大信息传输率。n一旦找到了信道容量一旦找到了信道容量,它就与信源不再有关它就与信源不再有关,而是信道而是信道特性的参量特性的参量,随信道特性的变化而变化随信道特性的变化而变化n不同的信道其信道容量不同。不同的信道其信道容量不同。21信息率失真函数信息率失真函数q假定信源给定的情况下假定信源给定的情况下,用户可以容忍的失真度内再现用户可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。信源消息所必须获得的最小平均信息量。q它反映的是信源可以压缩的程度它反映的是信源可以压缩的程度,是在满足一定失

16、真度是在满足一定失真度要求下信源可压缩的最低值。要求下信源可压缩的最低值。n率失真函数一旦找到率失真函数一旦找到,就与求极值过程中选择的试验就与求极值过程中选择的试验信道不再有关信道不再有关,而只是信源特性的参量而只是信源特性的参量n不同的信源其不同的信源其R(D)不同。不同。22：q充分利用已给信道充分利用已给信道,使传输的信息量最大使传输的信息量最大,而发生而发生错误错误的概率任意小的概率任意小。 ：q解决在已知信源和允许失真度解决在已知信源和允许失真度D的条件下的条件下,使信源必须使信源必须传送给信宿的信息率最小。即用尽可能少的码符号尽传送给信宿的信息率最小。即用尽可能少的码符号尽快地传

17、送尽可能多的信源消息快地传送尽可能多的信源消息,以提高通信的以提高通信的有效性有效性。23n例：设信源的符号表为例：设信源的符号表为A=al,a2,a2n,概率分布概率分布为为p(ai)=1/2n,i=1,22n,失真函数规定为失真函数规定为 jijiaadji10),(n信源熵信源熵 nnnnH2log)2121,21(n如果对信源进行不失真编码如果对信源进行不失真编码,平均每个符号至少需要平均每个符号至少需要log2n个二进制码元。个二进制码元。n现在假定允许有一定失真现在假定允许有一定失真,假设失真限度为假设失真限度为D=1/2设想设想采用下面的编码方案：采用下面的编码方案： a1a1，

18、 a2a2， anan an+1an ,an+2 an ,a2n ann即不发生差错时失真为即不发生差错时失真为0,出错失真为出错失真为1n研究在一定编码条件下信息压缩的程度。研究在一定编码条件下信息压缩的程度。24n平均失真平均失真 21),()|()(ijjiijiaadaapapDn则输出熵则输出熵H(Y) 1log(212log)21,2121,21()(nnnnnnnnnHYHn由该信道模型图由该信道模型图4-3看出看出,它是一个确定信道它是一个确定信道n pij=1(或或0)，H(Y|X)=0 )()|()(),(YHXYHYHYXI压缩254.1.4 4.1.4 信息率失真函数的

19、性质信息率失真函数的性质n1、R(D)的定义域的定义域n率失真的定义域问题就是在信源和失真函数已知的情率失真的定义域问题就是在信源和失真函数已知的情况下况下,讨论允许平均失真度讨论允许平均失真度D的的最小最小和和最大最大取值问题。取值问题。n由于平均失真度是非负实数由于平均失真度是非负实数d(xi,yj)的数学期望的数学期望,因此也因此也是非负的实数是非负的实数,即即 的的下界是下界是0。n允许平均失真度能否达到其下限值允许平均失真度能否达到其下限值0,与单个符号的失与单个符号的失真函数有关。真函数有关。DD, 026R(D)的定义域的定义域nDmin 和和R(Dmin)n信源的最小平均失真度

20、：信源的最小平均失真度：nijijiyxdxpD1min),(min)(n只有当失真矩阵的每一行至少有一个只有当失真矩阵的每一行至少有一个0元素时元素时,信源的信源的平均失真度才能达到下限值平均失真度才能达到下限值0。n当当Dmin = 0,即信源不允许任何失真时即信源不允许任何失真时,信息率至少应等信息率至少应等于信源输出的平均信息量于信源输出的平均信息量信息熵。即信息熵。即 R(0) =H(X)271111( ) () ( ,)( )() ( ,)nmnmijiijijiijijijDp x p y x d x yp xp y x d x y对每个 xi，选 j 使d(xi,yj)最小，对

21、应 p(yj|xi)=1，其余为0，则min1( )min ( ,)niijjiDp xd x y28n例：失真矩阵为例：失真矩阵为由于由于有有此时信道为无噪无损信道，有此时信道为无噪无损信道，有R(0) =H(X)01 1101dmin11220,()1, ()1DDp y xp y xx1x2y1y2y329R(D)的定义域的定义域n因为实际信道总是有干扰的因为实际信道总是有干扰的,其容量有限其容量有限,要无失真要无失真地传送连续信息是不可能的。地传送连续信息是不可能的。n当允许有一定失真时当允许有一定失真时,R(D)将为有限值将为有限值,传送才是可传送才是可能的。能的。n对于连续信源：对

22、于连续信源：min0()lim ( )(0)( )cDR DR DRH x30R(D)的定义域的定义域nDmax：定义域的上限。：定义域的上限。nDmax是满足是满足R(D)=0时所有的时所有的平均失真度中的平均失真度中的最小值最小值。DDDR0)(maxminn由于由于I(X,Y)是非负函数是非负函数,而而R(D)是在约束条件下的是在约束条件下的I(X,Y)的最小值的最小值,所以所以R(D)也是一个非负函数也是一个非负函数,它的下它的下限值是零。限值是零。 R(D)0nDmax 和和R(Dmax)31R(D)的定义域的定义域n由于由于I(X,Y) = 0的充要条件是的充要条件是X与与Y统计独

23、立统计独立,即：即：)()|(jijypxypjijiijypjjijiiypyxdxpypyxdypxpDjj),()()(min),()()(min)()(maxnijiimjyxdxpD12 , 1max),()(min 从上式观察可得：在从上式观察可得：在j=1，m中，可找到中，可找到 值最小的值最小的j，当该，当该j对应的对应的pj1，而其余，而其余pj为零时，上式为零时，上式右边达到最小，这时上式可简化成（课本有错）右边达到最小，这时上式可简化成（课本有错）niijidp132n例例4-3:设输入输出符号表为设输入输出符号表为X=Y=0,1,输入概率输入概率分布分布p(x)=1/3

24、,2/3,失真矩阵失真矩阵 0110dn求：求： Dmin 和和Dmax 解：解： 失真矩阵的每一行至少有一个失真矩阵的每一行至少有一个0元素时元素时, Dmin=0 当当Dmin0时，时，R(Dmin)H(X)H(1/3，2/3)0.91比特比特/符号，这时信源编码器无失真，所以该编码器符号，这时信源编码器无失真，所以该编码器的转移概率为的转移概率为 1001P333131,32min032131, 132031min,minmin2, 12, 12221212121112, 1212, 1maxjjjiijijdpdpdpdpdpD当当R(Dmax)0时时 此时输出符号概率此时输出符号概率

25、p(b1)0，p(b2)1， 所以这时的编码器的转移概率为所以这时的编码器的转移概率为 2221,baba1010P34n例例:设输入输出符号表为设输入输出符号表为X=Y=0,1,输入概率输入概率分布分布p(x)=1/3,2/3,失真矩阵失真矩阵 1212/ 1dn求：求： Dmin 和和Dmax 2max1,212111212minmin(2,11)323333min( ,1)1 (2()1, ()0)2iijjjijDp djp yp y 取 ， 即651322131),(min)(1minnijijiyxdxpD35R(D)的定义域的定义域nR(D)的定义域为的定义域为Dmin，Dmax

26、 。n通常通常Dmin = 0， R(Dmin) = H(X)n当当 DDmax时时, R(D) = 0n当当 0 DDmax时时, 0R(D) H(X)36信息率失真函数的性质信息率失真函数的性质n1、R(D)是非负的实数是非负的实数, R(D)0。 其定义域为其定义域为0Dmax , 其值为其值为0H(X)。 当当DDmax时时,R(D)0n2、R(D)是关于是关于D的下凸函数的下凸函数qR(D)在定义域内是失真度在定义域内是失真度D的的U型下凸函数型下凸函数n3、R(D)的单调递减性及连续性的单调递减性及连续性q容许的失真度越大，所要求的信息率越小。反之亦然。容许的失真度越大，所要求的信

27、息率越小。反之亦然。37图说明：图说明：nR(0) = H(X) ， R(Dmax) =0， 决定了曲线边缘上的两个点；决定了曲线边缘上的两个点；n在在0和和Dmax之间，之间， R(D)是单是单 调递减的下凸函数；调递减的下凸函数；n在连续信源时，当在连续信源时，当D0时，时， R(D) ，曲线将不与，曲线将不与R(D)轴相交。轴相交。38n阴影范围表示实际信源编码方案与理论值间的差距，我们阴影范围表示实际信源编码方案与理论值间的差距，我们完全可以找到更好，即更靠近理论值，缩小阴影范围的信完全可以找到更好，即更靠近理论值，缩小阴影范围的信源编码，这就是工程界寻找好的信源编码的方向和任务源编码

28、，这就是工程界寻找好的信源编码的方向和任务 )(DR（理论）)(DR)( 实际DRD2/11 394.2 离散信源离散信源R(D)计算计算 n给定信源概率给定信源概率pi和失真函数和失真函数dij,就可以求得该信源就可以求得该信源的的R(D)函数。函数。n它是在保真度准则下求极小值的问题。它是在保真度准则下求极小值的问题。n但要得到它的显式表达式但要得到它的显式表达式,一般比较困难通常用参一般比较困难通常用参量表达式。量表达式。n即使如此即使如此,除简单的情况外实际计算还是困难的除简单的情况外实际计算还是困难的,只能用迭代逐级逼近的方法。只能用迭代逐级逼近的方法。 40二元对称信源的二元对称信

29、源的R(D)函数函数 n设二元对称信源设二元对称信源X=0,1,其概率分布其概率分布p(x)=p,1-p,0p=1/2,接收变量接收变量Y=0,1,汉明失真矩阵汉明失真矩阵0110dn因而最小允许失真度因而最小允许失真度Dmin=0。（此时无失真）。（此时无失真）n并能找到满足该最小失真的试验信道并能找到满足该最小失真的试验信道,且是一个无噪且是一个无噪无损信道无损信道,其信道矩阵为其信道矩阵为1001pn计算得：计算得：R(0)=I(X;Y)=H(p)41n最大允许失真度为最大允许失真度为1max0,10minmin (0) (0,0)(1) (1,0), (0) (0,1)(1) (1,1

30、)min(1), iijjijDp dpdpdpdpdpppn要达到最大允许失真度的试验信道要达到最大允许失真度的试验信道, ,唯一确定为唯一确定为1010pn这个试验信道能正确传送信源符号这个试验信道能正确传送信源符号x=1,而传送信源符号而传送信源符号x=0时时,接收符号一定为接收符号一定为y=1n凡发送符号凡发送符号x=0时时,一定都错了。而一定都错了。而x=0出现的概率为出现的概率为p,所以所以信道的平均失真度为信道的平均失真度为p 。n在这种试验信道条件下，可计算得在这种试验信道条件下，可计算得 R(Dmax) = R(p) = 042 某些特殊情况下某些特殊情况下R(D)的表示式为

31、：的表示式为： （1）当）当d(x,y)=(x-y)2， 时，时，22221)(xexpDDRlog)(2)当当d(x,y)=|x-y|， 时，时，xexp2)(DDR1log)(43(3)当当d(x,y)= (x,y)，p(x=0)=p，p(x=1)=1-p时，时，R(D)=H(p)H(D) 0 Dmax D R(D) H(3)(1)(2)44信息率失真函数的参量表述信息率失真函数的参量表述 求信源的求信源的R(D)R(D)函数，原则上与求信道容量一样，是函数，原则上与求信道容量一样，是在有约束条件下求极小值的问题。在有约束条件下求极小值的问题。 也就是适当选取试验信道也就是适当选取试验信道

32、P(v/u)P(v/u)使平均互信息最小使平均互信息最小化，化，riijiijrisjijiuvPuPuvPuvPuPVUI111)/()()/(log)/()(),(45 但是，如果要求得到明显的解析表达式，则比较困但是，如果要求得到明显的解析表达式，则比较困难，通常只能用参量形式来表达。即便如此，除简难，通常只能用参量形式来表达。即便如此，除简单情况外，实际计算仍然是相当困难的。尤其是约单情况外，实际计算仍然是相当困难的。尤其是约束条件式，它是求解束条件式，它是求解R(D)函数最主要的障碍。函数最主要的障碍。 因为应用拉格朗日乘子法解得的一个或某几个因为应用拉格朗日乘子法解得的一个或某几个

33、P(vj/ui)很可能是负的。在这情况下，必须假设某些很可能是负的。在这情况下，必须假设某些P(vj/ui) =0，然后重新计算，这就使得计算复杂化了。，然后重新计算，这就使得计算复杂化了。 目前，可采用收敛的迭代算法在电子计算机上求解目前，可采用收敛的迭代算法在电子计算机上求解R(D)函数。函数。 下面介绍用拉格朗日乘子法求解下面介绍用拉格朗日乘子法求解R(D)函数，并用函数，并用S作作为参量来表述率失真函数为参量来表述率失真函数R(D)和失真函数和失真函数D(S)。46 由式由式(1)知，当信源的概率分布知，当信源的概率分布P(u)固定，平均互信息仅仅是试固定，平均互信息仅仅是试验信道验信道P(vj/ui)的函数。的函数。 若先不考虑式若先不考虑式(2)的约束，约束条件式的约束，约束条件式(3)包含包含r个等式，取拉格朗个等式，取拉格朗日乘子日乘子 i(i12， r)分别与之对应；并取拉氏乘子分别与之对应；并取拉氏乘子S与式与式(4)对应。由此构成辅助函数：对应。由此构成辅助函数：1( ; )(/)(5)sijijI U VP vuSD 0)/(ijuvPsjijuvP11)/(DvuduvPuPjirisjiji),()/()(11riijiijrisj