信息論基礎(chǔ)-第七章

信息論與編碼-限失真信源編碼第七章限失真信源編碼1信息論與編碼-限失真信源編碼第五章我們討論了無失真信源編碼。但是，在很多場(chǎng)合，特別是對(duì)于連續(xù)信源，因?yàn)槠浣^對(duì)熵為無限大，若要求無失真地對(duì)其進(jìn)行傳輸，則要求信道的信息傳輸率也為無限大，這是不現(xiàn)實(shí)的。因此也就不可能實(shí)現(xiàn)完全無失真?zhèn)鬏?。另一方面，從無失真信源編碼定理來考慮，由于要求碼字包含的信息量大于等于信源的熵，所以對(duì)于連續(xù)信源，要用無限多個(gè)比特才能完全無失真地來描述。2信息論與編碼-限失真信源編碼第16講7.1失真測(cè)度3信息論與編碼-限失真信源編碼即使對(duì)于離散信源，由于處理的信息量越來越大，使得信息的存儲(chǔ)和傳輸成本很高，而且在很多場(chǎng)合，過高的信息率也沒有必要，例如：由于人耳能夠接收的帶寬和分辨率是有限的，因此對(duì)數(shù)字音頻傳輸?shù)臅r(shí)候，就允許有一定的失真，并且對(duì)欣賞沒有影響。又如對(duì)于數(shù)字電視，由于人的視覺系統(tǒng)的分辨率有限，并且對(duì)低頻比較敏感，對(duì)高頻不太敏感，因此也可以損失部分高頻分量，當(dāng)然要在一定的限度內(nèi)。等等這些，都決定了限失真信源編碼的重要性。4信息論與編碼-限失真信源編碼在限失真信源編碼里，一個(gè)重要的問題就是在一定程度的允許失真限度內(nèi)，能把信源信息壓縮到什么程度，即最少用多少比特?cái)?shù)才能描述信源。這個(gè)問題已經(jīng)被香農(nóng)解決。香農(nóng)在1948年的經(jīng)典論文中已經(jīng)提到了這個(gè)問題，在1959年，香農(nóng)又在他的一篇論文“保真度準(zhǔn)則下的離散信源編碼定理”里討論了這個(gè)問題。研究這個(gè)問題并做出較大貢獻(xiàn)的還有前蘇聯(lián)的柯爾莫郭洛夫（Kolmogorov）以及伯格（T.Berger）等。5信息論與編碼-限失真信源編碼信息率失真理論是矢量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)。本章主要介紹信息率失真理論的基本內(nèi)容，包括信源的失真度和信息率失真函數(shù)的定義與性質(zhì)，離散信源和連續(xù)信源的信息率失真函數(shù)計(jì)算，在此基礎(chǔ)上論述保真度準(zhǔn)則下的信源編碼定理——即香農(nóng)第三編碼定理。6信息論與編碼-限失真信源編碼在實(shí)際中，信號(hào)有一定的失真是可以容忍的，但當(dāng)失真大于某一限度后，信息質(zhì)量將被嚴(yán)重?fù)p傷，甚至喪失其實(shí)用價(jià)值，因此，要規(guī)定失真限度，必須對(duì)其有一個(gè)定量的失真測(cè)度P(Yj/xi)XY信道的數(shù)學(xué)模型7信息論與編碼-限失真信源編碼轉(zhuǎn)移矩陣描述P=(P(yj/xi))nxmP矩陣為一個(gè)n×m矩陣，其每行元素之和等于1。

