1、第七章第七章 限失真信源編碼限失真信源編碼7.1 7.1 失真測度失真測度7.2 7.2 信息率失真函數(shù)信息率失真函數(shù) 7.3 7.3 信息率失真函數(shù)的計算信息率失真函數(shù)的計算 7.4 7.4 限失真信源編碼定理限失真信源編碼定理7.1.1 7.1.1 失真函數(shù)失真函數(shù))()()(2121rrxpxpxpxxxPX)()()(2121ssypypypyyyPYsjriyxdji, 2 , 1, 2 , 1, 0),(失真測度失真測度l對于每一對 ，指定一個非負(fù)的函數(shù)( ,)ijx y),(),(),(),(),(),(),(),(),(212221212111srrrssyxdyxdyxdyx

2、dyxdyxdyxdyxdyxdD失真矩陣 sr7.1.1 7.1.1 失真函數(shù)失真函數(shù)失真測度失真測度常用的失真函數(shù)有：（1） 漢明失真（2） 平方誤差失真函數(shù)失真函數(shù)是根據(jù)人們的實際需要和失真引起的損失、風(fēng)險大小等人為規(guī)定的。 jijijiyxyxyxd10),(2)(),(jijiyxyxd7.1.1 7.1.1 失真函數(shù)失真函數(shù)失真測度失真測度例7.1.1 設(shè)信道輸入 ，輸出 ，規(guī)定失真函數(shù) 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

3、失真函數(shù)失真函數(shù)失真測度失真測度NkjijijijijjjiiijikkNNNNyxdyxdyxdyxdyyyxxxdd1),(),(),(),(),(),(22112121yx符號序列的失真函數(shù)NXXX21XNYYY21YrxxxX,21syyyY,21Niiiixxx21xNjjjjyyy21y7.1.1 7.1.1 失真函數(shù)失真函數(shù)失真測度失真測度例7.1.2 假設(shè)信源輸出序列 ，其中每個隨機(jī)變量均取值于 。經(jīng)信道傳輸(編碼編碼）后的輸出為 ，其中每個隨機(jī)變量均取值于 。 定義失真函數(shù) d (0,0) =d (1,1) =0， d (0,1) =d (1,0) =1，求失真矩陣 D (N

4、 ）。 123X X XX0,1X 123YY YY0,1Y 7.1.1 7.1.1 失真函數(shù)失真函數(shù)失真測度失真測度0112122310212132120123122110322112230112213210212312120132212110)(ND7.1.1 7.1.1 失真函數(shù)失真函數(shù)失真測度失真測度(000,000)(0,0)(0,0)(0,0)0(000,001)(0,0)(0,0)(0,1)1dddddddd7.1.2 7.1.2 平均失真平均失真 ),()|()(),()(),(1111jiijrisjijirisjjijiyxdxypxpyxdyxpyxdED失真測度失真測度

5、7.1.2 7.1.2 平均失真平均失真 失真測度失真測度122,rXx xx1( ),1,2,22ip xirr12,rYy yy0( ,)1ijijd x yij011101110111111D100010001001001P211211( ) (|) ( ,)111(|) ( ,)222rrijiijijrrjiijijDp x p yx d x yp yx d x yrrr 例：7.1.2 7.1.2 平均失真平均失真 失真測度失真測度例：111236111362111632P012101210D012111()244XP X11( ) (|) ( ,)1 1111 1111 111(

6、012)(101)(210)2 2364 3624 63212rsijiijijDp x p yx d x y 7.2.1 D 允許信道 保真度準(zhǔn)則 DD NDND)(D失真允許信道 sjriDDxypBijD, 2 , 1;, 2 , 1: )|()(|):()1,2,;1,2,NND NjiBpD NNDirjsyx7.2 7.2 信息率失真函數(shù)信息率失真函數(shù)信息率失真函數(shù)信息率失真函數(shù)7.2.2 信息率失真函數(shù)的定義 );(min)()|(YXIDRDijBxyp()(|)()min( ;)jiD NNpBRDIy xX Y)()(DNRDRN當(dāng)信源為離散無記憶平穩(wěn)信源、信道為離散無記憶

7、平穩(wěn)信道時);();(YXNIIYX7.2 7.2 信息率失真函數(shù)信息率失真函數(shù)信息率失真函數(shù)信息率失真函數(shù));(max)(YXICixp是在信道固定前提下，選擇一種信源概率分布使信息傳輸率最大（求極大值）。它反映了信道傳輸信息的能力，是信道可靠傳輸?shù)淖畲笮畔鬏斅省Ｐ诺廊萘颗c信源無關(guān)，是反映信道特性的參量，不同的信道其信道容量不同。 7.2 7.2 信息率失真函數(shù)信息率失真函數(shù)信息率失真函數(shù)信息率失真函數(shù));(min)(: )|(YXIDRDDxypij是在信源固定，滿足保真度準(zhǔn)則的條件下的信息傳輸率的最小值。反映了滿足一定失真度的條件下信源可以壓縮的程度，也就是滿足失真要求而再現(xiàn)信源消息所

8、必須獲得的最少平均信息量。是信源特性的參量，一旦求到就與求極值過程中選擇的試驗信道無關(guān)，不同的信源率失真函數(shù)不同。 7.2 7.2 信息率失真函數(shù)信息率失真函數(shù)信息率失真函數(shù)信息率失真函數(shù) 這兩個概念適用范圍是不一樣。研究信道容量C 是為了解決在已知信道中盡可能多地傳送信息的問題，是為了充分利用已給定的信道，使傳輸?shù)男畔⒘孔畲蠖e誤概率任意小，以提高通信的可靠性，這是信道編碼的問題。 7.2 7.2 信息率失真函數(shù)信息率失真函數(shù)信息率失真函數(shù)信息率失真函數(shù)研究信息率失真函數(shù)是為了解決在已知信源和允許失真度條件下，使信源輸出的信息率盡可能小，也就是在允許一定失真度D 的條件下，使信源必須傳送給信

