信息論與編碼 第4章

1、信息率失真函數(shù)信息率失真函數(shù) 第第4 4章章24.14.1 平均失真和平均失真和信息率失真函數(shù)信息率失真函數(shù)4.24.2 離散信源和連續(xù)信源的離散信源和連續(xù)信源的R(D)計(jì)算計(jì)算內(nèi)內(nèi) 容容34.14.1 平均失真和平均失真和 信息率失真函數(shù)信息率失真函數(shù)44.1.1 4.1.1 失真函數(shù)失真函數(shù) n假如某一信源假如某一信源X,輸出樣值輸出樣值xi , xia1,a2,an,經(jīng)過(guò)有失真的經(jīng)過(guò)有失真的信源編碼器輸出后變成信源編碼器輸出后變成yj , yj b1, b2,bm,如果如果: xi yj 沒有失真沒有失真 xi yj 產(chǎn)生失真產(chǎn)生失真n失真的大小失真的大小,用一個(gè)量來(lái)表示用一個(gè)量來(lái)表示,

2、即失真函數(shù)即失真函數(shù)d(xi,yj),以衡量用以衡量用yj代替代替xi所引起的失真程度。所引起的失真程度。n失真函數(shù)定義為：失真函數(shù)定義為：jijijiyxyxyxd00),(5失真函數(shù)失真函數(shù)n將所有的將所有的d(xi,yj)排列起來(lái)排列起來(lái),用矩陣表示為用矩陣表示為:),(),(),(),(1111mnnmbadbadbadbadd失真矩陣n例：設(shè)信源符號(hào)序列為例：設(shè)信源符號(hào)序列為X=0,1,接收端收到符號(hào)序接收端收到符號(hào)序列為列為Y= 0,1,2,規(guī)定失真函數(shù)為規(guī)定失真函數(shù)為 d(0,0)d(1,1)= 0 d(0,1)d(1,0)= 1 d(0,2)d(1,2)= 0.55 . 001

3、5 . 010d失真矩陣62)(),(jijiyxyxdn失真函數(shù)形式可以根據(jù)需要任意選取失真函數(shù)形式可以根據(jù)需要任意選取,最常用的最常用的有有:|),(jijiyxyxd| / |),(ijijixyxyxd其他, 1, 0)(),(jijijiyxyxyxdn均方均方失真失真:n絕對(duì)絕對(duì)失真失真:n相對(duì)相對(duì)失真失真:n誤碼誤碼失真失真:適于連續(xù)信源適于離散信源失真函數(shù)失真函數(shù)7n漢明失真矩陣漢明失真矩陣 011101110dn對(duì)于二元對(duì)稱信源對(duì)于二元對(duì)稱信源(m=n),X=0,1,Y=0,1,漢明失真漢明失真矩陣矩陣:0110d8 失真函數(shù)的定義可推廣到序列編碼情況，如果假定失真函數(shù)的定義

4、可推廣到序列編碼情況，如果假定離散信源輸出符號(hào)序列離散信源輸出符號(hào)序列 ，其中，其中L長(zhǎng)符號(hào)長(zhǎng)符號(hào)序列樣值序列樣值 ，經(jīng)信源編碼后，輸出符號(hào)，經(jīng)信源編碼后，輸出符號(hào)序 列序 列 ， 其 中， 其 中 L 長(zhǎng) 符 號(hào) 序 列 樣長(zhǎng) 符 號(hào) 序 列 樣值值 ，則失真函數(shù)定義為：，則失真函數(shù)定義為： 12(,)LXXXX 其中其中d(xil，yjl)是信源輸出是信源輸出L長(zhǎng)符號(hào)樣值長(zhǎng)符號(hào)樣值 中的第中的第l個(gè)個(gè)符號(hào)符號(hào)xil時(shí)，編碼輸出時(shí)，編碼輸出L長(zhǎng)符號(hào)樣值長(zhǎng)符號(hào)樣值 中的第中的第l個(gè)符號(hào)個(gè)符號(hào)yjl的失真函數(shù)。的失真函數(shù)。 11( ,)(,)LLijiljlldd xyLx y 12( ,)LY

5、Y YY 12(,)jjjjLyyyy12(,)iiiiLxxxx ixiy 94.1.2 4.1.2 平均失真平均失真 nxi和和yj都是隨機(jī)變量都是隨機(jī)變量,所以失真函數(shù)所以失真函數(shù)d(xi,yj)也是隨機(jī)也是隨機(jī)變量變量,限失真時(shí)的失真值只能用數(shù)學(xué)期望表示限失真時(shí)的失真值只能用數(shù)學(xué)期望表示n將失真函數(shù)的數(shù)學(xué)期望稱為將失真函數(shù)的數(shù)學(xué)期望稱為平均失真平均失真：jjiijiibadabpapD),()|()(n失真函數(shù)失真函數(shù)d(xi,yj)：q描述了某個(gè)信源符號(hào)通過(guò)傳輸后失真的大小描述了某個(gè)信源符號(hào)通過(guò)傳輸后失真的大小n平均失真平均失真 ：q是是對(duì)給定對(duì)給定信源信源分布分布p(xi)經(jīng)過(guò)某一

6、轉(zhuǎn)移概率分布為經(jīng)過(guò)某一轉(zhuǎn)移概率分布為p(yj/xi)的的有失真信源編碼器后產(chǎn)生失真的總體量度有失真信源編碼器后產(chǎn)生失真的總體量度,是從是從總體總體上描上描述整個(gè)系統(tǒng)的失真。述整個(gè)系統(tǒng)的失真。D10n如果假定離散信源輸出符號(hào)序列如果假定離散信源輸出符號(hào)序列XX1X2 Xl Xn, 經(jīng)信源編碼后經(jīng)信源編碼后,輸出符號(hào)序列輸出符號(hào)序列Y=Y1YlYm, 則則平均失平均失真真定義為定義為1111 (,)LLLLLijlllDE d xyDLL dxdyyxdyxpDxy),(),(11平均失真為：平均失真為：),()/()(11jiinimjjibadabpapD 信源信源X經(jīng)過(guò)有失真的信源編碼器輸出

7、經(jīng)過(guò)有失真的信源編碼器輸出Y，其結(jié)構(gòu)如下：，其結(jié)構(gòu)如下：信源編碼器信源編碼器XY,.,21naaaX ,.,21mbbbY )/(ijxyp把上面的信源編碼器看成是有干擾的假想信道，這樣就可以把上面的信源編碼器看成是有干擾的假想信道，這樣就可以用分析信道傳輸?shù)姆椒▉?lái)分析信源編碼問(wèn)題。用分析信道傳輸?shù)姆椒▉?lái)分析信源編碼問(wèn)題。假想信道假想信道XY,.,21naaaX ,.,21mbbbY )/(ijxyp4.1.3 4.1.3 信息率失真函數(shù)信息率失真函數(shù)R(D)124.1.3 4.1.3 信息率失真函數(shù)信息率失真函數(shù)R(D)n無(wú)論是無(wú)噪信道還是有噪信道無(wú)論是無(wú)噪信道還是有噪信道: n RCq總能

8、找到一種編碼使在信道上能以任意小的錯(cuò)誤概率總能找到一種編碼使在信道上能以任意小的錯(cuò)誤概率,以任以任意接近意接近C的傳輸率來(lái)傳送信息的傳輸率來(lái)傳送信息n RCq就必須對(duì)信源壓縮就必須對(duì)信源壓縮,使其壓縮后信息傳輸率使其壓縮后信息傳輸率R小于信道容量小于信道容量C,但同時(shí)要保證壓縮所引入的失真不超過(guò)預(yù)先規(guī)定的限度。但同時(shí)要保證壓縮所引入的失真不超過(guò)預(yù)先規(guī)定的限度。n信源編碼器的目的是使編碼后所需的信息傳輸率信源編碼器的目的是使編碼后所需的信息傳輸率R盡量盡量小，然而小，然而R越小，引起的平均失真就越大。給出一個(gè)失越小，引起的平均失真就越大。給出一個(gè)失真的限制值真的限制值D，在滿足平均失真，在滿足平

9、均失真 D的條件下，選擇的條件下，選擇一種編碼方法使信息率一種編碼方法使信息率R盡可能小。盡可能小。D13信息率失真函數(shù)信息率失真函數(shù)R(D)n若平均失真度若平均失真度 不大于我們所允許的失真不大于我們所允許的失真,即即DDD n則稱此為則稱此為保真度準(zhǔn)則保真度準(zhǔn)則n當(dāng)信源當(dāng)信源p(xi)給定給定,單個(gè)符號(hào)失真度單個(gè)符號(hào)失真度d(xi,yj) 給定時(shí)給定時(shí),選擇選擇不同的試驗(yàn)信道不同的試驗(yàn)信道p(yj|xi), 相當(dāng)于不同的編碼方法相當(dāng)于不同的編碼方法,其所其所得的平均失真度不同。得的平均失真度不同。n試驗(yàn)信道試驗(yàn)信道DDDD滿足保真度準(zhǔn)則14D允許試驗(yàn)信道允許試驗(yàn)信道 n 若若p(xi)和和

10、d(xi，yj)已定，選擇信道，使其滿足保真已定，選擇信道，使其滿足保真度準(zhǔn)則，凡滿足要求的這種信道稱為度準(zhǔn)則，凡滿足要求的這種信道稱為D允許試驗(yàn)信道。允許試驗(yàn)信道。n 滿足這種要求的信道有多個(gè)，則可給出滿足下式滿足這種要求的信道有多個(gè)，則可給出滿足下式條件的所有轉(zhuǎn)移概率分布條件的所有轉(zhuǎn)移概率分布pij，它們構(gòu)成了一個(gè)信道集，它們構(gòu)成了一個(gè)信道集合合PD(/):1,2, ;1,2,DjiPp yxDDin jm15信息率失真函數(shù)信息率失真函數(shù)R(D)nR(D)：q在限定失真為在限定失真為D的條件下信源輸出的最小信息速率。的條件下信源輸出的最小信息速率。 ( )min ( ; )DPR DI X

11、 Yn在信源給定后在信源給定后, 在滿足一定失真的情況下在滿足一定失真的情況下,使信源必須傳輸使信源必須傳輸給收信者的給收信者的信息傳輸率信息傳輸率R盡可能地小。盡可能地小。n若從接收端來(lái)看若從接收端來(lái)看,就是在滿足保真度準(zhǔn)則下就是在滿足保真度準(zhǔn)則下,尋找再現(xiàn)信源尋找再現(xiàn)信源消息所必須獲得的消息所必須獲得的最低平均信息量最低平均信息量。即在滿足保真度準(zhǔn)。即在滿足保真度準(zhǔn)則的條件下尋找平均互信息則的條件下尋找平均互信息I(X,Y)的最小值。的最小值。16信息率失真函數(shù)信息率失真函數(shù)nPD是所有滿足保真度準(zhǔn)則的試驗(yàn)信道集合是所有滿足保真度準(zhǔn)則的試驗(yàn)信道集合,因而可因而可以在集合以在集合PD中尋找某

12、一個(gè)信道中尋找某一個(gè)信道pij,使使I (X,Y)取極小取極小值。值。n離散無(wú)記憶信源離散無(wú)記憶信源(|)( )min( ) (|)log()ijDjiijipPijjp baR Dp a p bap b17n例已知編碼器輸入的概率分布為例已知編碼器輸入的概率分布為p(x)=0.5 ,0.5n信道矩陣信道矩陣8 . 02 . 04 . 06 . 0ijpn求互信息)|()()(ijijixypxpyxp11122122()0.3()0.2()0.1()0.4p x yp x yp x yp x y6 . 0)(4 . 0)(21ypyp32)(41)|(31)|(43)|(22122121yx

13、pyxpyxpyxp(|)(; )()log0.125/( )jiijijip yxI X Yp x ybitp y符18n編碼器輸入的概率分布為編碼器輸入的概率分布為p(x)=0.5 ,0.5n信道矩陣信道矩陣8 . 02 . 01 . 09 . 0ijpn求互信息求互信息符號(hào)/397. 0)()|(log)();(bitypyxpyxpYXIijijijin可見當(dāng)可見當(dāng)p(x)一定時(shí)一定時(shí),I (X,Y)隨隨p(yj|xi)而變。而變。n因?yàn)橐驗(yàn)閜(x)分布一定時(shí)分布一定時(shí),信道受干擾不同所能傳遞的信息信道受干擾不同所能傳遞的信息量是不同的。量是不同的。n當(dāng)當(dāng)p(x)一定時(shí)一定時(shí),I (X

14、,Y)是關(guān)于是關(guān)于p(yj|xi)的下凸函數(shù)。的下凸函數(shù)。n因此當(dāng)改變因此當(dāng)改變p(yj|xi)時(shí)時(shí),I (X,Y)有一極小值。有一極小值。19平均互信息平均互信息n平均互信息平均互信息I(X;Y)： q信源的概率分布信源的概率分布p(xi)的上凸函數(shù)。的上凸函數(shù)。q信道傳遞概率信道傳遞概率p(yj|xi)的下凸函數(shù)。的下凸函數(shù)。);(max)(YXICixpn信道容量：信道容量： n信息率失真函數(shù)：信息率失真函數(shù)： );(min)(YXIDRDP20信道容量信道容量q假定信道固定的前提下假定信道固定的前提下,選擇一種試驗(yàn)信源使選擇一種試驗(yàn)信源使信息傳信息傳輸率最大。輸率最大。q它所反映的是信

15、道傳輸信息的能力它所反映的是信道傳輸信息的能力,是信道可靠傳送是信道可靠傳送的最大信息傳輸率。的最大信息傳輸率。n一旦找到了信道容量一旦找到了信道容量,它就與信源不再有關(guān)它就與信源不再有關(guān),而是信道而是信道特性的參量特性的參量,隨信道特性的變化而變化隨信道特性的變化而變化n不同的信道其信道容量不同。不同的信道其信道容量不同。21信息率失真函數(shù)信息率失真函數(shù)q假定信源給定的情況下假定信源給定的情況下,用戶可以容忍的失真度內(nèi)再現(xiàn)用戶可以容忍的失真度內(nèi)再現(xiàn)信源消息所必須獲得的最小平均信息量。信源消息所必須獲得的最小平均信息量。q它反映的是信源可以壓縮的程度它反映的是信源可以壓縮的程度,是在滿足一定失

16、真度是在滿足一定失真度要求下信源可壓縮的最低值。要求下信源可壓縮的最低值。n率失真函數(shù)一旦找到率失真函數(shù)一旦找到,就與求極值過(guò)程中選擇的試驗(yàn)就與求極值過(guò)程中選擇的試驗(yàn)信道不再有關(guān)信道不再有關(guān),而只是信源特性的參量而只是信源特性的參量n不同的信源其不同的信源其R(D)不同。不同。22：q充分利用已給信道充分利用已給信道,使傳輸?shù)男畔⒘孔畲笫箓鬏數(shù)男畔⒘孔畲?而發(fā)生而發(fā)生錯(cuò)誤錯(cuò)誤的概率任意小的概率任意小。 ：q解決在已知信源和允許失真度解決在已知信源和允許失真度D的條件下的條件下,使信源必須使信源必須傳送給信宿的信息率最小。即用盡可能少的碼符號(hào)盡傳送給信宿的信息率最小。即用盡可能少的碼符號(hào)盡快地傳

