限失真的信源編碼

限失真的信源編碼第1頁，課件共36頁，創(chuàng)作于2023年2月

限失真的信源編碼問題允許一定的失真度下，能將信源信息壓縮到什么程度？（最少需要多少比特才能在收端描述信源？）一定的信息傳輸率R下，允許的最大失真是多少？相關(guān)問題失真如何度量？率失真函數(shù)如何計算？第2頁，課件共36頁，創(chuàng)作于2023年2月7.1失真測度7.1.1失真函數(shù)假如某一信源X,輸出樣值xi,xi∈{a1,a2,…an},經(jīng)信道傳輸后變成yj,yj∈{b1,b2,…bm},如果:

xi＝y(tǒng)j

沒有失真

xi≠yj

產(chǎn)生失真失真的大小,用一個量來表示,即失真函數(shù)d(xi,yj),以衡量用yj代替xi所引起的失真程度。失真函數(shù)定義為：第3頁，課件共36頁，創(chuàng)作于2023年2月將所有的d(xi,yj)排列起來,用矩陣表示為:失真函數(shù)d(xi,yj)：描述了某個信源符號通過傳輸后失真的大小第4頁，課件共36頁，創(chuàng)作于2023年2月例：設(shè)信源符號序列為X={0,1},接收端收到符號序列為Y={0,1,2},規(guī)定失真函數(shù)為

