信息率失真函數(shù)1課件

1、第四章 信息率失真函數(shù) 第四章 信息率失真函數(shù) 無失真信源編碼和有噪信道編碼（香農(nóng)第一定理和香農(nóng)第二定理）告訴我們：只要信道的信息傳輸速率小于信道容量，總能找到一種編碼方法，使得在該信道上的信息傳輸?shù)牟铄e概率任意?。环粗?，若信道的信息傳輸速率大于信道容量，則不可能使信息傳輸差錯概率任意小。但是，無失真的編碼并非總是必要的。無失真信源編碼和有噪信道編碼（香農(nóng)第一定理和香農(nóng)第二定理）告原始圖像紅色圖像綠色圖像藍色圖像原始圖像和限失真圖像原始圖像紅色圖像綠色圖像藍色圖像原始圖像和限失真圖像香農(nóng)首先定義了信息率失真函數(shù)R(D)，并論述了關(guān)于這個函數(shù)的基本定理。定理指出：在允許一定失真度D的情況下，信源

2、輸出的信息傳輸率可壓縮到R(D)值，這就從理論上給出了信息傳輸率與允許失真之間的關(guān)系，奠定了信息率失真理論的基礎(chǔ)。信息率失真理論是進行量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)。本章主要介紹信息率失真理論的基本內(nèi)容，重點討論離散無記憶信源。給出信源的失真度和信息率失真函數(shù)的定義與性質(zhì)；討論離散信源和連續(xù)信源的信息率失真函數(shù)計算；在此基礎(chǔ)上論述保真度準則下的信源編碼定理。香農(nóng)首先定義了信息率失真函數(shù)R(D)，并論述了關(guān)于這個函數(shù)的 4.1 失真測度一、失真度從直觀感覺可知，若允許失真越大，信息傳輸率就可越小；若允許失真越小，信息傳輸率需越大。所以信息傳輸率與（信源）編碼所引起的失真(或誤差)是

