信息論與編碼第七章

信息論與編碼第七章第一頁，共三十六頁，2022年，8月28日如果R>C，在任意信道上都不可能實現(xiàn)錯誤譯碼概率無線小的無失真?zhèn)鬏?；或者說要實現(xiàn)錯誤譯碼概率任意小，在任何信道上傳輸都必然產(chǎn)生失真。在信道傳輸信息時，通常并不需要完全無失真。信宿對真實度的要求：實際語音信號：20Hz～8KHz人耳能夠分辨：300Hz～3400Hz圖象色差：可達足夠多視覺分辨：256級（黑白）已足夠

所以實際生活當中，通?？偸且ＷC在一定質(zhì)量的前提下在信宿近似地再現(xiàn)信源輸出的信息，或者說在保真度準則下允許信源輸出存在一定的失真。第二頁，共三十六頁，2022年，8月28日

失真如何度量？率失真函數(shù)如何計算？限失真的信源編碼問題允許一定的失真度下，能將信源信息壓縮到什么程度？（最少需要多少比特才能在收端描述信源？）第三頁，共三十六頁，2022年，8月28日7.1失真測度7.1.1失真函數(shù)失真的大小,用一個量來表示,即失真函數(shù)d(xi,yj),以衡量用yj代替xi所引起的失真程度。假設離散信號源為=經(jīng)過信道傳輸后的輸出序列為Y=xi≠yj

產(chǎn)生失真xi＝y(tǒng)j

沒有失真

第四頁，共三十六頁，2022年，8月28日將所有的d(xi,yj)排列起來,用矩陣表示為:失真函數(shù)d(xi,yj)：描述了某個信源符號通過傳輸后失真的大小。失真函數(shù)的定義為：=第五頁，共三十六頁，2022年，8月28日【例7.1】設信源符號序列為X={0,1},接收端收到符號序列為Y={0,1,2},規(guī)定失真函數(shù)為＝＝0＝＝1＝＝0.5

求失真序列解：由失真矩陣得==第六頁，共三十六頁，2022年，8月28日失真函數(shù)形式可以根據(jù)需要任意選取,最常用的有:均方失真:絕對失真:相對失真:誤碼失真:適于連續(xù)信源適于離散信源第七頁，共三十六頁，2022年，8月28日假設離散矢量N長符號序列為經(jīng)信道傳輸后，接收端收到的N長符號序列為則失真函數(shù)定義為失真函數(shù)的定義可以推廣到矢量傳輸?shù)那闆r，X=Y=第八頁，共三十六頁，2022年，8月28日【例7.2】假定離散矢量信源N=3，輸出矢量序列為,其中，的取值為；經(jīng)信道傳輸后的輸出為，其中，的取值為。定義失真函數(shù)為求矢量失真矩陣

解：由矢量失真函數(shù)的定義得第九頁，共三十六頁，2022年，8月28日類似的可以得到其他元素數(shù)值，矢量矩陣為第十頁，共三十六頁，2022年，8月28日平均失真假定離散信源為經(jīng)信道傳輸后輸出序列為失真矩陣為第十一頁，共三十六頁，2022年，8月28日

和

都是隨機變量,所以失真函數(shù)

也是隨機變量,限失真時的失真值只能用數(shù)學期望表示將失真函數(shù)的數(shù)學期望稱為平均失真：描述某個信源在某一試驗信道傳輸下的失真大小,它對信源和信道進行了統(tǒng)計平均,是從總體上描述整個系統(tǒng)的失真。第十二頁，共三十六頁，2022年，8月28日假設離散矢量N長符號序列經(jīng)信道傳輸后，接收端收到的N長符號序列為Y=[Y1,Y2,Y3,…,YN]X=[X1,X2,X3,…,XN]則平均失真度為平均失真是對給定信源分布

在給定轉(zhuǎn)移概率分布

為的信道中傳輸時的失真總體量度。第十三頁，共三十六頁，2022年，8月28日7.2信息率失真函數(shù)7.2.1允許信道（試驗信道）無論是無噪信道還是有噪信道:R＜C總能找到一種編碼使在信道上能以任意小的錯誤概率,以任意接近C的傳輸率來傳送信息

R＞C就必須對信源壓縮,使其壓縮后信息傳輸率R’小于信道容量C,但同時要保證壓縮所引入的失真不超過預先規(guī)定的限度。信息壓縮問題就是對于給定的信源,在滿足平均失真

的前提下,使信息率盡可能小。第十四頁，共三十六頁，2022年，8月28日若平均失真度不大于我們所允許的失真,即則稱此為保真度準則將滿足保真度準則的所有信道稱為失真度D允許信道（也稱D允許的試驗信道）記為對于離散無記憶信道，相應地有第十五頁，共三十六頁，2022年，8月28日7.2.2信息率失真函數(shù)的定義在失真允許的試驗信道中尋找一個信道，使給定的信源經(jīng)過此信道傳輸時，其信道傳輸率

達到最小，定義為信息率失真函數(shù),也稱為率失真函數(shù)，即對于離散無記憶信道第十六頁，共三十六頁，2022年，8月28日例已知編碼器輸入的概率分布為p(x)={0.5,0.5}信道矩陣求互信息第十七頁，共三十六頁，2022年，8月28日編碼器輸入的概率分布為p(x)={0.5,0.5}信道矩陣求互信息可見當p(x)一定時,I(X,Y)隨p(yj|xi)而變。第十八頁，共三十六頁，2022年，8月28日平均互信息I(X;Y)：信源的概率分布p(xi)的上凸函數(shù)。信道傳遞概率p(yj|xi)的下凸函數(shù)。信道容量：信息率失真函數(shù)：

