信息論與編碼-第4章

1、第4章 信息率失真函數(shù)l本章主要討論在信源允許一定失真情況下所需 的最少信息率； 從分析失真函數(shù)、平均失真出發(fā)，求出信息率失真函數(shù) R(D) l4.1 平均失真和信息率失真函數(shù)l4.2 離散信源和連續(xù)信源的 R(D) 計算4.1 平均失真和信息率失真函數(shù)l在實際問題中，信號有一定的失真是可以容忍的;l但是當(dāng)失真大于某一限度后，信息質(zhì)量將被嚴(yán)重?fù)p傷，甚至喪失其實用價值;l要規(guī)定失真限度，必須先有一個定量的失真測度;l為此可引入失真函數(shù)4.1.1 失真函數(shù)l假如某一信源 X，輸出樣值為 xi，xia1,an，經(jīng)過有失真的信源編碼器，輸出 Y，樣值為 yj，yj b1,bml如果xiyj，則認(rèn)為沒有

2、失真；如果 xiyj，那么就產(chǎn)生了失真l失真的大小，用一個非負(fù)量來表示，即失真函數(shù) d(xi,yj)，以衡量用 yj 代替 xi 所引起的失真程度l一般失真函數(shù)定義式為jijijiyxyx),yd(x004.1.1 失真函數(shù)l失真矩陣 單個符號的失真函數(shù)的全體排列起來構(gòu)成的矩陣，稱為失真矩陣注意：失真函數(shù)d(xi,yj)的數(shù)值是依據(jù)實際情況,用yj代替xi 所導(dǎo)致的失真大小是人為決定的111212122212( , )( , )( ,)( , )( , )( ,)( , )( , )( ,)mmnnnmd a bd a bd a bd a bd a bd a bd a bd a bd a bd

3、均方失真：ijijixyxyxd/),(2),(jijiyxyxdjijiyxyxd),(其它，1, 0),(),(jijijiyxyxyxd相對失真：誤碼失真：絕對失真：前三種失真函數(shù)適用于連續(xù)信源，后一種適用于離散信源 l最常用的失真函數(shù) 4.1.1 失真函數(shù)失真函數(shù)的定義可以推廣到序列編碼情況如果假定離散信源輸出符號序列X=(X1X2XlXL)，其中L長符號序列樣值xi(xi1xi2xilxiL)，經(jīng)信源編碼后，輸出符號序列Y=(Y 1Y 2Y lY L)，其中L長符號序列樣值yj(yj1yj2yjlyjL)，則序列失真函數(shù)定義為： 其中d(xil，yjl)是信源輸出L長符號樣值xi中的

4、第l個符號xil時，編碼輸出L長符號樣值yj中的第l個符號yjl的失真函數(shù)。 11( ,)(,)LLijiljlldd x yLx y4.1.1 失真函數(shù)4.1.2 平均失真 由于xi和yj都是隨機(jī)變量，所以失真函數(shù)d(xi,yj)也是隨機(jī)變量，考察整個信源有失真編碼狀況，需要用它的數(shù)學(xué)期望或統(tǒng)計平均值，因此將失真函數(shù)的數(shù)學(xué)期望稱為平均失真，記為 1111() (,)()(/) (,)nmijijijnmijiijijDp a bd a bp ap ba d a b符號轉(zhuǎn)移概率分布ixjyjip y x信源編碼器 對于連續(xù)隨機(jī)變量同樣可以定義平均失真,( , ) ( , )X YDpx y d

5、 x y dxdy LllLljlilLDLyxdELD111),(1對于L長序列編碼情況，平均失真為4.1.2 平均失真 其中pX,Y(x,y)是連續(xù)隨機(jī)變量的聯(lián)合概率密度其中 是第l個符號的平均失真lD4.1.3 信息率失真函數(shù)R(D)12,nXa aa信源編碼器12,nYb bbXY假想信道信源X經(jīng)過有失真的信源編碼器將信源編碼器輸出Y，將這樣的編碼器看作存在干擾的假想信道4.1.3 信息率失真函數(shù)R(D)l信源編碼器的目的：使編碼后所需的信息傳輸率 R 盡量小；l然而R越小，引起的平均失真就越大；l信息率 R 就是所需輸出的有關(guān)信源 X 的信息量；l對應(yīng)到假想信道，即為接收端 Y 需要

6、獲得的有關(guān) X 的信息量，也就是互信息 I(X;Y)；l這樣，選擇信源編碼方法的問題就變成了選擇假想信道的問題，符號轉(zhuǎn)移概率 p(yj/xi) 就對應(yīng)信道轉(zhuǎn)移概率DDl給出一個失真的限制值 D，在滿足平均失真 （保真度準(zhǔn)則）的條件下，選擇一種編碼方法使信息率 R 盡可能??；4.1.3 信息率失真函數(shù)R(D)mjniDDabpPijD, 2 , 1;, 2 , 1:)/(D允許試驗信道此信道集合稱為D允許試驗信道平均失真由信源分布 p(xi)、假想信道的轉(zhuǎn)移概率 p(yj/xi)和失真函數(shù) d(xi,yj) 決定，若 p(xi) 和 d(xi,yj) 已定，則可給出滿足 條件的所有轉(zhuǎn)移概率分布

7、pij，它們構(gòu)成了一個信道集合PDDD4.1.3 信息率失真函數(shù)R(D)由于互信息取決于信源分布和信道轉(zhuǎn)移概率分布，根據(jù) 2-2 節(jié)所述，當(dāng) p(xi) 一定時，互信息 I(X;Y) 是關(guān)于 p(yj/xi) 的 U 型凸函數(shù)，存在極小值。因而在上述允許信道 PD 中，可以尋找一種信道 pij，使給定的信源 p(xi) 經(jīng)過此信道傳輸后，互信息 I(X;Y) 達(dá)到最小。該最小的互信息就稱為信息率失真函數(shù) R(D)，即 信息率失真函數(shù) R(D)的物理意義：對于給定信源，在平均失真不超過失真限度D的條件下，信息率容許減小到（壓縮）的最小值 R(D);(min)(YXIDRDP信息率失真函數(shù)R(D)

8、4.1.3 信息率失真函數(shù)R(D) p(ai)，i1，2，n 是信源符號概率分布； p(bj/ai)，i1，2，n，j1，2，m 是轉(zhuǎn)移概率分布； p(bj)，j1，2，m 是接收端收到符號概率分布。 nimjjijijiPPbpabpabpapDRDij11)()/(log)/()(min)( 對于離散無記憶信源，R(D)函數(shù)可寫成 例4.1 (p.74) 設(shè)信源的符號表為Aa1，a2，a2n，概率分布為p(ai)1/2n，i1，2，2n，失真函數(shù)規(guī)定為 即符號不發(fā)生差錯時失真為0，一旦出錯，失真為1，試研究在一定編碼條件下信息壓縮的程度jijiaadji01),(4.1.3 信息率失真函數(shù)

9、R(D)4.1.3 信息率失真函數(shù)R(D)解：信源熵 設(shè)失真限度 D=1/2 等效試驗信道為一個確定信道 則 信道輸出概率分布為 則輸出熵為11,log2 bit/22Hnnn符號1 0 0ijpH Y X或， ;I X YH YH Y XH Y12111, 22nnnppppnn 111 11,log2log12222nnnH YHnnnnnn 個12DD平均失真應(yīng)為4.1.4 信息率失真函數(shù)的性質(zhì)1.R(D)函數(shù)的定義域函數(shù)的定義域 Dmin和 R(Dmin) Dmin0 對于離散信源 對于連續(xù)信源 )() 0 ()(minXHRDR )()0()(minxHRDRc (2) Dmax和

10、R(Dmax)niijimjdpD1, 2, 1maxmin選擇所有滿足R(D)0中D的最小值，定義為R(D)定義域的上限D(zhuǎn)max，即DDDR0)(maxmin因此可以得到R(D)的定義域為max,0 DD 4.1.4 信息率失真函數(shù)的性質(zhì)Dmax是怎樣來計算R(D)0就是I(X;Y)0，這時試驗信道輸入與輸出是互相獨(dú)立的，所以條件概率 p(yj/xi) 與xi 無關(guān)。即jjijijpypxypp)()/(4.1.4 信息率失真函數(shù)的性質(zhì)mjniijijdppD11maxmin nimjijjidppD11此時平均失真為4.1.4 信息率失真函數(shù)的性質(zhì)的D中的最小值，即11mjjp求出滿足條件

11、從上式觀察可得：在 j=1,2,m 中，可找到 值最小的 j，當(dāng)該 j 對應(yīng)的 pj1，而其余 pj 為零時，上式右邊達(dá)到最小，這時上式可簡化成niijidp1niijimjdpD1, 2 , 1maxmin例4.2 (p.76) 設(shè)輸入輸出符號表為 XY0，1，輸入概率分布p(x)=1/3，2/3，失真矩陣為分析R(D)定義域兩端的狀態(tài)11122122( , )( ,)01(, )(,)10d a bd a bd a bd a bd4.1.4 信息率失真函數(shù)的性質(zhì)解：當(dāng)Dmin0時，R(Dmin)H(X)H(1/3，2/3)0.91比特/符號，這時信源編碼器無失真，所以該編碼器的轉(zhuǎn)移概率為

12、1001P4.1.4 信息率失真函數(shù)的性質(zhì)1,21212min01,103333j 當(dāng)R(Dmax)0時 此時輸出符號概率 p(b1)0，p(b2)1， 所以這時的編碼器的轉(zhuǎn)移概率為 2221,baba0101P4.1.4 信息率失真函數(shù)的性質(zhì)2max1,21miniijjiDp d1112211122221,2min,jp dp dp dp d1,22 11min,3 33j2、R(D)函數(shù)的下凸性和連續(xù)性函數(shù)的下凸性和連續(xù)性 下凸性： 連續(xù)性：3、R(D)函數(shù)的單調(diào)遞減性函數(shù)的單調(diào)遞減性 物理意義：容許的失真度越大，所要求的信息率越小。反之亦然。4.1.4 信息率失真函數(shù)的性質(zhì) 1 01;

13、 1R DR DR DDDD其中0lim R DR DDD其中 DDR DR D若則綜上所述，可以得出如下結(jié)論：R(D)是非負(fù)的實數(shù)，即 R(D)0。其定義域為0Dmax，其值為0H(X)。當(dāng) DDmax 時， R(D) 0。R(D) 是關(guān)于D的下凸函數(shù)，因而也是關(guān)于D的連續(xù)函數(shù)。R(D)是關(guān)于D的嚴(yán)格單調(diào)遞減函數(shù)。4.1.4 信息率失真函數(shù)的性質(zhì)由以上三點(diǎn)結(jié)論，對一般R(D)曲線的形態(tài)可以畫出來： 4.1.4 信息率失真函數(shù)的性質(zhì)R(D)H(X)R(D) 0 D Dmax DR(D) 0 Dmax D 信息率失真曲線(a) 離散系統(tǒng)(b) 連續(xù)系統(tǒng)4.1.5 信息率失真函數(shù)與信道容量的比較信

14、道容量信道容量C率失真函數(shù)率失真函數(shù)R(D)研究對象信道信源給定條件信道轉(zhuǎn)移概率p(y/x)信源概率分布p(xi)選擇參數(shù)信源概率分布p(xi)信源編碼器映射關(guān)系p(y/x)結(jié)論噪聲干擾消失的信息量H(X/Y)信源壓縮損失的信息量H(X/Y)()max (; )ip aCI X Y()min (; )DPR DI X Y(; )()(/)I X YH XH X Y表4-1 R(D)與C的比較 信道容量表示信道的最大傳輸能力，反映信道的特性，與信源無關(guān)，以信源中能使平均互信息達(dá)到最大的信源為參考；信息率失真函數(shù)表示保真度條件下信源的信息率可被壓縮的最低限度，反映信源本身的特性，與信道無關(guān)，以編碼

15、器中能使平均互信息達(dá)到最小的信道為參考； 計算R(D)的顯式表達(dá)式一般是很困難的 某些特殊情況下 R(D) 的表示式為：DDRlog)(4.2 離散信源和連續(xù)信源的R(D)計算22221)(xexp（1）當(dāng)d(x,y)=(x-y)2， 時，(2)當(dāng)d(x,y)=|x-y|， 時，xexp2)(DDR1log)(3)當(dāng)d(x,y)=(x,y)，p(x=0)=p，p(x=1)=1-p時， 4.2 離散信源和連續(xù)信源的R(D)計算()( )() R DH pH D4.2 離散信源和連續(xù)信源的R(D)計算 0 Dmax D R(D) H(3)(1)(2)圖4-5 信息率失真函數(shù)R(D)這些 R(D)

16、可畫成三條曲線l對于R(D)函數(shù)，只在有限情況下，能夠得到它的解析表達(dá)式l更多的情況，只能通過計算機(jī)計算它的數(shù)值解l這種方法通常稱為參量表達(dá)式法l田寶玉等編著的信息論基礎(chǔ)習(xí)題解答（人民郵電出版社2010年版）一書中的192-193頁有一個例子的Matlab程序和迭代流程圖，以及解析解與數(shù)值解的對照曲線，結(jié)果是非常吻合的4.2 離散信源和連續(xù)信源的R(D)計算求信息率失真函數(shù)R(D)。解：（略）11122122( ,)( ,)01(,)(,)10d a bd a bd a bd a bd例4.3 (p.81)設(shè)輸入輸出符號表為XY0，1，輸入概率分布p(x)=(p，1-p)，0Dmax 時， R

17、(D) 0lR(D) 是關(guān)于D的下凸函數(shù)，也是關(guān)于D的連續(xù)函數(shù)lR(D)是關(guān)于D的嚴(yán)格單調(diào)遞減函數(shù)第第4章章 復(fù)習(xí)復(fù)習(xí)R(D)H(X)R(D) 0 D Dmax DR(D) 0 Dmax D 信息率失真曲線(a) 離散系統(tǒng)(b) 連續(xù)系統(tǒng)第第4章章 復(fù)習(xí)復(fù)習(xí)信道容量信道容量C率失真函數(shù)率失真函數(shù)R(D)研究對象信道信源給定條件信道轉(zhuǎn)移概率p(y/x)信源概率分布p(xi)選擇參數(shù)信源概率分布p(xi)信源編碼器映射關(guān)系p(y/x)結(jié)論噪聲干擾消失的信息量H(X/Y)信源壓縮損失的信息量H(X/Y)()max (; )ip aCI X Y( )min (; )DPR DI X Y(; )()(/

18、)I X YH XH X Y信道容量C 與率失真函數(shù)R(D)的比較 l對于R(D)函數(shù)，只在有限情況下，能夠得到它的解析表達(dá)式l更多的情況，只能通過計算機(jī)計算它的數(shù)值解 例4.1 (p.74) 設(shè)信源的符號表為Aa1，a2，a2n，概率分布為p(ai)1/2n，i1，2，2n，失真函數(shù)規(guī)定為 即符號不發(fā)生差錯時失真為0，一旦出錯，失真為1，試研究在一定編碼條件下信息壓縮的程度jijiaadji01),(4.1.3 信息率失真函數(shù)R(D)4.1.3 信息率失真函數(shù)R(D)解：信源熵 設(shè)失真限度 D=1/2 等效試驗信道為一個確定信道 則 信道輸出概率分布為 則輸出熵為11,log2 bit/22

19、Hnnn符號1 0 0ijpH Y X或， ;I X YH YH Y XH Y12111, 22nnnppppnn 111 11,log2log12222nnnH YHnnnnnn 個12DD平均失真應(yīng)為015.2 無失真信源編碼無失真信源編碼01例5.5 (p.96) 對例5.3中的信源進(jìn)行哈夫曼編碼 0.610.390.200.190.180.170.150.110.260.200.190.180.170.350.260.200.190.390.350.261.00.200.190.180.170.150.100.01a1a2a3a4a5a6a701010101信源ai概率p(ai)碼字Wi碼長Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114平均碼長 碼元/符號 72. 2)(71iiiKapK信息效率bit/符號96. 072. 261. 2)(KXHR5.2 無失真信源編碼無失真信源編碼可見，Huffman碼的平均碼長最小，R最大、編碼效率最高值得注意：哈夫曼編碼方法得到的碼并非唯一的