信息論與編碼課件第四章

1、124.14.1 平均失真和信息率失真函數(shù)平均失真和信息率失真函數(shù)4.24.2 離散信源和連續(xù)信源的離散信源和連續(xù)信源的R(D)計(jì)算計(jì)算341、失真函數(shù)的定義 假如某一信源X,輸出樣值xi , xia1,a2,an,經(jīng)信道傳輸后變成yj , yj b1, b2,bm,如果: xi yj 沒(méi)有失真 xi yj 產(chǎn)生失真 失真函數(shù)的含義: 即失真函數(shù)d(xi,yj),此函數(shù)衡量用yj代替xi所引起的失真程度。即失真的大小。 失真函數(shù)定義為：jijijiyxyxyxd00),(52、失真矩陣 將所有的d(xi,yj)排列起來(lái),用矩陣表示為:),(),(),(),(1111mnnmbadbadbadb

2、add失真矩陣 例1：設(shè)信源符號(hào)序列為X=0,1,接收端收到符號(hào)序列為Y= 0,1,2,規(guī)定失真函數(shù)為 d(0,0)d(1,1)= 0 d(0,1)d(1,0)= 1 d(0,2)d(1,2)= 0.55 . 0015 . 010d失真矩陣62)(),(jijiyxyxd3、失真函數(shù)的形式：（常用的）|),(jijiyxyxd| / |),(ijijixyxyxd0,( ,)1,ijijxyd x y其他 均方失真: 絕對(duì)失真: 相對(duì)失真: 誤碼失真:適于連續(xù)信源適于離散信源74、漢明失真矩陣（也是一種誤碼失真）： 011101(,)110ijd xy 對(duì)于二元對(duì)稱信源X=0,1,Y=0,1,

3、漢明失真矩陣（二元誤碼失真）:0110d81、單符號(hào)離散信源的平均失真 xi和yj都是隨機(jī)變量,所以失真函數(shù)d(xi,yj)也是隨機(jī)變量,有限失真時(shí)的信源（總體）失真值只能用數(shù)學(xué)期望表示 將失真函數(shù)的數(shù)學(xué)期望稱為平均失真：( ,) ( ,)ijijijDp a b d a b 92、兩者的區(qū)別l 失真函數(shù)d(xi,yj)： 描述了某個(gè)信源符號(hào)通過(guò)傳輸后失真的大小l平均失真 ： 描述某個(gè)信源在某一試驗(yàn)信道傳輸下的失真大小,它對(duì)信源和信道進(jìn)行了統(tǒng)計(jì)平均,是從總體上描述整個(gè)系統(tǒng)的失真D103、L長(zhǎng)序列編碼 如果假定離散信源輸入符號(hào)序列XX1X2 Xl Xn,其中L長(zhǎng)符號(hào)序列xi =xi1xi2xiL

4、,經(jīng)信源編碼后,輸出符號(hào)序列Y=Y1Y2YlYm,其中L長(zhǎng)符號(hào)序列yj=yj1yj2yj L 失真函數(shù)定義為jjijiLLLyxdLyxd),(1),(111 (,)LLLLijljlDE d xyDLL 平均失真111、保真度準(zhǔn)測(cè) 若平均失真度 不大于我們所允許的失真,即DD 則稱此為保真度準(zhǔn)則 當(dāng)信源p(xi)給定,單個(gè)符號(hào)失真度d(xi,yj) 給定時(shí),選擇不同的試驗(yàn)信道p(yj|xi), 相當(dāng)于不同的編碼方法,其所得的平均失真度不同。122、D失真允許的實(shí)驗(yàn)信道 -滿足保真度準(zhǔn)則的試驗(yàn)信道。 滿足 條件的所有轉(zhuǎn)移概率分布pij ,構(gòu)成了一個(gè)信道集合DD |(DDabpPijD）： PD

5、： 所有D失真允許的試驗(yàn)信道組成的一個(gè)集合。133、信息率失真函數(shù)R(D)： 在限定失真為D的條件下，信源輸出的最小信息速率。 ),(min)(YXIDRDP 在信源給定后,我們希望在滿足一定失真的情況下,使信源必須傳輸給收信者的最小信息量。 若從接收端來(lái)著,就是在滿足保真度準(zhǔn)則下,尋找再現(xiàn)信源消息所必須獲得的最低平均信息量。即在滿足保真度準(zhǔn)則的條件下，接受端Y需要獲得發(fā)送端 X的最小信息量144、信息率失真函數(shù)的求法： PD是所有滿足保真度準(zhǔn)則的試驗(yàn)信道集合,因而可以在集合PD中尋找某一個(gè)信道pij,使I (X,Y)取極小值。 離散無(wú)記憶信源( )min ( )(| )min ( )( |)

6、(|)min( ) (|)log( )jiDjiDjiDpPpPjiijipPijjR DH XH X YH YH Y Xp bap a p b ap b15例2 已知編碼器輸入的概率分布為p(x)=0.5 ,0.5信道矩陣8 . 02 . 04 . 06 . 0ijp求互信息)|()()(ijijixypxpyxp11122122()0.3()0.2()0.1()0.4p x yp x yp x yp x y6 . 0)(4 . 0)(21ypyp( ; )( )(| )( )( |)0.125/I X YH XH X YH YH Y Xbit符號(hào)16 若編碼器輸入的概率分布不變?nèi)詾閜(x)

7、=0.5 ,0.5 但信道矩陣8 . 02 . 01 . 09 . 0ijp 求互信息符號(hào)/397. 0)()|(log)();(bitypyxpyxpYXIijijiji 可見(jiàn)當(dāng)p(x)一定時(shí),I (X,Y)隨信道矩陣p(yj|xi)而變。 因?yàn)閜(x)分布一定時(shí),信道受干擾不同所能傳遞的信息量是不同的。 當(dāng)p(x)一定時(shí),I (X,Y)是關(guān)于p(yj|xi)的下凸函數(shù)。 因此當(dāng)改變p(yj|xi)時(shí),I (X,Y)有一極小值。171、計(jì)算不同l 平均互信息I(X;Y)： 信源的概率分布p(xi)的上凸函數(shù)。 信道傳遞概率p(yj|xi)的下凸函數(shù)。);(max)(YXICixpl 信道容量

8、： l信息率失真函數(shù)： );(min)(YXIDRDP182、反映的事物不同 假定信道固定的前提下,選擇一種試驗(yàn)信源使信息傳輸率最大。 它所反映的是信道傳輸信息的能力,是信道可靠傳送的最大信息傳輸率。 一旦找到了信道容量,它就與信源不再有關(guān),而是信道特性的參量,隨信道特性的變化而變化 不同的信道其信道容量不同。19 假定信源給定的情況下,用戶可以容忍的失真度內(nèi)再現(xiàn)信源消息所必須獲得的最小平均信息量。 它反映的是信源可以壓縮的程度,是在滿足一定失真度要求下信源可壓縮的最低值。 一旦找到信息率失真函數(shù),就與選擇的試驗(yàn)信道不再有關(guān),而只是信源特性的參量 不同的信源其R(D)不同。203、目地不同：

9、充分利用已給信道,使傳輸?shù)男畔⒘孔畲?，以提高通信的正確性 解決在已知信源和允許失真度D的條件下,使信源必須傳送給信宿的信息率最小。即用盡可能少的碼符傳送盡可能多的信源消息,以提高通信的有效性。21 例1：設(shè)信源的符號(hào)表為A=al,a2,a2n,概率分布為p(ai)=1/2n,i=1,22n,失真函數(shù)規(guī)定為 jijiaadji10),( 信源熵 nnnnH2log)2121,21( 如果對(duì)信源進(jìn)行不失真編碼,平均每個(gè)符號(hào)至少需要log2n個(gè)二進(jìn)制碼元。 現(xiàn)在假定允許有一定失真,假設(shè)失真限度為D=1/2設(shè)想采用下面的編碼方案： a1a1， a2a2， anan an+1an ,an+2 an ,a

10、2n an 即不發(fā)生差錯(cuò)時(shí)失真為0,出錯(cuò)失真為1 研究在一定編碼條件下信息壓縮的程度。2221),()|()(ijjiijiaadaapapD 而信宿Y的概率分布為111 11( , )( )(,)log2log(1)22222nnI X YH YHnnnnnnn 由該信道模型圖4-3(P75)看出,它是一個(gè)無(wú)噪有損信道，且滿足保真準(zhǔn)則 ，噪聲熵H(Y|X)=0 )()|()(),(YHXYHYHYXI壓縮DDYa1a2anP1/2n1/2n(1+n)/2n23 1、R(D)的定義域 信息率失真函數(shù)的定義域問(wèn)題就是在信源和失真函數(shù)已知的情況下,允許平均失真度D的最小和最大取值問(wèn)題。 由于平均失

11、真度是非負(fù)實(shí)數(shù)d(xi,yj)的數(shù)學(xué)期望,因此也是非負(fù)的實(shí)數(shù),即 的下界是0。 允許平均失真度能否達(dá)到其下限值0,與單個(gè)符號(hào)的失真函數(shù)有關(guān)。DD, 0242、平均失真度的最小值 Dmin 信源的最小平均失真度：min11minmin( ,) ( ,) ( )min ( ,)nijijijiijjDp x y d x yXYDp xd x y若 和 相互獨(dú)立，則 只有當(dāng)失真矩陣的每一行至少有一個(gè)0元素時(shí), 信源的平均失真度才能達(dá)到下限值0。 當(dāng)Dmin = 0,即信源不允許任何失真時(shí),此時(shí)噪聲熵為0，信息率至少應(yīng)等于信源輸出的平均信息量信息熵。即 R(0) =H(X)253、 R(D)的值域 R

12、(D)的定義域?yàn)镈min，Dmax 。 通常Dmin = 0， R(Dmin) = R(0)=H(X) 當(dāng) DDmax時(shí), R(D) = 0 當(dāng) 0=Dmin DDmax時(shí), 0 R( Dmax) R(D) H(X), 因此： 0 R(D) H(X),26 Dmax：定義域的上限。 由于當(dāng) DDmax時(shí), R(D) = 0 因此Dmax是滿足R(D)=0時(shí) 所有的平均失真度中 的最小值。DDDR0)(maxmin 4、平均失真度的最大值 Dmax 275、平均失真度的最大值 Dmax的計(jì)算 由于R(D) = 0 時(shí)，I(X,Y) = 0，而I(X,Y) = 0的充要條件是X與Y統(tǒng)計(jì)獨(dú)立,即：(

13、,)( ) ()jiijp y xp x p ymax() 0()()min=min( ) () ( ,)min()( ) ( ,)jjijijR Dp yijjiijp yjiDDp x p y d x yp yp x d x y nijiimjyxdxpD12 , 1max),()(min28 例1:設(shè)輸入輸出符號(hào)表為X=Y=0,1,輸入概率分布p(x)=1/3,2/3,失真矩陣 0110d 求： Dmin 和Dmax max1,211212min( ) ( ,)min(01,10)33332 11min( , )3 33niijjjijDp x d x y 失真矩陣的每一行至少有一個(gè)0元

14、素時(shí), Dmin=029 例2:設(shè)輸入輸出符號(hào)表為X=Y=0,1,輸入概率分布p(x)=1/3,2/3,失真矩陣 1212/ 1d 求： Dmin 和Dmax 1) 1 ,23(min) 132131, 2322131(minmin212, 1maxjjijiijdpD651322131),(min)(1minnijijiyxdxpD30 1、R(D)是非負(fù)的實(shí)數(shù), R(D)0。 其定義域?yàn)?Dmax , 其值為0H(X)。 當(dāng)DDmax時(shí),R(D)0 2、R(D)是關(guān)于D的下凸函數(shù) R(D)在定義域內(nèi)是失真度D的U型下凸函數(shù) 3、R(D)的單調(diào)遞減性及連續(xù)性 容許的失真度越大，所要求的信息率

