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

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

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

3、有關(guān)的。 4.1 失真測度一、失真度 首先討論失真的測度。 離散無記憶信源X，信源符號集Xa1,a2,ar，概率分布為p(x)p(a1),p(a2),p(ar) 。 信源符號通過信道傳輸?shù)浇邮斩耍邮斩说慕邮辗柤痀 b1,b2,bs 。 對應(yīng)于每一對(ai,bj)，我們指定一個非負(fù)的函數(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實(shí)際這里X指的是原始的未失真信源，而Y是指失真以后的信源。如果假設(shè)X是信源，Y是信宿，那么X和Y之間必有信道。從X到Y(jié)之間實(shí)際上是失真算法，所以這里的轉(zhuǎn)移概率p(bj/ai)是指一種失真算法，有時又把 p(bj/ai) 稱為試驗(yàn)信道的轉(zhuǎn)移概率，如圖所示。原始信源失真信源試驗(yàn)信道信道XYp (bj/ai)實(shí)際這里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 。若失真度定義為：如果信源符號代表信源輸出信號的幅度值，這就是一種平方誤差失真度。它意味著幅度差值大的要比幅度差值小的所引起的失真更為嚴(yán)重，其嚴(yán)重的程度用平方來表示。 當(dāng) r3時， 0,1,2，0,1,2 ，則失真矩陣為：上述例子說明了失真度的具體定義。一般情況下根據(jù)實(shí)際信源的失真，可以定義不同的失真和誤差的度量。另外還可以按其他標(biāo)準(zhǔn)，如引起的損失、風(fēng)險、主觀感覺上的差別大小等來定義失真度d(a,b)。 例 對稱信源(s = r) 。信源Xa1,a2,二、序列失真度設(shè) ，其中取自

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

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

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

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

11、允解：例4 設(shè)試驗(yàn)信道輸入符號集 ，各符號等概分布 ，失真矩陣如下所示，求 和 以及相應(yīng)的試驗(yàn)信道的轉(zhuǎn)移概率矩陣。 令對應(yīng)最小失真度 的 ，其它為“0”，可得對應(yīng) 的試驗(yàn)信道轉(zhuǎn)移概率矩陣為： 解：例4 設(shè)試驗(yàn)信道輸入符號集 上式中第二項(xiàng)最小，所以令 ， ，可得對應(yīng) 的試驗(yàn)信道轉(zhuǎn)移概率矩陣為:上式中第二項(xiàng)最小，所以令 2、 R(D)是關(guān)于平均失真度D的下凸函數(shù) 設(shè) 為任意兩個平均失真， ，則有： 3 、 R(D) 是 區(qū)間上的連續(xù)和嚴(yán)格單調(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ù)。原則上它與信道容量一樣，即在有約束條件下求極小值的問題。 也即選取適當(dāng)?shù)脑囼?yàn)信道p(x/y)使平均互信息最小化：其約束條件為: 一般取等號4.3 離散無記憶信源的信息率失真函數(shù) 已知一、 等概率、對稱失真信源的R(D)計(jì)算 對于等概、對稱失真的信源，存在一個與失真矩陣具有同樣對稱性的轉(zhuǎn)移概率分布達(dá)到率失真R(D)。一、 等概率、對稱失真信源的R(D)計(jì)算 對于解：例5有一個二元等概平穩(wěn)無記憶信源 ，接收符號集為 且失真矩陣為 ： 求率失真函數(shù)R(D) 。由于信源等概分布，失真函數(shù)具有對稱性，因此，存在著與失真矩陣具有同樣對稱性的轉(zhuǎn)移概率分布達(dá)

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

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

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

16、率失真函數(shù)R(D)。 解：根據(jù)(4.2.4)式計(jì)算可得 ，由題已知，根據(jù)參量表達(dá)式按如下步驟進(jìn)行。第一步：由式(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) ：應(yīng)用式(4.3.11)，還可求得此時的試驗(yàn)信道轉(zhuǎn)移概率：第四步：由式(4.3.17)求R(s) ：應(yīng)用式(4.3.14.4 連續(xù)無記憶信源的信息率失真函數(shù)研究連續(xù)信源的信息率失真函數(shù)

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

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

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