信息論-基礎(chǔ)理論與應(yīng)用：第七章 保真度準則下的信源編碼

1、1第七章 保真度準則下的信源編碼第一節(jié) 失真度和平均失真度第二節(jié) 信息率失真函數(shù)及其性質(zhì)第三節(jié) 離散信源的信息率失真函數(shù)第五節(jié) 保真度準則下的信源編碼定理 第六節(jié) 聯(lián)合有失真信源信道編碼定理第七節(jié) 有失真信源編碼定理的實用意義第四節(jié) 連續(xù)信源的信息率失真函數(shù)7.1 失真度和平均失真度 在實際生活中，人們不一定要求完全無失真的恢復消息，也就是允許有一定的失真。 那么在允許一定程度失真的條件下，能夠把信源信息壓縮到什么程度，也就是，允許一定程度失真的條件下，如何能快速的傳輸信息，這就是本章所要討論的問題。 (1) “消息完全無失真?zhèn)魉汀钡目蓪崿F(xiàn)性信道編碼定理：無論何種信道，只要信息率R小于信道容量

2、C，總能找到一種編碼，使在信道上能以任意小的錯誤概率和任意接近于C 的傳輸率來傳送信息。反之，若R C，則傳輸總要失真。完全無失真?zhèn)魉筒豢蓪崿F(xiàn)：實際的信源常常是連續(xù)的，信息率無限大，要無失真?zhèn)魉鸵笮畔⒙蔙為無窮大；實際信道帶寬是有限的，所以信道容量受限制。要想無失真?zhèn)鬏?，所需的信息率大大超過信道容量RC。一、引 言(2) 實際中允許一定程度的失真 技術(shù)發(fā)展的需要隨著科學技術(shù)的發(fā)展，數(shù)字系統(tǒng)應(yīng)用得越來越廣泛，這就需要傳送、存儲和處理大量的數(shù)據(jù)。為了提高傳輸和處理效率，往往需要對數(shù)據(jù)壓縮，這樣也會帶來一定的信息損失。人類社會已進入信息時代，信息爆炸的結(jié)果要求人們解決如何對浩如煙海的數(shù)據(jù)有效的壓縮

3、，減少數(shù)據(jù)的存儲容量(如各種數(shù)據(jù)庫、電子出版物、多媒體娛樂)、傳輸時間(如數(shù)據(jù)通信和遙測)、或占有帶寬(如多媒體通信、數(shù)字音頻廣播、高清晰度電視)，要想方設(shè)法壓縮給定消息 集合占用的空間域、時間域和頻率域資源。如海洋地球物理勘探遙測數(shù)據(jù)，用60路傳感器，每路信號1KHz，16位A/D量化，每航測1Km就需記錄1盤0.5英寸的磁帶，一條測量船每年就可勘測15000Km，數(shù)據(jù)流之大可見一斑。實際生活中的需要實際生活中，人們一般并不要求獲得完全無失真的消息，通常只要求近似地再現(xiàn)原始消息，即允許一定的失真存在。例如打電話：即使語音信號有一些失真，接電話的人也能聽懂。人耳接收信號的帶寬和分辨率是有限的。

4、放電影：理論上需要無窮多幅靜態(tài)畫面，由于人眼的“視覺暫留性”，實際上只要每秒放映24幅靜態(tài)畫面。有些失真沒有必要完全消除。在允許一定程度失真的條件下，能夠把信源信息壓縮到什么程度,即:最少需要多少比特數(shù)才能描述信源.也就是 在允許一定程度失真的條件下,如何能快速的傳輸信息.這就是信息率失真理論.(3) 信息率失真理論信息率失真函數(shù)香農(nóng)定義了信息率失真函數(shù)R(D)。定理指出：在允許一定失真度D的情況下，信源輸出的信息率可壓縮到R(D)。信息率失真理論是量化（模數(shù)轉(zhuǎn)換）、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)。我們將信道編碼和譯碼都看成是信道的一部分。又根據(jù)信道編碼定理，我們可以把信道編碼、信道、

