1、信息論與編碼-限失真信源編碼第三章簡要回顧信息率失真函數(shù)限失真信源編碼定理常用信源編碼方法信息論與編碼-限失真信源編碼第三章我們討論了無失真信源編碼。但是，在很多場合，特別是對于連續(xù)信源，因為其絕對熵為無限大，若要求無失真地對其進行傳輸，則要求信道的信息傳輸率也為無限大，這是不現(xiàn)實的。因此也就不可能實現(xiàn)完全無失真?zhèn)鬏?。另一方面，從無失真信源編碼定理來考慮，由于要求碼字包含的信息量大于等于信源的熵，所以對于連續(xù)信源，要用無限多個比特才能完全無失真地來描述。信息論與編碼-限失真信源編碼即使對于離散信源，由于處理的信息量越來越大，使得信息的存儲和傳輸成本很高，而且在很多場合，過高的信息率也沒有必要，

2、例如：由于人耳能夠接收的帶寬和分辨率是有限的，因此對數(shù)字音頻傳輸?shù)臅r候，就允許有一定的失真，并且對欣賞沒有影響。又如對于數(shù)字電視，由于人的視覺系統(tǒng)的分辨率有限，并且對低頻比較敏感，對高頻不太敏感，因此也可以損失部分高頻分量，當然要在一定的限度內(nèi)。等等這些，都決定了限失真信源編碼的重要性。信息論與編碼-限失真信源編碼在限失真信源編碼里，一個重要的問題就是在一定程度的允許失真限度內(nèi)，能把信源信息壓縮到什么程度，即最少用多少比特數(shù)才能描述信源。這個問題已經(jīng)被香農(nóng)解決。香農(nóng)在1948年的經(jīng)典論文中已經(jīng)提到了這個問題，在1959年，香農(nóng)又在他的一篇論文“保真度準則下的離散信源編碼定理”里討論了這個問題。

3、研究這個問題并做出較大貢獻的還有前蘇聯(lián)的柯爾莫郭洛夫（Kolmogorov）以及伯格（T. Berger）等。信息論與編碼-限失真信源編碼信息率失真理論矢量化、數(shù)摸轉換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎。本章主要介紹信息率失真理論的基本內(nèi)容，包括信源的失真度和信息率失真函數(shù)的定義與性質(zhì)，離散信源和連續(xù)信源的信息率失真函數(shù)計算，介紹一些常用的限失真編碼方法等。信息論與編碼-限失真信源編碼4.1 平均失真和信息率失真函數(shù)一、失真函數(shù)設某信源輸出的隨機變量為X，其值集合為 ，經(jīng)過編碼后輸出為 ，設 對應 ，如果則認為沒有失真。當 時，就產(chǎn)生了失真，失真的大小，用失真函數(shù)來衡量。失真函數(shù)的定義為信息論與編

4、碼-限失真信源編碼由于輸入符號有n個，輸出符號有m個，所以共有 個，寫成矩陣形式，就是d被稱為失真矩陣。信息論與編碼-限失真信源編碼失真函數(shù) 的函數(shù)形式可以根據(jù)需要適當選取，如平方代價函數(shù)、絕對代價函數(shù)、均勻代價函數(shù)等：平方失真：絕對失真：相對失真：誤碼失真：信息論與編碼-限失真信源編碼也可以按其它的標準，如引起的損失、風險、主觀感覺上的差別等來定義失真函數(shù)。二、平均失真由于信源X和信宿Y都是隨機變量，所以符號失真度函數(shù)也是一個隨機變量，傳輸時引起的平均失真應該是符號失真度函數(shù) 在信源概率空間和信宿概率空間求平均，即信息論與編碼-限失真信源編碼平均失真是符號失真函數(shù)在信源空間和信宿空間平均的結

