信息論與編碼技術(shù)：第四章 信息率失真函數(shù)

1、 第四章 信息率失真函數(shù) 4.1 失真測(cè)度 4.2 信息率失真函數(shù)及其性質(zhì) 4.3 離散無記憶信源的信息率失真函數(shù) 4.4 連續(xù)無記憶信源的信息率失真函數(shù) 4.5 保真度準(zhǔn)則下的信源編碼定理 1 在前面幾章的討論中，其基本出發(fā)點(diǎn)都是如何保證信息的無失真?zhèn)鬏敗?但在許多實(shí)際應(yīng)用中，人們并不要求完全無失真地恢復(fù)消息，而是只要滿足一定的條件，近似地恢復(fù)信源發(fā)出的消息就可以了。 什么是允許的失真？如何對(duì)失真進(jìn)行描述？ 信源輸出信息率被壓縮的最大程度是多少？信息率失真理論回答了這些問題，其中香農(nóng)的限失真編碼定理定量地描述了失真，研究 了信息率與失真的關(guān)系，討論了在限失真范圍內(nèi)的信源編碼問題，已成為量化、

2、數(shù)據(jù)轉(zhuǎn)化、頻帶壓縮和數(shù)據(jù)壓縮等現(xiàn)代通信技術(shù)的理論基礎(chǔ)。 2 本章主要討論： 在允許一定失真存在的條件下，能夠?qū)⑿旁磯嚎s到什么程度，即最少需要多少比特信息才能描述信源，如何能夠快速的傳輸信息。 本章主要介紹信息率失真理論的基本內(nèi)容，側(cè)重討論離散無記憶信源。 給出信源的失真度和信息率失真函數(shù)的定義與性質(zhì)； 討論離散信源和連續(xù)信源的信息率失真函數(shù)計(jì)算； 論述保真度準(zhǔn)則下的信源編碼定理(限失真信源編碼定理 香農(nóng)第三定理)。 3 引入限失真的必要性(1) 信宿的靈敏度和分辨率都是有限的，不必要求信息傳輸過程中絕對(duì)無失真。 如人耳對(duì)語音信號(hào)接收的帶寬和分辨率都有限，而語音信號(hào)的帶寬高達(dá)20KHz，可以把頻

3、譜范圍20Hz20KHz的語音信號(hào)去掉高低端部分，只保留3003400Hz間的部分，這樣，即使傳輸?shù)恼Z音信號(hào)存在一些失真，人耳也不易分辨或感覺出來，并可減少語音傳輸?shù)拈_銷，因而允許這種失真。 4 又如，由于人眼在接收視覺信號(hào)時(shí)的主觀視覺特征，允許信息有某些失真，可由此降低信息傳輸速率，從而降低信息傳輸成本。(2) 無失真編碼并非總是可能的。由于信源的輸出通常是取值連續(xù)的消息，即信源輸出的信息熵H無窮大，同時(shí)要求信道的信息傳輸率R也無窮大。但任何一個(gè)信道的實(shí)際帶寬總是有限的，即信道容量總要受到一定的限制，不可能達(dá)到無窮大，故不可能實(shí)現(xiàn)完全無失真的信源信息傳輸。(3) 由于信道噪聲的影響，即使信源

4、消息的編碼是無失真的，消息在傳輸過程中也會(huì)產(chǎn)生失真。 5結(jié)論： 實(shí)際信息傳輸系統(tǒng)中的失真是不可避免的，有時(shí)甚至是必要的。問題： 在允許一定失真度的條件下，能夠多大程度地壓縮信息(最少需要多少比特?cái)?shù)才能描述信源)。 香農(nóng)論述了限定失真范圍內(nèi)的信源編碼問題，定義了信息率失真函數(shù)R(D)，并論述了關(guān)于這個(gè)函數(shù)的基本性質(zhì)，指出在允許一定失真度D的情況下，信源輸出的信息傳輸率最低可壓縮到R(D)值(即R(D)值是信源信息傳輸率的下限值)，從理論上給出了信息傳輸率與允許失真之間的關(guān)系，奠定了信息率失真理論的基礎(chǔ)。 64.1 失真測(cè)度74.1 失真測(cè)度4.1.1 系統(tǒng)模型 限失真信源編碼的系統(tǒng)模型如下圖所示

