信息论与编码课件第六章.ppt

1、第六章第六章 限失真信源编码限失真信源编码作业6.1、6.2（不求（不求R(D)）限失真信源编码的意义限失真信源编码的意义云海（2M）云海（223K）云海（30K）云海（3K）率失真函数的定义率失真函数的定义失真度（失真函数）定义失真度（失真函数）定义失真矩阵失真矩阵D（失真度的矩阵表示失真度的矩阵表示）d(ui,vj)0 i=1，2，n,j=1，2，m mnmnnnmmvudvudvudvudvudvudvudvudvud ),(),(),(),(),(),(),(),(),(212221212111D率失真函数的定义率失真函数的定义平均失真度定义平均失真度定义),()(),(vuduvpv

2、udEdUV NnnnNNyxdyxd1),(),(NNNNNNNNYXyxNNNNNYXyxNNNNNyxdxyqxpyxdyxpXdEND),(),(N),()()(),()()Y,()()(1NDNDN NnnnNNNNxyqxyqxpxpxpxp121)()(,)().()()(DDN 率失真函数率失真函数R(D)的定义的定义率失真函数定义率失真函数定义);(min)()|(VUIDRDPuvp DduvpPD :)|(信信源源信信道道信源编码器信源编码器（试验信道）（试验信道）p p(v v|u u)无噪无噪信道信道率失真函数率失真函数R(D)与信道容量与信道容量C定义定义);(mi

3、n)()|(VUIDRDPuvp );(max)(VUICup 描述对象描述对象R(D):信源特性信源特性信源的可压缩性信源的可压缩性C :信道特性信道特性信道的传输能力信道的传输能力实际应用实际应用R(D):限失真信源编码（熵压缩编码）限失真信源编码（熵压缩编码）C :最大限度的利用信道，信道编码最大限度的利用信道，信道编码率失真函数率失真函数R(D)与信道容量与信道容量C的比较的比较求解求解R(D)已知已知 p(u)和和 d(u,v)求求 I(U;V)极小值极小值约束条件为约束条件为Dvuduvpupuvpuvpjiijmjniimjijij )()|()(1)|(0)|(111C已知已知

4、 p(v|u),求求 I(U;V)极大值极大值约束条件为约束条件为 niiiupup11)(0)(时时当当时时当当jijiaadji10),(nnnnaaanaaaaaanuvp221n2211)|(个信源符号个信源符号个信源符号个信源符号nnP 21111111(1)(1)R（D）的定义域的定义域（0,Dmax）(2)(2)R（D）是是D的下凸函数的下凸函数 RD1+(1)D2 R(D1)+(1)R(D2)率失真函数率失真函数R(D)的性质的性质 UVvudupD),(min)(min UVvudupD),()(minmax)()(minUHDR 0)(max DDR),(min),()(,

5、1)(),()(min)(),()()(minminvudvuduvpuvpvuduvpupvuduvpupDVVVUVUV 必必有有由由于于),(min)(),(min),()|(),(min),(0)|(),(min),(1)|(,.,2,1minvudupDvudvuduvpvudvuduvpvudvuduvpKiVuVVVV 而而则则对对对对所所有有取取试试验验信信道道如如下下：最最多多只只有有一一个个零零。有有一一个个零零，而而且且每每一一列列失失真真矩矩阵阵中中每每一一行行至至少少成成立立的的条条件件：，但但一一般般情情况况下下只只成成立立。的的信信息息量量，即即的的信信息息应应等

6、等于于信信源源输输出出即即传传输输源源不不允允许许有有任任何何失失真真，从从直直观观上上理理解解，表表示示信信)()()()()()(,0minminminminXHDRXHDRXHDRD )()0(0100010,21012110,2,1,0,1,0minXHRDDYX ，可得，可得，试验信道的矩阵试验信道的矩阵失真矩阵为：失真矩阵为：取值于取值于而而取值于取值于例：二元删除信道例：二元删除信道 )();(min)61()(,1)(1)()(1)(61,01212110,1,0:,313131210)()(min32222111minXHYXIRDRabpabpabpabpDDYxpXDij

7、Pabp 而而。即即试试验验信信道道为为无无穷穷多多个个应应满满足足：此此时时信信道道矩矩阵阵中中的的元元素素失失真真矩矩阵阵为为信信宿宿例例：设设信信源源Dmax是这样来计算的。是这样来计算的。R(D)0就是就是I(X;Y)0，这时试验信道输入与输出是互相独立的，所以条这时试验信道输入与输出是互相独立的，所以条件概率件概率p(yj/xi)与与xi无关。即无关。即jjijijpypxypp)()/(求出满足条件求出满足条件 的的D中的最中的最小值小值，即mjniijijdppD11maxmin11mjjp nimjijjidppD11此时平均失真为此时平均失真为从上式观察可得：在从上式观察可得

8、：在j=1，m中，可中，可找到找到 值最小的值最小的j，当该，当该j对应的对应的pj1，而其余而其余pj为零时，上式右边达到最小，这为零时，上式右边达到最小，这时上式可简化成时上式可简化成niijidp1niijimjdpD1,2,1maxmin例例设输入输出符号表为设输入输出符号表为XY 0，1，输入概率，输入概率分布分布p(x)=1/3，2/3，失真矩阵为，失真矩阵为0110),(),(),(),(22122111badbadbadbadd解：解：当当Dmin0时，时，R(Dmin)H(X)H(1/3，2/3)0.91比特比特/符号，这时信源编码器无失真，符号，这时信源编码器无失真，所以该

9、编码器的转移概率为所以该编码器的转移概率为 1001P3131,32min032131,132031min,minmin2,12,12221212121112,1212,1maxjjjiijijdpdpdpdpdpD当当R(Dmax)0时时 此时输出符号概率此时输出符号概率p(b1)0，p(b2)1，所以这时的编码器的转移概率为所以这时的编码器的转移概率为 2221,baba1010P(4)(4)对于离散无记忆信源，有对于离散无记忆信源，有 RN（D）=N R1（D）率失真函数率失真函数R(D)的性质的性质(3)(3)R（D）函数具有单调递减性和连续性函数具有单调递减性和连续性 若若 D1D2

10、 ，有有 R(D1)R(D2)率失真函数率失真函数R(D)的性质的性质率失真率失真函数函数R(D)的计算的计算 已知已知 p(u)和和 d(u,v)，求，求 I(U;V)极小值极小值约束条件为约束条件为Dvuduvpupuvpuvpjiijmjniimjijij ),()|()(1)|(0)|(111);(min)()|(VUIDRDPuvp )()0(,1001:,01?)(0110,1,0:,21,110)(1minXHRPDDRdYpppxpX 则则对对应应的的试试验验信信道道为为）计计算算最最小小允允许许失失真真解解：求求此此信信源源的的率率失失真真函函数数失失真真矩矩阵阵：二二元元信

11、信源源例例率失真率失真函数函数R(D)的计算的计算pppbadapDDijiij ,1min),()(min)221maxmax最最大大允允许许失失真真)()()()();(,)10()01(),()(),()()(,0)30)()(101021212121maxmaxYXHpHYXHXHYXIDdpppbadbapbadabpapdDDpRDRPEijjijiijjiiji 是是互互信信息息：我我们们选选取取一一信信道道概概率率。平平均均失失真真等等于于平平均均错错误误在在汉汉明明失失真真的的情情况况下下，即即平平均均失失真真为为当当一一试试验验信信道道为为：最最大大允允许许失失真真对对应应

12、的的唯唯)()();(min)()()()();(),()()(2)1log()()(DHpHYXIDHpHYXHpHYXIDHpHYXHrrppHYXHEEE 即即得得，所所以以，这这里里由由费费诺诺不不等等式式 DyxpDyxpDyxpDyxpDHpHYXIDHpHDR1)11()10()01(1)00()()();()()()()4试试验验信信道道如如下下：现现引引入入一一个个“反反向向”的的一一个个试试验验信信道道，满满足足，现现需需要要找找到到函函数数的的定定义义，其其可可能能为为由由DbadbapdyppDDDpypDDpypbpapbapijjijijiji 2121),()(,

13、1)(0210,211)1(,21)0()()()|(失失真真为为故故该该信信道道存存在在。而而平平均均则则得得、由由)()()()();()()()1log()1(log)(1log),()(212121DHpHYXHXHYXIDHbpDDDDbapbapYXHjjijjiji 真真函函数数为为：在在此此试试验验信信道道中中，率率失失0)(DRDpD max)(pH21 pDpDDHpHDR00)()()(则则高斯信源的率失真函数高斯信源的率失真函数R(D)例例22 若高斯信源若高斯信源U，它的概率密度为它的概率密度为而失真函数为而失真函数为d(u,v)=(uv)2。222)(exp21)(

14、muup则此信源的则此信源的率失真函数率失真函数为为 2220log21)(DDDDR 限失真信源编码定理限失真信源编码定理 设离散无记忆信源的率失真函数为设离散无记忆信源的率失真函数为R（D），如果信，如果信源编码后平均每个信源符号的信息传输率源编码后平均每个信源符号的信息传输率R R（D），则一定存在一种信源编码则一定存在一种信源编码 C，使编码后的平均失真度使编码后的平均失真度 。DCd)(限失真信源编码定理限失真信源编码定理 设离散无记忆信源的率失真函数为设离散无记忆信源的率失真函数为R（D），如果信，如果信源编码后平均每个信源符号的信息传输率源编码后平均每个信源符号的信息传输率R R（D），则一定存在一，则一定存在一种信源编码种信源编码 C，使编码后的平均失真度使编码后的平均失真度 。DCd)(限失真信源编码定理（香农第三定理）限失真信源编码定理（香农第三定理）无失真信源编码定理（香农第一定理）无失真信源编码定理（香农第一定理）离散无记忆信源离散无记忆信源S的的N次扩展信源次扩展信源SN，具有熵，具有熵H(SN)。若对信源。若对信源SN 进行进行r 进制编码，总可以找到一种编码方法，构成唯一可译码，进制编码，总可以找到一种编码方法，构成唯一可译码，码字平均长度满足码字平均长度满足rSHNNLrSHNlog)(1log)(