第九章率失真函數(shù)

1、第九章 率失真函數(shù),,無(wú)失真信源編碼和有噪信道編碼告訴我們：只要信道的信息傳輸速率小于信道容量，總能找到一種編碼方法,使得在該信道上的信息傳輸?shù)牟铄e(cuò)概率任意??；反之，若信道的信息傳輸速率大于信道容量，則不可能使信息傳輸差錯(cuò)概率任意小。問(wèn)題：若信息速率大于信道容量，怎么辦？無(wú)失真的編碼并非總是必要的。引入失真，允許失真大，信息率可以越低。P248例,香農(nóng)首先定義了信息率失真函數(shù)R(D)，并論述了關(guān)于這個(gè)函數(shù)的基本定理。定理指出：在

2、允許一定失真度D的情況下，信源輸出的信息傳輸率可壓縮到R(D)值，這就從理論上給出了信息傳輸率與允許失真之間的關(guān)系，奠定了信息率失真理論的基礎(chǔ)。信息率失真理論是進(jìn)行量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)。本章主要介紹信息率失真理論的基本內(nèi)容，側(cè)重討論離散無(wú)記憶信源。首先給出信源的失真度和信息率失真函數(shù)的定義與性質(zhì)；然后討論離散信源和連續(xù)信源的信息率失真函數(shù)計(jì)算；在這基礎(chǔ)上論述保真度準(zhǔn)則下的信源編碼定理。,失真測(cè)度,一、失真度

3、從直觀感覺(jué)可知，若允許失真越大，信息傳輸率可 越??；若允許失真越小，信息傳輸率需越大。所以信息傳輸率與信源編碼所引起的失真(或誤差)是有關(guān)的。,離散無(wú)記憶信源U，信源變量U＝{u1,u2,…ur}，概率分布為P(u)＝[P(u1),P(u2),…P(ur)] 。 信源符號(hào)通過(guò)信道傳輸?shù)侥辰邮斩?，接收端的接收變量V＝ {v1,v2,…vs} 。 對(duì)應(yīng)于每一對(duì)(u,v)，我們指定一個(gè)非負(fù)的函數(shù)：,稱為單個(gè)符號(hào)的失真度(或

4、失真函數(shù))。 通常較小的d值代表較小的失真，而d(ui,vj)＝0表示沒(méi)有失真。,失真測(cè)度,若信源變量U有r個(gè)符號(hào)，接收變量V有s個(gè)符號(hào)，則d(ui,vj)就有r×s個(gè),它可以排列成矩陣形式，即：,它為失真矩陣D，是 r×s 階矩陣。,失真矩陣D,U：原始的未失真信源V：失真以后的信源。從U到V：失真算法，轉(zhuǎn)移概率p(vj/ui)：一種失真算法p(vj/ui) 稱為試驗(yàn)信道的轉(zhuǎn)移概率，如圖所示。,

5、試驗(yàn)信道的轉(zhuǎn)移概率,[例1] 離散對(duì)稱信源(r=s)。信源變量U＝{u1,u2,…ur} ，接收變量V＝ {v1,v2,…vs}。定義單個(gè)符號(hào)失真度：,這種失真稱為漢明失真。漢明失真矩陣是一方陣，對(duì)角線上的元素為零，即：,對(duì)二元對(duì)稱信源(s＝r＝2)，信源U＝{0,1}，接收變量V＝{0,1}。在漢明失真定義下，失真矩陣為：,[例2] 刪除信源。信源變量U＝{u1,u2,…ur} ，接收變量V＝ {v1,v2,…vs} (s = r+

6、1) 。定義其單個(gè)符號(hào)失真度為：,其中接收符號(hào)vs作為一個(gè)刪除符號(hào)。在這種情況下，意味著若把信源符號(hào)再現(xiàn)為刪除符號(hào)vs時(shí)，其失真程度要比再現(xiàn)為其他接收符號(hào)的失真程度少一半。若二元?jiǎng)h除信源s ＝2，r＝3， U＝{0,1}，V＝{0,1 ,2} 。失真度為：,則,d(0,0)=d(1,2)=0 d(0,2)=d(1,0)=1d(0,1)=d(1,1)=1/2,[例3] 對(duì)稱信源(s = r) 。信源變量U＝{u1,u2,…ur}

7、 ，接收變量V＝ {v1,v2,…vs} 。失真度定義為：,若信源符號(hào)代表信源輸出信號(hào)的幅度值，這就是一種以方差表示的失真度。它意味著幅度差值大的要比幅度差值小的所引起的失真更為嚴(yán)重，嚴(yán)重程度用平方來(lái)表示。 當(dāng) r＝3時(shí)， U＝{0,1,2}，V＝{0,1,2} ，則失真矩陣為：,上述三個(gè)例子說(shuō)明了具體失真度的定義。一般情況下根據(jù)實(shí)際信源的失真，可以定義不同的失真和誤差的度量。另外還可以按其他標(biāo)準(zhǔn)，如引起的損失、風(fēng)險(xiǎn)、主觀感覺(jué)上的差別