5、。信源發(fā)出的消息X通過有失真信源編碼器，編碼后的輸出通過理想無噪信道傳輸，經(jīng)信源譯碼器譯碼后輸出Y 。 8 由于信源編碼為有失真編碼，故輸出的Y不是信源發(fā)出的消息X的精確重現(xiàn)。 為了定量描述信息傳輸率與失真之間的關(guān)系，已假定傳輸信道為理想無噪信道。 可以將信源編碼引起的失真視為由于信道不理想所造成的(將有失真信源編碼器與信源譯碼器之間的過程一并看作有噪信道該假想信道稱為試驗(yàn)信道)。 由此，把有失真信源編碼問題轉(zhuǎn)化為無失真信源編碼通過有噪信道傳輸?shù)膯栴}，進(jìn)而可通過研究試驗(yàn)信道輸入|輸出間的互信息來研究限失真信源編碼。 9在實(shí)際問題中，信號(hào)有一定的失真是可以容忍的。但是當(dāng)失真大于某一限度后，信息質(zhì)

6、量將被嚴(yán)重?fù)p傷，甚至喪失其實(shí)用價(jià)值。要規(guī)定 失真限度，必須先有一個(gè)定量地失真測(cè)度。為此可引入失真函數(shù)。4.1.2 失真度和平均失真度1.單符號(hào)失真度 試驗(yàn)信道的輸入為X，取值于符號(hào)集Aa1,a2,an，試驗(yàn)信道的輸出為Y，取值于符號(hào)集Bb1,b2,bm。設(shè) 分別為試驗(yàn)信道的輸入與輸出，若 ，則沒有失真；否則就產(chǎn)生了失真。對(duì)每一對(duì)(xi,yj)，定義非負(fù)函數(shù)d(xi,yj)為單符號(hào)失真度(單符號(hào)失真函數(shù))。 一般有 11 單符號(hào)失真度d(xi,yj)用來度量信源發(fā)出一個(gè)符號(hào)xi (i=1,n)時(shí)，信源譯碼器輸出符號(hào)yj(j=1,m)所引起信息失真的大小。 規(guī)定d(xi,yj)的值越小代表失真越小

7、，顯然，d(xi,yj)=0表示沒有失真。 若信源符號(hào)集有n個(gè)符號(hào)，信源譯碼器的輸出符號(hào)集有m個(gè)符號(hào)，則單符號(hào)失真度d(ui,vj)就有nm個(gè)，它可以排列成nm階矩陣d稱為(nm 階)失真矩陣。 12說明： 這里假設(shè)X是信源，Y是信宿，那么X和Y之間必有信道。 實(shí)際上X指的是原始未失真信源，Y是失真信源。因此，從X到Y(jié)之間實(shí)際上包含了失真算法。所以這里的轉(zhuǎn)移概率p(yj|xi)是指一種失真算法。也把p(yj|xi) 稱為試驗(yàn)信道的轉(zhuǎn)移概率，如圖所示。 單符號(hào)失真度d(xi,yj)可根據(jù)實(shí)際信源的的失真情況來定義，方法各異。 13例1 設(shè)離散對(duì)稱信源(r=s)，信源變量Xa1,a2,ar ，接收