5、果，是描述某一信源在某一信道傳輸時失真的大小，是從整體上描述系統(tǒng)的失真情況。三、信源符號序列的失真從上面的單符號失真函數(shù)，可以得到信源符號序列的失真函數(shù)和平均失真度。由于序列時相當于是一個由單符號隨機變量組成的隨機矢量，仿照單符號時的情況，可得：信息論與編碼-限失真信源編碼設信源輸出的符號序列為 ，其中的每一個隨機變量 取自同一符號集 ，所以X共有 種不同的符號序列，記為 ，接收到的符號為 式中每一個符號取自符號集 ，所以Y共有 種不同的符號序列，記為 ，則 信息論與編碼-限失真信源編碼失真函數(shù)矩陣應該是一個 的矩陣。故對L長的信源序列，其平均失真度為平均每個符號的平均失真度為當信源無記憶時，

6、 ，而信息論與編碼-限失真信源編碼若平均失真度不大于我們所允許的失真D，即我們稱此為保真度準則。四、信息率失真函數(shù)在信源給定，并且也定義了具體的失真函數(shù)之后，我們總是希望在滿足一定的失真限度要求的情況下，使信源最后輸出的信息率R盡可能地小。也就是說，要在滿足保真度準則下（ ），尋找信源輸出信息率R的下限值。如果將信源編碼也看成是一個信道，構成了一類假想信道，信息論與編碼-限失真信源編碼稱為D允許信道（或D失真許可的試驗信道），記為對于離散無記憶信道，有我們的目的，就是要在上述允許信道 中，尋找到一個信道P(Y/X)，使得從輸入端傳送過來的信息量最少，即I(X;Y)最小。這個最小的互信息就稱為信

7、息率失真函數(shù)R(D)，簡稱為率失真函數(shù)，即信息論與編碼-限失真信源編碼其單位是比特/信源符號。應當注意，在研究R(D)時，我們引用的條件概率 并沒有實際信道的含義，只是為了求平均互信息的最小值而引用的、假想的可變試驗信道。實際上這些信道反應的僅是不同的有失真信源編碼，或稱信源壓縮。所以改變試驗信道求最小值，實質(zhì)上是選擇一種編碼方式式信息信息論與編碼-限失真信源編碼傳輸率為最小，也就是在保真度準則下，使信源的壓縮率最高。五、信息率失真函數(shù)的性質(zhì) 1. R(D)的定義域R(D)的定義域，即D的取值范圍。（1）因為D是非負函數(shù)d(x,y)的數(shù)學期望，因此D也是非負函數(shù)，其下界為0。此時，信息論與編碼

8、-限失真信源編碼意味著不允許失真，所以信道的信息率等于信源的熵，即（2）平均失真D也有一上界值 。根據(jù)R(D)的定義，R(D)是在一定的約束條件下，平均互信息量I(X;Y)的最小值，其下界為0。R(D)和D的關系曲線一般如下圖所示。當D大到一定程度，R(D)就達到其下界0，我們定義這時的D為 。信息論與編碼-限失真信源編碼 的計算：設當平均失真 時，R(D)以達到其下界0。當允許更大失真時，即 時，R(D)仍只能繼續(xù)是0。因為當X和Y統(tǒng)計獨立時，平均互信息I(X;Y)=0，可見當 時，信源X和接收符號Y已經(jīng)統(tǒng)計獨立了，因此 ，與x無關。 R(D)DR(D)0R(D)=0信息論與編碼-限失真信源

9、編碼因此， 就是在R(D)=0的條件下，看在什么分布下，能夠得到的平均失真D的最小值，即也可以改寫成信息論與編碼-限失真信源編碼也就是說，要求 的數(shù)學期望的最小值。這個最小值是一定存在的。比如 這樣分布：當某一個 使得 為最小時，就取 ，而其余的 ，此時求得的 的數(shù)學期望一定是最小的。此時，有例題：設輸入輸出符號表為X=Y=0,1，輸入概率分布為 ，失真矩陣為信息論與編碼-限失真信源編碼求解：信息論與編碼-限失真信源編碼而輸出符號概率為例題2：輸入輸出符號表同上題，失真矩陣為求解：信息論與編碼-限失真信源編碼此時，（2）R(D)函數(shù)的單調(diào)遞減性和連續(xù)性R(D)的單調(diào)遞減性是很容易理解的。因為允