9、宿的信息量最少，盡可能用最少的碼符號來傳送信源信息，使信源的信息可以盡快地傳送出去，以提高通信的有效性，這是信源編碼問題。1.1. 的定義域的定義域 ()R D),(min)(),()|(min)(),()|()(minminjiijijjiijiijiijijiyxdxpyxdxypxpyxdxypxpD信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)11( ) (|) ( ,)rsijiijijDp x p yx d x ymaxmin0(; )()I X YH XDD例7.3：刪除信道 ，求 21012110DminD1.1. 的定義域的定義域 ()R D信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)

10、解：100010Pmin12( )min ( ,)() 0() 00iijjiDp xd x yp xp x l只有當(dāng)失真矩陣每一行至少只有當(dāng)失真矩陣每一行至少有一個零元素時有一個零元素時, , 信源的平均信源的平均失真度才能達(dá)到下限值失真度才能達(dá)到下限值0 ,0 ,l否則否則D Dmin 0 .min 0 .例： 求 21102DminD1.1. 的定義域的定義域 ()R D信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)解：0110Pmin121( )min ( ,)() 1() 0()iijjiDp xd x yp xp xp x 10102Dmin12() 0() 00Dp xp x (0)(

11、; )()(|)()RI X YH XH X YH X0110P011011101D100100010P1.1. 的定義域的定義域 信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)()R Dmin123() 0() 0() 00Dp xp xp x (0)(; )()(|)()RI X YH XH X YH X例7.4 設(shè)信源 ,313131210)(XPX 1 , 0Y01212110D，求minD1.1. 的定義域的定義域 信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)()R D解： 610312131031minD1)|(0)|(1)|()|(0)|(1)|(323122211211xypxypxyp

12、xypxypxypminmin(|)1()( )6min(; )()jiDp y xBR DRI X YH X1.1. 的定義域的定義域 信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)()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. 的定義域的定義域 信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)()R Dmaxmin0(; )()I X YH XDD例： 二元信源 , 計算

13、。6 . 04 . 0)(21xxXPXmaxD00D1.1. 的定義域的定義域 信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)()R D解： maxmin( ) ( ,)min(0.40,00.6 )0.4iijjiDp x d x y對于任意 和 有0112max,D DD)()1 ()()1 (2121DRDRDDR2. 2. 是關(guān)于是關(guān)于D D的下凸函數(shù)的下凸函數(shù) 信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)()R D201DDD10()()R DR D21DD 12()()R DR D3. 3. 在定義域內(nèi)是嚴(yán)格遞減函數(shù)在定義域內(nèi)是嚴(yán)格遞減函數(shù)信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)12()(

14、)R DR D()R D一、一、R(D)的性質(zhì)的性質(zhì) 1.下凸性下凸性(有最小值有最小值)；2.連續(xù)性；連續(xù)性；3.單調(diào)遞減性單調(diào)遞減性二、二、 R(D)的定義域的定義域0, Dmax 1. Dmin= 0 (對應(yīng)無失真情形對應(yīng)無失真情形)一般地一般地,僅當(dāng)失真矩陣每行均有零元素時僅當(dāng)失真矩陣每行均有零元素時, Dmin= 0 2. Dmax (1) Dmax對應(yīng)于對應(yīng)于R(D)的零點的零點 (2) 由于由于p(ai, bj)(PD)的不同，的不同， 使使R(D)|min= 0的的D值可能有多個，值可能有多個， 此時應(yīng)取最小一個此時應(yīng)取最小一個min1( )min ( ,)niijjiDp a