17、送盡可能多的信源消息快地傳送盡可能多的信源消息,以提高通信的以提高通信的有效性有效性。23n例：設(shè)信源的符號(hào)表為例：設(shè)信源的符號(hào)表為A=al,a2,a2n,概率分布概率分布為為p(ai)=1/2n,i=1,22n,失真函數(shù)規(guī)定為失真函數(shù)規(guī)定為 jijiaadji10),(n信源熵信源熵 nnnnH2log)2121,21(n如果對(duì)信源進(jìn)行不失真編碼如果對(duì)信源進(jìn)行不失真編碼,平均每個(gè)符號(hào)至少需要平均每個(gè)符號(hào)至少需要log2n個(gè)二進(jìn)制碼元。個(gè)二進(jìn)制碼元。n現(xiàn)在假定允許有一定失真現(xiàn)在假定允許有一定失真,假設(shè)失真限度為假設(shè)失真限度為D=1/2設(shè)想設(shè)想采用下面的編碼方案：采用下面的編碼方案： a1a1，

18、 a2a2， anan an+1an ,an+2 an ,a2n ann即不發(fā)生差錯(cuò)時(shí)失真為即不發(fā)生差錯(cuò)時(shí)失真為0,出錯(cuò)失真為出錯(cuò)失真為1n研究在一定編碼條件下信息壓縮的程度。研究在一定編碼條件下信息壓縮的程度。24n平均失真平均失真 21),()|()(ijjiijiaadaapapDn則輸出熵則輸出熵H(Y) 1log(212log)21,2121,21()(nnnnnnnnnHYHn由該信道模型圖由該信道模型圖4-3看出看出,它是一個(gè)確定信道它是一個(gè)確定信道n pij=1(或或0)，H(Y|X)=0 )()|()(),(YHXYHYHYXI壓縮254.1.4 4.1.4 信息率失真函數(shù)的

19、性質(zhì)信息率失真函數(shù)的性質(zhì)n1、R(D)的定義域的定義域n率失真的定義域問(wèn)題就是在信源和失真函數(shù)已知的情率失真的定義域問(wèn)題就是在信源和失真函數(shù)已知的情況下況下,討論允許平均失真度討論允許平均失真度D的的最小最小和和最大最大取值問(wèn)題。取值問(wèn)題。n由于平均失真度是非負(fù)實(shí)數(shù)由于平均失真度是非負(fù)實(shí)數(shù)d(xi,yj)的數(shù)學(xué)期望的數(shù)學(xué)期望,因此也因此也是非負(fù)的實(shí)數(shù)是非負(fù)的實(shí)數(shù),即即 的的下界是下界是0。n允許平均失真度能否達(dá)到其下限值允許平均失真度能否達(dá)到其下限值0,與單個(gè)符號(hào)的失與單個(gè)符號(hào)的失真函數(shù)有關(guān)。真函數(shù)有關(guān)。DD, 026R(D)的定義域的定義域nDmin 和和R(Dmin)n信源的最小平均失真度

20、：信源的最小平均失真度：nijijiyxdxpD1min),(min)(n只有當(dāng)失真矩陣的每一行至少有一個(gè)只有當(dāng)失真矩陣的每一行至少有一個(gè)0元素時(shí)元素時(shí),信源的信源的平均失真度才能達(dá)到下限值平均失真度才能達(dá)到下限值0。n當(dāng)當(dāng)Dmin = 0,即信源不允許任何失真時(shí)即信源不允許任何失真時(shí),信息率至少應(yīng)等信息率至少應(yīng)等于信源輸出的平均信息量于信源輸出的平均信息量信息熵。即信息熵。即 R(0) =H(X)271111( ) () ( ,)( )() ( ,)nmnmijiijijiijijijDp x p y x d x yp xp y x d x y對(duì)每個(gè) xi，選 j 使d(xi,yj)最小，對(duì)

21、應(yīng) p(yj|xi)=1，其余為0，則min1( )min ( ,)niijjiDp xd x y28n例：失真矩陣為例：失真矩陣為由于由于有有此時(shí)信道為無(wú)噪無(wú)損信道，有此時(shí)信道為無(wú)噪無(wú)損信道，有R(0) =H(X)01 1101dmin11220,()1, ()1DDp y xp y xx1x2y1y2y329R(D)的定義域的定義域n因?yàn)閷?shí)際信道總是有干擾的因?yàn)閷?shí)際信道總是有干擾的,其容量有限其容量有限,要無(wú)失真要無(wú)失真地傳送連續(xù)信息是不可能的。地傳送連續(xù)信息是不可能的。n當(dāng)允許有一定失真時(shí)當(dāng)允許有一定失真時(shí),R(D)將為有限值將為有限值,傳送才是可傳送才是可能的。能的。n對(duì)于連續(xù)信源：對(duì)

