1、第五章 限失真信源編碼和率失真函數(shù)5.1 失真度和率失真函數(shù)5.2 率失真函數(shù)的計算5.3 限失真信源編碼定理 在第 3章,討論了離散信源的無失真信源編碼,它是一種冗余度壓縮編碼,可以對信源輸出的信息進行有效地表示,并且可以保證信源輸出的信號在編譯碼前后不會有任何失真 .從信號攜帶信息的角度看,還可以保證編譯碼前后的信號具有相同的信息熵,因此冗余度壓縮編碼是無失真的保熵的編碼 . 但是無失真的保熵的編碼并非是必需的,有時候也不可能實現(xiàn) .比如,在傳送語音信號時,由于人耳接受的帶寬和分辨是有限的,因此可以把頻譜范圍從 20 Hz20 kHz的語音信號去掉低端和高端的頻率,看成帶寬只有 3003

2、400 Hz的信號 .這樣雖然會有一些失真,但是這種失真是允許的 .再比如,在傳送活動圖像時,由于人眼的視覺暫留特性,我們只需每秒種傳送 25幀的靜止圖像,人們看到的就是連貫的活動圖像 .所以在實際生活中,通?？偸且笤诒ＷC一定質(zhì)量的前提下,在信宿近似地再現(xiàn)信源輸出的信息 .因此,實際的信息傳輸率可以降低 .另一方面,由于受到信息存儲,處理或傳輸設(shè)備的限制而不得不對信源輸出的信號作某種近似的表示 .比如實際信源的輸出常常是連續(xù)的消息,連續(xù)信源的絕對熵 H(S)是無限大 .若要求無失真地傳送連續(xù)信源的消息,則信息傳輸率 R也為無限大 .在信道中,由于帶寬總是有限的,所以信道容量總是受到限制,而實

3、際信源輸出的信息率總是大大超過信道容量(R C) ,因此也就不可能實現(xiàn)完全無失真地傳輸信源的消息 . 如果要把連續(xù)信源的消息離散化,由于信源熵為無窮大,根據(jù)無失真信源編碼定理,要用無窮多個比特數(shù)才能完全無失真地描述它,這在實際中是做不到的,因此必然會帶來一定程度的失真 .在允許一定失真程度的條件下,怎樣用盡可能少的信道符號來表達信源的信息,也就是信源熵所能壓縮的極限或者說編碼后信源輸出的信息率壓縮的極限值,這就是本章要討論的問題限失真信源編碼問題 .限失真信源編碼也稱保真度準則下的信源編碼、熵壓縮編碼或者稱信息率失真理論,它是量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ) . 如果無失真的冗余度

4、壓縮編碼主要是針對離散信源的,那么,有失真的熵壓縮編碼主要是針對連續(xù)信源 .本章討論的是離散無記憶信源的限失真信源編碼理論,這樣便于理解率失真理論的基本概念 . 我們討論的物理模型仍然是信源編碼器,編碼器的輸入符號集 X = x1, x2, , xr ,輸出符號集 Y = y1, y2, , ys .編碼器可以看作一個廣義的信道, X是信道的輸入, Y是信道的輸出 .與無失真信源編碼不同,這時從輸入到輸出的映射是一個多對一的映射,它是不可逆的,信源符號序列和碼符號序列之間的差異就是編碼時引入的失真 . 無失真信源編碼定理和信道編碼定理得出這樣一個結(jié)論:無論是無噪信道還是有噪信道,只要信道的信息

5、傳輸率R小于信道容量C,總能找到一種編碼,在信道上以任意小的錯誤概率和任意接近信道容量C的信息率傳輸消息.反之,若信道信息傳輸率R大于信道容量C,一定不能使傳輸錯誤概率任意小而實現(xiàn)無失真?zhèn)鬏? 然而,實際中的信源往往是連續(xù)信源,一般來說,不可能實現(xiàn)完全無失真的傳輸信源的信息.同時,在實際生活中人們并不要求完全無失真地恢復消息,只要求在一定的保真度條件下,近似地恢復信源發(fā)出的消息.這就是本章要討論的限失真信源編碼問題.5.1 失真度和率失真函數(shù)在實際中,允許有一定程度失真的通信模型可描述如下:圖5.1.1 限失真信源編碼模型 設(shè)一個信源產(chǎn)生的 長消息序列為，其復制序列為 ，其中 和 分別取值于有