5、信道譯碼這三部分看成是一個沒有任何干擾的廣義信道。這樣收信者收到消息后所產(chǎn)生的失真(或誤差)只是由信源編碼帶來的。從直觀感覺可知，若允許失真越大，信息傳輸率可越小；若允許失真越小，信息傳輸率需越大。所以信息傳輸率與信源編碼所引起的失真(或誤差)是有關(guān)的。為了定量地描述信息傳輸率和失真的關(guān)系，我們用虛擬手法拿信道來表示失真信源編碼的作用，把信源編碼和信源譯碼等價成一個信道，由于是失真編碼，所以信道不是一一對應(yīng)的，用信道傳遞概率來描述編、譯碼前后的關(guān)系。一般此信道稱為試驗信道。信源編碼信道編碼信道信道譯碼信源譯碼信源信宿信源編碼信道*信源譯碼信源信宿信源信宿試驗信道UVp(vj/ui)現(xiàn)在我們要研

6、究在給定允許失真的條件下，是否可以設(shè)計一種信源編碼使信息傳輸率為最低。為此，我們首先討論失真的測度。設(shè)信源變量為 ，其概率分布為 對于每一對(ui,vj)，我們指定一個非負的函數(shù)二、失真度（或稱失真函數(shù)）接收端變量為 稱為單個符號的失真度（或稱失真函數(shù)） 失真函數(shù)用來表征信源發(fā)出一個符號ui，而在接收端再現(xiàn)成符號vj 所引起的誤差或失真。d(ui, vj)越小表示失真越小，等于0表示沒有失真。 可以將所有的失真函數(shù)排列成矩陣的形式：我們稱它為失真矩陣。常用的失真函數(shù)第一種當i=j時，U與V的取值一樣，用V來代表U就沒有誤差，所以定義失真函數(shù)為0；當ij時，用V代表U就有誤差。這種定義認為對所有

7、不同的i和j引起的誤差都一樣，所以定義失真函數(shù)為常數(shù)a。失真矩陣的特點是對角線上的元素均為0，對角線以外的其它元素都為常數(shù)a。當a=1時的失真函數(shù)稱為漢明失真函數(shù)。 第二種：d(ui,vj)=(vjui)2這種函數(shù)稱為平方誤差失真函數(shù)，失真矩陣稱為平方誤差失真矩陣。若信源符號代表輸出信號的幅度值，則較大的幅度失真比較小的幅度失真引起的錯誤更為嚴重，嚴重程度用平方表示。失真函數(shù)是根據(jù)人們的實際需要和失真引起的損失、風險、主觀感覺上的差別大小等因素人為規(guī)定的。三、平均失真度若已知試驗信道的傳遞概率，則平均失真度為： 若平均失真度 不大于我們所允許的失真限度D，我們稱此為保真度準則。凡滿足保真度準則

8、的這些試驗信道稱為D失真許可的試驗信道。把所有D失真許可的試驗信道組成一個集合，用符號BD 表示。平均失真度的意義 是在平均意義上，從總體上對整個系統(tǒng)失真情況的描述。它是信源統(tǒng)計特性p(ui) 、信道統(tǒng)計特性p(vj/ui )和失真度d(ui,vj)的函數(shù) 。當p(ui)，p(vj/ui )和d(ui,vj)給定后，平均失真度就不是一個隨機變量了，而是一個確定的量。如果信源和失真度一定， 就只是信道統(tǒng)計特性的函數(shù)。信道傳遞概率不同，平均失真度隨之改變。N 次擴展信道的平均失真度N次擴展單符號離散無記憶信源Uu1,u2,ur的N次擴展信源UN =u1u2uN ，在信道中的傳遞作用相當于單符號離散

9、無記憶信道的N次擴展信道，輸出也是一個隨機變量序列VN =V1V2VN 。此時輸入共有rN個不同的符號信道的輸出共有sN個不同的符號定義離散無記憶信道U P(V/U) V的N次擴展信道的輸入序列i和輸出序列j之間的失真函數(shù)為上式說明：離散無記憶信道的N次擴展信道輸入輸出之間的失真，等于輸入序列i中N個信源符號ui1,ui2,uiN各自通過信道U P(V/U) V，分別輸出對應(yīng)的N個信宿符號vj1,vj2,vjN后所引起的N個單符號失真d(uik ,vjk)(k=1,2, ,N)之和。N次擴展的失真度 定義N次離散無記憶擴展信源和信道的平均失真度為 ，則 “N次擴展”與“單符號”平均失真度的關(guān)系

