第4章限失真信源編碼4.1平均失真和信息率失真函數(shù)4.2離散信源的信息率失真函數(shù)4.3連續(xù)信源的信息率失真函數(shù)4.4限失真信源編碼定理(香農(nóng)第三定理) 4.5常見的限失真信源編碼方法4.1平均失真和信息率失真函數(shù)4.1.1失真度與平均失真度4.1.2信息率失真函數(shù)4.1.3信息率失真函數(shù)的特性限失真信源編碼的必要性1．信源特性對于連續(xù)信源，因?yàn)槠浣^對熵為無限大，若要求無失真地對其進(jìn)行傳輸，則要求信道的信息傳輸率也為無限大，這是不現(xiàn)實(shí)的。（在信道中，由于帶寬總是有限的，所以信道容量總要受到限制）因此也就不可能實(shí)現(xiàn)完全無失真?zhèn)鬏?。另一方面，從無失真信源編碼定理來考慮，由于要求碼字包含的信息量大于等于信源的熵，所以對于連續(xù)信源，要用無限多個(gè)比特才能完全無失真地來描述2．?dāng)?shù)據(jù)壓縮即使對于離散信源，由于處理的信息量越來越大，使得信息的存儲和傳輸成本很高，（數(shù)字系統(tǒng)的廣泛應(yīng)用，需要傳送、存儲和處理大量的數(shù)據(jù)），為了提高傳輸和存儲的效率，就必須對有待傳送和存儲的數(shù)據(jù)進(jìn)行壓縮，這樣也會損失一定信息，帶來失真。3．符合實(shí)際在很多場合，過高的信息率也沒有必要。例如：由于人耳能夠接收的帶寬和分辨率是有限的，因此對數(shù)字音頻傳輸?shù)臅r(shí)候，就允許有一定的失真，并且對欣賞沒有影響。——把頻譜范圍從20Hz~8000Hz的語音信號去掉低頻和高頻，看成帶寬只有300Hz~3400Hz的信號。這樣，即使傳輸?shù)恼Z音信號會有一些失真，人耳還可以分辨和感覺出來，已滿足語音傳輸?shù)囊?，所以這種失真是允許的。例如對于數(shù)字電視，由于人的視覺系統(tǒng)的分辨率有限，并且對低頻比較敏感，對高頻不太敏感，因此也可以損失部分高頻分量，當(dāng)然要在一定的限度內(nèi)。等等這些，都決定了限失真信源編碼的重要性。限失真信源編碼的必要性限失真信源編碼研究的問題在限失真信源編碼里，一個(gè)重要的問題就是在一定程度的允許失真限度內(nèi)，能把信源信息壓縮到什么程度，即最少用多少比特?cái)?shù)才能描述信源。也就是，在允許一定程度失真的條件下，如何能快速地傳輸消息。這是本章討論的問題。(編碼前)信源的信息率：每個(gè)信源符號所攜帶的平均信息量。

如果信源輸出的信息率大于信道的傳輸能力，（此時(shí)不可能無差錯(cuò)傳輸）就必須對信源進(jìn)行壓縮，使壓縮后的信源信息率小于信道傳輸能力，但同時(shí)保證壓縮所引入的失真不超過預(yù)先規(guī)定的限度D。因此，信息壓縮問題就是對于給定的信源，在滿足平均失真的前提下，使編碼后的信息率盡可能小。限失真信源編碼研究的問題

上述問題已經(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）等。信息率失真理論是量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)。限失真信源編碼研究的問題4.1平均失真和信息率失真函數(shù)

4.1.1

失真度與平均失真度信源編碼器描述失真函數(shù)

失真矩陣圖4.1.1信源編碼器例4.1.1離散對稱信道(m=n)，信源變量，接收變量，定義單符號失真度（失真函數(shù)）為：當(dāng)a=1時(shí)，這種失真稱為漢明失真。漢明失真矩陣為一方陣，而且對角線上的元素為零，即4.1.1

失真度與平均失真度

4.1.1

失真度與平均失真度

例4.1.2二元刪除信源信源符號X∈｛0，1｝,編碼器輸出符號Y∈｛0,1,2｝,規(guī)定失真函數(shù)為求失真矩陣常用失真函數(shù)平方失真：絕對失真：相對失真：

誤碼失真：4.1.1

失真度與平均失真度

平均失真平均失真是對給定信源分布且轉(zhuǎn)移概率分布為的信源編碼器失真的總體量度。平均失真是符號失真函數(shù)在信源空間和信宿空間平均的結(jié)果，是從整體上描述系統(tǒng)的失真情況。4.1.1

