第6章信息率失真函数

1、2022-3-161内容提要数据压缩是信息传输和处理的重要研究内容，率失真理论研究的就是在允许一定失真的前提下，对信源的压缩编码。率失真信源编码定理（香农第三定理）指出：率失真函数R (D) 就是在给定失真测度条件下，对信源熵可压缩的最低程度。本章只限于研究率失真理论最基本的内容，失真测度，率失真函数，率失真函数的定义域，值域，性质及定量计算。R (D) 的计算很烦琐，文中通过二个例子介绍了几种特殊情况下R (D )的求法，一般情况只能用参数法求解。,( )1( )RRXp x dxp x()( )log( )aRH Xp xp x dx (|)( ) ( | )log( | )aRH Y X

2、p x p y xp y x dxdy (|)( ) ( | )log( | )aRH X Yp x p x yp x y dxdy ()()log()aRH XYp xyp xy dxdy (| )1Rp y x dy ,( )1( )( )RYRp y dyp yp y,( )1( )( )RXRp x dxp xp x( | )(; )()(|)()log( )( | )( )(|)()log( )()()( )()()log( ) ( )aRaRaRp x yI X YH XH X Yp xydxdyp xp y xH YH Y Xp xydxdyp yp yxH XH YH XYp

3、xydxdyp x p y2022-3-1612/1642022-3-1613/1642022-3-1614/1642022-3-1615/1642022-3-1616/1642022-3-1617/1646.1.1系统模型系统模型这样收信者收到消息后，这样收信者收到消息后，所产生的失真只是所产生的失真只是由信源编码带来的由信源编码带来的。我们也可以把信源编码。我们也可以把信源编码和信源译码等价成一个信道。和信源译码等价成一个信道。信信源源信信源源编编码码信信源源译译码码信信宿宿信信道道编编码码信信道道信信道道译译码码干扰干扰广义无干扰信道广义无干扰信道图6.1 通信系统2022-3-1618

4、/164信信源源信信宿宿试验信道试验信道 为了定量地描述信息传输率和失真的关系，一方面可以略去广义的无为了定量地描述信息传输率和失真的关系，一方面可以略去广义的无扰信道，另一方面我们用虚拟手法拿信道来表示失真信源编码的作用，扰信道，另一方面我们用虚拟手法拿信道来表示失真信源编码的作用，把信源编码和信源译码等价成一个信道，由于是失真编码，所以信道把信源编码和信源译码等价成一个信道，由于是失真编码，所以信道不是一一对应的，用信道传递概率来描述编、译码前后的关系。这就不是一一对应的，用信道传递概率来描述编、译码前后的关系。这就使图使图6.16.1的通信系统简化成图的通信系统简化成图6.2.6.2.一