6、限字母集 和 上。 n),(21nnXXXX),(21nnXXXXiXiX 定義定義5.1.1 設(shè) 是定義在 上的函數(shù)且滿足以下條件: , 對任意的 成立; 當且僅當 則稱 是 上的一個失真測度以下給出幾個常見的失真測度： （1）漢明失真測度) ,(xxd) ,(xxd)(i0) ,(xxd, xx)(ii0,xxdxx) ,(xxdxxxx10（2）平方失真測度（3）絕對失真測度 2) () ,(xxxxdxxxxd) ,(定義定義5.1.2設(shè) 是 上的一個失真測度， 和分別是 和 上的信源序列和其復制序列。定義 和 之間的平均失真測度為：以下我們給出率失真碼和率失真函數(shù)的定義。) ,(xx

7、d),(21nnxxxx),(21nnxxxxnxnx niiinnxxdnxxd1),(1),( 定義定義5.1.3 信源的一個 率失真碼包含編碼和譯碼函數(shù)對 其中平均失真定義為 碼率定義為 )(,()()(,(nnxnnnnnnnxfgxdxpXfgXEdnn),(nM),(nngfMfnn,2, 1:nng:MnR2log1定義定義 5.1.4 設(shè)信源隨機變量 與其復制隨機變量 服從概率分布 ，有失真測度 定義信息率失真函數(shù)為 其中 是對所有滿足以下性質(zhì)的條件概率 取值。在給定的信源概率分布 及條件概率 的乘積所得的聯(lián)合分布 XX)(xp) ,(xxd),(min)(),(),| (XX

8、IDRDXXEdxxQmin)(xxQ)(xp)(xxQ)()() ,(xxQxpxxp下的平均失真信息率失真函數(shù)也有以下等價表達式為了討論率失真函數(shù)的性質(zhì)，我們記 xxDxxdxxpXXEd) ,() ,(),();(min)(),(),(QpIDRDXXEdxxQ于是有xxxxdxxQxpQd) ,()()()( DQdxxQDQ)(:)()( xxxxdxpD) ,()(minmax),(min)()(QpIDRDQQ 如果信源輸出的信息率為 R,在信道容量為 C的信道上傳輸,如果 R C,就會引起失真,需要對信源進行壓縮,使壓縮后信源輸出的信息率 R *小于信道容量 C .壓縮的過程中

9、也會引入失真,但可以控制失真在一個可控的范圍內(nèi),即滿足保真度準則 .從另一方面來說,我們總希望在滿足保真度準則以后,壓縮后的信息傳輸率 R *盡可能地小 . 把信源的壓縮編碼的過程看成一個信道,從這個信道的接收端來說, R *可以用平均互信息 I( X; Y)來表示,壓縮過程中引入的失真可以用 H( X |Y)表示 .我們的任務(wù)就是在滿足保真度準則的 D失真許可的試驗信道集合 BD中尋找某一個信道 p( yj | xi) ,使 I( X; Y)達到最小,即:這個最小值 R(D)就是信息率失真函數(shù),也稱率失真函數(shù),它的單位是比特/信源符號、哈特萊/信源符號或奈特/信源符號 .對于 N維信源符號序

10、列,同樣可以得其信息率失真函數(shù):當信源和信道均為無記憶時, I( X; Y) = NI( X; Y) ,所以有對于給定的信源,在滿足保真度準則 D D的前提下,信息率失真函數(shù) R( D)是信源輸出的信息率允許壓縮到的最小值 .由于 I( X; Y)是 p( yj | xi)的下凸函數(shù),所以在 BD集合中, I( X; Y)的最小值一定存在 .從數(shù)學上來看,平均互信息 I( X; Y)既是信源概率分布 p( xi)的上凸函數(shù),又是信道傳遞概率p ( yj | xi)的下凸函數(shù),因此信道容量 C和信息率失真函數(shù) R(D)具有對偶性 . 信道容量 是指在信道固定前提下,選擇一種信源概率分布使信息傳輸

11、率最大(求極大值) .它反映了信道傳輸信息的能力,是信道可靠傳輸?shù)淖畲笮畔鬏斅?.信道容量與信源無關(guān),是信道特性的參量,不同的信道其信道容量不同 . 信息率失真函數(shù) 是在信源固定,滿足保真度準則的條件下的信息傳輸率的最小值,它反映了滿足一定失真度的條件下信源可以壓縮的程度,也就是滿足失真要求而再現(xiàn)信源消息所必須獲得的最少平均信息量 .R( D)是信源特性的參量, R( D)一旦求出就與求極值過程中選擇的試驗信道無關(guān),不同的信源 R( D)不同 . 這兩個概念的適用范圍是不一樣的,研究信道容量 C是為了在已知信道中盡可能地傳送信息,是為了充分利用已給定的信道,使傳輸?shù)男畔⒘孔畲蠖e誤概率任意小

12、,以提高通信的可靠性,這是信道編碼的問題 . 研究信息率失真函數(shù)是為了在已知信源和允許失真度條件下,使信源輸出的信息率盡可能小,也就是在允許的一定失真度 D的條件下,使信源必須傳送給信宿的信息量最少,盡可能用最少的碼符號來傳送信源信息,使信源的信息可以盡快地傳送出去,以提高通信的有效性,這是信源編碼問題 .定理5.1.1 率失真函數(shù) 具有以下性質(zhì)：(i) 并且 當且僅當 ； (ii) 是 上的下凸函數(shù)；(iii) 是 上的減函數(shù)；(iv) 是 上的連續(xù)函數(shù)。 證明證明 （i）由互信息的性質(zhì)有 進而，由定義知： 的充要條件是存在轉(zhuǎn)移概率 使 )(DR)()(0XHDR0)(DRmaxDD )(D

13、R, 0)(DRmax, 0 D)(DR, 0)()()(),(0XHXXHXHXXI0)(DR),()(DQxxQ0);(XXI即 與 獨立，這時對任意的 成立。 （5.1） 如果 ，則存在滿足上述條件的 ，使得 由 的定義必有 。)()(DQxxQXXxxxQxpxpxxQ)()() ()(, xx0)(DRxxxxdxxQxpXXEd ,) ,()(),(xxxxdxpxp) ,()() (maxD)(DQmaxDD 反之，設(shè) 。由定義知，存在 ，使 定義條件概率 其中 ，易驗證 滿足（5.1）。從而對 的平均失真 ，且此時有 。從而， 。maxDD *xxxxdxpD),()(*max

14、)(xxQ*01xxxxx)(xxQ)()() ,( xxQxpxxpDDXXEdmax),(0),(XXI0)(DR (ii) 設(shè) 。由 的定義知，存在 使于是 所以由于 是轉(zhuǎn)移概率的下凸函數(shù)。所以 10, 0,21DD)(DR)()(iiDQxxQ2 , 1),(),(iDRQpIii)()1 ()()1 (2121QdQdQQd21)1 (DD)1 ()1 (2121DDQQQQ),(QpI)1 (,()1 (2121QQpIDDR)()1 ()(),()1 (),(2121DRDRQpIQpI這就證明了 為 上的下凸函數(shù)。)(DR, 0(iii) 設(shè) ，則 ，從而 (iv) 由微積分知

15、識知凸函數(shù)必連續(xù)，故由(ii), 在 上連續(xù)。再由(i)得， 在 上連續(xù)。210DD )()(21DQDQ).()(12DRDR)(DRmax, 0 D)(DRmax, 0 D5.2 率失真函數(shù)的計算 率失真的計算問題本質(zhì)上是一個條件極值問題,對簡單信源可以找到解析表達式.對一般信源則可用拉格朗日乘子法求解,我們將討論求解過程. 例5.2.1 設(shè) 為二進無記憶信源,服從貝努里分布,即 試計算信源在漢明失真測度下的率失真函數(shù) XppxpX110)()210( p)(DR解 我們先給出);(XXI的一個下界,再證明此下界pXPXEdDr) 1()0 ,(max考慮模2加法運算,即 xxxxxx10

16、注意 )()();(XXHXHXXI是可達的.易見)()()()(XXHphXXXHph(5.2)其中)(ph為二進熵函數(shù).記1XXPXXPprr則有0)(XXPXXHr0log XXPr1log1XXPXXPrr)( ph從而當pDDmax時) 10() 1()01()0(),(XXPXpXXPXpXXEdDpXXPr因此有)()(Dhph,代入(5.2)得)()();(DhphXXI(5.3)以下證(5.3)右端是可達的，即要找到);(XX的一個聯(lián)合分布) ,(xxp，使其對應(yīng)的DXXEd),(而).()(),(DhphXXI求解滿足要求的反向條件概率) (xxQ為此設(shè)aXPr ) 1(并

17、考慮如圖5.2.1的反向.1)0(pXP解決這個問題，我們采用二進對稱信道，使輸出分布為 即)1 ()1 (DaDap或DDpa21 (5.4)21maxpDD時，我們有. 0a同時，由于DDpDpDp21, 1,21,所以. 1aXD1Xa1p1ap圖5.2.1 反向二進對稱信道001D1DD1從而， 1010110XPaXParr即（5.4）定義的a是有意義的。 此時有 DaDDaXXEd)1 (),(且)()()()(),()()(),()(DhphXXHXHXXIDhXXHphXH及(5.3)的下界是可達的。當pD 時，取1XPr可得. 0)(DR 綜上所述，我們得到 pDpDDhph

18、DR, 00),()()()21(p )(DR 1 0 D圖5.2.2 二進信源的率失真函數(shù) 以下討論一般率失真函數(shù)的計算問題，即在約束條件0 xxQ xxxQx, 1(5.5) DxxdxxQxpQdxx) ,()()( 下求解 ),(min)(QpIDR對（5.5）引入待定系數(shù))(x對（5.6）引入待定系數(shù)構(gòu)造 (5.6) (5.7) 拉格朗日函數(shù) xxxxQxQdQpIQJ)()(),()( xxxxxQxpxxQxxQxp)()(log)( xxxxxxQxxxdxxQxp)() ,()(對xxQ 求導，利用Kuhn-Tucker條件得，0, 00, 0)(xxQxxQxxQQJ達到（

19、5.7）中最小值的充要條件是 （5.8）先討論0 xxQ的情況，記xxxQxpxq)() (則 )() (1)()() (log)(/ ,xpxqxxQxpxpxqxxQxpxxQQJx0)() ,()(xxxdxp其中)()() (1)(,xpxpxqxxQxpx。 令)()()(logxpxx則有0)(log) ,() (log)(xxxdxqxxQxp和)() () ,(xexqxxQxxd（5.9）利用（5.5）中的條件得 xxxdexqx) ,() ()( xxxdxxdexqexqxxQ) ,() ,() () (兩邊乘)(xp再對x求和得 xxxxdxxdexqexpxqxq,)

20、 ,(,) ,()()() () (當0) (xq時，上式兩端同除) (xq得 1)()(,) ,(,) ,(xxxxdxxdexqexp（5.10）將（5.6）中的xxQ 用（5.9）代入，連同1 個方程和1 個未知量，),(,xxq一般可以求解。再用（5.9）可得)(DRI的條件概率分布。,xxxxQ對0 xxQ的情形，只須將（5.10）中的等號，即 1)()(,) ,(,) ,(xxxxdxxdexqexp（5.11）（5.10）共有達到變成不等號(5.10)和(5.11)是與(5.8)等價的Kuhn-Tucker條件，它們可以用來檢驗一個給定的的解，但對一般的信源用此方法計算 xq 是

21、否達到 DRI)(DRI并不簡單。5.3 限失真信源編碼定理 本節(jié)我們給出限失真信源編碼定理，作為準備，先介紹失真典型序列的概念及其性質(zhì)。 定義定義5.3.1 設(shè)二維隨機向量 為獨立同分布且有公共分布 ， 為 上的有界失真測度。對任意給定的 稱序列對 為失真 典型序列，如果它們滿足以下條件： , 2 , 1),(iXXii) ,(xxp) ,(xxd0),(nnxxw（i） (5.12)w w（ii） (5.13)w w（iii） (5.14)w w (iv) (5.15)()(log1XHxpnn)()(log1XHxpnn),(),(log1XXHxxpnnn),(),(XXEdxxdnn

22、 我們將失真 典型序列的全體所構(gòu)成的集合記為 ，稱為 典型序列集。顯然 有 。 ndW, nndWW,以下討論失真 典型序列的性質(zhì)。 引理5.3.1 設(shè) 為獨立同分布隨機向量序列，其公共分布為 則, 2 , 1),(iXXii, xxp 1lim,ndrnWP, 2 , 1),(iXXii證明 由已知 為獨立同分布隨機向量序列，且 由大數(shù)定理， 依概率1收斂到 ),(),(),(xxdxxpXXEdxxniiinnXXdnXXd1,1,).,(XXEd2),(),(),()()()(,nnnrnnnrndnnrBxxPWxxPWxxP對任意給定的,0如記),(),(: ),()(XXEdxxd

23、xxBnnnnn則當n充分大時， 1)()(nrBP又由聯(lián)合典型序列集 nW的性質(zhì)知，當n充分大時， 1)()(nrWP于是由)()()(,nnndBWW所以 ,21),()(,ndnnrWxxP證畢。引理5.3.2 當ndnnWxx,),(時，)3),(2)()(XXInnnnxxpxp證明：設(shè)ndnnWxx,),(則由定義5.3.1可得)()(),()()(),()(nnnnnnnnnnxpxpxxpxpxpxxpxxp )()(),(222)(XHnXHnXXHnnxp )3),(2)(XXInnxp上式兩端同乘)3),(2XXIn即可。引理5.3.3 對任意1, 0,yx，和任意自然數(shù)

24、n，有ynexxy11證明 令 yeyfy1，則 0, 01)(, 00yeyffy故當0y時， 0yf從而yey1對任意10 y成立。上式兩邊同乘n次方得nyney1這表明引理在1x時成立。又0 x時，引理顯然成立。而函數(shù) 為離散無nxyyxg 1,在10 x時為x的凸函數(shù)，故 nxy1), 10)1(,yxxgyxg nynyexxexyxgygx11, 1, 01 定理5.3.4（限失真信源編碼定理）設(shè)X記憶信源，則（i）(正定理) 對任意的 DRR ，必存在一個),2(nnR碼，使DXXEdnn),(ii) (反定理) 對任意滿足條件DXXEdnn),(的碼，必有 .DRR ),2(n

25、nRiiinnxnnxnnnnnnnXXEdnXXEdxxdxxQxpXXEdXXEdnn),(1),(),()()(),(),(離散無記憶信源總有并且，我們指出：對于定義如下：注意：定理中的 證明 (i) 設(shè)xxQ 為達到 XXIDRDQQ;min的條件概率分布，這時 xxQxpxqx設(shè)信源依概率niinxpxp1)()(發(fā)送消息nX我們先構(gòu)造隨機碼和編譯碼方案，進而估計誤差概率。依概率niinxqxq1隨機獨立產(chǎn)生nR2個碼字，構(gòu)成一個隨機碼 nXXXCnnn,2,1編碼：對給定信源nX，如果存在w使 ndnnWwXX,，則將nX編碼為wXfn)(否則編碼為0)(nXf 譯碼：譯碼器收到碼

26、字w時譯為)()(wXwgn我們稱上述碼為率失真碼。以下估計誤差概率。對于固定的隨機碼C和任意選定的0可以將序列nnx分為兩類：(a)存在碼字 wXn使 ndnnWwXx,，即 DwXxdnn,我們記這種序列nx的全體為 CJ(b) CJxn這時就會出現(xiàn)譯碼錯誤。記 CJXPPdxxdnrexx,) ,(maxmax,則 nnnnnxCJxCJxnnxxdxxQxpwXXEdnnn,maxdPDe （5.16）下面證明eP可以任意小。我們在隨機碼集C上估計eP的期望值eP得cJxnCrenxpCPP)()(交換上面的求和順序得CPxpPCJxCrxnenn:)(首先定義： ndnnndnnnn

27、WxxWxxxxK,),(, 0),(, 1),( ：樣一組編碼的概率，即這的。下面來考慮能取到是按照同樣的方式產(chǎn)生編碼。而且所有的不能構(gòu)成失真典型序列的所有碼字都與中的每一個，和式注意：對給定的每一個)()(:CPCxCCPxrnCJxCrnn因為隨機選取一個碼字與給定的nx不構(gòu)成典型序列對的 0),(),(,nnrndnnrxxKPWxxP ),()(1nnxnxxKxpn由于隨機碼是隨機選取nR2個碼字，故 nRnnnnnxnnxnCJxCrxnexxKxpxpCPxpP2:),()(1)()(概率為由引理5.3.2得 nnxnnXXInnnnnxnxxKxxpxxKxp)3),(),(2)(),()( （5.18）將上式代入（5.17）式并應(yīng)用引理5.3.3得 nnnRxxnnnnXXInnexxKxxpxpP2)3);(),()(21)( nnnRXXInxxnnnnnexxKxxpxp)22(),()(1)()3);( nRXXInnnexxKxxpxpxxnnnnn)3);(2),()()(1當3);(XXIR時，（5.18）式右端最后一項將隨著n趨于0，這是可以做到的。 事實上，當)(xxQ達到);()(XXIDR時，在碼率);()(XXIDRR的條件下，可取充分小，使3);(XXIR成立。而（5.18）右端的前兩項，應(yīng)用引理5.