10、許的失真越大，所要求的信息率就可以越小。根據(jù)R(D)的定義，他是在平均失真度小于或等于允許失真度D的所有試驗信道集合 中，取I(X;Y)的最小值。當允許失真D擴大，則 的集合也擴大，當然仍然包含原來滿足條件的所有信道。這是在擴大了的 集合中找I(X;Y)的最小值，信息論與編碼-限失真信源編碼顯然或者是最小值不變，或者是變小了，所以R(D)是非增的。關于R(D)的連續(xù)性，這里我們就不再證明了。所以，R(D)有如下基本性質(zhì)： ，定義域為 ，當 時，R(D)=0。R(D)是關于D的連續(xù)函數(shù)。R(D)是關于D的嚴格遞減函數(shù)。信息論與編碼-限失真信源編碼因此，當規(guī)定了允許失真，又找到了適當?shù)氖д婧瘮?shù) ，

11、就可以找到該失真條件下的最小信息率R(D)，用不同的方法進行數(shù)據(jù)壓縮時（在允許的失真限度D內(nèi)），其壓縮的程度如何，可以用R(D)來衡量。由它可知是否還有壓縮潛力，有多大的壓縮潛力。因此，有關R(D)的研究也是信息論領域的一個研究熱點。4.2 R(D)的計算已知信源的概率分布和失真函數(shù) ，就可以求得信源的R(D)函數(shù)。信息論與編碼-限失真信源編碼求R(D)函數(shù)，實際上是一個求有約束問題的最小值問題。即適當選取試驗信道的 使平均互信息最小化，并使 滿足以下約束條件信息論與編碼-限失真信源編碼應用拉格朗日乘子法，原則上總是可以求出上述問題的界。但一般來說，求解會是非常復雜的。這里不準備做復雜的推導過

12、程，只給出幾個結果。（1）當 ， 時，信息論與編碼-限失真信源編碼 ，（2）當 ， 時， ，（3）當 ， 時， ，信息論與編碼-限失真信源編碼4.3 限失真信源編碼定理（香農(nóng)第三定理）設R(D)唯一離散誤記憶平穩(wěn)信源的信息率失真函數(shù)，并且有有限的失真測度。則對于任意的 和 ，當信息率RR(D)時，一定存在一種編碼方法，其譯碼失真小于或等于 ，條件是編碼的信源序列長度L足夠長。反之，如果RR(D)，則無論采用什么編碼方法，其譯碼失真必大于D。定理說明，在允許失真為D的條件下，信源最小可信息論與編碼-限失真信源編碼達的信息傳輸率是信源的R(D)。保真度準則下的信源編碼定理（限失真信源編碼定理）是有

13、失真信源壓縮的理論基礎。定理說明了在允許失真D確定后，總存在一種編碼方法，使編碼的信息傳輸率大于R(D)且可以任意接近R(D)，而平均失真度小于允許失真D。而當信息傳輸率小于R(D)時，編碼的平均失真將大于D?？梢姡琑(D)是允許失真度為D的情況下信源信息壓縮的下限值。比較香農(nóng)第一定理和香農(nóng)第三定理可知，當信源給定后，無失真信源壓縮的信息論與編碼-限失真信源編碼極限值是信源熵H(X)，而又失真信源壓縮的極限值是信息率失真函數(shù)R(D)。在給定D后，一般R(D)H(X)。R(D)可以作為衡量各種壓縮編碼方法性能優(yōu)劣的一種尺度。但香農(nóng)第三定理同樣是一個指出存在性的定理，至于如何尋找這種最佳壓縮編碼方

14、法，定理中沒有給出。在實際應用中，該理論主要存在以下兩類問題：（1）符合實際信源的R(D)函數(shù)的計算相當困難。信息論與編碼-限失真信源編碼首先，對需要對實際信源的統(tǒng)計特性有確切的數(shù)學描述，其次，需要符合主客觀實際的失真度量。這些都不是很容易的事情。即使有了這些，率失真函數(shù)的計算也是相當困難的。（2）即使求得了符合實際的信息率失真函數(shù)，還需要研究采用何種編碼方法，才能達到或接近極限值R(D)。信息論與編碼-限失真信源編碼4.4 常用信源編碼方法簡介 1. 游程編碼在二元序列中，只有“0”和“1”兩個碼元，我們吧連續(xù)出現(xiàn)的“0”叫做“0”游程，連續(xù)出現(xiàn)的“1”叫做“1”游程。連續(xù)出現(xiàn)“0”或者“1