從這個(gè)角度看編碼器可以看作一個(gè)廣義的信道，X為信道的輸入，Y是信道的輸出。與無失真編碼不同，這是從輸入到輸出是一個(gè)多對(duì)一的映射，它是不可逆的，信源符號(hào)與碼元符號(hào)之間的差異就是編碼時(shí)引入的失真。8信息論與編碼-限失真信源編碼7.1.1、失真函數(shù)（定量地描述信息失真程度）設(shè)某信源輸出的隨機(jī)變量為X，其值集合為，經(jīng)過編碼后輸出為，設(shè)對(duì)應(yīng)，如果則認(rèn)為沒有失真。當(dāng)時(shí)，就產(chǎn)生了失真，失真的大小，用失真函數(shù)來衡量。單個(gè)符號(hào)的失真函數(shù)(失真度)的定義為9信息論與編碼-限失真信源編碼由于輸入符號(hào)有n個(gè)，輸出符號(hào)有m個(gè)，所以共有個(gè)，寫成矩陣形式，就是d被稱為失真矩陣。10信息論與編碼-限失真信源編碼例4-1-1設(shè)信源符號(hào),編碼器的輸出符號(hào)，規(guī)定失真函數(shù)為：d(0,0)=d(1,1)=0;d(0,1)=d(1,0)=1;d(0,2)=d(1,2)=0.5求失真矩陣d.解：由失真矩陣定義：11信息論與編碼-限失真信源編碼失真函數(shù)的函數(shù)形式可以根據(jù)需要適當(dāng)選取，如平方代價(jià)函數(shù)、絕對(duì)代價(jià)函數(shù)、均勻代價(jià)函數(shù)等：平方失真：絕對(duì)失真：相對(duì)失真：誤碼(漢明)失真：12信息論與編碼-限失真信源編碼也可以按其它的標(biāo)準(zhǔn)，如引起的損失、風(fēng)險(xiǎn)、主觀感覺上的差別等來定義失真函數(shù)。二、平均失真由于信源X和信宿Y都是隨機(jī)變量，所以符號(hào)失真度函數(shù)也是一個(gè)隨機(jī)變量，傳輸時(shí)引起的平均失真應(yīng)該是符號(hào)失真度函數(shù)在信源概率空間和信宿概率空間求平均，即：13信息論與編碼-限失真信源編碼平均失真是符號(hào)失真函數(shù)在信源空間和信宿空間平均的結(jié)果，是描述某一信源在某一信道傳輸時(shí)失真的大小，是從整體上描述系統(tǒng)的失真情況。14信息論與編碼-限失真信源編碼三、信源符號(hào)序列的失真從上面的單符號(hào)失真函數(shù)，可以得到信源符號(hào)序列的失真函數(shù)和平均失真度。由于序列時(shí)相當(dāng)于是一個(gè)由單符號(hào)隨機(jī)變量組成的隨機(jī)矢量，仿照單符號(hào)時(shí)的情況，對(duì)單符號(hào)離散無記憶信源的L次擴(kuò)展信源，在信道中的傳遞作用相當(dāng)于單符號(hào)離散無記憶信道的L次擴(kuò)展信道，輸出也是一個(gè)隨機(jī)變量序列，可得：15信息論與編碼-限失真信源編碼定義7.1設(shè)發(fā)送序列xi=xi1xi2…xiN,,接收序列為yi=yj1yj2…yjN,定義序列失真度為：d(xi,yj)=d(xi1xi2…xiN,

yj1yj2…yjN)=d(xi1,yj1)+d(xi2,yj2)+…+d(xiN,yjN)=∑d(xik,yjk)(k=1toN)也就是說信源序列的失真度等于序列對(duì)應(yīng)單個(gè)符號(hào)失真度之和，寫成矩陣形式rNxsN16信息論與編碼-限失真信源編碼故對(duì)L長的信源序列，其平均失真度為17信息論與編碼-限失真信源編碼18信息論與編碼-限失真信源編碼平均每個(gè)符號(hào)的平均失真度為當(dāng)信源與信道無記憶時(shí)，，而19信息論與編碼-限失真信源編碼如果滿足平穩(wěn)條件：若平均失真度不大于我們所允許的失真D，即我們稱此為保真度準(zhǔn)則。20信息論與編碼-限失真信源編碼7.2信息率失真函數(shù)在信源給定，并且也定義了具體的失真函數(shù)之后，我們總是希望在滿足一定的失真限度要求的情況下，使信源最后輸出的信息率R盡可能地小。也就是說，要在滿足保真度準(zhǔn)則下（），尋找信源輸出信息率R的下限值。1)信息壓縮問題對(duì)于給定的信源，在滿足給定失真的前提下使編碼后的信息率（I(X；Y)）最小。212）限失真編碼的研究方法將有失真信源編碼器視作有干擾的信道，用分析信道傳輸?shù)姆椒▉硌芯肯奘д婢幋a問題。3）D允許信道滿足的所有轉(zhuǎn)移概率Pij構(gòu)成了一類假想信道，稱為D允許信道（或D失真許可的試驗(yàn)信道），對(duì)于模擬信道記為信息論與編碼-限失真信源編碼22信息論與編碼-限失真信源編碼對(duì)于離散無記憶信道，有我們的目的，就是要在上述允許信道中，尋找到一個(gè)信道P(Y/X)，使得從輸入端傳送過來的信息量最少，即I(X;Y)最小。對(duì)于離散無記憶信源的N次擴(kuò)展信源和離散無記憶N次擴(kuò)展信道，相應(yīng)的D失真許可信道為：4）信息率失真函數(shù)R(D)這個(gè)最小的互信息就稱為信息率失真函數(shù)R(D)，簡稱為率失真函數(shù)。23信息論與編碼-限失真信源編碼。應(yīng)當(dāng)注意，在研究R(D)時(shí)，我們引用的條件概率并沒有實(shí)際信道的含義，只是為了求平均互信息的最小值而引用的、假想的可變?cè)囼?yàn)信道。實(shí)際上這些信道反應(yīng)的僅是不同的有失真信源編碼，或稱信源壓縮。所以改變?cè)囼?yàn)信道求最小值，實(shí)質(zhì)上是選擇一種編碼方式式信息24信息論與編碼-限失真信源編碼傳輸率為最小，也就是在保真度準(zhǔn)則下，使信源的壓縮率最高。R(D)是在信源和允許失真固定情況下，接收端用戶收到的滿足失真要求而再現(xiàn)信源消息所必須獲得的最少平均信息量。R(D)反映了信源可以壓縮的程度，是在滿足一定失真條件下，信源可壓縮的最低值。25信息論與編碼-限失真信源編碼[例4-1-2]已知編碼器輸入的概率分布是信道轉(zhuǎn)移矩陣分別為：解：因?yàn)?，用代入因?yàn)椋核裕?6信息論與編碼-限失真信源編碼又因?yàn)?，所以：代入互信息公式可得：用代入同樣可?7信息論與編碼-限失真信源編碼可見，當(dāng)p(x)一定時(shí)，I(X;Y)隨Pij而變。可以證明，當(dāng)p(x)一定時(shí)，I(X;Y)是關(guān)于Pij的下凸函數(shù)。因此當(dāng)Pij改變時(shí)I(X;Y)有一極小值。信息率失真函數(shù)的物理意義：對(duì)于給定的信源，在平均失真限度D條件下()，信息率容許壓縮的最小值。是衡量一種具體信源壓縮方法的尺子。此時(shí)的Pij實(shí)際上指的是一種限失真信源編碼方法。下面通過對(duì)一個(gè)信源處理的例子，進(jìn)一步明確信息率失真函數(shù)的物理意義。28信息論與編碼-限失真信源編碼[例4-1-3]設(shè)信源的符號(hào)表A={a1,a2,a3,…,a2n},概率分布為p(ai)=1/2n,i=1,2,…2n,失真函數(shù)規(guī)定為由信源的概率分布可求出信源的熵為29信息論與編碼-限失真信源編碼如果對(duì)信源進(jìn)行不失真編碼，平均每個(gè)符號(hào)至少需要log2n個(gè)二進(jìn)制碼元?，F(xiàn)在假定允許有一定失真，假設(shè)失真限度D=1/2。也就是說，當(dāng)收到100個(gè)符號(hào)時(shí)，允許其中有50個(gè)以下的差錯(cuò)。這時(shí)信源的信息能夠少到多少呢？每個(gè)符號(hào)平均碼長能夠壓縮到什么程度呢？設(shè)想采用以下編碼方案。30信息論與編碼-限失真信源編碼等效試驗(yàn)信道圖：31信息論與編碼-限失真信源編碼按照上述關(guān)于失真函數(shù)的規(guī)定，求平均失真D由于上述編碼相當(dāng)于下圖所示的試驗(yàn)信道，它是一個(gè)確定信道，所以32信息論與編碼-限失真信源編碼由互信息量公式：信道輸出概率分布為：則輸出熵H（Y）為：33信息論與編碼-限失真信源編碼由以上結(jié)果可知道，經(jīng)壓縮編碼以后，信源需要傳送的信息率由原來的log2n，壓縮到也就是說信息率壓縮了所付出的代價(jià)是容忍1/2的平均失真。注意：一旦達(dá)到最小互信息量這個(gè)極限值，就是R(D)的數(shù)值（此處D=1/2）。如果超過這個(gè)極限值，那么，失真就要超過失真限度。如果需要壓縮的信息率更大，則容忍的失真就更大34信息論與編碼-限失真信源編碼五、信息率失真函數(shù)的性質(zhì)1.R(D)的定義域R(D)的定義域，即D的取值范圍。（1）因?yàn)镈是非負(fù)函數(shù)d(x,y)的數(shù)學(xué)期望，因此D也是非負(fù)函數(shù)，其下界為0。此時(shí)，意味著不允許失真，所以信道的信息率等于信源的熵，即但是平均失真度D,是否能達(dá)到下限值0，與單符號(hào)失真函數(shù)的定義有關(guān)35信息論與編碼-限失真信源編碼36信息論與編碼-限失真信源編碼37信息論與編碼-限失真信源編碼38信息論與編碼-限失真信源編碼（2）平均失真D也有一上界值。根據(jù)R(D)的定義，R(D)是在一定的約束條件下，平均互信息量I(X;Y)的最小值，其下界為0。R(D)和D的關(guān)系曲線一般如下圖所示。當(dāng)D大到一定程度，R(D)就達(dá)到其下界0，我們定義這時(shí)的D為。39信息論與編碼-限失真信源編碼

