第七章 限失真信源编码

1、第七章第七章 限失真信源编码限失真信源编码7.1 7.1 失真测度失真测度7.2 7.2 信息率失真函数信息率失真函数 7.3 7.3 信息率失真函数的计算信息率失真函数的计算 7.4 7.4 限失真信源编码定理限失真信源编码定理7.1.1 7.1.1 失真函数失真函数)()()(2121rrxpxpxpxxxPX)()()(2121ssypypypyyyPYsjriyxdji, 2 , 1, 2 , 1, 0),(失真测度失真测度l对于每一对 ，指定一个非负的函数( ,)ijx y),(),(),(),(),(),(),(),(),(212221212111srrrssyxdyxdyxdyx

2、dyxdyxdyxdyxdyxdD失真矩阵 sr7.1.1 7.1.1 失真函数失真函数失真测度失真测度常用的失真函数有：（1） 汉明失真（2） 平方误差失真函数失真函数是根据人们的实际需要和失真引起的损失、风险大小等人为规定的。 jijijiyxyxyxd10),(2)(),(jijiyxyxd7.1.1 7.1.1 失真函数失真函数失真测度失真测度例7.1.1 设信道输入 ，输出 ，规定失真函数 d(0,0)=d(1,1)=0，d(0,1)=d(1,0)=1， d(0,2)=d(1,2)=0.5，求 D 。解： 0,1X 0,1,2Y 5 . 0015 . 010D7.1.1 7.1.1

3、失真函数失真函数失真测度失真测度NkjijijijijjjiiijikkNNNNyxdyxdyxdyxdyyyxxxdd1),(),(),(),(),(),(22112121yx符号序列的失真函数NXXX21XNYYY21YrxxxX,21syyyY,21Niiiixxx21xNjjjjyyy21y7.1.1 7.1.1 失真函数失真函数失真测度失真测度例7.1.2 假设信源输出序列 ，其中每个随机变量均取值于 。经信道传输(编码编码）后的输出为 ，其中每个随机变量均取值于 。 定义失真函数 d (0,0) =d (1,1) =0， d (0,1) =d (1,0) =1，求失真矩阵 D (N

4、 ）。 123X X XX0,1X 123YY YY0,1Y 7.1.1 7.1.1 失真函数失真函数失真测度失真测度0112122310212132120123122110322112230112213210212312120132212110)(ND7.1.1 7.1.1 失真函数失真函数失真测度失真测度(000,000)(0,0)(0,0)(0,0)0(000,001)(0,0)(0,0)(0,1)1dddddddd7.1.2 7.1.2 平均失真平均失真 ),()|()(),()(),(1111jiijrisjijirisjjijiyxdxypxpyxdyxpyxdED失真测度失真测度

5、7.1.2 7.1.2 平均失真平均失真 失真测度失真测度122,rXx xx1( ),1,2,22ip xirr12,rYy yy0( ,)1ijijd x yij011101110111111D100010001001001P211211( ) (|) ( ,)111(|) ( ,)222rrijiijijrrjiijijDp x p yx d x yp yx d x yrrr 例：7.1.2 7.1.2 平均失真平均失真 失真测度失真测度例：111236111362111632P012101210D012111()244XP X11( ) (|) ( ,)1 1111 1111 111(

6、012)(101)(210)2 2364 3624 63212rsijiijijDp x p yx d x y 7.2.1 D 允许信道 保真度准则 DD NDND)(D失真允许信道 sjriDDxypBijD, 2 , 1;, 2 , 1: )|()(|):()1,2,;1,2,NND NjiBpD NNDirjsyx7.2 7.2 信息率失真函数信息率失真函数信息率失真函数信息率失真函数7.2.2 信息率失真函数的定义 );(min)()|(YXIDRDijBxyp()(|)()min( ;)jiD NNpBRDIy xX Y)()(DNRDRN当信源为离散无记忆平稳信源、信道为离散无记忆

7、平稳信道时);();(YXNIIYX7.2 7.2 信息率失真函数信息率失真函数信息率失真函数信息率失真函数);(max)(YXICixp是在信道固定前提下，选择一种信源概率分布使信息传输率最大（求极大值）。它反映了信道传输信息的能力，是信道可靠传输的最大信息传输率。信道容量与信源无关，是反映信道特性的参量，不同的信道其信道容量不同。 7.2 7.2 信息率失真函数信息率失真函数信息率失真函数信息率失真函数);(min)(: )|(YXIDRDDxypij是在信源固定，满足保真度准则的条件下的信息传输率的最小值。反映了满足一定失真度的条件下信源可以压缩的程度，也就是满足失真要求而再现信源消息所

8、必须获得的最少平均信息量。是信源特性的参量，一旦求到就与求极值过程中选择的试验信道无关，不同的信源率失真函数不同。 7.2 7.2 信息率失真函数信息率失真函数信息率失真函数信息率失真函数 这两个概念适用范围是不一样。研究信道容量C 是为了解决在已知信道中尽可能多地传送信息的问题，是为了充分利用已给定的信道，使传输的信息量最大而错误概率任意小，以提高通信的可靠性，这是信道编码的问题。 7.2 7.2 信息率失真函数信息率失真函数信息率失真函数信息率失真函数研究信息率失真函数是为了解决在已知信源和允许失真度条件下，使信源输出的信息率尽可能小，也就是在允许一定失真度D 的条件下，使信源必须传送给信

9、宿的信息量最少，尽可能用最少的码符号来传送信源信息，使信源的信息可以尽快地传送出去，以提高通信的有效性，这是信源编码问题。1.1. 的定义域的定义域 ()R D),(min)(),()|(min)(),()|()(minminjiijijjiijiijiijijiyxdxpyxdxypxpyxdxypxpD信息率失真函数的性质信息率失真函数的性质11( ) (|) ( ,)rsijiijijDp x p yx d x ymaxmin0(; )()I X YH XDD例7.3：删除信道 ，求 21012110DminD1.1. 的定义域的定义域 ()R D信息率失真函数的性质信息率失真函数的性质

10、解：100010Pmin12( )min ( ,)() 0() 00iijjiDp xd x yp xp x l只有当失真矩阵每一行至少只有当失真矩阵每一行至少有一个零元素时有一个零元素时, , 信源的平均信源的平均失真度才能达到下限值失真度才能达到下限值0 ,0 ,l否则否则D Dmin 0 .min 0 .例： 求 21102DminD1.1. 的定义域的定义域 ()R D信息率失真函数的性质信息率失真函数的性质解：0110Pmin121( )min ( ,)() 1() 0()iijjiDp xd x yp xp xp x 10102Dmin12() 0() 00Dp xp x (0)(

11、; )()(|)()RI X YH XH X YH X0110P011011101D100100010P1.1. 的定义域的定义域 信息率失真函数的性质信息率失真函数的性质()R Dmin123() 0() 0() 00Dp xp xp x (0)(; )()(|)()RI X YH XH X YH X例7.4 设信源 ,313131210)(XPX 1 , 0Y01212110D，求minD1.1. 的定义域的定义域 信息率失真函数的性质信息率失真函数的性质()R D解： 610312131031minD1)|(0)|(1)|()|(0)|(1)|(323122211211xypxypxyp

12、xypxypxypminmin(|)1()( )6min(; )()jiDp y xBR DRI X YH X1.1. 的定义域的定义域 信息率失真函数的性质信息率失真函数的性质()R D10112201Pmax()min()( ) ( ,)min( ) ( ,)jjiijp yjiiijjiDp yp x d x yp x d x y)()|(jijypxyp0)(DR11( ) (|) ( ,)rsijiijijDp x p yx d x y1.1. 的定义域的定义域 信息率失真函数的性质信息率失真函数的性质()R Dmaxmin0(; )()I X YH XDD例： 二元信源 , 计算

13、。6 . 04 . 0)(21xxXPXmaxD00D1.1. 的定义域的定义域 信息率失真函数的性质信息率失真函数的性质()R D解： maxmin( ) ( ,)min(0.40,00.6 )0.4iijjiDp x d x y对于任意 和 有0112max,D DD)()1 ()()1 (2121DRDRDDR2. 2. 是关于是关于D D的下凸函数的下凸函数 信息率失真函数的性质信息率失真函数的性质()R D201DDD10()()R DR D21DD 12()()R DR D3. 3. 在定义域内是严格递减函数在定义域内是严格递减函数信息率失真函数的性质信息率失真函数的性质12()(

14、)R DR D()R D一、一、R(D)的性质的性质 1.下凸性下凸性(有最小值有最小值)；2.连续性；连续性；3.单调递减性单调递减性二、二、 R(D)的定义域的定义域0, Dmax 1. Dmin= 0 (对应无失真情形对应无失真情形)一般地一般地,仅当失真矩阵每行均有零元素时仅当失真矩阵每行均有零元素时, Dmin= 0 2. Dmax (1) Dmax对应于对应于R(D)的零点的零点 (2) 由于由于p(ai, bj)(PD)的不同，的不同， 使使R(D)|min= 0的的D值可能有多个，值可能有多个， 此时应取最小一个此时应取最小一个min1( )min ( ,)niijjiDp a

15、d a b4.4.小结小结0 D* Dmax DR(D)H(X)R(D*)例7.9 二元信源的信息率失真函数信源输出符号集为（0，1），失真函数定义为汉明失真 ，求 。011,12XpPpp01,21ijijdi jij,7.3.2 二元信源和离散等概信源的 信息率失真函数的计算信息率失真函数的计算()R D()R D解： 且满足该最小失真的试验信道是一个无噪无损信道。 0minD1001Pmin()(0)()( )R DRH XH pmaxmin( ) ( ,)min(1, )iijjDp x d x yp pp1010Pmax()( )0R DR p信息率失真函数的计算信息率失真函数的计算

16、7.3.2 二元信源和离散等概信源的 ()R DpDDmax0 ( ,)() ( ,)(x0,y1)(x1,y0)ijijijijEDE d x yp x y d x yppP)|()()|()();(YXHpHYXHXHYXI(|)()( ) (根据Fano不等式)EH XYH PH D(; )( )()I X YH pH D当 时，信息率失真函数的计算信息率失真函数的计算7.3.2 二元信源和离散等概信源的 ()R D选取一信道使DD l根据根据R(D)R(D)的定义的定义, ,满足保真度的试验信道的满足保真度的试验信道的I(X;Y) I(X;Y) 的最小值就是的最小值就是R(D).R(D

17、).为了证实这一点为了证实这一点, ,必须找到一个试必须找到一个试 验信道验信道. .使其平均失真度使其平均失真度DD,DD,而而I(X;Y)I(X;Y)达到这个最小达到这个最小值值, ,即即I(X;Y)=R(D)=H(p)-H(D).I(X;Y)=R(D)=H(p)-H(D).121()()1 21 21020()1jpDpDp yp yDDDpp y信息率失真函数的计算信息率失真函数的计算7.3.2 二元信源和离散等概信源的 ( ,)() ( ,)(1)()1 21 2ijijijijDE d x yp x y d x yDpDD pDDDD( )( ; )( )( | )( )( )R

18、DI X YH XH X YH pH D()R D121211xxyDDyDDQl 已知信源的概率分布已知信源的概率分布P(ai)和失真函数和失真函数d(ai,bj)，就可求得信源，就可求得信源的的R(D)函数。原则上它与信道容量一样，即在有约束条件下求函数。原则上它与信道容量一样，即在有约束条件下求极小值的问题。极小值的问题。 也就是适当选取试验信道也就是适当选取试验信道P(v/u)使平均互信息最小化，使平均互信息最小化，111(/)(,)()(/)log()(/)nmjiijinijijiiP baI X YP a P baP a P bal其约束条件为其约束条件为:(/)0jiP ba1

19、(/)1mjijP ba11( ) (/) ( ,)nmijiijijP a P ba d a bDl 对于等概、对称失真的信源，存在一个与失真矩阵具有同样对称性的转移概率分布达到率失真R(D)。l解：由 0,1X 0,1,2Y 01 01d求率失真函数R(D) 。由于信源等概分布，失真函数具有对称性，因此，存在着与失真矩阵具有同样对称性的转移概率分布达到率失真函数R(D) ，该转移概率矩阵可写为：(),1p y x由于 ，因此对于任何有限平均失真，必须 。于是转移概率矩阵变为：(0,1)(1,0)dd 0min( )min( , )0yxDp xd x ymaxmin( )( , )1yxD

20、p x d x y对应此转移概率矩阵的平均失真：因此 可求出此时的互信息为：01()01p y xa,( ) () ( , )1x yDp x p y x d x y 1D ()(; )( )(/)11(,(1,)22112loglog(1)log(1)log22(1)(1)log(1)(1)log(1)(1)1R DI X YH YH YXDDHDHD DDDDDDDDDDDDDDDD）l相应的率失真函数R(D)如图所示。)(DR10D1D1,.,Xn1,.,Yn11011110D =1111011nnnnnnminmax1( )min( , )0 min( )( , )yyxxDp xd x yDp x d x yn由于信源等概分布，失真函数具有对称性，因此，存在由于信源等概分布，失真函数具有对称性，因此，存在着与失真矩阵具有同样对称性的转移概率分布达到率失着与失真矩阵具有同样对称性的转移概率分布达到率失真真R(D)。该转移概率矩阵可写为。该转移概率矩阵可写为对应此转移概率矩阵的平均失真对应此转移概率矩阵的平均失真11 ( / ) 0111AAnAp y xAAAn ,1( ) () ( , )1x yADp x p y x d x yn因此因此A=1-(n-1)D。由此不难求出此时