3.2 數據壓縮的理論依據

在討論數據壓縮的時候，需要涉及現代科學領域中的一個重要分支——信息論。香農所創立的信息論對數據壓縮有著極其重要的指導意義。它一方面給出了數據壓縮的理論極限，另一方面又指明了數據壓縮的技術途徑。本節將對無信息損失條件下數據壓縮的理論極限作一簡要的介紹；而下一節將討論限定失真條件下數據壓縮的理論極限。

3.2.1 離散信源的信息熵

在日常生活中，當我們收到書信、電話或看到圖像時，則說得到了消息，在這些消息中包含著對我們有用的信息。通常，消息由一個有次序的符號（如狀態、字母、數字、電平等）序列構成。例如，一封英文信是利用由26個英文字母加上標點符號所構成的序列來傳遞消息的。一個符號所攜帶的信息量I用它所出現的概率p按如下關系定義：

I＝log（1/p）＝－logp （3-1）

上述定義符合我們日常生活中的概念。例如，如果符號出現的概率為1，這說明傳遞給我們的是一條幾乎肯定要發生的事件的消息，對我們來說是“不出所料”，沒有什么信息量；因此，I＝0。反之，概率較小的符號（事件），出現的不肯定性大，那么收到這個事件發生的消息時，帶給我們較大的信息量。

當（3-1）式中的對數以2為底時，它的單位是比特。從后面的討論中將會看到，表示信息量的比特其含義與二進制符號中的比特并不完全相同。

若信息源所產生的符號取自某一離散集合，則該信源稱為離散信源。離散信源X可以用下式來描述：

式中，p（si）為符號集中的符號si發生（或出現）的概率。由于信源產生的符號si是一個隨機變量（在符號產生之前，我們不知道信源X將發出符號集中的哪一個符號），而信息量I是si[或p（si）]的函數，因此I也是一個隨機變量。對于一個隨機變量，研究它的統計特性更有意義。考慮I的統計平均值

式中，〈 〉表示數學期望。

借用熱力學的名詞，我們把H叫做熵。在符號出現之前，熵表示符號集中符號出現的平均不肯定性；在符號出現之后，熵代表接收一個符號所獲得的平均信息量。因此，熵是在平均意義上表征信源總體特性的一個物理量。

3.2.2 信源的概率分布與熵的關系

由（3-3）式可以看出，熵的大小與信源的概率模型有著密切的關系。如果符號集中任一符號出現的概率為1，則其他符號出現的概率必然為零，信源的平均信息量（熵）則為零。如果所有符號出現的概率都小于1，熵則為某一正值。這說明，各符號出現的概率分布不同，信源的熵也不同。下面我們來求證，當信源中各事件服從什么樣的分布時，熵具有極大值，即求解

根據求條件極值的拉格朗日乘數法，我們有

式中，λ為拉格朗日常數。解方程組（3-5）前，得到

此時，信源具有最大熵

Hmax（X）＝log2n （3-7）

這是一個重要結論，有時稱為最大離散熵定理。

以n＝2為例，熵隨符號“1”的概率p的變化曲線如圖3-1所示。p＝0或1時，H（X）＝0。當p＝1/2時，H（X）＝1bit/符號。p為其他值時，0＜H（X）＜1。從物理意義上講，通常存儲或傳輸1位的二進制數碼（1或0），其所含的信息量總低于1bit；只有當字符0和1出現的概率均為1/2時，不肯定性最大，1位二進數碼才含有習慣上所說的1比特的信息量。

3.2.3 信源的相關性與序列熵的關系

上面討論的離散信源所能輸出的信息量，是針對一個信源符號而言的。實際上，離散信源輸出的不只是一個符號，而是一個隨機符號序列（離散型隨機過程）。若序列中各符號具有相同的概率分布，該序列（過程）是平穩的。若序列中各符號間是統計獨立的，即前一個符號的出現不影響以后任何一個符號出現的概率，則該序列是無記憶的。

假設離散無記憶信源產生的隨機序列包括兩個符號X和Y（即序列長度等于2），且X取值于（3-2）式所表示的集合，而Y取值于

那么接收到該序列后所獲得的平均信息量稱為聯合熵，定義為

式中，rij為符號si和tj同時發生時的聯合概率。由于X和Y相互獨立，rij＝p（si）q（tj），（3-9）式變為

H（X·Y）＝H（X）＋H（Y）（3-10）

將上面的結果推廣到多個符號的情況，可以得到如下結論：離散無記憶信源所產生的符號序列的熵等于各符號熵之和。要知道收到其中一個符號所得到的平均信息量（即序列的平均符號熵）可以用序列熵除以序列的長度求得。顯然，當序列是平穩的，任一符號的熵就是序列的平均符號熵。

假設離散信源是有記憶的，而且為了簡單起見，只考慮相鄰兩個符號（X和Y）相關的情況。由于其相關性，聯合概率rij＝p（si）Pji＝q（tj）Pij，其中Pji＝P（tj/si）和Pij＝P（si/tj）為條件概率。

在給定X的條件下，Y所具有的熵稱為條件熵，即

上式中在對-log2Pji進行統計平均時，由于要對si和tj進行兩次平均，所以用的是聯合概率rij。利用（3-9）式和（3-11）式以及聯合概率與條件概率之間的關系，不難證明聯合熵與條件熵之間存在下述關系：

H（X·Y）＝H（X）＋H（Y/X）＝H（Y）＋H（X/Y）（3-12）

上式表明，如果X和Y之間存在著一定的關聯，那么當X發生，在解除X的不肯定性的同時，也解除了一部分Y的不肯定性。但此時Y還殘剩有部分的不肯定性，這就是（3-12）式中H（Y/X）的含義。我們把無條件熵和條件熵之差定義為互信息，即

I（X；Y）＝H（Y）－H（Y/X）（3-13）

I（Y；X）＝H（X）－H（X/Y）（3-14）

顯然，I（X；Y）＝I（Y；X）≥0。

兩個事件的相關性越小，互信息越小，殘剩的不肯定性便越大。當兩事件相互獨立時，X的出現，絲毫不能解除Y的不肯定性。在這種情況下，聯合熵變為兩個獨立熵之和（見（3-10）式），從而達到它的最大值。圖3-2給出了無條件熵、條件熵和互信息之間關系的示意。

由（3-12）式和（3-10）式，可以得到

H（X·Y）＝H（X）＋H（Y/X）≤H（X）＋H（Y）（3-15）

對于信源輸出序列中有多個符號相關的情況，也可以得到類似的結果。序列熵與其可能達到的最大值之間的差值反映了該信源所含有的冗余度。信源的冗余度越小，即每個符號所獨立攜帶的信息量越大，那么傳送相同的信息量所需要的序列長度越短，或符號數越少。因此數據壓縮的一個基本途徑是去除信源產生的符號之間的相關性，盡可能地使序列成為無記憶的。而對于無記憶信源而言，如3.2.2節所述，在等概率情況下，離散平穩無記憶信源單個符號的熵（平均信息量）具有極大值。因此，在無信息損失的情況下，數據壓縮的另一基本途徑是改變離散無記憶信源的概率分布，使其盡可能地達到等概率分布的目的。