22、于連續(xù)信源：min0()lim ( )(0)( )cDR DR DRH x30R(D)的定義域的定義域nDmax：定義域的上限。：定義域的上限。nDmax是滿足是滿足R(D)=0時(shí)所有的時(shí)所有的平均失真度中的平均失真度中的最小值最小值。DDDR0)(maxminn由于由于I(X,Y)是非負(fù)函數(shù)是非負(fù)函數(shù),而而R(D)是在約束條件下的是在約束條件下的I(X,Y)的最小值的最小值,所以所以R(D)也是一個(gè)非負(fù)函數(shù)也是一個(gè)非負(fù)函數(shù),它的下它的下限值是零。限值是零。 R(D)0nDmax 和和R(Dmax)31R(D)的定義域的定義域n由于由于I(X,Y) = 0的充要條件是的充要條件是X與與Y統(tǒng)計(jì)獨(dú)

23、立統(tǒng)計(jì)獨(dú)立,即：即：)()|(jijypxypjijiijypjjijiiypyxdxpypyxdypxpDjj),()()(min),()()(min)()(maxnijiimjyxdxpD12 , 1max),()(min 從上式觀察可得：在從上式觀察可得：在j=1，m中，可找到中，可找到 值最小的值最小的j，當(dāng)該，當(dāng)該j對(duì)應(yīng)的對(duì)應(yīng)的pj1，而其余，而其余pj為零時(shí)，上式為零時(shí)，上式右邊達(dá)到最小，這時(shí)上式可簡(jiǎn)化成（課本有錯(cuò)）右邊達(dá)到最小，這時(shí)上式可簡(jiǎn)化成（課本有錯(cuò)）niijidp132n例例4-3:設(shè)輸入輸出符號(hào)表為設(shè)輸入輸出符號(hào)表為X=Y=0,1,輸入概率輸入概率分布分布p(x)=1/3

24、,2/3,失真矩陣失真矩陣 0110dn求：求： Dmin 和和Dmax 解：解： 失真矩陣的每一行至少有一個(gè)失真矩陣的每一行至少有一個(gè)0元素時(shí)元素時(shí), Dmin=0 當(dāng)當(dāng)Dmin0時(shí)，時(shí)，R(Dmin)H(X)H(1/3，2/3)0.91比特比特/符號(hào)，這時(shí)信源編碼器無(wú)失真，所以該編碼器符號(hào)，這時(shí)信源編碼器無(wú)失真，所以該編碼器的轉(zhuǎn)移概率為的轉(zhuǎn)移概率為 1001P333131,32min032131, 132031min,minmin2, 12, 12221212121112, 1212, 1maxjjjiijijdpdpdpdpdpD當(dāng)當(dāng)R(Dmax)0時(shí)時(shí) 此時(shí)輸出符號(hào)概率此時(shí)輸出符號(hào)概率

25、p(b1)0，p(b2)1， 所以這時(shí)的編碼器的轉(zhuǎn)移概率為所以這時(shí)的編碼器的轉(zhuǎn)移概率為 2221,baba1010P34n例例:設(shè)輸入輸出符號(hào)表為設(shè)輸入輸出符號(hào)表為X=Y=0,1,輸入概率輸入概率分布分布p(x)=1/3,2/3,失真矩陣失真矩陣 1212/ 1dn求：求： Dmin 和和Dmax 2max1,212111212minmin(2,11)323333min( ,1)1 (2()1, ()0)2iijjjijDp djp yp y 取 ， 即651322131),(min)(1minnijijiyxdxpD35R(D)的定義域的定義域nR(D)的定義域?yàn)榈亩x域?yàn)镈min，Dmax

