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

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

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

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

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

5、元對(duì)稱信源(sr2)，信源X0,1，接收變量Y0,1。在漢明失真定義下，失真矩陣為： 例1 離散對(duì)稱信源(r=s)，“0-1”失真。信源X 例2 刪除信源。信源Xa1,a2,ar ，接收Y b1,b2,bs (s = r+1) 。定義其單個(gè)符號(hào)失真度為：其中接收符號(hào)bs作為一個(gè)刪除符號(hào)。此時(shí)，意味著若把信源符號(hào)再現(xiàn)為刪除符號(hào)bs時(shí)，其失真程度要比再現(xiàn)為其他接收符號(hào)的失真程度少一半。二元?jiǎng)h除信源 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 ，接收 例 對(duì)稱信源(s = r) 。信源Xa1,a2,ar ，接收Y b1,b2,bs 。若失真度定義為：如果信源符號(hào)代表信源輸出信號(hào)的幅度值，這就是一種平方誤差失真度。它意味著幅度差值大的要比幅度差值小的所引起的失真更為嚴(yán)重，其嚴(yán)重的程度用平方來(lái)表示。 當(dāng) r3時(shí)， 0,1,2，0,1,2 ，則失真矩陣為：上述例子說(shuō)明了失真度的具體定義。一般情況下根據(jù)實(shí)際信源的失真，可以定義不同的失真和誤差的度量。另外還可以按其他標(biāo)準(zhǔn)，如引起的損失、風(fēng)險(xiǎn)、主觀感覺上的差別大小等來(lái)定義失真度d(a,b)。 例 對(duì)稱信源(s = r) 。信源Xa1,a2,二、序列失真度設(shè) ，其中取自

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

8、即給定了p(x)），單個(gè)符號(hào)失真度固定時(shí)（即給定了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)信道組成一個(gè)集合，用符號(hào)PD表示，則： PD=p (bj / ai)： D D0 若平均失真度D不大于我們所允許的失真D0，即：信源固定（即4.2 信息率失真函數(shù)及其性質(zhì)一、信息率失真函數(shù)的定義 信源給定，且又具體定義了失真函數(shù)以后，總希望在滿足一定失真的情況下，使信源傳輸給收信者的信息傳輸率R盡可能地小。-即在滿

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

10、集合中，極小值存在。這個(gè)最小值就是在D D0的條件下，信源進(jìn)行傳輸?shù)淖钚∑骄畔⒘?。即：R(D)-信息率失真函數(shù)或簡(jiǎn)稱率失真函數(shù) 單位是：比特信源符號(hào)尋找平均互信息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)信道輸入符號(hào)集 ，各符號(hào)等概分布 ，失真矩陣如下所示，求 和 以及相應(yīng)的試驗(yàn)信道的轉(zhuǎn)移概率矩陣。 令對(duì)應(yīng)最小失真度 的 ，其它為“0”，可得對(duì)應(yīng) 的試驗(yàn)信道轉(zhuǎn)移概率矩陣為： 解：例4 設(shè)試驗(yàn)信道輸入符號(hào)集 上式中第二項(xiàng)最小，所以令 ， ，可得對(duì)應(yīng) 的試驗(yàn)信道轉(zhuǎn)移概率矩陣為:上式中第二項(xiàng)最小，所以令 2、 R(D)是關(guān)于平均失真度D的下凸函數(shù) 設(shè) 為任意兩個(gè)平均失真， ，則有： 3 、 R(D) 是 區(qū)間上的連續(xù)和嚴(yán)格單調(diào)遞減函數(shù)。 信息率失真函數(shù)的一般形狀 () 2、 R(D)是關(guān)于平均失真度D的下凸函數(shù) 設(shè) 4.3 離散無(wú)記憶信源的信息率失真函數(shù) 已知信源的概率分布p(x)

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

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

14、拉格朗日乘子法解得的某些p(bj/ai)很可能是負(fù)的。在這情況下，必須假設(shè)其p(bj/ai) =0，然后重新計(jì)算，這就使得計(jì)算復(fù)雜化了。下面介紹用拉格朗日乘子法求解R(D)函數(shù)，并用s作為參量來(lái)表述率失真函數(shù)R(s)和失真函數(shù)D(s)。困難在于： 由 (1)式知，當(dāng)信源的概率分布p(x)固定，平均互信息僅僅是試驗(yàn)信道p(bj/ai)的函數(shù)。若先不考慮 (2)式的約束，約束條件 (3)式包含n個(gè)等式，取拉格朗日乘子i(i1,2, n)分別與之對(duì)應(yīng)；并取拉氏乘子s與 (4)式對(duì)應(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é)論：注：這時(shí)所得的結(jié)果是以s為參量的表達(dá)式，而不是顯式表達(dá)式，因而所得到的R(D)的表達(dá)式也是以s為參量的表達(dá)式。參量s對(duì)應(yīng)的限制條件為(4)式，它與允許的失真度D有關(guān)，所以，以s為參量就相當(dāng)于以D為參量。(4)注：這時(shí)所得的結(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)，還可求得此時(shí)的試驗(yàn)信道轉(zhuǎn)移概率：第四步：由式(4.3.17)求R(s) ：應(yīng)用式(4.3.14.4 連續(xù)無(wú)記憶信源的信息率失真函數(shù)研究連續(xù)信源的信息率失真函數(shù)

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

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

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