第五章信息率失真函數(shù)及限失真信源編碼

第五章信息率失真函數(shù)及限失真信源編碼

5.1信息率失真函數(shù)概念和定義5.2信息率失真函數(shù)R（D）的性質(zhì)5.3離散信源的R(D)函數(shù)的計算5.4連續(xù)信源的R(D)函數(shù)5.5限失真信源編碼定理（香農(nóng)第三定理）5.6限失真信源編碼原理5.1信息率失真函數(shù)概念和定義

在實際應用場合，容許一定程度失真的情況比要求無失真的情況更為重要。信息率失真函數(shù)擬解決的問題：信息率和失真之間的關系。信息率失真理論的基本概念：在允許傳輸消息出現(xiàn)一定的失真時，傳輸該消息所需要的信息速率（最小值）將比不允許失真時小，且允許的失真愈大，則信息速率（最小值）允許減小的程度也愈大。在給定平均失真函數(shù)D的條件下，可以求出信息速率的最小值。一、失真函數(shù)失真函數(shù)d(x,y)表征了接收消息y與發(fā)送消息x之間的定量失真度。即：d(x,y)∣x=ai,y=aj＝dij其中，失真函數(shù)dij是一個與失真情況相對應的非負實數(shù)：0，i＝jdij＝d,d＞0i≠j顯然：i＝j時，收發(fā)之間無失真，失真函數(shù)dij＝0i≠j時，意味著出現(xiàn)了失真，dij值的大小表示這種失真的程度。若X集有N個符號，Y集有M個符號時，則聯(lián)合集上有N×M個不同i、j取值的失真函數(shù)。失真函數(shù)dij的二種表示方式：（1）矩陣表示法（2）連線表示法平均失真度：失真函數(shù)的統(tǒng)計平均值（數(shù)學期望）D數(shù)學式為：兩個L維矢量之間的失真函數(shù)為：信源的平均失真度：若平均失真度不大于所允許的失真，則稱為保真度準則。二、信息率失真函數(shù)（率失真函數(shù)）當某條件概率P(yj/xi)能使互信息I最小，此時的I就稱為在保真度準則下所必須具有的最小信息速率，用R(D)表示。數(shù)學式為：R(D)＝minI(X;Y)＝minI(X;Y)其中PD為滿足失真條件的轉移概率Pji的集合，D為允許的失真。Pji∈PDd≤D信息率失真函數(shù)R(D)定義：在給定信源消息的概率分布{P(xi)}及平均失真函數(shù)允許值D的前提下，傳輸這些信源消息并使其失真程度在允許范圍內(nèi)時，所需要的信息傳輸速率的極小值。R(D)反映了信源可以壓縮的程度，是在滿足一定失真度要求下，信源可壓縮的最低值，對不同的信源，R(D)不同。例：設信源符號有2n種，且等概，失真函數(shù)定義為：dij＝0（i＝j時），dij＝1（i≠j時），允許平均失真D＝1/2，要傳送此信源，需要多少信息率？課堂練習：設信源具有100個以等概率出現(xiàn)的符號，并以每秒發(fā)出1個符號的速率從信源輸出，試求在允許失真度D＝0.1的條件下，傳輸這些符號所需要的最小信息傳輸速率的大小。結論：在允許一定失真的條件下，信息傳輸速率可以減小，同時所需要的信道容量也可以相應地減小，允許的失真度愈大，則信息傳輸速率可被壓縮的程度亦愈大。5.2信息率失真函數(shù)R(D)的性質(zhì)一、當D＝0時，R(0)＝H(X)通常Dmin＝0；D＝0時不允許有失真；注意：D是否能達到0，與單個符號的失真函數(shù)有關，只有當失真矩陣中每行至少有一個0元素時，D才能達到0值。定義域下界滿足Dmin≥0。二、R(Dmax)＝0Dmax是平均失真度的上界值，使平均互信息量等于0時所允許的失真度。注意：D≥Dmax時，R(D)仍為0，R(D)的定義域為（0，Dmax）三、在0～Dmax范圍內(nèi)，R(D)是D上的凹函數(shù)（下凸函數(shù)）四、R(D)是D的單調(diào)遞減的連續(xù)函數(shù)如圖為R(D)的典型曲線：在連續(xù)信源的情況下，R(0)→∞，曲線不與R(D)軸相交。5.3離散信源的R(D)函數(shù)的計算一、R(D)的參量表達式已知：其中：求R(D)就是求I的極值引入拉氏乘子S和ui，再對Pji求導，并令其為0，即幾個有用的結果：（1）（2）（3）信息率失真函數(shù)參量表達式：注意：參變數(shù)S是R(D)函數(shù)曲線的斜率，即：dR/dD＝S，由于R(D)曲線是單調(diào)遞減的凹函數(shù)曲線，所以該曲線的斜率S為負值，同時，在D從0～Dmax過程中，S值逐漸增大（S的絕對值逐漸減?。?。二、二元信源和對稱失真函數(shù)的R(D)函數(shù)信源概率：p1＝p≤1/2，p2＝1－p≥1/2失真函數(shù)：dij