10、由擴展信源和擴展信道的無記憶性有實際上， (k=1,2, ,N)是同一信源U在 N個不同時刻通過同一信道U P(Y/U) Y所造成的平均失真度，因此都等于單符號信源U通過信道U P(Y/U) Y所造成的平均失真度，即上式說明：離散無記憶N次擴展信源通過離散無記憶N次擴展信道的平均失真度是單符號信源通過單符號信道的平均失真度的N倍。N次擴展的保真度準則 離散無記憶N次擴展信源通過離散無記憶N次擴展信道的保真度準則為 凡滿足保真度準則的這些試驗信道稱為D失真許可的試驗信道。把所有D失真許可的試驗信道組成一個集合，用符號BD 表示。7.2 信息率失真函數(shù)及其性質(zhì)1、信息率失真函數(shù) 當信源和失真函數(shù)給

11、定后，我們總希望在滿足保真度準則下尋找平均互信息的最小值。也就是在BD 中找一個信道，使平均互信息最?。ㄇ髽O小值）。這個最小值就是在 的條件下，信源必須傳輸?shù)淖钚∑骄畔⒘俊?改變試驗信道求平均互信息的最小值，實質(zhì)上是選擇一種編碼方式使信息傳輸率為最小。單符號信源和單符號信道的信息率失真函數(shù)在信源和失真度給定以后，BD是滿足保真 度準則 的試驗信道集合，平均互信息I(U;V)是信道傳遞概率p(vj /ui)的下凸函數(shù)，所以在BD中一定可以找到某個試驗信道，使I(U;V)達到最小，即這個最小值R(D)稱為信息率失真函數(shù).物理意義：對于給定的信源，在 的條件下，信息率允許壓縮到的最小值?！癗次擴展

12、”的信息率失真函數(shù) 對于離散無記憶信源的N次擴展信源和離散無記憶信道的N次擴展信道，在所有滿足保真度準則 的N維試驗信道集合中，一定可以尋找到某個信道使平均互信息取最小值RN(D)，這個最小值稱為它的信息率失真函數(shù)。由信源和信道的無記憶性，可以證明RN(D)=NR(D)。例:設(shè)信源有2n種不同的符號，即， 且該信源為一等概信源，即 若選定失真函數(shù)為漢明失真如允許的平均失真為D=0 即：不允許有失真，則必須用下圖所示的信道進行傳輸。此時信道的信息傳輸率若D=1/2，為了滿足保真度準則，我們用下列信道進行傳輸。 此時這個信道（信源編碼方法）的平均失真為 保真度準則要求 為了能用盡保真度準則所規(guī)定的

13、允許失真范圍，可取 由于這個信道的傳遞概率等于1或0，所以噪聲熵一定為0這表明：如允許平均失真達到規(guī)定值 ，那么我們就可以只要傳送 這n個符號，并以 來代替 這n個符號，以致使信息傳輸率降低了 ，即信源輸出信息率可壓縮 所求得的 如能求出 ，則信源輸出信息率可望進一步壓縮。此例子使我們初步領(lǐng)悟到信息率失真函數(shù)的含義和作用2.信息率失真函數(shù)的性質(zhì)(1) 信息率失真函數(shù)的定義域什么是率失真函數(shù)的定義域允許平均失真度：率失真函數(shù)中的自變量D，也就是人們規(guī)定的平均失真度 的上限值。率失真函數(shù)的定義域問題就是在信源和失真函數(shù)已知的情況下，討論允許失真限度D 的最小和最大值問題。D的選取必須根據(jù)固定信源X

14、的統(tǒng)計特性P(X)和選定的失真函數(shù)d(ui ,vj)，在平均失真度 的可能取值范圍內(nèi)。（1）失真度限度的最小值Dmin 這就是不允許有任何失真的情況。此時要求失真矩陣中每行至少有一個零元素，才能達到零。直觀的理解就是，若信源要求無失真地傳輸，則信息傳輸率至少應(yīng)等于信源輸出的信息量-信源熵 R(0)=H(U)一般來說 欲讓上式的和式最小，每一項均應(yīng)最小，應(yīng)選擇合適的試驗信道使和式最小。若令失真矩陣 D中某一行中的最小元素所對應(yīng)的試驗信道的轉(zhuǎn)移概率為1，其余為0，則和式最小，即：則可得信源的最小平均失真度為：例:設(shè)信源為 信宿為(0,1)失真矩陣為計算得連續(xù)信源有 。這時雖然信源熵是有限的，但信息