的計(jì)算：設(shè)當(dāng)平均失真時(shí)，R(D)以達(dá)到其下界0。當(dāng)允許更大失真時(shí)，即時(shí)，R(D)仍只能繼續(xù)是0。因?yàn)楫?dāng)X和Y統(tǒng)計(jì)獨(dú)立時(shí)，平均互信息I(X;Y)=0，可見當(dāng)時(shí)，信源X和接收符號(hào)Y已經(jīng)統(tǒng)計(jì)獨(dú)立了，因此，與x無關(guān)。R(D)DR(D)>0R(D)=040信息論與編碼-限失真信源編碼因此，就是在R(D)=0的條件下，看在什么分布下(P(xi)一定)，能夠得到的平均失真D的最小值，即也可以改寫成41信息論與編碼-限失真信源編碼也就是說，要求的數(shù)學(xué)期望的最小值。這個(gè)最小值是一定存在的。比如這樣分布：當(dāng)某一個(gè)使得為最小時(shí)，就取，而其余的，此時(shí)求得的的數(shù)學(xué)期望一定是最小的。此時(shí)，有例題：設(shè)輸入輸出符號(hào)表為X=Y={0,1}，輸入概率分布為，失真矩陣為42信息論與編碼-限失真信源編碼求解：43信息論與編碼-限失真信源編碼而輸出符號(hào)概率為例題2：輸入輸出符號(hào)表同上題，失真矩陣為求解：此時(shí)44信息論與編碼-限失真信源編碼(3)R(D)函數(shù)的連續(xù)性現(xiàn)在證明R(D)在定義域0~Dmax之間的連續(xù)性（1）（2）由于是的連續(xù)函數(shù)，即當(dāng)（3）則45信息論與編碼-限失真信源編碼(4)R(D)函數(shù)的下凸性46信息論與編碼-限失真信源編碼