失真度與平均失真度

圖4.1.2信源編碼器等效模型例4.1.3已知編碼器輸入的概率分布為，編碼器轉(zhuǎn)移矩陣分別為定義單符號失真度，計(jì)算兩種信源編碼方法帶來的平均失真。解：得4.1.1

失真度與平均失真度

D允許信道（D允許的試驗(yàn)信道）對于離散無記憶信道信息率失真函數(shù)R(D)對于離散無記憶信源4.1.2

信息率失真函數(shù)D允許信道（D允許的試驗(yàn)信道）對于離散無記憶信道信息率失真函數(shù)R(D)對于離散無記憶信源4.1.2

信息率失真函數(shù)例4.1.3已知編碼器輸入的概率分布為，編碼器轉(zhuǎn)移矩陣分別為定義單符號失真度，計(jì)算兩種信源編碼方法帶來的平均失真。解：平均失真

編碼后得信源信息率為bit/符號bit/符號說明編碼1對信源數(shù)據(jù)的壓縮率高，但是編碼1帶來的失真要大一些。若例4.1.3中的兩種編碼方法都滿足失真度的限制，當(dāng)然編碼1要好些，因?yàn)樗鼔嚎s掉了更多的信息。事實(shí)上，在失真度的限制下，肯定存在一種編碼方法，使編碼后的信息率最小，這個(gè)最小的信息率就是信息率失真函數(shù)。但具體是什么編碼方法，香農(nóng)定理沒有指出來。4.1.2

信息率失真函數(shù)例4.1.4限失真信源編碼實(shí)例，信源符號等概率分布，失真限度D=1/2.失真函數(shù)規(guī)定為由信源概率分布可求出信源熵為編碼映射表相當(dāng)于轉(zhuǎn)移概率矩陣圖4.1.3編碼映射關(guān)系4.1.2

信息率失真函數(shù)編碼方案：平均失真D為圖4.1.3編碼映射關(guān)系4.1.2

信息率失真函數(shù)由該試驗(yàn)信道模型知，它是一個(gè)確定信道由互信息公式可得信道輸出概率分布為所以輸出an的概率分布為4.1.2

信息率失真函數(shù)則輸出熵H(Y)為結(jié)論：經(jīng)信源壓縮編碼后，信源的信息率由編碼前的H(X)=log2n，壓縮到編碼后的這是采用了上述壓縮編碼方法的結(jié)果，所付出的代價(jià)是容忍了1/2的平均失真。輸入熵失真D下?lián)p失的熵4.1.2

信息率失真函數(shù)思考1：如果某編碼方法造成的失真D>1/2，則該編碼器輸出信息率比上例中的輸出信息率的關(guān)系？思考1：如果規(guī)定失真限度為1/2，則如何根據(jù)輸出信息率評價(jià)編碼方法的性能？4.1.2

信息率失真函數(shù)4.1.3

信息率失真函數(shù)的特性1.R(D)函數(shù)的定義域D∈［0,Dmax］2.R(D))函數(shù)的下凸性和連續(xù)性3.R(D)函數(shù)的單調(diào)遞減性圖4.1.4R(D)和D的關(guān)系結(jié)論：R(D)是非負(fù)的實(shí)數(shù)，即R(D)≥0。其定義域?yàn)?～Dmax，其值為0～H(X)。當(dāng)D＞Dmax時(shí),R(D)≡0。R(D是關(guān)于D的下凸函數(shù)，因而也是關(guān)于D的連續(xù)函數(shù)。R(D)是關(guān)于D的嚴(yán)格遞減函數(shù)。4.1.3

信息率失真函數(shù)的特性求解DmaxR(D)R(D)>0R(D)=0是滿足的所有平均失真D中的最小值。當(dāng)時(shí)，當(dāng)時(shí)，推導(dǎo)過程也可寫成求解方法：令當(dāng)某一個(gè)yj使得最小時(shí)，就取,而其余的.此時(shí)求得的一定是最小的.例4.1.5設(shè)輸入輸出符號表為X=Y={0,1}，輸入概率分布為，失真矩陣為求解：而輸出符號概率為4.1.3

信息率失真函數(shù)的特性思考：已知輸出符號概率，如何確定編碼映射表或轉(zhuǎn)移概率矩陣思考：失真D=0時(shí)，如何確定編碼映射表或轉(zhuǎn)移概率矩陣4.1.3

信息率失真函數(shù)的特性4.2離散信源的信息率失真函數(shù)已知信源的概率分布和失真函數(shù)，就可以求得信源的R(D)函數(shù)。求R(D)函數(shù)，實(shí)際上是一個(gè)求有約束問題的最小值問題。即適當(dāng)選取試驗(yàn)信道的使平均互信息最小化.并使?jié)M足以下約束條件應(yīng)用拉格朗日乘子法，原則上總是可以求出上述問題的界。但一般來說，求解會是非常復(fù)雜的。4.2.1二元信源的信息率失真函數(shù)例4.2.1二元對稱信源，若失真矩陣為