15、量是無窮大。實際信道容量總是有限的，無失真?zhèn)魉瓦@種連續(xù)信息是不可能的。只有當允許失真,并且R(D )為有限值時，傳送才是可能的。 （2）失真限度的 最大值Dmax根據(jù)R(D)的定義知，R(D)是在一定的約束條件下平均互信息的極小值。已知平均互信息是非負的，其下限值為零。由此可得，R(D)也是非 負的，它的下限值也為 零。所以當R(D)等于零 時，所對應(yīng)的平均失真 度的下界就是失真限度 的 最大值 Dmax。如圖所 示。設(shè)：當 時，R(D)已達到下限值“0”。若失真限度更大時，即當DDmax時，從數(shù)學意義上講，因為R(D)是非負函數(shù)，所以它仍只能等于0。這相當于輸入U和輸出V統(tǒng)計獨立。此時 而D

16、max就是在R(D)=0時所對應(yīng)的平均失真度的最小值。則可得輸入U和輸出V統(tǒng)計獨立條件下的最小平均失真。例4.1.1 二元信源 ，相應(yīng)的失真矩陣為 ，計算Dmax 及相應(yīng)的試驗信道矩陣。先計算Dj ： D10.6 D2=0.4所以 Dmax=min(D1 , D2)=0.4相應(yīng)的試驗信道矩陣為結(jié) 論R(D)的定義域為 (Dmin, Dmax)；一般情況下Dmin =0， R(Dmin)=H(U)；當DDmax時， R(D)=0；當DminD Dmax時， 0R(D)H(U)。信息率失真函數(shù)的性質(zhì)2、 率失真函數(shù)對允許平均失真度的下凸性對任一01和任意平均失真度D，DDmax，有 RD+(1)D

17、R(D)+(1)R(D)3、 率失真函數(shù)的單調(diào)遞減和連續(xù)性由于函數(shù)R(D)具有凸狀性，保證了它在定義域內(nèi)是連續(xù)的。在DminD Dmax時：在D=Dmax處，除某些特例外，S將從某一個負值跳到0，S在此點不連續(xù)。在D的定義域0, Dmax內(nèi)，除某些特例外，S將是D的連續(xù)函數(shù)。1、連續(xù)信源的信息率失真函數(shù)的參量表達式2、高斯信源的信息率失真函數(shù)7.6 連續(xù)信源的信息率失真函數(shù)條件信源XR=(,) 信源X的概率密度函數(shù)為p(x)信道的傳遞概率密度函數(shù)為p(y /x)信宿YR=(,)信宿Y的概率密度函數(shù)為p(y)X和Y之間的失真度d(x,y)01、連續(xù)信源的信息率失真函數(shù)的參量表達式平均失真度為平均

18、互信息為BD為滿足保真度準則 的所有試驗信道集合。信息率失真函數(shù)為相當于離散信源中求極小值，嚴格地說，連續(xù)集合未必存在極小值，但是一定存在下確界。R(D)函數(shù)的參量表達式：一般情況，在失真度積分存在情況下， R(D) 的解存在，直接求解困難，用迭代算法計算機求解，只在特殊情況下求解比較簡單。(1) 高斯信源特性及失真度設(shè)連續(xù)信源的概率密度為正態(tài)分布函數(shù)數(shù)學期望為方差為定義其失真函數(shù)為d(u,v)=(uv)2，即把均方誤差作為失真，表明通信系統(tǒng)中輸入輸出之間誤差越大，失真越嚴重，嚴重程度隨誤差增大呈平方增長。2、 高斯信源的信息率失真函數(shù)根據(jù)詹森不等式：下面討論 取不同值時的R（D）函數(shù)值12(

19、2) 曲線圖說明 曲線如右圖所示。當信源均值不為0時，仍有這個結(jié)果，因為高斯信源的熵只與隨機變量的方差有關(guān)，與均值無關(guān)。當D=2時，R(D)=0 ：這就是說，如果允許失真（均方誤差）等于信源的方差，只需用確知的均值m來表示信源的輸出，不需要傳送信源的任何實際輸出；當D=0時，R(D)：這點說明在連續(xù)信源情況下，要毫無失真地傳送信源的輸出是不可能的。即要毫無失真地傳送信源的輸出必須要求信道具有無限大的容量；當0D2時：即允許一定的失真，傳送信源的信息率可以降低，意味著信源的信息率可以壓縮，連續(xù)信源的率失真理論正是連續(xù)信源量化、壓縮的理論基礎(chǔ)。當D=0.252時，R(D)=1比特/符號：這就是說在