15、越小。反之亦然。31 Step1:給定信源概率pi和失真函數(shù)dij,就可以求得該信源的R(D)的函數(shù)表達(dá)式。 Step2: 求R(D)函數(shù)滿足保真度準(zhǔn)則下極小值的問(wèn)題。 但要得到它的顯式表達(dá)式,一般比較困難通常用參量表達(dá)式。 即使如此,除簡(jiǎn)單的情況外實(shí)際計(jì)算還是困難的,只能用迭代逐級(jí)逼近的方法。 32 設(shè)二元對(duì)稱信源X=0,1,其概率分布p(x)=p,1-p,接收變量Y=0,1,漢明失真矩陣0110d 因而最小允許失真度Dmin=0。 并能找到滿足該最小失真的試驗(yàn)信道,且是一個(gè)無(wú)噪無(wú)損信道,其信道矩陣為1001p33 計(jì)算得：R(0)=I(X;Y)=H(X) 最大允許失真度為pppdpdpdp

16、dpdpDjijiij),1(min)1 , 1 () 1 () 1 , 0()0(),0 , 1 () 1 ()0 , 0()0(minmin101 , 0max 要達(dá)到最大允許失真度的試驗(yàn)信道,唯一確定為1010p34 這個(gè)試驗(yàn)信道能正確傳送信源符號(hào)x=1,而傳送信源符號(hào)x=0時(shí),接收符號(hào)一定為y=1 凡發(fā)送符號(hào)x=0時(shí),一定都錯(cuò)了。而x=0出現(xiàn)的概率為p,所以信道的平均失真度為p 。 在這種試驗(yàn)信道條件下，可計(jì)算得 R(Dmax) = R(p) = 035 失真函數(shù)，失真函數(shù)矩陣 平均失真 -單符號(hào)離散信源平均失真 jijijiyxyxyxd00),(),(),(),(),(1111mnnmbadbadbadbadd( ,) ( ,)ijijijDp a b d a b 36jjijiLLL