8、變量Y b1,b2,br。定義單符號(hào)失真度這種失真稱為漢明失真。漢明失真矩陣是一方陣，主對(duì)角線上的元素為零，其余全為1 對(duì)二元對(duì)稱信源(s=r=2)，信源X=0,1，接收變量Y=0,1，則漢明失真矩陣為 14例2 設(shè)有刪除信源，其信源變量X=a1,a2,ar，接收變量Y=b1,b2,bs (s=r+1) 。定義其單個(gè)符號(hào)失真度為 其中接收符號(hào)bs作為一個(gè)刪除符號(hào)。 在這種情況下，意味著若把信源符號(hào)再現(xiàn)為刪除符號(hào)bs時(shí)，其失真程度要比再現(xiàn)為其他接收符號(hào)的失真程度少一半。 若二元?jiǎng)h除信源r=2，s=3，X=0,1, Y=0,1,2。失真度為 d(0,0)=d(1,1)=0 d(0,1)=d(1,0

9、)=1 則 d(0,2)=d(1,2)=1/2 15例3 設(shè)有對(duì)稱信源(s = r) 。信源變量Xa1,a2,ar ，接收變量Y b1,b2,br 。失真度定義為 若信源符號(hào)代表信源輸出信號(hào)的幅度值，這就是一種以方差表示的失真度。它意味著幅度差值大的要比幅度差值小的所引起的失真更為嚴(yán)重，嚴(yán)重程度用平方來表示。 當(dāng) r=s=3時(shí)， X=0,1,2，Y=0,1,2 ，則失真矩陣為： (d由信道各輸出與輸入符號(hào)差的平方構(gòu)成。) 162.序列失真度 上述例子說明了具體失真度的定義。一般情況下根據(jù)實(shí)際信源的失真，可以定義不同的失真和誤差的度量。另外還可以按其他標(biāo)準(zhǔn)，如引起的損失、風(fēng)險(xiǎn)、主觀感覺上的差別大

10、小等來定義失真度d(xi,yj)。 173. 平均失真度 信源X和信宿Y都是隨機(jī)變量，故單個(gè)符號(hào)失真度d(xi,yj) 也是隨機(jī)變量。 單個(gè)符號(hào)失真函數(shù)d(xi,yj)和序列失真函數(shù) 僅表示兩個(gè)具體符號(hào)或符號(hào)序列之間的失真大小，有必要在規(guī)定了d(xi,yj)后，定義一個(gè)能在平均意義上衡量信道每傳輸一個(gè)符號(hào)所引起的平均失真大小的量，即定義平均失真度： 設(shè)在離散情況下，信源X=a1,a2,ar，其概率分布P(x)=P(a1),P(a2),P(ar) ，信宿Y= b1,b2,bs 。若已知試驗(yàn)信道的傳遞概率為P(yj|xi)時(shí)，則平均失真度為： 18 稱為單符號(hào)平均失真度，表示由信源X和試驗(yàn)信道X,