20、允許均方誤差小于或等于0.252時，連續(xù)信號的每個樣本值最少需用一個二進制符號來傳輸。由香農(nóng)第三定理證明了這種壓縮編碼是存在的，然而實際上要找到這種可實現(xiàn)的最佳編碼方法很困難的。信道容量與信息率失真函數(shù)的比較 從數(shù)學上說，信道容量和信息率失真函數(shù)的問題，都是求平均互信息極值問題，有相仿之處，故常稱為對偶問題。(1) 求極值問題(2) 特性(3) 解決的問題(1) 求極值問題平均互信息I(X;Y)是信源概率分布p(xi)(i=1,2,n)或概率密度函數(shù)p(x)的上凸函數(shù)，根據(jù)上凸函數(shù)定義，如果I(X;Y)在定義域內(nèi)對p(xi) 的極值存在，則該極值一定是極大值。信道容量就是在固定信道情況下，求平

21、均互信息極大值的問題，即I(X;Y)又是信道轉(zhuǎn)移概率分布p(vj /ui)或條件概率密度函數(shù)p(y/x)的下凸函數(shù)，因此在滿足保真度準則條件下，I(X;Y)對p(vj /ui) 的條件極值若存在，則一定是極小值。信息率失真函數(shù)就是在試驗信道（滿足保真度準則的信道）中尋找平均互信息極小值的問題，即(2) 特 性信道容量C一旦求出后，就只與信道轉(zhuǎn)移概率p(yj /xi)有關(guān)，反映信道特性，與信源特性無關(guān)；信息率失真函數(shù)R(D)一旦求出后，就只與信源概率分布p(xi)有關(guān)，反映信源特性，與信道特性無關(guān)。(3) 解決的問題信道容量是為了解決通信的可靠性問題，是信息傳輸?shù)睦碚摶A(chǔ)，通過信道編碼增加信息的

22、冗余度來實現(xiàn)；信息率失真函數(shù)是為了解決通信的有效性問題，是信源壓縮的理論基礎(chǔ)，通過信源編碼減少信息的冗余度來實現(xiàn)。CR(D) 的上凸函數(shù) 的下凸函數(shù) 的極大值 的條件極小值 的函數(shù) 的函數(shù)僅與信道特性有關(guān)僅與信源特性有關(guān)解決可靠性問題解決有效性問題信息傳輸?shù)幕A(chǔ)信源壓縮的基礎(chǔ)7.7 保真度準則下的信源編碼定理 定理7.1 保真度準則下的信源編碼定理 設(shè)R(D)為一離散無記憶信源的信息率失真函數(shù)，并且有有限的失真測度。對于任意的 ，以及任意足夠長的碼長n，則一定存在一種信源編碼C，其碼字個數(shù)為而編碼后的平均失真度如果用二元編碼，則： 該定理稱為香農(nóng)第三定理。它告訴我們，對于任何失真度D，只要碼長足夠長，總可以找到一種編碼C，使編碼后的每個信源符號的信息傳輸率 定理7.2（信源編碼逆定理）不存在平均失真度D，而平均信息傳輸率 的任何信源編碼。即對任意碼長n的信源碼C，若碼字個數(shù) ，一定 該定理告訴我們：如果編碼后平均每個信源符號的信息傳輸率R 小于信息率失真函數(shù)R(D)，就不能在保真度準則下再現(xiàn)信源的消息。這理論再一次地告訴我們，要在點對點的通信中有效可靠地傳輸信息，可以把信源編碼和信道編碼分成兩部分進