1、2022-4-31內容提要數據壓縮是信息傳輸和處理的重要研究內容，率失真理論研究的就是在允許一定失真的前提下，對信源的壓縮編碼。率失真信源編碼定理（香農第三定理）指出：率失真函數R (D) 就是在給定失真測度條件下，對信源熵可壓縮的最低程度。本章只限于研究率失真理論最基本的內容，失真測度，率失真函數，率失真函數的定義域，值域，性質及定量計算。R (D) 的計算很煩瑣，文中通過二個例子介紹了幾種特殊情況下R (D )的求法，一般情況只能用參數法求解。,( )1( )RRXp x dxp x()( )log( )aRH Xp xp x dx (|)( ) ( | )log( | )aRH Y Xp

2、 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 x

3、ydxdyp x p y2022-4-312/1642022-4-313/1642022-4-314/1642022-4-315/1642022-4-316/1642022-4-317/1646.1.1系統模型系統模型這樣收信者收到消息后，這樣收信者收到消息后，所產生的失真只是所產生的失真只是由信源編碼帶來的由信源編碼帶來的。我們也可以把信源編碼。我們也可以把信源編碼和信源譯碼等價成一個信道。和信源譯碼等價成一個信道。信信源源信信源源編編碼碼信信源源譯譯碼碼信信宿宿信信道道編編碼碼信信道道信信道道譯譯碼碼干擾干擾廣義無干擾信道廣義無干擾信道圖6.1 通信系統2022-4-318/164信信源源

4、信信宿宿試驗信道試驗信道 為了定量地描述信息傳輸率和失真的關系，一方面可以略去廣義的無為了定量地描述信息傳輸率和失真的關系，一方面可以略去廣義的無擾信道，另一方面我們用虛擬手法拿信道來表示失真信源編碼的作用，擾信道，另一方面我們用虛擬手法拿信道來表示失真信源編碼的作用，把信源編碼和信源譯碼等價成一個信道，由于是失真編碼，所以信道把信源編碼和信源譯碼等價成一個信道，由于是失真編碼，所以信道不是一一對應的，用信道傳遞概率來描述編、譯碼前后的關系。這就不是一一對應的，用信道傳遞概率來描述編、譯碼前后的關系。這就使圖使圖6.16.1的通信系統簡化成圖的通信系統簡化成圖6.2.6.2.一般我們稱此信道為