11、P(Y|X),Y組成的通信系統(tǒng)的平均失真度。 單符號(hào)平均失真度D不再像失真函數(shù)那樣只是表示某兩個(gè)具體符號(hào)或序列之間的失真大小，而是從總體平均意義上度量整個(gè)通信系統(tǒng)失真的大小。 單符號(hào)平均失真度D是信源統(tǒng)計(jì)特性p(ai)(i=1,2,r)，試驗(yàn)信道傳遞特性p(bj|ai)(i=1,2,r; j=1,2,s)和定義的失真函數(shù)(失真度)d(ai,bj) (i=1,2, ,r; j=1,2, ,s)的函數(shù)，即 D=f(p(ai), p(bj|ai), d(ai,bj) (i=1,2, ,r; j=1,2, ,s) 19 當(dāng)d(ai,bj)被確定，信源的統(tǒng)計(jì)特性p(ai)給定以后，平均失真度D僅是試驗(yàn)信

12、道傳遞概率p(bj|ai)的函數(shù)，故改變信道傳遞概率，就可改變平均失真度D。 或者說，在信源固定(給定P(x)，單符號(hào)失真度固定時(shí)(給定d(ui,vj) ，選擇不同的試驗(yàn)信道，相當(dāng)于采用不同的編碼方法，所得的平均失真度不同。 同理，序列平均失真度定義為 20保真度準(zhǔn)則：若規(guī)定系統(tǒng)的平均失真度D不超過某一限定值D0，即 D D0作為“允許的失真” 。 有些試驗(yàn)信道滿足DD0，而有些試驗(yàn)信道DD0，凡滿足保真度準(zhǔn)則平均失真度DD0的試驗(yàn)信道稱為D失真許可的試驗(yàn)信道。 把所有D失真許可的試驗(yàn)信道組成一個(gè)集合，用符號(hào)PD表示，即 PD=P (yj |xi): D D0 引入D0使我們有可能把允許的平均

13、失真度D0作為對(duì)信道傳遞概率p(bj|ai)的一種約束條件，在此約束條件下，求解試驗(yàn)信道的信息傳輸速率的最小值，并賦予該最小值某種使用價(jià)值。 214.2 信息率失真函數(shù)及其性質(zhì)224.2.1 信息率失真函數(shù)的定義 從直觀感覺可知，若允許失真越大，信息傳輸率可越??；若允許失真越小，信息傳輸率越大，所以信息傳輸率與信源編碼所引起的失真是有關(guān)的信源給定，且又具體定義了失真函數(shù)以后，總希望在滿足一定失真的情況下，使信源傳輸給收信者的信息傳輸率R盡可能地小。即在滿足保真度準(zhǔn)則下，尋找信源必須傳輸給收信者的信息率R的下限值這個(gè)下限值與D有關(guān)。 從接收端來看，就是在滿足保真度準(zhǔn)則下，尋找再現(xiàn)信源消息所必須獲

14、得的最低平均信息量。 23 從接收端來看，就是在滿足保真度準(zhǔn)則下，尋找再現(xiàn)信源消息所必須獲得的最低平均信息量。 而接收端獲得的平均信息量可用平均互信息I(X;Y)來表示，問題變成了在滿足保真度準(zhǔn)則的條件下，尋找平均互信息I(X;Y)的最小值。 24 尋找平均互信息I(U;V)的最小值 許可試驗(yàn)信道集合PD=P(yj|xi):DD0是所有滿足保真度準(zhǔn)則的試驗(yàn)信道集合，由任一試驗(yàn)信道的的傳遞概率所得的平均失真度D都滿足保真度準(zhǔn)則DD0，即平均失真度D都不超過給定的允許值D0，因而可以在D失真許可的試驗(yàn)信道集合PD中尋找一個(gè)信道P(yj|xi)，使I(X;Y) 取極小值。 25信息率失真函數(shù)定義 平

15、均互信息I(X;Y)是P(yj|xi)的型凸函數(shù)，在PD集合中, I(X;Y)極小值存在。這個(gè)最小值就是在DD0的條件下，信源必須傳輸?shù)淖钚∑骄畔⒘?，即R(D)稱為信源的信息速率失真函數(shù)，簡(jiǎn)稱信息率失真函數(shù)或率失真函數(shù)。 R(D) 的單位：比特/信源符號(hào)(奈特|哈特/信源符號(hào)) 說明 率失真函數(shù)R(D)給出了熵壓縮編碼可能達(dá)到的最小熵率與失真的關(guān)系。 率失真函數(shù)R(D)的逆函數(shù)稱為失真率函數(shù)D(R)，表示一定信息速率下所可能達(dá)到的最小的平均失真。 261. R(D)的定義域證 先證明下界4.2.2 信息率失真函數(shù)的性質(zhì) 27 對(duì)x的每一取值ai，令對(duì)應(yīng)最小的d(ai,bj)條件概率p(bj|

16、ai)為1，其余條件概率為0，得Dmin，即取 因?yàn)镽(D)為滿足保真度準(zhǔn)則的平均互信息I(X;Y)的最小值。 I(X;Y)是非負(fù)的，其最小值為0，因此把I(X;Y)=0的最小平均失真度定義為最大允許失真度Dmax，它也是R(D)=0中所有D中的最小值。 28因?yàn)镮(X;Y)非負(fù)，所以R(D)0。在較大范圍內(nèi)求極小值一定不大于在所含的小范圍內(nèi)求極小值，所以 D1D2 R(D1) R(D2)表明R(D)是D的非增函數(shù)。D繼續(xù)增加時(shí)，R(D)仍然為0，所以Dmax是使R(D)=0的最小平均失真度。 I(X;Y)=0時(shí)，輸入隨機(jī)變量X和輸出隨機(jī)變量Y統(tǒng)計(jì)獨(dú)立，p(x,y)=p(x)p(y)，有 29