3、有關(guān)的。 4.1 失真測度一、失真度 首先討論失真的測度。 離散無記憶信源X，信源符號集Xa1,a2,ar，概率分布為p(x)p(a1),p(a2),p(ar) 。 信源符號通過信道傳輸?shù)浇邮斩?，接收端的接收符號集Y b1,b2,bs 。 對應于每一對(ai,bj)，我們指定一個非負的函數(shù)：稱為單個符號的失真度(或失真函數(shù))。 通常較小的d值代表較小的失真，而d(ai,bj)0表示沒有失真。 首先討論失真的測度。稱為單個符號的失真度(或失真函數(shù)若信源變量X有r個符號，接收變量Y有s個符號，則d(ai,bj)就有rs個,它可以排列成矩陣形式，即：該失真矩陣D，是 rs 階矩陣。若信源變量X有r個

4、符號，接收變量Y有s個符號，則d(ai,b實際這里X指的是原始的未失真信源，而Y是指失真以后的信源。如果假設(shè)X是信源，Y是信宿，那么X和Y之間必有信道。從X到Y(jié)之間實際上是失真算法，所以這里的轉(zhuǎn)移概率p(bj/ai)是指一種失真算法，有時又把 p(bj/ai) 稱為試驗信道的轉(zhuǎn)移概率，如圖所示。原始信源失真信源試驗信道信道XYp (bj/ai)實際這里X指的是原始的未失真信源，而Y是指失真以后的信源。如 例1 離散對稱信源(r=s)，“0-1”失真。信源Xa1,a2,ar ，接收Y b1,b2,bs。定義單個符號失真度：這種失真稱為漢明失真。漢明失真矩陣是一方陣，對角線上的元素為零，即： 對二

5、元對稱信源(sr2)，信源X0,1，接收變量Y0,1。在漢明失真定義下，失真矩陣為： 例1 離散對稱信源(r=s)，“0-1”失真。信源X 例2 刪除信源。信源Xa1,a2,ar ，接收Y b1,b2,bs (s = r+1) 。定義其單個符號失真度為：其中接收符號bs作為一個刪除符號。此時，意味著若把信源符號再現(xiàn)為刪除符號bs時，其失真程度要比再現(xiàn)為其他接收符號的失真程度少一半。二元刪除信源 r 2， s 3，X0,1，Y0,1 ,2 。失真度為： 則d(0,0)=d(1,1)=0 d(0,1)=d(1,0)=1d(0,2)=d(1,2)=1/2除j=s以外所有的j和i所有i 例2 刪除信源

6、。信源Xa1,a2,ar ，接收 例 對稱信源(s = r) 。信源Xa1,a2,ar ，接收Y b1,b2,bs 。若失真度定義為：如果信源符號代表信源輸出信號的幅度值，這就是一種平方誤差失真度。它意味著幅度差值大的要比幅度差值小的所引起的失真更為嚴重，其嚴重的程度用平方來表示。 當 r3時， 0,1,2，0,1,2 ，則失真矩陣為：上述例子說明了失真度的具體定義。一般情況下根據(jù)實際信源的失真，可以定義不同的失真和誤差的度量。另外還可以按其他標準，如引起的損失、風險、主觀感覺上的差別大小等來定義失真度d(a,b)。 例 對稱信源(s = r) 。信源Xa1,a2,二、序列失真度設(shè) ，其中取自

7、信源符號集A； 其中取自信宿符號集B。則序列失真度定義為： 二、序列失真度設(shè) 三、 平均失真度信源 X 和信宿 Y 都是隨機變量，故單個符號失真度d(ai,bj) 也是隨機變量。規(guī)定了單個符號失真度d(ai,bj) 后，傳輸一個符號引起的平均失真，即信源平均失真度： 在離散情況下，信源Xa1,a2,ar ，其概率分布p(x)p(a1),p(a2),p(ar) ，信宿Y b1,b2,bs 。若已知試驗信道的傳遞概率為p(bj/ai)時，則平均失其度為：三、 平均失真度信源 X 和信宿 Y 都是隨機變量，故單個 若平均失真度D不大于我們所允許的失真D0，即： D D0 稱此為保真度準則。信源固定（

8、即給定了p(x)），單個符號失真度固定時（即給定了d(ai,bj)） ，選擇不同試驗信道，相當于不同的編碼方法，所得的平均失真度是不同的。有些試驗信道滿足D D0，而有些試驗信道DD0。凡滿足保真度準則-平均失真度D D0的試驗信通稱為 -D失真許可的試驗信道。把所有D失真許可的試驗信道組成一個集合，用符號PD表示，則： PD=p (bj / ai)： D D0 若平均失真度D不大于我們所允許的失真D0，即：信源固定（即4.2 信息率失真函數(shù)及其性質(zhì)一、信息率失真函數(shù)的定義 信源給定，且又具體定義了失真函數(shù)以后，總希望在滿足一定失真的情況下，使信源傳輸給收信者的信息傳輸率R盡可能地小。-即在滿

9、足保真度準則下，尋找信源必須傳輸給信宿的信息率R的下限值-這個下限值與D有關(guān)。從接收端來看，就是在滿足保真度準則下，尋找再現(xiàn)信源消息所必須獲得的最低平均信息量。而接收端獲得的平均信息量可用平均互信息I(X;Y)來表示，這就變成了在滿足保真度準則的條件下，尋找平均互信息I(X;Y)的最小值。4.2 信息率失真函數(shù)及其性質(zhì)一、信息率失真函數(shù)的定義 信尋找平均互信息I(X;Y)的最小值。而PD是所有滿足保真度準則的試驗信道集合，因而可以在D失真許可的試驗信道集合PD中尋找一個信道p(bj / ai) ，使I(X;Y) 取極小值。由于平均互信息I(X;Y)是p(bj / ai)的U型凸函數(shù)，所以在PD

10、集合中，極小值存在。這個最小值就是在D D0的條件下，信源進行傳輸?shù)淖钚∑骄畔⒘俊＜矗篟(D)-信息率失真函數(shù)或簡稱率失真函數(shù) 單位是：比特信源符號尋找平均互信息I(X;Y)的最小值。而PD是所有滿足保真度準率失真函數(shù)給出了熵壓縮編碼可能達到的最小熵率與失真的關(guān)系;其逆函數(shù)D(R)稱為失真率函數(shù), D(R)表示一定信息速率下所可能達到的最小的平均失真。 率失真函數(shù)給出了熵壓縮編碼可能達到的最小熵率與失真的關(guān)系;二、信息率失真函數(shù)的性質(zhì)允許失真度D的下限可以是零，這是不允許任何失真的情況。 1、 R(D)的定義域R(D)的定義域為 且：二、信息率失真函數(shù)的性質(zhì)允許失真度D的下限可以是零，這是不

11、允解：例4 設(shè)試驗信道輸入符號集 ，各符號等概分布 ，失真矩陣如下所示，求 和 以及相應的試驗信道的轉(zhuǎn)移概率矩陣。 令對應最小失真度 的 ，其它為“0”，可得對應 的試驗信道轉(zhuǎn)移概率矩陣為： 解：例4 設(shè)試驗信道輸入符號集 上式中第二項最小，所以令 ， ，可得對應 的試驗信道轉(zhuǎn)移概率矩陣為:上式中第二項最小，所以令 2、 R(D)是關(guān)于平均失真度D的下凸函數(shù) 設(shè) 為任意兩個平均失真， ，則有： 3 、 R(D) 是 區(qū)間上的連續(xù)和嚴格單調(diào)遞減函數(shù)。 信息率失真函數(shù)的一般形狀 () 2、 R(D)是關(guān)于平均失真度D的下凸函數(shù) 設(shè) 4.3 離散無記憶信源的信息率失真函數(shù) 已知信源的概率分布p(x)

12、和失真函數(shù)d(x,y)，就可求得信源的R(D)函數(shù)。原則上它與信道容量一樣，即在有約束條件下求極小值的問題。 也即選取適當?shù)脑囼炐诺纏(x/y)使平均互信息最小化：其約束條件為: 一般取等號4.3 離散無記憶信源的信息率失真函數(shù) 已知一、 等概率、對稱失真信源的R(D)計算 對于等概、對稱失真的信源，存在一個與失真矩陣具有同樣對稱性的轉(zhuǎn)移概率分布達到率失真R(D)。一、 等概率、對稱失真信源的R(D)計算 對于解：例5有一個二元等概平穩(wěn)無記憶信源 ，接收符號集為 且失真矩陣為 ： 求率失真函數(shù)R(D) 。由于信源等概分布，失真函數(shù)具有對稱性，因此，存在著與失真矩陣具有同樣對稱性的轉(zhuǎn)移概率分布達