5、一般我們稱此信道為試驗信道試驗信道?，F在我們要研究在現在我們要研究在給定允許失真的條件下，給定允許失真的條件下，是否可以設計一種信源編碼使信息傳輸率為是否可以設計一種信源編碼使信息傳輸率為最低最低。為此，我們首先討論失真的測度。為此，我們首先討論失真的測度。p (y|x)圖6.2 簡化的通信系統UV2022-4-319/1642022-4-320/1640,(,),0ijijijxyd xyxy 21myyyY ),(jiyxd用用一一個個非非負負的的函函數數2022-4-321/164它為失真矩陣它為失真矩陣D，是，是 rs 階矩陣。階矩陣。2022-4-322/1642022-4-323/

6、164原始信源原始信源失真信源失真信源試驗信道試驗信道信道信道xyp (yj/xi)2022-4-324/1640( ,)1ijijijxyd x yxy2022-4-325/164rrD 0.11:.:1.011.10 0110D2022-4-326/1640( ,)1 1/ 2ijijd x yijjs除除j=s以外所有的以外所有的j和和i所有所有ir+12022-4-327/164d(0,0)=d(1,1)=0 d(0,1)=d(1,0)=1d(0,2)=d(1,2)=1/210121102 則 D2022-4-328/1642022-4-329/1642022-4-330/164202

7、2-4-331/1642( ,)()ijjid x yyx2022-4-332/164 014101410D寫出每個失真矩陣的矩陣元寫出每個失真矩陣的矩陣元2022-4-333/1642)(),(jijiyxyxd 均均方方失失真真|),(jijiyxyxd 絕絕對對失失真真| ,1,2,3ijijdxyi j2022-4-336/164| / |),(ijijixyxyxd 相相對對失失真真0 ,(,)(,)1,ijijijxydxyxy 漢漢 明明 失失 真真其其 它它2022-4-337/164 ,21NXXX X X,N,212121miNniyyyYiYYYxxxXi的取值為的取值為

8、個符號個符號其中第其中第長的符號序列為長的符號序列為傳輸后，接收端收到的傳輸后，接收端收到的經過信道經過信道的取值為的取值為個符號個符號其中第其中第 Y Y11(, )(,)NNijiNNdX Yd X YNnm失真函數定義為序列失真函數矩陣共有個元素。2022-4-338/1642022-4-339/164),(),(vudEvudEDji 2022-4-340/164),()/()(),()(11jirisjijiXYyxdxyPxPyxdxyPD 2022-4-341/1642022-4-342/164真。真。個位置上符號的平均失個位置上符號的平均失是第是第其中其中則平均失真度為則平均失

9、真度為iDDNYXdENdEDiNiiNiiiNN 111 ),(1 ,321NXXXX X X,321NYYYY Y Y輸出序列為輸出序列為,2121miniyyyYxxxXi 個符號的取值分別為個符號的取值分別為第第2022-4-343/164擴展后的失真矩陣利用前一頁的公式2022-4-344/164過傳輸后失真的大小。描述了某個信源符號通單個符號的失真度),(jiyxd統的失真情況。是從總體上描述整個系下的失真大小，源在某一試驗信道傳輸所以此值描述了某一信了統計平均，對信源與試驗信道進行平均失真度D2022-4-345/164),()/()(),()(11jirisjijiXYyxdx

10、yPxPyxdxyPD 2022-4-346/1642022-4-347/164,1nxxXX 信源編碼器信源編碼器,1myyYY ,1nxxXX 假想信道假想信道,1myyYY 希望在滿足一定失真的情況下，必須傳希望在滿足一定失真的情況下，必須傳輸的信息量盡可能的少輸的信息量盡可能的少 希望在用來再現信源信息的所必須獲希望在用來再現信源信息的所必須獲得的平均信息量最低得的平均信息量最低The seventeenth class-20142022-4-348/164新內容新內容2022-4-349/1642022-4-350/1642022-4-351/164 );()(min)|(YXIDR

11、DBxyP nimjjijijiBxyPypxypxypxpDRD11)|()()|(log)|()()(min率失真函數可以寫成率失真函數可以寫成對于離散無記憶信道，對于離散無記憶信道，2022-4-352/164DD 2022-4-353/164);(max)(YXICixp);(min)()/(YXIDRDiiBxyp 2022-4-354/1642022-4-355/1642022-4-356/1642022-4-357/1642022-4-358/1642022-4-359/1642022-4-360/1642022-4-361/164允許平均失真度允許平均失真度D一定能達到一定能達

12、到Dmin 0這個下界嗎？這個下界嗎？11() ( , )( ) (/) ( ,)rsijiijXYijDP xy d x yP x P yx d x y2022-4-362/164),()(min1minjijniiyxdxpD 1 d,0 d,jjiijjyjiijjp y xx yyYp y xx yyY所有 最小值的最小值的2022-4-364/164信息傳輸率等于信源輸出的信息量信息傳輸率等于信源輸出的信息量)()0()(minXHRDR 2022-4-365/164 )(limDRDminD10121102D minD012111()333Xq X01112210DminDmin1

13、11110033236D 解：2022-4-368/1642022-4-369/1642022-4-370/164 YXYyxdxpypD),()()(minmax則則2022-4-371/1640),(0)( YXIDR)()|(ypxyp這時這時X和和Y相互獨立，相互獨立，等效于通信中斷等效于通信中斷YXyxdxpypD),()()(minmax2022-4-372/164最小時最小時 Xyxdxp),()( YXYyxdxpypD),()()(minmax1)( yp Xyxdxp),()(其它的其它的0)( yp2022-4-373/1642022-4-374/1642022-4-37

14、5/1642022-4-376/164 123213321d2022-4-377/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-4-378/164 max123123123min( ) ( , )min() 1() 2() 3 ,() 2() 1() 2 ,() 3() 3() 1yxDp x d x yp ap ap ap ap ap ap ap ap a 2()1p b13( )()0p

15、 bp bmaxD010( |010010p y x2022-4-379/1642022-4-380/1642022-4-381/164The eighteenth class-2014021203110q()XX新內容新內容2022-4-383/1642022-4-384/164求 Dmin以及相應的試驗信道？2022-4-385/1642022-4-386/1642022-4-387/164)|()|(min)()|()|(min)(),()|()|(2)|(21)|(121212121xypIxypIDRxypIxypIDRYXIDDxypxypDDDDBxypBxyp 即即達到極小的信

16、道，達到極小的信道，前提下使前提下使和和保真度準則保真度準則是滿足是滿足和和是兩個失真度，是兩個失真度，和和假設假設)|()1()|()|(. 10 ,)1(210210 xypxypxypDDD 令令2022-4-388/164212100)1()1()|(RDRDDDRDxyp 進一步可證明進一步可證明的信道的信道是滿足保真度準則是滿足保真度準則可以證明可以證明的下凸函數的下凸函數是是這表明這表明DDR)(均值的函數小于等于函數的均值書書P122有詳細的證明有詳細的證明2022-4-389/164 ;, ( | )( | )()()I X YI p xp y xp y xR DR D是的連

17、續函數，由的定義可以知道是連續函數。小值，即小值，即其中一個小范圍內求極其中一個小范圍內求極極小值一定不大于在極小值一定不大于在，在一個較大范圍內求，在一個較大范圍內求有有和和的試驗信道集合的試驗信道集合和和則滿足保真度則滿足保真度若若21212121,DDDDBBBBDDDD 的等號不成立（略）的等號不成立（略）可以證明上述不等式中可以證明上述不等式中顯然是非增函數。顯然是非增函數。有有)(),()(21DRDRDR 是是嚴嚴格格遞遞減減函函數數所所以以，)(DR2022-4-390/164；時時，當當其其值值域域為為為為是是非非負負函函數數，其其定定義義域域0)(),(00)()1(max

18、maxDRDDXHDDR 的的下下凸凸函函數數；是是關關于于失失真真度度D)()2(DR的嚴格遞減函數的嚴格遞減函數是關于失真度是關于失真度D)()3(DR2022-4-391/164 0R 連續信源的情況下2022-4-392/1642022-4-393/1642022-4-394/164DDDDDD2022-4-395/1642022-4-396/164 香農第三定理是一個存在定理，至于如何尋找香農第三定理是一個存在定理，至于如何尋找這種最佳編碼方法并沒有給出，在實際應用中，這種最佳編碼方法并沒有給出，在實際應用中，存在以下兩方面的問題：存在以下兩方面的問題： 1、符合實際信源的、符合實際

19、信源的R(D)函數的計算相當困難。函數的計算相當困難。1）需要對實際信源的統計特性有確切的描述）需要對實際信源的統計特性有確切的描述 2）需要對符合主客觀實際的失真給予正確的）需要對符合主客觀實際的失真給予正確的描述描述3）即使滿足了前兩條，）即使滿足了前兩條，R(D)的計算也比較困的計算也比較困難難2022-4-397/164 2、即使求得很好的、即使求得很好的R(D)函數，還需要研究采函數，還需要研究采取何種編碼方法才能達到極限值取何種編碼方法才能達到極限值R(D)。目前，這兩方面工作都有進展。目前，這兩方面工作都有進展。2022-4-398/1642022-4-399/1642022-4

20、-3100/164The 13th week2022-4-3101/1642022-4-3102/164 )()()(2121nnxpxpxpxxxPX )()()(2121mnypypypyyyPYmjniyxdji, 2 , 1, 2 , 1),( 2022-4-3103/164 niijiijniijjjiiijijjiijppxypxpypypqxppxyppyxdd11)|()()();();();|();,(2022-4-3104/164極小值問題極小值問題求求 nimjjijjiimjjinimjjijiiqpppYXInipDdpp11111log);(, 2 , 11信道矩陣

21、每一行等于12022-4-3105/164)();(,.,2 , 10);(),.,2 , 1(1DRYXIpnipsDYXIpnisijmjijiiji即即的極小值，的極小值，得到約束條件下得，得到約束條件下得解出解出：換成為無條件極值問題換成為無條件極值問題將上述條件極值問題轉將上述條件極值問題轉和和引入乘子引入乘子應用拉格朗日乘子法，應用拉格朗日乘子法， 信道的傳遞概率具體的過程可以參照書上P129，做為了解過程。2022-4-3106/1642022-4-3107/1642 , 1,10 jijijidij2022-4-3108/164NoImage則則簡簡記記, 2 , 1,),()

22、,(),( jieypqxppxsjiiiii (,)1122112212(1)() ()1,1,2,1111111,1(1)(1)(1)ijsd xyiiixp xejmpppppp 按按下下式式解解方方程程寫寫成成矩矩陣陣形形式式由由此此解解得得2022-4-3109/164(,)112212122221(2)1(),1,2,()1111111()(1)11111()(1)11ijsd xyjjip yeinxqqqppqpp 按按下下式式解解方方程程寫寫成成矩矩陣陣形形式式解解得得2022-4-3110/164(,)2(3)( ) (),1,2,., ;1,2,.,(1)11P(1)11

23、-1ijijsd x yijijppx p yein jmpppppppppppp按下式解轉分布寫成矩陣移概率形式2022-4-3111/164)1log(loglog1,11)1(1(11)log()4(222222212121212111111DDsDDDppppdppdppdppdppdppDssijijiji 求求2022-4-3112/164)()1log()1(log)(11log1log)1log()(1log)1)(1(1log)1()1(1log1loglog)(),()5(pHDDDDpHDDDDpHDDDppppDDDpsDDRDRiii 將上面各式帶入，則有將上面各式帶

24、入，則有計算計算2022-4-3113/164 pDpDDHpHDR,0210),()()(式為式為得到如圖曲線。其表達得到如圖曲線。其表達結果很重要The nineteenth class-2014Over!2022-4-3114/1642022-4-3115/1642022-4-3116/1642022-4-3117/1642 , 1,10 jijijidij2022-4-3118/164 pDpDDHpHDR,0210),()()(式為式為得到如圖曲線。其表達得到如圖曲線。其表達結果很重要2022-4-3119/164四、二元信源在對稱失真函數定義下的率失真函數四、二元信源在對稱失真函數

25、定義下的率失真函數0100,;0ijijijx ya addijor對對于于 這樣的條件下，我們稱該信源為二元對稱信源。Binary Symmetric Source-BSS 由于此類信源的特殊性，故可以求得它的信息率失真函數的解析表達式:新內容新內容2022-4-3120/1640011max000001 10110011 1101max11.()()10,0,1min(1)12jiijijijjiiiiiiP xappP xappijDpdi jdijDDDpdp dpdpDpdp dpdppDDDDp andherethenletthen2022-4-3121/1642 .21ieijs

26、diinmpand 0000111000011111exp()exp()1exp()exp()1psdpsdpsdpsd0101(1)exp()1exp()(1)1ppspspor解之:011exp()11exp(2)1exp()11exp() (1)sspspsp2022-4-3122/164000101001011111exp()exp()1exp()exp()qsdqsdqsdqsd：即即101ijsdjjiq e其中的q為理想的輸出分布。帶入 i得聯立方程組：0101exp()1exp()exp()1exp() (1)qqsspqsqsp2022-4-3123/164(1) exp()

27、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-4-3124/1641exp()exp()exp()11ln1DssDDsDDDSDthenmaxmax1ln1DDppSSp又又 2022-4-3125/164( )( )log1loglog(1)log(1) log11log(1)log(1)log(1)log(1)( )()( )

28、()iiiR DDpDDppppDDDDDDppppDDH pHH XHss max( )() 0DD0 DDH pHpR Dp所以計算得二元離散對稱信源的信息率失真函數-重要結論-課后的習題經常用到0011()()1P xappP xapp 00ijd 對應的率失真分布：1loglog(1)()01()101rDrH DDrR DDr 01(), ( |( ( |)1)(D xxp xQp xxxxDxr r元對稱信源X=x1,x2,xr,且信源為等概分布P(x)=1/r,失真度為漢明失真度，率失真函數為01231111( )4444XP x0,1,2,3Y 0111101111011110

29、D3log4log3()04()304DH DDDDR1loglog(1)()01()101rDrH DDrR DDr 利用已知公式2022-4-3130/1642022-4-3131/1642022-4-3132/1640,(,),0ijijijxyd xyxy 21myyyY ),(jiyxd用用一一個個非非負負的的函函數數2022-4-3133/164),()/()(),()(11jirisjijiXYyxdxyPxPyxdxyPD 2022-4-3134/164 );()(min)|(YXIDRDBxyP nimjjijijiBxyPypxypxypxpDRD11)|()()|(log

30、)|()()(min率失真函數可以寫成率失真函數可以寫成對于離散無記憶信道，對于離散無記憶信道，2022-4-3135/1642022-4-3136/1642022-4-3137/1642022-4-3138/1642022-4-3139/1642022-4-3140/1642022-4-3141/1642022-4-3142/1642022-4-3143/1642022-4-3144/1642022-4-3145/1642022-4-3146/1642022-4-3147/1642022-4-3148/1642022-4-3149/1642022-4-3150/1640,(,),0ijiji

31、jxyd xyxy 21myyyY ),(jiyxd用用一一個個非非負負的的函函數數2022-4-3151/164它為失真矩陣它為失真矩陣D，是，是 rs 階矩陣。階矩陣。2022-4-3152/1642)(),(jijiyxyxd 均均方方失失真真|),(jijiyxyxd 絕絕對對失失真真| / |),(ijijixyxyxd 相相對對失失真真0,(,)(,)1,ijijijxyd xyxy 漢漢明明失失真真其其它它2022-4-3153/164),(),(vudEvudEDji 2022-4-3154/164),()/()(),()(11jirisjijiXYyxdxyPxPyxdxyP

32、D 2022-4-3155/1642022-4-3156/164過傳輸后失真的大小。描述了某個信源符號通單個符號的失真度),(jiyxd統的失真情況。是從總體上描述整個系下的失真大小，源在某一試驗信道傳輸所以此值描述了某一信了統計平均，對信源與試驗信道進行平均失真度D2022-4-3157/164),()/()(),()(11jirisjijiXYyxdxyPxPyxdxyPD 2022-4-3158/1642022-4-3159/1642022-4-3160/1642022-4-3161/1642022-4-3162/164 );()(min)|(YXIDRDBxyP nimjjijijiB

33、xyPypxypxypxpDRD11)|()()|(log)|()()(min率失真函數可以寫成率失真函數可以寫成對于離散無記憶信道，對于離散無記憶信道，2022-4-3163/164DD 2022-4-3164/164);(max)(YXICixp);(min)()/(YXIDRDiiBxyp 2022-4-3165/1642022-4-3166/1642022-4-3167/1642022-4-3168/1642022-4-3169/1642022-4-3170/1642022-4-3171/1642022-4-3172/164允許平均失真度允許平均失真度D一定能達到一定能達到Dmin 0這個下界嗎？這個下界嗎？2022-4-3173/164),()(min1minjijniiyxdxpD 2022-4-3174/164信息傳輸率等于信源輸出的信息量信息傳輸率等于信源輸出的信息量)()0()(minXHRDR 2022-4-3175/164012111()333Xq X01112210DminDmin111110033236D 解：2022-4-3176/1642022-4-3177/1642022-4-3178/1642022-4-3179/1642022-4-3180/1642022-4-3181/164 123213321d202