17、由于信源概率分布p(xi)和失真函數(shù)d(xi,yj)已經(jīng)給定，故求Dmax相當(dāng)于尋找分布p(yj)，使 最小。如果選取 最小時(shí)的分布p(yj)=1，而對(duì)其他的 選取p(yj)=0，則有 綜上所述，信息率失真函數(shù)R(D)的定義域?yàn)?Dmin,Dmax)， 30說明： 允許失真度D的下限可以是零，當(dāng)Dmin=0時(shí)，即信源不允許任何失真，此時(shí)，信息傳輸率應(yīng)不大于信源熵，即 R(0)H(X)。 當(dāng)允許失真度大于上限值(DDmax)時(shí)，R(D)=0。 而當(dāng)DminDDmax時(shí)， 0R(D)H(X) 。 31例 設(shè)試驗(yàn)信道輸入概率空間和失真矩陣如下所示，求Dmin和 Dmax以及相應(yīng)的試驗(yàn)信道的轉(zhuǎn)移概率矩

18、陣。解令對(duì)應(yīng)最小失真度d(ai,bj) 的 p(bj|ai)=1，其它為“0”，可得對(duì)應(yīng)Dmin 的試驗(yàn)信道轉(zhuǎn)移概率矩陣為 (顯然p(y|x)與d同階。) 32上式中第二項(xiàng)最小，所以令 p(b2)=1，p(b1)=p(b3)=0，可得對(duì)應(yīng) Dmax的試驗(yàn)信道轉(zhuǎn)移概率矩陣為 332. R(D)是關(guān)于平均失真度D的下凸函數(shù) 設(shè) D1，D2 為任意兩個(gè)平均失真度，取0a1 ，則有： R(a D1+(1-a)D2)a R( D1)+(1-a)R(D2)證 信源分布給定后，信息率失真函數(shù)R(D)可以看作試驗(yàn)信道轉(zhuǎn)移概率p(y|x)的函數(shù)，即 34令D0=aD1+(1-a)D2, p0(y|x)=ap1(

19、y|x)+(1-a)p2(y|x), 顯然0p0(y|x)1，p0(y|x)可視為一個(gè)新的試驗(yàn)信道，該試驗(yàn)信道的平均失真度D為 353 . R(D) 是 (Dmin,Dmax)區(qū)間上的連續(xù)和嚴(yán)格單調(diào)遞減函數(shù)。 由信息率失真函數(shù)的下凸性可知，R(D)在(Dmin,Dmax)上連續(xù)。又由R(D)函數(shù)的非增性且不為常數(shù)知，R(D)是區(qū)間(Dmin,Dmax) 上的嚴(yán)格單調(diào)遞減函數(shù)。 信息率失真函數(shù)的一般形狀如下圖所示 36說明 Dmin和Dmax的取值取決于失真矩陣。 若對(duì)任一ai，都至少存在一個(gè)bj使得d(ai,bj)=0，則有 Dmin=0； 若失真矩陣中存在無窮大值，則Dmax可取到無窮大，