5、般我们称此信道为一般我们称此信道为试验信道试验信道。现在我们要研究在现在我们要研究在给定允许失真的条件下，给定允许失真的条件下，是否可以设计一种信源编码使信息传输率为是否可以设计一种信源编码使信息传输率为最低最低。为此，我们首先讨论失真的测度。为此，我们首先讨论失真的测度。p (y|x)图6.2 简化的通信系统UV2022-3-1619/1642022-3-1620/1640,(,),0ijijijxyd xyxy 21myyyY ),(jiyxd用用一一个个非非负负的的函函数数2022-3-1621/164它为失真矩阵它为失真矩阵D，是，是 rs 阶矩阵。阶矩阵。2022-3-1622/16

6、42022-3-1623/164原始信源原始信源失真信源失真信源试验信道试验信道信道信道xyp (yj/xi)2022-3-1624/1640( ,)1ijijijxyd x yxy2022-3-1625/164rrD 0.11:.:1.011.10 0110D2022-3-1626/1640( ,)1 1/ 2ijijd x yijjs除除j=s以外所有的以外所有的j和和i所有所有ir+12022-3-1627/164d(0,0)=d(1,1)=0 d(0,1)=d(1,0)=1d(0,2)=d(1,2)=1/210121102 则 D2022-3-1628/1642022-3-1629/1

7、642022-3-1630/1642022-3-1631/1642( ,)()ijjid x yyx2022-3-1632/164 014101410D写出每个失真矩阵的矩阵元写出每个失真矩阵的矩阵元2022-3-1633/1642)(),(jijiyxyxd 均均方方失失真真|),(jijiyxyxd 绝绝对对失失真真| ,1,2,3ijijdxyi j2022-3-1636/164| / |),(ijijixyxyxd 相相对对失失真真0 ,(,)(,)1,ijijijxydxyxy 汉汉 明明 失失 真真其其 它它2022-3-1637/164 ,21NXXX X X,N,212121m

8、iNniyyyYiYYYxxxXi的取值为的取值为个符号个符号其中第其中第长的符号序列为长的符号序列为传输后，接收端收到的传输后，接收端收到的经过信道经过信道的取值为的取值为个符号个符号其中第其中第 Y Y11(, )(,)NNijiNNdX Yd X YNnm失真函数定义为序列失真函数矩阵共有个元素。2022-3-1638/1642022-3-1639/164),(),(vudEvudEDji 2022-3-1640/164),()/()(),()(11jirisjijiXYyxdxyPxPyxdxyPD 2022-3-1641/1642022-3-1642/164真。真。个位置上符号的平均

9、失个位置上符号的平均失是第是第其中其中则平均失真度为则平均失真度为iDDNYXdENdEDiNiiNiiiNN 111 ),(1 ,321NXXXX X X,321NYYYY Y Y输出序列为输出序列为,2121miniyyyYxxxXi 个符号的取值分别为个符号的取值分别为第第2022-3-1643/164扩展后的失真矩阵利用前一页的公式2022-3-1644/164过传输后失真的大小。描述了某个信源符号通单个符号的失真度),(jiyxd统的失真情况。是从总体上描述整个系下的失真大小，源在某一试验信道传输所以此值描述了某一信了统计平均，对信源与试验信道进行平均失真度D2022-3-1645/

10、164),()/()(),()(11jirisjijiXYyxdxyPxPyxdxyPD 2022-3-1646/1642022-3-1647/164,1nxxXX 信源编码器信源编码器,1myyYY ,1nxxXX 假想信道假想信道,1myyYY 希望在满足一定失真的情况下，必须传希望在满足一定失真的情况下，必须传输的信息量尽可能的少输的信息量尽可能的少 希望在用来再现信源信息的所必须获希望在用来再现信源信息的所必须获得的平均信息量最低得的平均信息量最低The seventeenth class-20142022-3-1648/164新内容新内容2022-3-1649/1642022-3-1

11、650/1642022-3-1651/164 );()(min)|(YXIDRDBxyP nimjjijijiBxyPypxypxypxpDRD11)|()()|(log)|()()(min率失真函数可以写成率失真函数可以写成对于离散无记忆信道，对于离散无记忆信道，2022-3-1652/164DD 2022-3-1653/164);(max)(YXICixp);(min)()/(YXIDRDiiBxyp 2022-3-1654/1642022-3-1655/1642022-3-1656/1642022-3-1657/1642022-3-1658/1642022-3-1659/1642022-

12、3-1660/1642022-3-1661/164允许平均失真度允许平均失真度D一定能达到一定能达到Dmin 0这个下界吗？这个下界吗？11() ( , )( ) (/) ( ,)rsijiijXYijDP xy d x yP x P yx d x y2022-3-1662/164),()(min1minjijniiyxdxpD 1 d,0 d,jjiijjyjiijjp y xx yyYp y xx yyY所有 最小值的最小值的2022-3-1664/164信息传输率等于信源输出的信息量信息传输率等于信源输出的信息量)()0()(minXHRDR 2022-3-1665/164 )(limD

13、RDminD10121102D minD012111()333Xq X01112210DminDmin111110033236D 解：2022-3-1668/1642022-3-1669/1642022-3-1670/164 YXYyxdxpypD),()()(minmax则则2022-3-1671/1640),(0)( YXIDR)()|(ypxyp这时这时X和和Y相互独立，相互独立，等效于通信中断等效于通信中断YXyxdxpypD),()()(minmax2022-3-1672/164最小时最小时 Xyxdxp),()( YXYyxdxpypD),()()(minmax1)( yp Xyx

14、dxp),()(其它的其它的0)( yp2022-3-1673/1642022-3-1674/1642022-3-1675/1642022-3-1676/164 123213321d2022-3-1677/164123()min(1,2,3)()min(2,1,3)()min(3,2,1)p ap ap amin( )min( , )yxDp xd x y ( ,)ijd a b(|)1jip baminD100( | )010001p y x2022-3-1678/164 max123123123min( ) ( , )min() 1() 2() 3 ,() 2() 1() 2 ,() 3(

15、) 3() 1yxDp x d x yp ap ap ap ap ap ap ap ap a 2()1p b13( )()0p bp bmaxD010( |010010p y x2022-3-1679/1642022-3-1680/1642022-3-1681/164The eighteenth class-2014021203110q()XX新内容新内容2022-3-1683/1642022-3-1684/164求 Dmin以及相应的试验信道？2022-3-1685/1642022-3-1686/1642022-3-1687/164)|()|(min)()|()|(min)(),()|()|

16、(2)|(21)|(121212121xypIxypIDRxypIxypIDRYXIDDxypxypDDDDBxypBxyp 即即达到极小的信道，达到极小的信道，前提下使前提下使和和保真度准则保真度准则是满足是满足和和是两个失真度，是两个失真度，和和假设假设)|()1()|()|(. 10 ,)1(210210 xypxypxypDDD 令令2022-3-1688/164212100)1()1()|(RDRDDDRDxyp 进一步可证明进一步可证明的信道的信道是满足保真度准则是满足保真度准则可以证明可以证明的下凸函数的下凸函数是是这表明这表明DDR)(均值的函数小于等于函数的均值书书P122有

17、详细的证明有详细的证明2022-3-1689/164 ;, ( | )( | )()()I X YI p xp y xp y xR DR D是的连续函数，由的定义可以知道是连续函数。小值，即小值，即其中一个小范围内求极其中一个小范围内求极极小值一定不大于在极小值一定不大于在，在一个较大范围内求，在一个较大范围内求有有和和的试验信道集合的试验信道集合和和则满足保真度则满足保真度若若21212121,DDDDBBBBDDDD 的等号不成立（略）的等号不成立（略）可以证明上述不等式中可以证明上述不等式中显然是非增函数。显然是非增函数。有有)(),()(21DRDRDR 是是严严格格递递减减函函数数所

18、所以以，)(DR2022-3-1690/164；时时，当当其其值值域域为为为为是是非非负负函函数数，其其定定义义域域0)(),(00)()1(maxmaxDRDDXHDDR 的的下下凸凸函函数数；是是关关于于失失真真度度D)()2(DR的严格递减函数的严格递减函数是关于失真度是关于失真度D)()3(DR2022-3-1691/164 0R 连续信源的情况下2022-3-1692/1642022-3-1693/1642022-3-1694/164DDDDDD2022-3-1695/1642022-3-1696/164 香农第三定理是一个存在定理，至于如何寻找香农第三定理是一个存在定理，至于如何寻

19、找这种最佳编码方法并没有给出，在实际应用中，这种最佳编码方法并没有给出，在实际应用中，存在以下两方面的问题：存在以下两方面的问题： 1、符合实际信源的、符合实际信源的R(D)函数的计算相当困难。函数的计算相当困难。1）需要对实际信源的统计特性有确切的描述）需要对实际信源的统计特性有确切的描述 2）需要对符合主客观实际的失真给予正确的）需要对符合主客观实际的失真给予正确的描述描述3）即使满足了前两条，）即使满足了前两条，R(D)的计算也比较困的计算也比较困难难2022-3-1697/164 2、即使求得很好的、即使求得很好的R(D)函数，还需要研究采函数，还需要研究采取何种编码方法才能达到极限值

20、取何种编码方法才能达到极限值R(D)。目前，这两方面工作都有进展。目前，这两方面工作都有进展。2022-3-1698/1642022-3-1699/1642022-3-16100/164The 13th week2022-3-16101/1642022-3-16102/164 )()()(2121nnxpxpxpxxxPX )()()(2121mnypypypyyyPYmjniyxdji, 2 , 1, 2 , 1),( 2022-3-16103/164 niijiijniijjjiiijijjiijppxypxpypypqxppxyppyxdd11)|()()();();();|();,(2

21、022-3-16104/164极小值问题极小值问题求求 nimjjijjiimjjinimjjijiiqpppYXInipDdpp11111log);(, 2 , 11信道矩阵每一行等于12022-3-16105/164)();(,.,2 , 10);(),.,2 , 1(1DRYXIpnipsDYXIpnisijmjijiiji即即的极小值，的极小值，得到约束条件下得，得到约束条件下得解出解出：换成为无条件极值问题换成为无条件极值问题将上述条件极值问题转将上述条件极值问题转和和引入乘子引入乘子应用拉格朗日乘子法，应用拉格朗日乘子法， 信道的传递概率具体的过程可以参照书上P129，做为了解过程

22、。2022-3-16106/1642022-3-16107/1642 , 1,10 jijijidij2022-3-16108/164NoImage则则简简记记, 2 , 1,),(),(),( jieypqxppxsjiiiii (,)1122112212(1)() ()1,1,2,1111111,1(1)(1)(1)ijsd xyiiixp xejmpppppp 按按下下式式解解方方程程写写成成矩矩阵阵形形式式由由此此解解得得2022-3-16109/164(,)112212122221(2)1(),1,2,()1111111()(1)11111()(1)11ijsd xyjjip yei

23、nxqqqppqpp 按按下下式式解解方方程程写写成成矩矩阵阵形形式式解解得得2022-3-16110/164(,)2(3)( ) (),1,2,., ;1,2,.,(1)11P(1)11-1ijijsd x yijijppx p yein jmpppppppppppp按下式解转分布写成矩阵移概率形式2022-3-16111/164)1log(loglog1,11)1(1(11)log()4(222222212121212111111DDsDDDppppdppdppdppdppdppDssijijiji 求求2022-3-16112/164)()1log()1(log)(11log1log)1

24、log()(1log)1)(1(1log)1()1(1log1loglog)(),()5(pHDDDDpHDDDDpHDDDppppDDDpsDDRDRiii 将上面各式带入，则有将上面各式带入，则有计算计算2022-3-16113/164 pDpDDHpHDR,0210),()()(式为式为得到如图曲线。其表达得到如图曲线。其表达结果很重要The nineteenth class-2014Over!2022-3-16114/1642022-3-16115/1642022-3-16116/1642022-3-16117/1642 , 1,10 jijijidij2022-3-16118/164

25、 pDpDDHpHDR,0210),()()(式为式为得到如图曲线。其表达得到如图曲线。其表达结果很重要2022-3-16119/164四、二元信源在对称失真函数定义下的率失真函数四、二元信源在对称失真函数定义下的率失真函数0100,;0ijijijx ya addijor对对于于 这样的条件下，我们称该信源为二元对称信源。Binary Symmetric Source-BSS 由于此类信源的特殊性，故可以求得它的信息率失真函数的解析表达式:新内容新内容2022-3-16120/1640011max000001 10110011 1101max11.()()10,0,1min(1)12jiij

26、ijijjiiiiiiP xappP xappijDpdi jdijDDDpdp dpdpDpdp dpdppDDDDp andherethenletthen2022-3-16121/1642 .21ieijsdiinmpand 0000111000011111exp()exp()1exp()exp()1psdpsdpsdpsd0101(1)exp()1exp()(1)1ppspspor解之:011exp()11exp(2)1exp()11exp() (1)sspspsp2022-3-16122/164000101001011111exp()exp()1exp()exp()qsdqsdqsdq

27、sd：即即101ijsdjjiq e其中的q为理想的输出分布。带入 i得联立方程组：0101exp()1exp()exp()1exp() (1)qqsspqsqsp2022-3-16123/164(1) exp()1exp()(1)exp()1exp()ppssppss01qq下一步带入参数表达式R(D)：exp()( )exp()1exp()( )( )logexp()log(1)log(1)1exp()log 1exp()ijiijijijiiisD sp qdsdsR ss D spssppppss o32022-3-16124/1641exp()exp()exp()11ln1DssDD

28、sDDDSDthenmaxmax1ln1DDppSSp又又 2022-3-16125/164( )( )log1loglog(1)log(1) log11log(1)log(1)log(1)log(1)( )()( )()iiiR DDpDDppppDDDDDDppppDDH pHH XHss max( )() 0DD0 DDH pHpR Dp所以计算得二元离散对称信源的信息率失真函数-重要结论-课后的习题经常用到0011()()1P xappP xapp 00ijd 对应的率失真分布：1loglog(1)()01()101rDrH DDrR DDr 01(), ( |( ( |)1)(D x

29、xp xQp xxxxDxr r元对称信源X=x1,x2,xr,且信源为等概分布P(x)=1/r,失真度为汉明失真度，率失真函数为01231111( )4444XP x0,1,2,3Y 0111101111011110D3log4log3()04()304DH DDDDR1loglog(1)()01()101rDrH DDrR DDr 利用已知公式2022-3-16130/1642022-3-16131/1642022-3-16132/1640,(,),0ijijijxyd xyxy 21myyyY ),(jiyxd用用一一个个非非负负的的函函数数2022-3-16133/164),()/()

30、(),()(11jirisjijiXYyxdxyPxPyxdxyPD 2022-3-16134/164 );()(min)|(YXIDRDBxyP nimjjijijiBxyPypxypxypxpDRD11)|()()|(log)|()()(min率失真函数可以写成率失真函数可以写成对于离散无记忆信道，对于离散无记忆信道，2022-3-16135/1642022-3-16136/1642022-3-16137/1642022-3-16138/1642022-3-16139/1642022-3-16140/1642022-3-16141/1642022-3-16142/1642022-3-161

31、43/1642022-3-16144/1642022-3-16145/1642022-3-16146/1642022-3-16147/1642022-3-16148/1642022-3-16149/1642022-3-16150/1640,(,),0ijijijxyd xyxy 21myyyY ),(jiyxd用用一一个个非非负负的的函函数数2022-3-16151/164它为失真矩阵它为失真矩阵D，是，是 rs 阶矩阵。阶矩阵。2022-3-16152/1642)(),(jijiyxyxd 均均方方失失真真|),(jijiyxyxd 绝绝对对失失真真| / |),(ijijixyxyxd 相

32、相对对失失真真0,(,)(,)1,ijijijxyd xyxy 汉汉明明失失真真其其它它2022-3-16153/164),(),(vudEvudEDji 2022-3-16154/164),()/()(),()(11jirisjijiXYyxdxyPxPyxdxyPD 2022-3-16155/1642022-3-16156/164过传输后失真的大小。描述了某个信源符号通单个符号的失真度),(jiyxd统的失真情况。是从总体上描述整个系下的失真大小，源在某一试验信道传输所以此值描述了某一信了统计平均，对信源与试验信道进行平均失真度D2022-3-16157/164),()/()(),()(1

33、1jirisjijiXYyxdxyPxPyxdxyPD 2022-3-16158/1642022-3-16159/1642022-3-16160/1642022-3-16161/1642022-3-16162/164 );()(min)|(YXIDRDBxyP nimjjijijiBxyPypxypxypxpDRD11)|()()|(log)|()()(min率失真函数可以写成率失真函数可以写成对于离散无记忆信道，对于离散无记忆信道，2022-3-16163/164DD 2022-3-16164/164);(max)(YXICixp);(min)()/(YXIDRDiiBxyp 2022-3-

34、16165/1642022-3-16166/1642022-3-16167/1642022-3-16168/1642022-3-16169/1642022-3-16170/1642022-3-16171/1642022-3-16172/164允许平均失真度允许平均失真度D一定能达到一定能达到Dmin 0这个下界吗？这个下界吗？2022-3-16173/164),()(min1minjijniiyxdxpD 2022-3-16174/164信息传输率等于信源输出的信息量信息传输率等于信源输出的信息量)()0()(minXHRDR 2022-3-16175/164012111()333Xq X01112210DminDmin111110033236D 解：2022-3-16176/1642022-3-16177/1642022-3-16178/1642022-3-16179/1642022-3-16180/1642022-3-16181/164 123213321d2