15、”碼元的個數(shù)叫做游程長度。這樣，一個二元序列可以轉換成游程序列，例如：二元序列0001100111100010可以變換成3224311，若規(guī)定游程必須從“0”游程開始，則上述變換是可逆的。如果連“0”或連信息論與編碼-限失真信源編碼“1”非常多，則可以達到信源壓縮的目的。游程編碼是無失真信源編碼。 信息論與編碼-限失真信源編碼2. 矢量量化連續(xù)信源進行編碼的主要方法是量化，即將連續(xù)的樣值 離散化成為 。n是量化級數(shù)，這樣就把連續(xù)值轉化為n個實數(shù)中的一個，可以用0，1，2，n等n個數(shù)字來表示。由于 是一個標量，因此稱為標量量化。在量化的過程中，將會引入失真，量化是必須使這些失真最小。要想得到更好

16、的性能，僅采用標量量化是不可能信息論與編碼-限失真信源編碼 的。從前面的討論我們已經(jīng)知道，把多個信源符號組成一個符號序列進行聯(lián)合編碼可以提高編碼效率。連續(xù)信源也是如此，當把多個信源符號聯(lián)合起來形成多維矢量，然后進行量化，可以進一步壓縮碼率，這種量化方法叫做矢量量化。實驗證明，即使各信源符號相互獨立，矢量量化也可以壓縮信息率，因此，人們對矢量量化非常感興趣，是當前信源編碼的一個熱點，而且信息論與編碼-限失真信源編碼 不僅限于連續(xù)信源，對離散信源也可以如此。如圖像編碼時采用矢量量化，但由于聯(lián)合概率密度不易測定，目前常用的是訓練序列的方法，如圖像編碼時就要采用訓練序列的方法，找到其碼書，進行量化。還

17、可以與神經(jīng)網(wǎng)絡方法結合，利用神經(jīng)網(wǎng)絡的自組織來得到訓練集。 3. 預測編碼預測就是從已收到的符號來提取關于為收到的符號的信息，從而預測其最可能的制作為預測值。信息論與編碼-限失真信源編碼并把它與實際值之差進行編碼，由于這個差值一般都比較小，所以在編碼時會出現(xiàn)很多連“0”值，再采用游程編碼，就可以大大地壓縮碼率。由此可見，預測編碼是利用信源符號之間的相關性來壓縮碼率的，對于獨立信源，預測就沒有可能。 4. 變換編碼變換是一個廣泛的概念。變換編碼就是經(jīng)變換后的信號能更有效地編碼，也就是通過變換來解信息論與編碼-限失真信源編碼 除或減弱信源符號間的相關性，以達到壓縮碼率的效果（如單頻率正弦波信號，變

18、換到頻域）。一般地，對一個函數(shù) ，變換式為：而反變換為：信息論與編碼-限失真信源編碼要使上式成立，要求 必須是正交完備的（相當于歐氏空間的坐標投影），求 的公式，實際上就是內(nèi)積運算，把函數(shù) 投影到 上去。信源編碼常用的變換有：DCT（discrete Cosine Transform）變換：如JPEG、MPEG等圖像壓縮標準中，就是主要采用的這種變換壓縮方法。K-L變換：K-L變換是均方誤差準則下的最佳變換。信息論與編碼-限失真信源編碼它是一種正交變換，變幻后的隨機變量之間互不相關，一般認為，K-L變換是最佳變換，其最大缺點是計算復雜，除了需要測定相關函數(shù)和解積分方程外，變換時的運算也十分復雜，也沒有快速算法，因此，K-L變換不是一種實用的變換編碼方法，但經(jīng)常用來作為標準，評估其他方法的優(yōu)劣。小波（Wavelet Transform）變換： 小波變換是當前信號處理以及多種應用科學中信息論與編碼-限失真信源編碼 廣泛用到的一種相當有效的數(shù)學工具。小波變換的概念首先是由法國的石油地質(zhì)工程師J.Morlet于 1980年提出的，1990年Mallat等人一起建立了多分辯分析的概念。與經(jīng)典的Fourier分