20、此時(shí)R(Dmax)=0。 如果失真矩陣的每行和每列有且僅有一個(gè)元素為0， 則此時(shí)Dmin=0，且有R(0)=H(X)-H(X|Y)=H(X)，當(dāng)信 源為連續(xù)信源時(shí)，H(X)=，此時(shí)R(0)=。 37R(D）的物理意義：對(duì)于給定的信源，在滿足保真度準(zhǔn)則下，必須傳送的最小信息量，它既反映了用戶容忍程度，也反映了信息率允許壓縮的最小值，R(D)越大，越難壓縮，反之可壓縮率就大。4.3離散無記憶信源的信息率失真函數(shù)394.3 離散無記憶信源的信息率失真函數(shù) 已知信源的概率分布p(x)和失真函數(shù)d(x,y)，就可求得信源的信息率失真函數(shù)R(D) 。原則上它與信道容量一樣，即在有約束條件下求極小值的問題(

21、即適當(dāng)選取試驗(yàn)信道P(y|x)使平均互信息最小化)。即求 40 使用變分法或拉格朗日乘子法等方法求解約束條件下函數(shù)極值問題時(shí)，通常得到參數(shù)形式表述，且很難計(jì)算。 若信道具有某種對(duì)稱性，則可簡(jiǎn)化信道容量的計(jì)算。同樣在計(jì)算率失真函數(shù)時(shí)，利用信源和失真矩陣的對(duì)稱性也可大大簡(jiǎn)化率失真函數(shù)的計(jì)算。 以下先說明特殊情況下R(D)的計(jì)算，然后討論R(D)一般的參數(shù)表述。 414.3.1 等概率、對(duì)稱失真信源的R(D)計(jì)算 對(duì)于等概、對(duì)稱失真的信源，存在一個(gè)與失真矩陣具有同樣對(duì)稱性的轉(zhuǎn)移概率分布達(dá)到率失真R(D)(證明略)。例4.3.1一個(gè)二元等概平穩(wěn)無記憶信源X=0,1，接收符號(hào)集為Y=0,1,2，失真矩陣

22、為 求率失真函數(shù)R(D) 。解 由于信源等概分布，失真函數(shù)具有對(duì)稱性，故存在著與失真矩陣同樣具有對(duì)稱性的轉(zhuǎn)移概率分布達(dá)到率失真R(D) 。 42該轉(zhuǎn)移概率矩陣可寫為由于d(0,1)=d(1,0)=，因此對(duì)于任何有限平均失真，必須有=0。于是轉(zhuǎn)移概率矩陣變?yōu)?因此，=1-D 43 44可求出此時(shí)的互信息為相應(yīng)的率失真函數(shù)R(D)如圖所示。 45例4.3.2 設(shè)有n元等概平穩(wěn)無記憶信源X=1,n，接收符號(hào)集Y =1,n，若規(guī)定失真矩陣為求率失真函數(shù)。解 由于信源等概分布，失真函數(shù)具有對(duì)稱性，存在著與失真矩陣同樣具有對(duì)稱性的轉(zhuǎn)移概率分布達(dá)到率失真函數(shù)R(D)。 46該轉(zhuǎn)移概率矩陣可寫為 47分別取n