，求該信源的，和函數(shù)。解：圖4.2.1二元對稱信源的R(D)曲線4.2.2離散對稱信源的信息率失真函數(shù)例4.2.2四元對稱信源，若失真矩陣為

，求該信源的，和函數(shù)。解：圖4.2.2四元對稱信源的R(D)曲線4.3連續(xù)信源的信息率失真函數(shù)連續(xù)信源，概率密度函數(shù)為。編碼輸出，漢明失真函數(shù)為。編碼器對應(yīng)的假想信道的轉(zhuǎn)移概率密度為?？捎?jì)算平均失真度假想信道的平均互信息假若允許的失真度為D，滿足的假想信道叫做D允許信道，則連續(xù)信源的信息率失真函數(shù)為式中Inf指下邊界，相當(dāng)于離散信源中的最小值。嚴(yán)格地說，連續(xù)信源的取值集合為連續(xù)集合，連續(xù)信源的信息率失真函數(shù)可能不存在最小值，但存在下邊界。4.3連續(xù)信源的信息率失真函數(shù)某些特殊情況下R(D)的表示式為：率失真函數(shù)4.4限失真信源編碼定理（香農(nóng)第三定理）限失真信源編碼定理：設(shè)離散無記憶信源X的信息率失真函數(shù)R(D)，則當(dāng)信息率R＞R(D)，只要信源序列長度N足夠長，一定存在一種編碼方法，其譯碼失真小于或等于D+ε，ε為任意小的正數(shù)；反之，若R＜R(D)，則無論采用什么樣的編碼方法，其譯碼失真必大于D

。如果是二元信源，對于任意小的ε＞0，每一個(gè)信源符號的平均碼長滿足如下公式在失真限度內(nèi)使信息率任意接近R(D)編碼方法存在。4.5.1矢量量化的MATLAB實(shí)現(xiàn) 4.5.2預(yù)測編碼 4.5.3變換編碼4.5常見的限失真信源編碼方法4.5.1矢量量化的MATLAB實(shí)現(xiàn)標(biāo)量量化

連續(xù)信源進(jìn)行編碼的主要方法是量化，即將連續(xù)的樣值x離散化成為yi，i=1,2,3,…,n。由于x是一個(gè)標(biāo)量，因此稱為標(biāo)量量化。在量化的過程中，將會引入失真，量化是必須使這些失真最小。設(shè)信源符號的取值區(qū)間為(a0,

an)，即a0＜x＜an，a0可為負(fù)無限，an可為正無限，所以上述假設(shè)不失一般性。量化就是將上面的區(qū)間分成n個(gè)小區(qū)間，每個(gè)區(qū)間內(nèi)定一個(gè)量化值yi，若各區(qū)間端點(diǎn)為ai-1和ai，必有

a0≤y1≤a1≤y2≤…≤an-1≤yn≤an

最佳標(biāo)量量化就是在一定的n值時(shí)，選擇各ai和yi以使失真最小。此時(shí)的信息率為

R=logn

4.5.1矢量量化的MATLAB實(shí)現(xiàn)標(biāo)量量化

在MATLAB仿真中，可以使用量化函數(shù)quantiz，根據(jù)預(yù)設(shè)的量化分區(qū)partition和碼書codebook實(shí)現(xiàn)標(biāo)量量化。例4.5.2

對單音信號進(jìn)行量化，并采

用Lloyd算法優(yōu)化碼書和量

化間隔。圖4.5.1標(biāo)量量化壓擴(kuò)技術(shù)

綜合考慮大、小功率的情況，將它們區(qū)別對待，即非均勻量化，小功率時(shí)量化級差小；大功率時(shí)量化級差大。這樣就減小了小功率時(shí)的量化噪聲，增大了大功率時(shí)的量化噪聲。使得在較低的比特?cái)?shù)編碼時(shí)，既保證了小功率時(shí)的信噪比，又利用了大功率時(shí)信噪比的富余量。矢量量化

