第七章 限失真信源编码

1、第七章第七章 限失真信源编码限失真信源编码7.1 7.1 失真测度失真测度7.2 7.2 信息率失真函数信息率失真函数 7.3 7.3 信息率失真函数的计算信息率失真函数的计算 7.4 7.4 限失真信源编码定理限失真信源编码定理 * * 7.5 7.5 常用的限失真信源编码方法常用的限失真信源编码方法概述概述失真测度失真测度信宿信源编码器/信道YXR=I(X;Y)R(D) 概述概述失真测度失真测度12345678000001010011100101110111ssssssss00011011017.1.1 7.1.1 失真函数失真函数)()()(2121rrxpxpxpxxxPX)()()(

2、2121ssypypypyyyPYsjriyxdji, 2 , 1, 2 , 1, 0),(失真测度失真测度),(),(),(),(),(),(),(),(),(212221212111srrrssyxdyxdyxdyxdyxdyxdyxdyxdyxdD失真矩阵 sr7.1.1 7.1.1 失真函数失真函数失真测度失真测度常用的失真函数有：（1） 汉明失真（2） 平方误差失真函数失真函数是根据人们的实际需要和失真引起的损失、风险大小等人为规定的。 jijijiyxyxyxd10),(2)(),(jijiyxyxd7.1.1 7.1.1 失真函数失真函数失真测度失真测度例7.1.1 设信道输入

3、，输出 ，规定失真函数 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 失真函数失真函数失真测度失真测度0,1X 0,1Y d(0,0)=d(1,1)=0，d(0,1)=d(1,0)=1，求 D 。NkjijijijijjjiiijikkNNNNyxdyxdyxdyxdyyyxxxdd1),(),(),(),(),(),(22112121yx符号序列的失真函数NXXX21XNYYY21YrxxxX,21syyyY,21Niiiixxx21xNjjj

4、jyyy21y7.1.1 7.1.1 失真函数失真函数失真测度失真测度例7.1.2 假设信源输出序列 ，其中每个随机变量均取值于 。经信道传输(编码编码）后的输出为 ，其中每个随机变量均取值于 。 定义失真函数 d (0,0) =d (1,1) =0， d (0,1) =d (1,0) =1，求失真矩阵 D (N ）。 123X X XX0,1X 123YY YY0,1Y 7.1.1 7.1.1 失真函数失真函数失真测度失真测度0112122310212132120123122110322112230112213210212312120132212110)(ND7.1.1 7.1.1 失真函数

5、失真函数失真测度失真测度(000,000)(0,0)(0,0)(0,0)0(000,001)(0,0)(0,0)(0,1)1dddddddd7.1.2 7.1.2 平均失真平均失真 ),()|()(),()(),(1111jiijrisjijirisjjijiyxdxypxpyxdyxpyxdED失真测度失真测度7.1.2 7.1.2 平均失真平均失真 失真测度失真测度122,rXx xx1( ),1,2,22ip xirr12,rYy yy0( ,)1ijijijxyd x yxy011101110111111D100010001001001P211211( ) (|) ( ,)111(|)

6、 ( ,)222rrijiijijrrjiijijDp x p yx d x yp yx d x yrrr 例：7.1.2 7.1.2 平均失真平均失真 失真测度失真测度例：111236111362111632P012101210D012111()244XP X11( ) (|) ( ,)1 1111 1111 111(012)(101)(210)2 2364 3624 63212rsijiijijDp x p yx d x y 11111()(,)() (|) (,)() (|)(,)NNNNkkijrsijiijijrsNijiijijkD NE dppdppd xyx yxyxx yxy

7、x1()NkkD ND失真测度失真测度7.1.2 7.1.2 平均失真平均失真 )()(iixpxpk), 2 , 1()|()|(NkxypxypijijkkDDkDNND)(失真测度失真测度7.1.2 7.1.2 平均失真平均失真 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(

8、)(|)()min( ;)jiD NNpBRDIy xX Y)()(DNRDRN当信源为离散无记忆平稳信源、信道为离散无记忆平稳信道时);();(YXNIIYX7.2 7.2 信息率失真函数信息率失真函数信息率失真函数信息率失真函数);(max)(YXICixp是在信道固定前提下，选择一种信源概率分布使信息传输率最大（求极大值）。它反映了信道传输信息的能力，是信道可靠传输的最大信息传输率。信道容量与信源无关，是反映信道特性的参量，不同的信道其信道容量不同。 7.2 7.2 信息率失真函数信息率失真函数信息率失真函数信息率失真函数);(min)(: )|(YXIDRDDxypij是在信源固定，满

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

10、就是在允许一定失真度D 的条件下，使信源必须传送给信宿的信息量最少，尽可能用最少的码符号来传送信源信息，使信源的信息可以尽快地传送出去，以提高通信的有效性，这是信源编码问题。7.2 7.2 信息率失真函数信息率失真函数信息率失真函数信息率失真函数1.1. 的定义域的定义域 ()R D),(min)(),()|(min)(),()|()(minminjiijijjiijiijiijijiyxdxpyxdxypxpyxdxypxpD信息率失真函数的性质信息率失真函数的性质11( ) (|) ( ,)rsijiijijDp x p yx d x ymaxmin0(; )()I X YH XDD例7.

11、3：删除信道 ，求 21012110DminD1.1. 的定义域的定义域 ()R D信息率失真函数的性质信息率失真函数的性质解：100010Pmin12( )min ( ,)() 0() 00iijjiDp xd x yp xp x 例： 求 21102DminD1.1. 的定义域的定义域 ()R D信息率失真函数的性质信息率失真函数的性质解：0110Pmin121( )min ( ,)() 1() 0()iijjiDp xd x yp xp xp x 10102Dmin12() 0() 00Dp xp x (0)(; )()(|)()RI X YH XH X YH X0110P0110111

12、01D100100010P1.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)|(323122211211xypxypxypxypxypxypminmin(|)1()( )6min(; )()jiDp

13、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例： 二元信源 , 计算 。6 . 04 . 0)(21xxXPXmaxD00D1.1. 的定义域的定义

14、域 信息率失真函数的性质信息率失真函数的性质()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()()R DR D()R D二元信源的信息率失真函数例7.6 信源输出符号集为（0

15、，1），失真函数定义为 ， 求 。011,12XpPpp01,21ijijdi jij,7.3.1 应用参量表示式计算信息率失真函数的计算信息率失真函数的计算()R D()R D解：（1）由 计算 和 。 ( )1ijsdiiip xe121()ijsdjjip y e（2）由 计算 和 。1()p y2()p y（3）将求得的 ， 和 ， 代入得到平均失真度D(S)，并将S表示为D的函数。 7.3.1 应用参量表示式计算信息率失真函数的计算信息率失真函数的计算121()p y2()p y()R D（4） 将参量S代入得到率失真函数。 7.3.1 应用参量表示式计算信息率失真函数的计算信息率失

16、真函数的计算()R D( )( )( )R DH pH D7.3.1 应用参量表示式计算信息率失真函数的计算信息率失真函数的计算()R D等概信源的信息率失真函数例7.7 信源输出符号集 ，等概分布，输出符号集 ，失真函数定义为 求 。rxxxX,21ryyyY,21rjijijiyxdji, 2 , 1,10),( ( )loglog(1)()R DrDrH D7.3.1 应用参量表示式计算信息率失真函数的计算信息率失真函数的计算()R D()R D7.3.1 应用参量表示式计算信息率失真函数的计算信息率失真函数的计算 ( ) loglog(1)( )RDr DrH D ()R D例7.8

17、设信源符号集 。概率分布为 ，失真函数选为求当允许的失真度为1/2时信源的率失真函数。rxxxX221,rirxpi2 , 2 , 1,21)(jijijiyxyxyxd10),(7.3.1 应用参量表示式计算信息率失真函数的计算信息率失真函数的计算()R D例7.9 二元信源的信息率失真函数信源输出符号集为（0，1），失真函数定义为汉明失真 ，求 。011,12XpPpp01,21ijijdi jij,7.3.2 二元信源和离散等概信源的 信息率失真函数的计算信息率失真函数的计算()R D()R D解： 且满足该最小失真的试验信道是一个无噪无损信道。 0minD1001Pmin()(0)()

18、( )R DRH XH pmaxmin( ) ( ,)min(1, )iijjDp x d x yp pp1010Pmax()( )0R DR p信息率失真函数的计算信息率失真函数的计算7.3.2 二元信源和离散等概信源的 ()R DpDDmax0 ( ,)() ( ,)(0,1)(1,0)ijijijijEDE d x yp x y d x yP XYP XYP)|()()|()();(YXHpHYXHXHYXI)()()|(DHPHYXHE(; )( )()I X YH pH D当 时，信息率失真函数的计算信息率失真函数的计算7.3.2 二元信源和离散等概信源的 ()R D121()()1 21 21020()1jpDpDp yp yDDDpp y信息率失真函数的计算信息率失真函数的计算7.3.2 二元信源和离散等概信源的 ( ,)() ( ,)(1)()1 21 2ijijijijDE d x yp x y d x yDpDD pDDDD( )( ; )( )( | )( )( )R DI X YH XH X YH pH D()R D121211xxyDDyDDQ定理7.1 设 是离散无记忆信源的信息率失真函数。对于任意的允许失真度 和任意小的正数 ，当码长N 足够长时，一定存在一种编码 其码字个数 而编码后的平均失真