23、=2，則 R(D)=1-H(D,1-D) 取n=4，則 R(D)=2-H(D,1-D)Dlog3 取n=8，則 R(D)=3-H(D,1-D)Dlog7 48得到率失真函數(shù)曲線如下圖所示。當(dāng)D=0，即無失真時(shí)，n=2, R(0)=1-H(1)=1 (bit/sym) n=4, R(0)=2-H(1)=2 (bit/sym) n=8, R(0)=3-H(1)=3 (bit/sym) 49有失真時(shí)，如D=0.2時(shí) 50R(D）的物理意義：對(duì)于給定的信源，在滿足保真度準(zhǔn)則下，必須傳送的最小信息量，它既反映了用戶容忍程度，也反映了信息率允許壓縮的最小值，R(D)越大，越難壓縮，反之可壓縮率就大。 4.

24、3.2 離散無記憶信源的信息率失真函數(shù)的參量 表述 求信源的R(D)函數(shù)，原則上與求信道容量一樣，是在有約束條件下求極小值的問題，也就是適當(dāng)選取試驗(yàn)信道P(y|x)使平均互信息最小化，應(yīng)用拉格朗日乘子法，原則上可以求出解來。 在沒有不等式約束(P(Y|X)非負(fù))條件下，互信息I(X;Y)是信道轉(zhuǎn)移概率P(Y|X)的下凸函數(shù)，故必有唯一的極小值(最小值)。 在不等式約束下，互信息I(X;Y)的最小值有可能發(fā)生在某幾個(gè)條件概率為0的邊界上，進(jìn)而可能涉及多組等式約束的極值求解問題，故一般無顯式解析解，可求得其參量表述。 52 設(shè)試驗(yàn)信道的輸入為X，輸入符號(hào)集A=a1,a2,an，對(duì)應(yīng)的p(x)=(p

25、1,p2, ,pn)；設(shè)試驗(yàn)信道的輸出為Y，輸出符號(hào)集B=b1,b2,bm，對(duì)應(yīng)的q(y)=(q1,q2, ,qm)，失真矩陣為 53 由于應(yīng)用拉格朗日乘子法解得的一個(gè)或某幾個(gè)P(yj|xi)很可能是負(fù)的。在這情況下，必須假設(shè)某些P(yj|xi) =0，然后重新計(jì)算，這就使得計(jì)算復(fù)雜化了。 一般可采用收斂的迭代算法在計(jì)算機(jī)上求解R(D)函數(shù)。 以下用拉格朗日乘子法求解R(D)函數(shù)，并用S作為參量來表述率失真函數(shù)R(D)和失真函數(shù)D(S)。 54 問題表述：求解信息率失真函數(shù)R(D)就是尋找達(dá)到R(D)的轉(zhuǎn)移概率分布，即求解有約束的極值問題 由于使R(D)最小的Pj|i總是在許可試驗(yàn)信道集合PD

26、的邊界上，所以求極值時(shí)，平均失真度約束條件的不等式取等號(hào)，即 55 由式(1)知，當(dāng)信源的概率分布pi固定時(shí)，平均互信息僅僅是試驗(yàn)信道Pj|i的函數(shù)。 考慮問題描述方程組中的約束條件(3)和(5)可知，約束條件有r+1個(gè)；未知數(shù)為轉(zhuǎn)移概率Pj|i，有rs個(gè)。 若先不考慮式(2)的約束，約束條件式(3)包含r個(gè)等式，取拉格朗日乘子i(i1,2,r)分別與之對(duì)應(yīng)；并取拉氏乘子S與式(5)對(duì)應(yīng)。則S、i (i1,2,r)分別表示r+1個(gè)約束條件的待定常數(shù)。構(gòu)造目標(biāo)函數(shù) 56 (6)表示的目標(biāo)函數(shù)右邊第一項(xiàng)為互信息，后兩項(xiàng)都是轉(zhuǎn)移概率Pj|i的線性函數(shù)，所以(Pj|i)仍是Pj|i的下凸函數(shù)，因此局部

27、極小也就是全局極小。 求極值，就是求目標(biāo)函數(shù)一階導(dǎo)數(shù)等于零的方程組的解，即求該式共有rs個(gè)方程，加上式(3) r 個(gè)方程和式(4) 1 個(gè)方程，共有(r+1+ rs)個(gè)方程。 而未知數(shù)i(i=1,2,r)、S和P(yj|xi )(i=1,2,r，j=1,2,s)也正好對(duì)應(yīng)(r+1+rs)個(gè)，所以原則上只需求解式(6)、(3)和(4)的方程組，即可求出I(X;Y)在約束條件下的極小值。 57 58 59 (*)含有s個(gè)方程，s個(gè)未知數(shù)qj(j=1,2,s)，S為參數(shù)，可解。整個(gè)問題的求解順序?yàn)?先求qj(j=1,2,s) = i(i=1,2,r) = pj|i = D(S) = R(S) 60注