d(0,0)＝d(1,1)=0d(0,1)＝d(1,0)=1d(0,2)＝d(1,2)=0.5第5頁，課件共36頁，創(chuàng)作于2023年2月失真函數(shù)形式可以根據(jù)需要任意選取,最常用的有:均方失真:絕對失真:相對失真:誤碼失真:適于連續(xù)信源適于離散信源第6頁，課件共36頁，創(chuàng)作于2023年2月假設(shè)離散矢量N長符號序列為X=[X1,X2,X3,…,XN](Xi取值為{x1,x2,…,xn}經(jīng)信道傳輸后，接收端收到的N長符號序列為Y=[Y1,Y2,Y3,…,YN](Yj取值為{x1,x2,…,xn}則失真函數(shù)定義為第7頁，課件共36頁，創(chuàng)作于2023年2月7.1.2平均失真設(shè)離散信源經(jīng)信道傳輸后輸出序列為Y=[Y1,Y2,Y3,…,YN]失真矩陣為第8頁，課件共36頁，創(chuàng)作于2023年2月xi和yj都是隨機變量,所以失真函數(shù)d(xi,yj)也是隨機變量,限失真時的失真值只能用數(shù)學期望表示將失真函數(shù)的數(shù)學期望稱為平均失真：描述某個信源在某一試驗信道傳輸下的失真大小,它對信源和信道進行了統(tǒng)計平均,是從總體上描述整個系統(tǒng)的失真。第9頁，課件共36頁，創(chuàng)作于2023年2月假設(shè)離散矢量N長符號序列為X=[X1,X2,X3,…,XN](Xi取值為{x1,x2,…,xn}經(jīng)信道傳輸后，接收端收到的N長符號序列為Y=[Y1,Y2,Y3,…,YN](Yj取值為{x1,x2,…,xn}則平均失真度為第10頁，課件共36頁，創(chuàng)作于2023年2月7.2信息率失真函數(shù)7.2.1D允許信道（試驗信道）無論是無噪信道還是有噪信道:

R＜C總能找到一種編碼使在信道上能以任意小的錯誤概率,以任意接近C的傳輸率來傳送信息

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

第11頁，課件共36頁，創(chuàng)作于2023年2月若平均失真度不大于我們所允許的失真,即則稱此為保真度準則將滿足保真度準則的所有信道稱為失真度D允許信道（也稱D允許的試驗信道）記為對于離散無記憶信道，相應(yīng)地有第12頁，課件共36頁，創(chuàng)作于2023年2月7.2.2信息率失真函數(shù)的定義在D失真允許的試驗信道中尋找一個信道，使給定的信源經(jīng)過此信道傳輸時，其信道傳輸率I(X;Y)達到最小，定義為信息率失真函數(shù)R(D),也稱為率失真函數(shù)，即對于離散無記憶信道第13頁，課件共36頁，創(chuàng)作于2023年2月例已知編碼器輸入的概率分布為p(x)={0.5,0.5}信道矩陣求互信息第14頁，課件共36頁，創(chuàng)作于2023年2月編碼器輸入的概率分布為p(x)={0.5,0.5}信道矩陣求互信息可見當p(x)一定時,I(X,Y)隨p(yj|xi)而變。因為p(x)分布一定時,信道受干擾不同所能傳遞的信息量是不同的。當p(x)一定時,I(X,Y)是關(guān)于p(yj|xi)的下凸函數(shù)。因此當改變p(yj|xi)時,I(X,Y)有一極小值。第15頁，課件共36頁，創(chuàng)作于2023年2月平均互信息I(X;Y)：信源的概率分布p(xi)的上凸函數(shù)。信道傳遞概率p(yj|xi)的下凸函數(shù)。信道容量：信息率失真函數(shù)：

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

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

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

an+1→an,an+2→an,…a2n→an即不發(fā)生差錯時失真為0,出錯失真為1研究在一定編碼條件下信息壓縮的程度。第20頁，課件共36頁，創(chuàng)作于2023年2月平均失真

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

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

壓縮第21頁，課件共36頁，創(chuàng)作于2023年2月7.2.3信息率失真函數(shù)的性質(zhì)1、R(D)的定義域率失真的定義域問題就是在信源和失真函數(shù)已知的情況下,討論允許平均失真度D的最小和最大取值問題。由于平均失真度是非負實數(shù)d(xi,yj)的數(shù)學期望,因此也是非負的實數(shù),即的下界是0。允許平均失真度能否達到其下限值0,與單個符號的失真函數(shù)有關(guān)。第22頁，課件共36頁，創(chuàng)作于2023年2月R(D)的定義域Dmin和R(Dmin)信源的最小平均失真度：只有當失真矩陣的每一行至少有一個0元素時,信源的平均失真度才能達到下限值0。當Dmin=0,即信源不允許任何失真時,信息率至少應(yīng)等于信源輸出的平均信息量—信息熵。即R(0)=H(X)第23頁，課件共36頁，創(chuàng)作于2023年2月R(D)的定義域因為實際信道總是有干擾的,其容量有限,要無失真地傳送連續(xù)信息是不可能的。當允許有一定失真時,R(D)將為有限值,傳送才是可能的。對于連續(xù)信源：第24頁，課件共36頁，創(chuàng)作于2023年2月R(D)的定義域R(D)的定義域為[Dmin，Dmax]。通常Dmin=0，R(Dmin)=H(X)當D≥Dmax時,R(D)=0當0≤D≤Dmax時,0＜R(D)＜H(X)第25頁，課件共36頁，創(chuàng)作于2023年2月R(D)的定義域Dmax：定義域的上限。Dmax是滿足R(D)=0時所有的平均失真度中的最小值。由于I(X,Y)是非負函數(shù),而R(D)是在約束條件下的I(X,Y)的最小值,所以R(D)也是一個非負函數(shù),它的下限值是零。

R(D)≥0第26頁，課件共36頁，創(chuàng)作于2023年2月R(D)的定義域由于I(X,Y)=0的充要條件是X與Y統(tǒng)計獨立,即：第27頁，課件共36頁，創(chuàng)作于2023年2月例4-3:設(shè)輸入輸出符號表為X=Y={0,1},輸入概率分布p(x)={1/3,2/3},失真矩陣求：Dmin

和Dmax

失真矩陣的每一行至少有一個0元素時,Dmin=0第28頁，課件共36頁，創(chuàng)作于2023年2月例:設(shè)輸入輸出符號表為X=Y={0,1},輸入概率分布p(x)={1/3,2/3},失真矩陣

求：Dmin

和Dmax

第29頁，課件共36頁，創(chuàng)作于2023年2月信息率失真函數(shù)的性質(zhì)1、R(D)是非負的實數(shù),R(D)≥0。其定義域為0～Dmax,其值為0～H(X)。當D＞Dmax時,R(D)≡02、R(D)是關(guān)于D的下凸函數(shù)R(D)在定義域內(nèi)是失真度D的U型下凸函數(shù)3、R(D)的單調(diào)遞減性及連續(xù)性容許的失真度越大，所要求的信息率越小。反之亦然。第30頁，課件共36頁，創(chuàng)作于2023年2月第31頁，課件共36頁，創(chuàng)作于2023年2月離散信源R(D)計算給定信源概率pi和失真函數(shù)dij,就可以求得該信源的R(D)函數(shù)。它是在保真度準則下求極小值的問題。但要得到它的顯式表達式,一般比較困難通常用參量表達式。即使如此,除簡單的情況外實際計算還是困難的,只能用迭代逐級逼近的方法。第32頁，課件共36頁，創(chuàng)作于2023年2月二元對稱信源的R(D)函數(shù)設(shè)二元對稱信源X={0,1},其概率分布p(x)=[p,1-p],接收變量Y={0,1},漢明失真矩陣因而最小允許失真度Dmin=0。并能找到滿足該最小失真的試驗信道,且是一個無噪無損信道,其信道矩陣為第33頁，課件共36頁，創(chuàng)作于2023年2月這個試驗信道能正確傳送信源符號x=1,而傳送信源符號x=0時,接收符號一定為y=1凡發(fā)送符號x=0時,一定都錯了。而x=0出現(xiàn)的概率為p,所以信道的平均失真度為p

。在這種試驗信道條件下，可計算得

R(Dmax)=R(p)=0第34頁，課件共36頁，創(chuàng)作于2023年2月7.3限失真信源編碼定理和逆定理定理7.3.1限失真信源編碼定理設(shè)離散n長序列無記憶信源為單字符失真函數(shù)為d（xik，yjk），給定單字符失真度下的信息率失真函數(shù)R(D)，當n足夠