26、 。n通常通常Dmin = 0， R(Dmin) = H(X)n當(dāng)當(dāng) DDmax時(shí)時(shí), R(D) = 0n當(dāng)當(dāng) 0 DDmax時(shí)時(shí), 0R(D) H(X)36信息率失真函數(shù)的性質(zhì)信息率失真函數(shù)的性質(zhì)n1、R(D)是非負(fù)的實(shí)數(shù)是非負(fù)的實(shí)數(shù), R(D)0。 其定義域?yàn)槠涠x域?yàn)?Dmax , 其值為其值為0H(X)。 當(dāng)當(dāng)DDmax時(shí)時(shí),R(D)0n2、R(D)是關(guān)于是關(guān)于D的下凸函數(shù)的下凸函數(shù)qR(D)在定義域內(nèi)是失真度在定義域內(nèi)是失真度D的的U型下凸函數(shù)型下凸函數(shù)n3、R(D)的單調(diào)遞減性及連續(xù)性的單調(diào)遞減性及連續(xù)性q容許的失真度越大，所要求的信息率越小。反之亦然。容許的失真度越大，所要求的信

27、息率越小。反之亦然。37圖說(shuō)明：圖說(shuō)明：nR(0) = H(X) ， R(Dmax) =0， 決定了曲線邊緣上的兩個(gè)點(diǎn)；決定了曲線邊緣上的兩個(gè)點(diǎn)；n在在0和和Dmax之間，之間， R(D)是單是單 調(diào)遞減的下凸函數(shù)；調(diào)遞減的下凸函數(shù)；n在連續(xù)信源時(shí)，當(dāng)在連續(xù)信源時(shí)，當(dāng)D0時(shí)，時(shí)， R(D) ，曲線將不與，曲線將不與R(D)軸相交。軸相交。38n陰影范圍表示實(shí)際信源編碼方案與理論值間的差距，我們陰影范圍表示實(shí)際信源編碼方案與理論值間的差距，我們完全可以找到更好，即更靠近理論值，縮小陰影范圍的信完全可以找到更好，即更靠近理論值，縮小陰影范圍的信源編碼，這就是工程界尋找好的信源編碼的方向和任務(wù)源編碼