47信息論與編碼-限失真信源編碼

48信息論與編碼-限失真信源編碼（5）R(D)函數(shù)的單調(diào)性證明：非遞增性證明由定義可以證明，當(dāng)則于是上式表明因?yàn)楹螅谝粋€(gè)較大范圍內(nèi)求得的極小值不會(huì)大于一個(gè)小范圍的極小值。所以R(D)是非遞增函數(shù)。49信息論與編碼-限失真信源編碼單調(diào)性證明即證明不等式中的等號(hào)不成立。用反證法：設(shè)50信息論與編碼-限失真信源編碼

51信息論與編碼-限失真信源編碼所以，R(D)有如下基本性質(zhì)：，定義域?yàn)椋?dāng)時(shí)，R(D)=0。R(D)是關(guān)于D的連續(xù)函數(shù)。R(D)是關(guān)于D的嚴(yán)格遞減函數(shù)。52信息論與編碼-限失真信源編碼

53信息論與編碼-限失真信源編碼因此，當(dāng)規(guī)定了允許失真，又找到了適當(dāng)?shù)氖д婧瘮?shù)，就可以找到該失真條件下的最小信息率R(D)，用不同的方法進(jìn)行數(shù)據(jù)壓縮時(shí)（在允許的失真限度D內(nèi)），其壓縮的程度如何，可以用R(D)來衡量。由它可知是否還有壓縮潛力，有多大的壓縮潛力。因此，有關(guān)R(D)的研究也是信息論領(lǐng)域的一個(gè)研究熱點(diǎn)。54信息論與編碼-限失真信源編碼§7.3R(D)的計(jì)算[信息論基礎(chǔ)教程,李亦農(nóng),北郵出版社]已知信源的概率分布和失真函數(shù)，就可以求得信源的R(D)函數(shù)。求R(D)函數(shù)，實(shí)際上是一個(gè)求有約束問題的最小值問題。即適當(dāng)選取試驗(yàn)信道的使平均互信息55信息論與編碼-限失真信源編碼最小化，并使?jié)M足以下約束條件應(yīng)用拉格朗日乘子法，原則上總是可以求出上述問題的界。56信息論與編碼-限失真信源編碼（1）R(D)函數(shù)的參量表達(dá)式：已知57信息論與編碼-限失真信源編碼為了在（2）式的n+1個(gè)條件下求（1）式的極值，引入拉格郎日乘子s和ui(i=1,2,…,n),然后對(duì)p(yj/xi)進(jìn)行求導(dǎo)，并令其為零，即得：58信息論與編碼-限失真信源編碼得：59信息論與編碼-限失真信源編碼由此可解出s為參量的P(yj).為了保證P(yj)均為非負(fù)值，對(duì)s有限制。用這些P(yj)得到n個(gè)60信息論與編碼-限失真信源編碼所以有：61信息論與編碼-限失真信源編碼一般情況下，參量s無法消去，因此得不到R(D)函數(shù)的閉式解。若無法消去參量s就需要進(jìn)行逐點(diǎn)計(jì)算。將R(D)看成D(s)和s的隱函數(shù)，而又是s的函數(shù)，即R(D)=f(D,S,)利用全微分公式對(duì)R(D)函數(shù)求導(dǎo)，得