第十九頁，共三十六頁，2022年，8月28日

一旦找到了信道容量,它就與信源不再有關,而是信道特性的參量,隨信道特性的變化而變化不同的信道其信道容量不同。假定信道固定的前提下,選擇一種試驗信源使信息傳輸率最大。它所反映的是信道傳輸信息的能力,是信道可靠傳送的最大信息傳輸率。信息率失真函數(shù)：假定信源給定的情況下,用戶可以容忍的失真度內(nèi)再現(xiàn)信源消息所必須獲得的最小平均信息量。它反映的是信源可以壓縮的程度,是在滿足一定失真度要求下信源可壓縮的最低值。第二十頁，共三十六頁，2022年，8月28日率失真函數(shù)一旦找到,就與求極值過程中選擇的試驗信道不再有關,而只是信源特性的參量不同的信源其R(D)不同。研究信道容量：充分利用已給信道,使傳輸?shù)男畔⒘孔畲?而發(fā)生錯誤的概率任意小。研究信息率失真函數(shù)：解決在已知信源和允許失真度D的條件下,使信源必須傳送給信宿的信息率最小。即用盡可能少的碼符號盡快地傳送盡可能多的信源消息,以提高通信的有效性。第二十一頁，共三十六頁，2022年，8月28日例:設信源的符號表為A={al,a2,…,a2n},概率分布為p(ai)=1/2n,i=1,2…2n,失真函數(shù)規(guī)定為

信源熵

如果對信源進行不失真編碼,平均每個符號至少需要log2n個二進制碼元。現(xiàn)在假定允許有一定失真,假設失真限度為D=1/2設想采用下面的編碼方案：

a1→a1，a2→a2，…an→an

an+1→an,an+2→an,…a2n→an即不發(fā)生差錯時失真為0,出錯失真為1研究在一定編碼條件下信息壓縮的程度。第二十二頁，共三十六頁，2022年，8月28日平均失真

則輸出熵H(Y)由該信道模型圖看出,它是一個確定信道

pij=1(或0)，H(Y|X)=0

壓縮第二十三頁，共三十六頁，2022年，8月28日7.2.3信息率失真函數(shù)的性質(zhì)1、R(D)的定義域率失真的定義域問題就是在信源和失真函數(shù)已知的情況下,討論允許平均失真度D的最小和最大取值問題。由于平均失真度是非負實數(shù)d(xi,yj)的數(shù)學期望,因此也是非負的實數(shù),即的下界是0。允許平均失真度能否達到其下限值0,與單個符號的失真函數(shù)有關。第二十四頁，共三十六頁，2022年，8月28日信源的最小平均失真度：只有當失真矩陣的每一行至少有一個0元素時,信源的平均失真度才能達到下限值0。當Dmin=0,即信源不允許任何失真時,信息率至少應等于信源輸出的平均信息量—信息熵。即R(0)=H(X)當不滿足失真矩陣的每一行至少有一個0元素時,第二十五頁，共三十六頁，2022年，8月28日通常Dmin=0，R(Dmin)=H(X)當

D≥Dmax時,R(D)=0當0≤D≤Dmax時,0＜R(D)＜H(X)R(D)的定義域為[Dmin，Dmax

]。

第二十六頁，共三十六頁，2022年，8月28日Dmax：定義域的上限。Dmax是滿足R(D)=0時所有的平均失真度中的最小值。R(D)≥0由于I(X,Y)是非負函數(shù),而R(D)是在約束條件下的I(X,Y)的最小值,所以R(D)也是一個非負函數(shù),它的下限值是零。第二十七頁，共三十六頁，2022年，8月28日

由于I(X,Y)

=0的充要條件是X與Y統(tǒng)計獨立,即：第二十八頁，共三十六頁，2022年，8月28日例:設輸入輸出符號表為X=Y={0,1},輸入概率分布p(x)={1/3,2/3},失真矩陣求：Dmin

和Dmax

失真矩陣的每一行至少有一個0元素時,Dmin=0第二十九頁，共三十六頁，2022年，8月28日例:設輸入輸出符號表為X=Y={0,1},輸入概率分布p(x)={1/3,2/3},失真矩陣

求：Dmin

和Dmax

第三十頁，共三十六頁，2022年，8月28日信息率失真函數(shù)的性質(zhì)1、R(D)是非負的實數(shù),

R(D)≥0。

其定義域為0～Dmax,其值為0～H(X)。

當D＞Dmax時,R(D)≡02、R(D)是關于D的下凸函數(shù)

R(D)在定義域內(nèi)是失真度D的U型下凸函數(shù)3、R(D)的單調(diào)遞減性及連續(xù)性容許的失真度越大，所要求的信息率越小。反之亦然。第三十一頁，共三十六頁，2022年，8月28日第三十二頁，共三十六頁，2022年，8月28日離散信源R(D)計算給定信源概率pi和失真函數(shù)dij,就可以求得該信源的R(D)函數(shù)。它是在保真度準則下求極小值的問題。但要得到它的顯式表達式,一般比較困難通常用參量表達式。即使如此,除簡單的情況外實際計算還是困難的,只能用迭代逐級逼近的方法。第三十三頁，共三十六頁，2022年，8月28日7.3限失真信源編碼定理和逆定理定理7.1限失真信源編碼定理設離散n長序列無記憶信源為單字符失真函數(shù)為，給定單字符失真度下的信息率失真函數(shù)，對任意和，可以找到滿足保真度準則的允許碼，當n足夠大時，其速率R為7.3.1限失真信源編碼定理碼字數(shù)目

為：第三十四頁，共三十六頁，2022年，8月28日7.3.2限失真信源編碼逆定理定理7.2