《信息論與編碼(第二版)》第4章

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

2、dd失真矩陣 例：設(shè)信源符號序列為X=0,1,接收端收到符號序列為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)(),(jijiyxyxd 失真函數(shù)形式可以根據(jù)需要任意選取,最常用的有:|),(jijiyxyxd| / |),(ijijixyxyxd其他, 1, 0)(),(jijijiyxyxyxd 均方失真: 絕對失真: 相對失真: 誤碼失真:適于連續(xù)信源適于離散信源7 漢明失真矩陣 011101110d 對于二元對稱信源(m=n),X=0,1,Y=0,1,漢明

3、失真矩陣:0110d8 xi和yj都是隨機變量,所以失真函數(shù)d(xi,yj)也是隨機變量,限失真時的失真值只能用數(shù)學(xué)期望表示 將失真函數(shù)的數(shù)學(xué)期望稱為平均失真：jjiijiibadabpapD),()|()( 失真函數(shù)d(xi,yj)： 描述了某個信源符號通過傳輸后失真的大小 平均失真 ： 描述某個信源在某一試驗信道傳輸下的失真大小,它對信源和信道進(jìn)行了統(tǒng)計平均,是從總體上描述整個系統(tǒng)的失真D9 如果假定離散信源輸出符號序列XX1X2 Xl Xn,其中L長符號序列xi =xi1xi2xiL,經(jīng)信源編碼后,輸出符號序列Y=Y1Y2YlYm,其中L長符號序列yj=yj1yj2yjN ,則失真函數(shù)定

4、義為jjijiLLLyxdLyxd),(1),(LllLDLD11 平均失真10 無論是無噪信道還是有噪信道: RC 總能找到一種編碼使在信道上能以任意小的錯誤概率,以任意接近C的傳輸率來傳送信息 RC 就必須對信源壓縮,使其壓縮后信息傳輸率R小于信道容量C,但同時要保證壓縮所引入的失真不超過預(yù)先規(guī)定的限度。 信息壓縮問題就是對于給定的信源,在滿足平均失真 的前提下,使信息率盡可能小。 DD 11 若平均失真度 不大于我們所允許的失真,即DDD 則稱此為保真度準(zhǔn)則 當(dāng)信源p(xi)給定,單個符號失真度d(xi,yj) 給定時,選擇不同的試驗信道p(yj|xi), 相當(dāng)于不同的編碼方法,其所得的

5、平均失真度不同。 試驗信道DDDD滿足保真度準(zhǔn)則12 滿足 條件的所有轉(zhuǎn)移概率分布pij ,構(gòu)成了一個信道集合DD |(DDabpPijD）： D失真允許的試驗信道： 滿足保真度準(zhǔn)則的試驗信道。 PD： 所有D失真允許的試驗信道組成的一個集合。13 R(D)： 在限定失真為D的條件下信源輸出的最小信息速率。 ),(min)(YXIDRDP 在信源給定后,我們希望在滿足一定失真的情況下,使信源必須傳輸給收信者的信息傳輸率R盡可能地小。 若從接收端來著,就是在滿足保真度準(zhǔn)則下,尋找再現(xiàn)信源消息所必須獲得的最低平均信息量。即在滿足保真度準(zhǔn)則的條件下尋找平均互信息I(X,Y)的最小值。14 PD是所有

6、滿足保真度準(zhǔn)則的試驗信道集合,因而可以在集合PD中尋找某一個信道pij,使I (X,Y)取極小值。 離散無記憶信源ijjijijiPpbpabpabpapDRDji)()|(log)|()(min)(15 例已知編碼器輸入的概率分布為p(x)=0.5 ,0.5 信道矩陣8 . 02 . 04 . 06 . 0ijp 求互信息)|()()(ijijixypxpyxp4 . 0)(1 . 0)(2 . 0)(3 . 0)(22122121yxpyxpyxpyxp6 . 0)(4 . 0)(21ypyp32)(41)|(31)|(43)|(22122121yxpyxpyxpyxp符號/125. 0)

7、()|(log)();(bitypyxpyxpYXIijijiji16 編碼器輸入的概率分布為p(x)=0.5 ,0.5 信道矩陣8 . 02 . 01 . 09 . 0ijp 求互信息符號/397. 0)()|(log)();(bitypyxpyxpYXIijijiji 可見當(dāng)p(x)一定時,I (X,Y)隨p(yj|xi)而變。 因為p(x)分布一定時,信道受干擾不同所能傳遞的信息量是不同的。 當(dāng)p(x)一定時,I (X,Y)是關(guān)于p(yj|xi)的下凸函數(shù)。 因此當(dāng)改變p(yj|xi)時,I (X,Y)有一極小值。17 平均互信息I(X;Y)： 信源的概率分布p(xi)的上凸函數(shù)。 信道

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

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

10、1a1， a2a2， anan an+1an ,an+2 an ,a2n an 即不發(fā)生差錯時失真為0,出錯失真為1 研究在一定編碼條件下信息壓縮的程度。22 平均失真 21),()|()(ijjiijiaadaapapD 則輸出熵H(Y) 1log(212log)21,2121,21()(nnnnnnnnnHYH 由該信道模型圖4-3看出,它是一個確定信道 pij=1(或0)，H(Y|X)=0 )()|()(),(YHXYHYHYXI壓縮23 1、R(D)的定義域 率失真的定義域問題就是在信源和失真函數(shù)已知的情況下,討論允許平均失真度D的最小和最大取值問題。 由于平均失真度是非負(fù)實數(shù)d(xi

11、,yj)的數(shù)學(xué)期望,因此也是非負(fù)的實數(shù),即 的下界是0。 允許平均失真度能否達(dá)到其下限值0,與單個符號的失真函數(shù)有關(guān)。DD, 024 Dmin 和R(Dmin) 信源的最小平均失真度：nijijiyxdxpD1min),(min)( 只有當(dāng)失真矩陣的每一行至少有一個0元素時,信源的平均失真度才能達(dá)到下限值0。 當(dāng)Dmin = 0,即信源不允許任何失真時,信息率至少應(yīng)等于信源輸出的平均信息量信息熵。即 R(0) =H(X)25 因為實際信道總是有干擾的,其容量有限,要無失真地傳送連續(xù)信息是不可能的。 當(dāng)允許有一定失真時,R(D)將為有限值,傳送才是可能的。 對于連續(xù)信源：)(lim)(0minD

12、RDRD26 R(D)的定義域為Dmin，Dmax 。 通常Dmin = 0， R(Dmin) = H(X) 當(dāng) DDmax時, R(D) = 0 當(dāng) 0 DDmax時, 0R(D) H(X)27 Dmax：定義域的上限。 Dmax是滿足R(D)=0時所有的平均失真度中的最小值。DDDR0)(maxmin 由于I(X,Y)是非負(fù)函數(shù),而R(D)是在約束條件下的I(X,Y)的最小值,所以R(D)也是一個非負(fù)函數(shù),它的下限值是零。 R(D)028 由于I(X,Y) = 0的充要條件是X與Y統(tǒng)計獨立,即：)()|(jijypxypjijiijypjjijiiypyxdxpypyxdypxpDjj),

13、()()(min),()()(min)()(maxnijiimjyxdxpD12 , 1max),()(min29 例4-3:設(shè)輸入輸出符號表為X=Y=0,1,輸入概率分布p(x)=1/3,2/3,失真矩陣 0110d 求： Dmin 和Dmax 31)31,32(min) 032131, 132031(minmin212 , 1maxjjijiijdpD 失真矩陣的每一行至少有一個0元素時, Dmin=030 例:設(shè)輸入輸出符號表為X=Y=0,1,輸入概率分布p(x)=1/3,2/3,失真矩陣 1212/ 1d 求： Dmin 和Dmax 1) 1 ,23(min) 132131, 2322

14、131(minmin212, 1maxjjijiijdpD651322131),(min)(1minnijijiyxdxpD31 1、R(D)是非負(fù)的實數(shù), R(D)0。 其定義域為0Dmax , 其值為0H(X)。 當(dāng)DDmax時,R(D)0 2、R(D)是關(guān)于D的下凸函數(shù) R(D)在定義域內(nèi)是失真度D的U型下凸函數(shù) 3、R(D)的單調(diào)遞減性及連續(xù)性 容許的失真度越大，所要求的信息率越小。反之亦然。3233 給定信源概率pi和失真函數(shù)dij,就可以求得該信源的R(D)函數(shù)。 它是在保真度準(zhǔn)則下求極小值的問題。 但要得到它的顯式表達(dá)式,一般比較困難通常用參量表達(dá)式。 即使如此,除簡單的情況外實際計算還是困難的,只能用迭代逐級逼近的方法。 34 設(shè)二元對稱信源X=0,1,其概率分布p(x)=p,1-p,接收變量Y=0,1,漢明失真矩陣0110d 因而最小允許失真度Dmin=0。 并能找到滿足該最小失真的試驗信道,且是一個無噪無損信道,其信道矩陣為1001p35 計算得：R(0)=I(X;Y)=H(p) 最大允許失真度為pppdpdpdpdpdpDjijiij