可分別求得平均失真函數(shù)：可得最大允許的失真度：引用（2）式，得：結果：試驗信道的傳輸概率：可見：平均失真函數(shù)D就是平均誤碼率。如圖為不同信源概率值的R(D)曲線：顯然Dmax＝p，R(Dmax)＝0結論：在信源壓縮問題中，規(guī)定D是一個困難的任務。實際中，失真總是可以容忍的，只是如何定義失真函數(shù)dij和規(guī)定可容許的D值，D↑→壓縮量↑→傳輸代價↓要發(fā)揮R(D)函數(shù)理論的作用，核心問題是研究失真函數(shù)和平均失真值的合理性問題，這須通過大量實驗才能達到。三、迭代算法基本步驟：1）任選一個Pji①代入下式，求得各qj①2）再代入下式求得各Pji②，依此類推，直到各階段的R(S)值穩(wěn)定為止。5.4連續(xù)信源的R(D)函數(shù)一、定義和表達式設：平均失真≤允許失真度時，{P(y/x)}∈PD則定義連續(xù)信源的率失真函數(shù)R(D)為：R（D）＝InfI（P(y/x)）{P(y/x)}∈PD與離散情況類似，并設得公式：（1）

（2）（3）（4）二、d(x,y)只與(x－y)有關時的求解法令：且：最終得：常用方法：（1）分別求出p(x)和g(x)的特征函數(shù)（2）則：（3）若q0(x)符合概率密度函數(shù)的要求（非負性、歸一性），就可得到R(D)函數(shù)的參量表達式。例：設連續(xù)信源的變量x服從正態(tài)分布，即定義失真函數(shù)且求信息率失真函數(shù)R(D)。解：給定允許失真度D＝－1/2S，即：上式為正態(tài)變量在均方誤差準則下的率失真函數(shù)。當＝1時的R(D)曲線可見：1）D＝1時，R(1)＝0；2）D＞1時，R(D)保持為0，與離散情況一致；3）D＝0時，R(D)→∞，

與離散情況不同。5.5限失真信源編碼定理（香農(nóng)第三定理）限失真信源編碼定理也稱香農(nóng)第三定理，是保真度準則下的信源編碼定理。（具體描述可參考相關教材）限失真編碼定理說明：當傳輸速率R＞R(D)時，只要碼長足夠長，就一定存在一種編碼方法，使平均失真任意接近于D，否則這種編碼不存在。注意：不同的編碼，將有不同的平均失真，希望找到平均失真最小的編碼，即最佳編碼。小結：比較香農(nóng)第一和第三定理可知，當信源給定后，無失真信源壓縮的極限值是信源熵H(S)，而有失真信源壓縮的極限值是信息率失真函數(shù)R(D)，在給定失真值D后，一般R(D)＜H(S)。存在的問題：1）符合實際信源的R(D)函數(shù)的計算相當困難；2）采用何種實用的最佳編碼方法才能達到R(D)？以下例子可說明如何進行限失真的信源編碼和信息率失真函數(shù)R(D)的實用意義：P216，例8.65.6限失真信源編碼原理采用限失真的信源編碼，能夠以一定限度的失真換取更加有效地數(shù)據(jù)壓縮，這可大大提高信息傳輸和存儲系統(tǒng)的有效性。實際工程中常用其他的主、客觀評價準則來衡量限失真編碼的效果。一、保真度準則1、客觀保真度準則通過計算輸入與輸出之間的誤差，客觀地評價兩者的差異，以度量信源壓縮編碼所產(chǎn)生的失真大小，比較不同信源編碼方法的失真性能。計算并客觀度量壓縮編碼失真大小的方法有均方根誤差和均方根信噪比等。2、主觀保真度準則根據(jù)人們的生理和心理特性，由觀察者對編碼結果做出主觀評價的一種方法。因為多數(shù)信息傳輸和存儲處理的結果最終由人接受，所以主觀評價準則也是壓縮編碼處理質(zhì)量評價的主要方法。二、預測編碼方法預測編碼：編碼傳輸或存儲的并不是信源輸出地數(shù)據(jù)本身，而是當前數(shù)據(jù)的預測值（或稱估值）與實際值之間的差值。這是一種直接利用數(shù)據(jù)間的相關性進行估計預測，誤差數(shù)據(jù)間的相關性減小，信息冗余降低，差值信號的信息熵較小，若不量化直接編碼，則構成無失真預測編碼；若根據(jù)人的感覺特性對差值重新量化，將實現(xiàn)更大的數(shù)據(jù)壓縮，構成限失真預測編碼方法。預測編碼方法主要有：1）差值脈沖編碼調(diào)制（DPCM）；2）線性預測（前值預測、一維線性預測、二維線性預測）；3）量化編碼。三、正交變換編碼正交變換編碼：通過施加某種正交變換，使得變換域中數(shù)據(jù)的相關性減小或消除，從而減小信源的信息冗余，實現(xiàn)數(shù)據(jù)壓縮。此方法首先對輸入數(shù)據(jù)序列施加某種形式的正交變換，然后用濾波器取出信源信息中的主要部分，舍棄次要部分，從而實現(xiàn)數(shù)據(jù)壓縮。最佳正交變換：K-L變換，但計算量大，難以實用；準最佳正交變換：DFT、DCT、W-HT正交變換編碼基本方法有：1）區(qū)域采樣法：利用變換域中能量集中于低頻區(qū)域的特點，用一個二維低通濾波器使低頻分量的變換域系數(shù)被保留和編碼，其他分量被舍棄。解碼后的誤差與變換形式及能量集中程度有關。2）區(qū)域編碼法：在區(qū)域采樣的基礎上，依據(jù)變換域系數(shù)特點，分成子區(qū)域進行量化和編碼?？蛇M一步節(jié)省數(shù)碼率，更有效地壓