在前面的最佳編碼中可看到將離散信源的多個(gè)符號聯(lián)合編碼可提高效率。連續(xù)信源也是如此，當(dāng)把多個(gè)信源符號聯(lián)合起來形成多維矢量，再對矢量進(jìn)行標(biāo)量量化時(shí)，自由度將更大，同樣的失真下，量化級數(shù)可進(jìn)一步減少，碼率可進(jìn)一步壓縮。4.5.1矢量量化的MATLAB實(shí)現(xiàn)預(yù)測編碼就是從已收到的符號來提取關(guān)于未收到的符號的信息，從而預(yù)測其最可能的值作為預(yù)測值；并對它與實(shí)際值之差進(jìn)行編碼。由于這個(gè)差值一般都比較小，所以在編碼時(shí)會出現(xiàn)很多連“0”值，再采用游程編碼，就可以大大地壓縮碼率。由此可見，預(yù)測編碼是利用信源符號之間的相關(guān)性來壓縮碼率的，對于獨(dú)立信源，預(yù)測就沒有可能。樣本相關(guān)性越強(qiáng)，預(yù)測模型越準(zhǔn)確，就可以獲得較高的壓縮比。根據(jù)預(yù)測模型的不同，預(yù)測編碼可分為線性預(yù)測和非線性預(yù)測。線性預(yù)測是利用線性方程計(jì)算預(yù)測值的編碼方法，也稱差值脈沖編碼調(diào)制(DifferentionPulseCodeModulation，DPCM)；非線性預(yù)測是利用非線性方程計(jì)算預(yù)測值的編碼方法。本教程主要介紹線性預(yù)測編碼DPCM。4.5.2預(yù)測編碼線性預(yù)測編碼DPCMDPCM算法中，若已知k時(shí)刻之前的m個(gè)數(shù)據(jù)為以這m個(gè)數(shù)據(jù)為先驗(yàn)數(shù)據(jù)預(yù)測第k時(shí)刻的輸出為，可表達(dá)為

所有輸出數(shù)據(jù)與預(yù)測數(shù)據(jù)之間的差值為待預(yù)測量，即[0,p(1),

p(2),

p(3),...,

p(m-1),

p(m)]求出預(yù)測值與實(shí)際值的差后，可對其進(jìn)行壓縮編碼，由于該差值與實(shí)際值相比較小，所以壓縮編碼的平均碼長將大大縮短，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。4.5.2預(yù)測編碼[0,p(1),

p(2),

p(3),...,

p(m-1),

p(m)]線性預(yù)測編碼DPCMDPCM算法中，若已知k時(shí)刻之前的m個(gè)數(shù)據(jù)為以這m個(gè)數(shù)據(jù)為先驗(yàn)數(shù)據(jù)預(yù)測第k時(shí)刻的輸出為，可表達(dá)為

所有輸出數(shù)據(jù)與預(yù)測數(shù)據(jù)之間的差值為待預(yù)測量，即[0,p(1),

p(2),

p(3),...,

p(m-1),

p(m)]求出預(yù)測值與實(shí)際值的差后，可對其進(jìn)行壓縮編碼，由于該差值與實(shí)際值相比較小，所以壓縮編碼的平均碼長將大大縮短，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。4.5.2預(yù)測編碼[0,p(1),

p(2),

p(3),...,

p(m-1),

p(m)]例4.5.3對單音信號進(jìn)行差分預(yù)測，并采用MATLAB中的dpcmopt函數(shù)優(yōu)化碼書、量化間隔和預(yù)測模型系數(shù)。

4.5.2預(yù)測編碼圖4.5.2DPCM編碼程序運(yùn)行結(jié)果如圖4.5.2所示，量化誤差分別為ans=0.00347.5325e-0044.5.3變換編碼變換編碼通過變換來解除或減弱信源符號間的相關(guān)性，再將變換后的樣值進(jìn)行標(biāo)量量化，或采用對于獨(dú)立信源符號的編碼方法，以達(dá)到壓縮碼率的目的。設(shè)有函數(shù)f(t)，0＜t＜T，則正交性歸一性其變換式為

反變換為

4.5.3變換編碼變換編碼常用的變換1.DCT(DiscreteCosineTransform)變換JPEG、MPEG等圖像壓縮標(biāo)準(zhǔn)中，就是主要采用的這種變換壓縮方法MATLAB中可采用dct2和idct2進(jìn)行數(shù)字圖像的2維DCT變換和逆變換。

例4.5.4對數(shù)字圖像進(jìn)行DC