15、d a b4.4.小結(jié)小結(jié)0 D* Dmax DR(D)H(X)R(D*)例7.9 二元信源的信息率失真函數(shù)信源輸出符號集為（0，1），失真函數(shù)定義為漢明失真 ，求 。011,12XpPpp01,21ijijdi jij,7.3.2 二元信源和離散等概信源的 信息率失真函數(shù)的計算信息率失真函數(shù)的計算()R D()R D解： 且滿足該最小失真的試驗信道是一個無噪無損信道。 0minD1001Pmin()(0)()( )R DRH XH pmaxmin( ) ( ,)min(1, )iijjDp x d x yp pp1010Pmax()( )0R DR p信息率失真函數(shù)的計算信息率失真函數(shù)的計算

16、7.3.2 二元信源和離散等概信源的 ()R DpDDmax0 ( ,)() ( ,)(x0,y1)(x1,y0)ijijijijEDE d x yp x y d x yppP)|()()|()();(YXHpHYXHXHYXI(|)()( ) (根據(jù)Fano不等式)EH XYH PH D(; )( )()I X YH pH D當(dāng) 時，信息率失真函數(shù)的計算信息率失真函數(shù)的計算7.3.2 二元信源和離散等概信源的 ()R D選取一信道使DD l根據(jù)根據(jù)R(D)R(D)的定義的定義, ,滿足保真度的試驗信道的滿足保真度的試驗信道的I(X;Y) I(X;Y) 的最小值就是的最小值就是R(D).R(D

17、).為了證實這一點為了證實這一點, ,必須找到一個試必須找到一個試 驗信道驗信道. .使其平均失真度使其平均失真度DD,DD,而而I(X;Y)I(X;Y)達(dá)到這個最小達(dá)到這個最小值值, ,即即I(X;Y)=R(D)=H(p)-H(D).I(X;Y)=R(D)=H(p)-H(D).121()()1 21 21020()1jpDpDp yp yDDDpp y信息率失真函數(shù)的計算信息率失真函數(shù)的計算7.3.2 二元信源和離散等概信源的 ( ,)() ( ,)(1)()1 21 2ijijijijDE d x yp x y d x yDpDD pDDDD( )( ; )( )( | )( )( )R

18、DI X YH XH X YH pH D()R D121211xxyDDyDDQl 已知信源的概率分布已知信源的概率分布P(ai)和失真函數(shù)和失真函數(shù)d(ai,bj)，就可求得信源，就可求得信源的的R(D)函數(shù)。原則上它與信道容量一樣，即在有約束條件下求函數(shù)。原則上它與信道容量一樣，即在有約束條件下求極小值的問題。極小值的問題。 也就是適當(dāng)選取試驗信道也就是適當(dāng)選取試驗信道P(v/u)使平均互信息最小化，使平均互信息最小化，111(/)(,)()(/)log()(/)nmjiijinijijiiP baI X YP a P baP a P bal其約束條件為其約束條件為:(/)0jiP ba1

19、(/)1mjijP ba11( ) (/) ( ,)nmijiijijP a P ba d a bDl 對于等概、對稱失真的信源，存在一個與失真矩陣具有同樣對稱性的轉(zhuǎn)移概率分布達(dá)到率失真R(D)。l解：由 0,1X 0,1,2Y 01 01d求率失真函數(shù)R(D) 。由于信源等概分布，失真函數(shù)具有對稱性，因此，存在著與失真矩陣具有同樣對稱性的轉(zhuǎn)移概率分布達(dá)到率失真函數(shù)R(D) ，該轉(zhuǎn)移概率矩陣可寫為：(),1p y x由于 ，因此對于任何有限平均失真，必須 。于是轉(zhuǎn)移概率矩陣變?yōu)椋?0,1)(1,0)dd 0min( )min( , )0yxDp xd x ymaxmin( )( , )1yxD

20、p x d x y對應(yīng)此轉(zhuǎn)移概率矩陣的平均失真：因此 可求出此時的互信息為：01()01p y xa,( ) () ( , )1x yDp x p y x d x y 1D ()(; )( )(/)11(,(1,)22112loglog(1)log(1)log22(1)(1)log(1)(1)log(1)(1)1R DI X YH YH YXDDHDHD DDDDDDDDDDDDDDDD）l相應(yīng)的率失真函數(shù)R(D)如圖所示。)(DR10D1D1,.,Xn1,.,Yn11011110D =1111011nnnnnnminmax1( )min( , )0 min( )( , )yyxxDp xd x yDp x d x yn由于信源等概分布，失真函數(shù)具有對稱性，因此，存在由于信源等概分布，失真函數(shù)具有對稱性，因此，存在著與失真矩陣具有同樣對稱性的轉(zhuǎn)移概率分布達(dá)到率失著與失真矩陣具有同樣對稱性的轉(zhuǎn)移概率分布達(dá)到率失真真R(D)。該轉(zhuǎn)移概率矩陣可寫為。該轉(zhuǎn)移概率矩陣可寫為對應(yīng)此轉(zhuǎn)移概率矩陣的平均失真對應(yīng)此轉(zhuǎn)移概率矩陣的平均失真11 ( / ) 0111AAnAp y xAAAn ,1( ) () ( , )1x yADp x p y x d x yn因此因此A=1-(n-1)D。由此不難求出此時