28、意： 這時(shí)所得的D(S)是以S為參量的表達(dá)式，而不是顯式表達(dá)式，因而所得到的R(D)的表達(dá)式也是以S為參量的表達(dá)式。 參量S對(duì)應(yīng)的限制條件為 ，它與允許的失真度D有關(guān)，所以以S為參量就相當(dāng)于以D為參量。 61信息率失真函數(shù)R(D)的求解過程： 參數(shù)S給定時(shí)，由 求出i (i=1,2,r)； 由 求出qj (j=1,2,s) ； 再由 62參數(shù)S的幾何意義(信息率失真函數(shù)R(D)與參數(shù)S關(guān)系分析)： 63 64例 設(shè)離散信源 和接收變量：Y=0,1 并設(shè)失真矩陣為:求該信源的信息率失真函數(shù)R(D)。解 根據(jù)計(jì)算可得 Dmin=0，Dmax=1/2 ，由題設(shè)知 p1=p2=1/2，d11=0，d1

29、2=2，d21=1，d22=0根據(jù)參量表達(dá)式按如下步驟進(jìn)行求解。 65第一步：由 (j=1,2)，求i。第二步：由 (j=1,2)，求qj。 66第三步：由式 求D(s)。 將前兩步的結(jié)果代入上式，有第四步：由 求R(s)。 將前三步結(jié)果代入上式，有 67由 ，還可求得此時(shí)的試驗(yàn)信道轉(zhuǎn)移概率為 68例 設(shè)有二進(jìn)制非等概信源，試驗(yàn)信道輸入符號(hào)集A=0,1，p(0)=p1=p，p(1)=p2=1-p，試驗(yàn)信道輸出符號(hào)集B=0,1 ，失真函數(shù)為漢明失真。求該信源的信息率失真函數(shù)R(D)。解 由題知，d11=0, d22=0, d12=d21=1，按前述參數(shù)方程的求解步驟求解。第一步：由 (j=1,2

30、)，求i。第二步：由 (j=1,2)，求qj。 69第三步：由式 (i,j=1,2)，求D(s) 將前兩步的結(jié)果代入上式，有第四步：將S、1和2的結(jié)果代入R(s)，有 70 由圖可見，當(dāng)D=0(無失真時(shí))，R0.5(0)=1bit/sym， R0.25(0)=0.8bit/sym, R0.125(0)=0.6bit/sym；限失真時(shí)，如D=0.1， R0.5(0.1)=0.67bit/sym,R0.25(0.1)=0.45bit/sym, R0.125(0.1)=0.17bit/sym壓縮比分別為K0.5=1/0.67K0.250.8/0.450 ，以及任意長(zhǎng)的碼長(zhǎng)k，一定存在一種信源編碼C，其碼字個(gè)數(shù)為M2kR(D) +，使編碼后碼的平均失真度DD0。 106定理解釋 對(duì)于任何失真度D，只要碼長(zhǎng)k足夠長(zhǎng)，總可以找到一種信源編碼，使編碼后每個(gè)信源符號(hào)的信息傳輸率略大于(直至無限逼近)率失真函數(shù)R(D)而碼的平均失真度不大于給定的允許失真度，即DD0。 由于R(D)為給定D前提下信源編碼可能達(dá)到的信息傳輸率下限， 所以香農(nóng)第三定理說明了： 達(dá)到信息傳輸率下限的最佳信源編碼是存在的。 107實(shí)際的信源編碼(無失真編碼或先限失真編碼后無失真編碼)的最終目標(biāo)是盡量接近最佳編碼，使編碼信息傳輸率接近最大值logr，而同