28、，這就是工程界尋找好的信源編碼的方向和任務(wù) )(DR（理論）)(DR)( 實(shí)際DRD2/11 394.2 離散信源離散信源R(D)計(jì)算計(jì)算 n給定信源概率給定信源概率pi和失真函數(shù)和失真函數(shù)dij,就可以求得該信源就可以求得該信源的的R(D)函數(shù)。函數(shù)。n它是在保真度準(zhǔn)則下求極小值的問(wèn)題。它是在保真度準(zhǔn)則下求極小值的問(wèn)題。n但要得到它的顯式表達(dá)式但要得到它的顯式表達(dá)式,一般比較困難通常用參一般比較困難通常用參量表達(dá)式。量表達(dá)式。n即使如此即使如此,除簡(jiǎn)單的情況外實(shí)際計(jì)算還是困難的除簡(jiǎn)單的情況外實(shí)際計(jì)算還是困難的,只能用迭代逐級(jí)逼近的方法。只能用迭代逐級(jí)逼近的方法。 40二元對(duì)稱信源的二元對(duì)稱信

29、源的R(D)函數(shù)函數(shù) n設(shè)二元對(duì)稱信源設(shè)二元對(duì)稱信源X=0,1,其概率分布其概率分布p(x)=p,1-p,0p=1/2,接收變量接收變量Y=0,1,漢明失真矩陣漢明失真矩陣0110dn因而最小允許失真度因而最小允許失真度Dmin=0。（此時(shí)無(wú)失真）。（此時(shí)無(wú)失真）n并能找到滿足該最小失真的試驗(yàn)信道并能找到滿足該最小失真的試驗(yàn)信道,且是一個(gè)無(wú)噪且是一個(gè)無(wú)噪無(wú)損信道無(wú)損信道,其信道矩陣為其信道矩陣為1001pn計(jì)算得：計(jì)算得：R(0)=I(X;Y)=H(p)41n最大允許失真度為最大允許失真度為1max0,10minmin (0) (0,0)(1) (1,0), (0) (0,1)(1) (1,1

30、)min(1), iijjijDp dpdpdpdpdpppn要達(dá)到最大允許失真度的試驗(yàn)信道要達(dá)到最大允許失真度的試驗(yàn)信道, ,唯一確定為唯一確定為1010pn這個(gè)試驗(yàn)信道能正確傳送信源符號(hào)這個(gè)試驗(yàn)信道能正確傳送信源符號(hào)x=1,而傳送信源符號(hào)而傳送信源符號(hào)x=0時(shí)時(shí),接收符號(hào)一定為接收符號(hào)一定為y=1n凡發(fā)送符號(hào)凡發(fā)送符號(hào)x=0時(shí)時(shí),一定都錯(cuò)了。而一定都錯(cuò)了。而x=0出現(xiàn)的概率為出現(xiàn)的概率為p,所以所以信道的平均失真度為信道的平均失真度為p 。n在這種試驗(yàn)信道條件下，可計(jì)算得在這種試驗(yàn)信道條件下，可計(jì)算得 R(Dmax) = R(p) = 042 某些特殊情況下某些特殊情況下R(D)的表示式為

31、：的表示式為： （1）當(dāng)）當(dāng)d(x,y)=(x-y)2， 時(shí)，時(shí)，22221)(xexpDDRlog)(2)當(dāng)當(dāng)d(x,y)=|x-y|， 時(shí)，時(shí)，xexp2)(DDR1log)(43(3)當(dāng)當(dāng)d(x,y)= (x,y)，p(x=0)=p，p(x=1)=1-p時(shí)，時(shí)，R(D)=H(p)H(D) 0 Dmax D R(D) H(3)(1)(2)44信息率失真函數(shù)的參量表述信息率失真函數(shù)的參量表述 求信源的求信源的R(D)R(D)函數(shù)，原則上與求信道容量一樣，是函數(shù)，原則上與求信道容量一樣，是在有約束條件下求極小值的問(wèn)題。在有約束條件下求極小值的問(wèn)題。 也就是適當(dāng)選取試驗(yàn)信道也就是適當(dāng)選取試驗(yàn)信道

32、P(v/u)P(v/u)使平均互信息最小使平均互信息最小化，化，riijiijrisjijiuvPuPuvPuvPuPVUI111)/()()/(log)/()(),(45 但是，如果要求得到明顯的解析表達(dá)式，則比較困但是，如果要求得到明顯的解析表達(dá)式，則比較困難，通常只能用參量形式來(lái)表達(dá)。即便如此，除簡(jiǎn)難，通常只能用參量形式來(lái)表達(dá)。即便如此，除簡(jiǎn)單情況外，實(shí)際計(jì)算仍然是相當(dāng)困難的。尤其是約單情況外，實(shí)際計(jì)算仍然是相當(dāng)困難的。尤其是約束條件式，它是求解束條件式，它是求解R(D)函數(shù)最主要的障礙。函數(shù)最主要的障礙。 因?yàn)閼?yīng)用拉格朗日乘子法解得的一個(gè)或某幾個(gè)因?yàn)閼?yīng)用拉格朗日乘子法解得的一個(gè)或某幾個(gè)