62信息論與編碼-限失真信源編碼為求出將（7）式對(duì)s求導(dǎo)得到63信息論與編碼-限失真信源編碼此式表明：參量s是信息率失真函數(shù)R(D)的斜率。由R(D)函數(shù)在0<D<Dmax之間是嚴(yán)格單調(diào)遞減函數(shù)可知，s是負(fù)值，且s將隨D的增加而增加。又R(D)的性質(zhì)可知，在D=0處R(D)的斜率可能為負(fù)無窮大；當(dāng)D>Dmax時(shí)，R(D)=0,其斜率為0，所以參量s的取值范圍是64信息論與編碼-限失真信源編碼下面將簡單介紹參量表達(dá)式方法求解失真函數(shù)R(D)。這里結(jié)合例子給出計(jì)算步驟：[例4-2-1]設(shè)輸入輸出符號(hào)表為X=Y={0，1}，輸入概率分布p(x)={p,1-p},0<p<=1/2,失真矩陣為求信息率失真函數(shù)R(D)65信息論與編碼-限失真信源編碼

66信息論與編碼-限失真信源編碼

67信息論與編碼-限失真信源編碼

68信息論與編碼-限失真信源編碼

69信息論與編碼-限失真信源編碼結(jié)果得到如下圖所示曲線：70信息論與編碼-限失真信源編碼但一般來說，求解會(huì)是非常復(fù)雜的。這里不準(zhǔn)備做復(fù)雜的推導(dǎo)過程，只給出幾個(gè)結(jié)果。（1）當(dāng)，時(shí)，71信息論與編碼-限失真信源編碼，（2）當(dāng)，時(shí)，，（3）當(dāng)，時(shí)，，72信息論與編碼-限失真信源編碼7.4限失真信源編碼定理（香農(nóng)第三編碼定理-信息率與失真之間關(guān)系的一個(gè)極限定律）定理7.1設(shè)R(D)是離散無記憶信源的信息率失真函數(shù)并且失真函數(shù)為有限值，對(duì)于任意的允許失真D≥0和任意小的正數(shù)ε>0，當(dāng)信源長度N足夠長時(shí)，一定存在一種編碼CK,其碼字個(gè)數(shù)M≤exp{N[R(D)+ε]},而編碼后的平均失真73信息論與編碼-限失真信源編碼定理7.2（