13、到率失真R(D) ，該轉(zhuǎn)移概率矩陣可寫為：由于 ，因此對于任何有限平均失真，必須 ,于是轉(zhuǎn)移概率矩陣為：解：例5有一個二元等概平穩(wěn)無記憶信源 對應此轉(zhuǎn)移概率矩陣的平均失真：因此: 可求得此時的互信息為：對應此轉(zhuǎn)移概率矩陣的平均失真：二、 信息率失真函數(shù)的參量表述 求信源的R(D)函數(shù)，原則上與求信道容量一樣，是在有約束條件下求極小值的問題。 也就是適當選取試驗信道p(y/x)使平均互信息最小化， 應用拉格朗日乘子法，原則上可以求出解來。二、 信息率失真函數(shù)的參量表述 求信源的R(D困難在于：要得到顯式的解析表達式，則比較困難，通常只能用參量形式來表達。要保證約束條件式p(bj/ai) 0，應用

14、拉格朗日乘子法解得的某些p(bj/ai)很可能是負的。在這情況下，必須假設(shè)其p(bj/ai) =0，然后重新計算，這就使得計算復雜化了。下面介紹用拉格朗日乘子法求解R(D)函數(shù)，并用s作為參量來表述率失真函數(shù)R(s)和失真函數(shù)D(s)。困難在于： 由 (1)式知，當信源的概率分布p(x)固定，平均互信息僅僅是試驗信道p(bj/ai)的函數(shù)。若先不考慮 (2)式的約束，約束條件 (3)式包含n個等式，取拉格朗日乘子i(i1,2, n)分別與之對應；并取拉氏乘子s與 (4)式對應。由此構(gòu)成輔助函數(shù)：(2)(3)(4)(1) 由 (1)式知，當信源的概率分布p(x)固定，平均互信息僅求極值，即為求(

15、5) 式一階導數(shù)等于零的方程組的解。已知平均互信息I(X;Y)是信道P的U型凸函數(shù)，所以，若極值存在，它一定是極小值。即求：得：-(6)求極值，即為求(5) 式一階導數(shù)等于零的方程組的解。得：-(6)(1)(3)(4)-(6)(1)(3)(4)經(jīng)整理得結(jié)論：經(jīng)整理得結(jié)論：注：這時所得的結(jié)果是以s為參量的表達式，而不是顯式表達式，因而所得到的R(D)的表達式也是以s為參量的表達式。參量s對應的限制條件為(4)式，它與允許的失真度D有關(guān)，所以，以s為參量就相當于以D為參量。(4)注：這時所得的結(jié)果是以s為參量的表達式，而不是顯式表達式，因 例6 設(shè)離散信源和接收變量：并設(shè)失真矩陣為:求該信源的信息

16、率失真函數(shù)R(D)。 解：根據(jù)(4.2.4)式計算可得 ，由題已知，根據(jù)參量表達式按如下步驟進行。第一步：由式(4.3.14)求 例6 設(shè)離散信源和接收變量：求該信源的信息率失真函數(shù)第二步：由式(4.3.13)求第二步：由式(4.3.13)求第三步：由式(4.3.16)求D(s)，將上述結(jié)果代入式(4.3.16)有第三步：由式(4.3.16)求D(s)，將上述結(jié)果代入式(4第四步：由式(4.3.17)求R(s) ：應用式(4.3.11)，還可求得此時的試驗信道轉(zhuǎn)移概率：第四步：由式(4.3.17)求R(s) ：應用式(4.3.14.4 連續(xù)無記憶信源的信息率失真函數(shù)研究連續(xù)信源的信息率失真函數(shù)

17、比離散信源更有實際意義，因為連續(xù)隨機變量不可能用有限比特加以精確描述，即連續(xù)信源信息量為無限大，傳送無限大信息量既無必要，也不可能。所以連續(xù)信源的討論都屬于限失真范疇。4.4 連續(xù)無記憶信源的信息率失真函數(shù)研究連續(xù)信源的信息率失一、連續(xù)無記憶信源的信息率失真函數(shù)的定義 連續(xù)信源的平均失真度定義為： 通過試驗信道獲得的平均互信息為：同樣，確定一允許失真度D，凡滿足平均失真小于D的所有試驗信道的集合記為PD，則連續(xù)信源的信息率失真函數(shù)定義為：一、連續(xù)無記憶信源的信息率失真函數(shù)的定義通過試驗信道獲得的平 二、高斯信源的信息率失真函數(shù) 對高斯信源，在一般失真函數(shù)下，其率失真函數(shù)是很難求得的，但在平方誤

18、差失真度量下，其率失真函數(shù)有簡單的封閉表達式。 對平方誤差失真，試驗信道輸入符號和輸出符號之間失真為： 對應的平均失真度為： 二、高斯信源的信息率失真函數(shù) 對應的平均失真度為：在平方誤差失真下，設(shè)允許失真為D，則高斯信源 的率失真函數(shù)為：下圖表示當 時， 的曲線。在平方誤差失真下，設(shè)允許失真為D，則高斯信源 三、連續(xù)無記憶信源信息率失真函數(shù)的參量表述類似于離散信源，連續(xù)信源的率失真函數(shù)的計算也歸結(jié)為求有約束極值的問題，不過在連續(xù)信源情況下試驗信道的條件概率也是函數(shù)，所以，率失真函數(shù)的計算就變成求泛函的極值，即求： 的極小值，滿足約束條件為： 三、連續(xù)無記憶信源信息率失真函數(shù)的參量表述的極小值，

19、滿足約 約束條件下的泛函求極值問題和約束條件下的函數(shù)求極值問題類似，即利用拉格朗日乘子將問題轉(zhuǎn)化為無約束極值問題，并用變分代替微分，對本節(jié)討論的問題，等價于使下式的一階變分為零： 其中 為待定函數(shù)，s為待定常數(shù)，其求解順序完全類似于離散情況。 約束條件下的泛函求極值問題和約束條件下的函數(shù)在此我們僅給出最終結(jié)論：在連續(xù)無記憶信源下，達到信息率失真函數(shù)的試驗信道的轉(zhuǎn)移概率密度函數(shù)必需滿足：其中在此我們僅給出最終結(jié)論：其中此時的率失真函數(shù)和失真D滿足參量方程： 需要說明的是，連續(xù)情況下的信息率失真函數(shù)與離散情況下信息率失真函數(shù)的一個主要差別在于當時，由于連續(xù)信源的差熵而使從此意義上講，連續(xù)信源的熵壓縮編碼是必不可少的。此時的率失真函數(shù)和失真D滿足參量方程： 需要說明的是， 四、差值失真度量下連續(xù)無記憶信源的信息率失真函數(shù) 一般情況下，連續(xù)無記憶信源下信息率失真函數(shù)的計算相當困難，絕大多數(shù)情況下無解析解。 但當連續(xù)信源的失真函數(shù)D (x,y)為x和y的差值形式如： |x-y|，(x-y)2時，可以較容易地采用參量表述式來求得其上、下限。 四、差值失真度量下連續(xù)無記憶信源的信息率失真函數(shù) (1) 差值失真度量下率失真函數(shù)的Shannon下限 上式是香農(nóng)首先得到的，因此稱其右端為差值失真度量時連續(xù)信源的香農(nóng)下限。 (2) 平方誤差(差方)失真度量下率失真