8、大小等來(lái)定義失真度d(u,v)。,失真度d(ui,vj)是隨機(jī)變量。規(guī)定了單個(gè)符號(hào)失真度d(ui,vj) 后，傳輸一個(gè)符號(hào)引起的平均失真，稱為信源平均失真度：,在離散情況下，信源U＝{u1,u2,…ur} ，其概率分布P(u)＝[P(u1),P(u2),…P(ur)] ，信宿V＝ {v1,v2,…vs} 。若已知試驗(yàn)信道的傳遞概率為P(vj/ui)時(shí)，則平均失其度為：,平均失真度,若平均失真度D不大于我們所允許的失真D，即：

9、 D ? D 稱此為保真度準(zhǔn)則。,信源固定(給定P(u))，單個(gè)符號(hào)失真度固定時(shí)(給定d(ui,vj)) ，選擇不同試驗(yàn)信道，相當(dāng)于不同的編碼方法，所得的平均失真度是不同的。有些試驗(yàn)信道滿足D ? D，而有些試驗(yàn)信道D＞D。凡滿足保真度準(zhǔn)則，即平均失真度D ? D的試驗(yàn)信道統(tǒng)稱為“D失真許可的試驗(yàn)信道”。把所有D失真許可的試驗(yàn)信道組成一個(gè)集合，用符號(hào)BD表示，即：

10、 BD={P (vj / ui)： D ? D},,,,保真度準(zhǔn)則,信息率失真函數(shù)及其性質(zhì),一、信息率失真函數(shù)的定義,信源給定，且又具體定義了失真函數(shù)以后，總希望在滿足一定失真的情況下，使信源傳輸給收信者的信息傳輸率R盡可能地小。即在滿足保真度準(zhǔn)則下，尋找信源必須傳輸給收信者的信息率R的下限值------這個(gè)下限值與D有關(guān)。從接收端來(lái)看，就是在滿足保真度準(zhǔn)則下，尋找再現(xiàn)信源消息所必須獲得的最低平均信息量。而接收端獲得的平均信息量

11、可用平均互信息I(U;V)來(lái)表示，這就變成了在滿足保真度準(zhǔn)則的條件下，尋找平均互信息I(U;V)的最小值。,R(D)-------信息率失真函數(shù)或簡(jiǎn)稱率失真函數(shù)。 單位是奈特／信源符號(hào) 或 比特／信源符號(hào),率失真函數(shù)給出了熵壓縮編碼可能達(dá)到的最小熵率與失真的關(guān)系，其逆函數(shù)稱為失真率函數(shù)，表示一定信息速率下所可能達(dá)到的最小的平均失真。,二、信息率失真函數(shù)的性質(zhì),允許失

12、真度D的下限可以是零，即不允許任何失真的情況。,1、 R(D)的定義域,R(D)的定義域?yàn)?且：,解：,[例4] 設(shè)試驗(yàn)信道輸入符號(hào)集 ，各符號(hào)對(duì)應(yīng)概率分別為)={1/3,1/3,1/3} ，失真矩陣如下所示，求 和 以及相應(yīng)的試驗(yàn)信道的轉(zhuǎn)移概率矩陣。,令對(duì)應(yīng)最小失真度 的

13、 ，其它為“0”，可得對(duì)應(yīng) 的試驗(yàn)信道轉(zhuǎn)移概率矩陣為,上式中第二項(xiàng)最小，所以令 ， ，可得對(duì)應(yīng) 的試驗(yàn)信道轉(zhuǎn)移概率矩陣為,2、 R(D)是關(guān)于平均失真度D的下凸函數(shù),設(shè) 為任意兩個(gè)平均失真， ，則有：,3 、 R(D) 是

14、 區(qū)間上的連續(xù)和嚴(yán)格單調(diào)遞減函數(shù)。 由信息率失真函數(shù)的下凸性可知， R(D)在 上連續(xù)。又由R(D)函數(shù)的非增性且不為常數(shù)知， R(D)是區(qū)間 上的嚴(yán)格單調(diào)遞減函數(shù)。,信息率失真函數(shù)的一般形狀,有失真時(shí)逆信源編碼定理,率失真函數(shù)R(D)是保證失真不超過(guò)D時(shí)，改變編碼方式（p(v|u)），使平均互信息最小當(dāng)速率R小于R(D)