33、P(vj/ui)很可能是負(fù)的。在這情況下，必須假設(shè)某些很可能是負(fù)的。在這情況下，必須假設(shè)某些P(vj/ui) =0，然后重新計(jì)算，這就使得計(jì)算復(fù)雜化了。，然后重新計(jì)算，這就使得計(jì)算復(fù)雜化了。 目前，可采用收斂的迭代算法在電子計(jì)算機(jī)上求解目前，可采用收斂的迭代算法在電子計(jì)算機(jī)上求解R(D)函數(shù)。函數(shù)。 下面介紹用拉格朗日乘子法求解下面介紹用拉格朗日乘子法求解R(D)函數(shù)，并用函數(shù)，并用S作作為參量來(lái)表述率失真函數(shù)為參量來(lái)表述率失真函數(shù)R(D)和失真函數(shù)和失真函數(shù)D(S)。46 由式由式(1)知，當(dāng)信源的概率分布知，當(dāng)信源的概率分布P(u)固定，平均互信息僅僅是試固定，平均互信息僅僅是試驗(yàn)信道驗(yàn)信道P(vj/ui)的函數(shù)。的函數(shù)。 若先不考慮式若先不考慮式(2)的約束，約束條件式的約束，約束條件式(3)包含包含r個(gè)等式，取拉格朗個(gè)等式，取拉格朗日乘子日乘子 i(i12， r)分別與之對(duì)應(yīng)；并取拉氏乘子分別與之對(duì)應(yīng)；并取拉氏乘子S與式與式(4)對(duì)應(yīng)。由此構(gòu)成輔助函數(shù)：對(duì)應(yīng)。由此構(gòu)成輔助函數(shù)：1( ; )(/)(5)sijijI U VP vuSD 0)/(ijuvPsjijuvP11)/(DvuduvPuPjirisjiji),()/()(11riijiijrisj