信源編碼定理

資訊理論中,山農的信源編碼定理(或無雜訊編碼定理)確立了數據壓縮的限度,以及山農熵的操作意義。

信源編碼定理表明(在極限情況下,隨着獨立同分佈隨機變量數據流的長度趨於無窮)不可能把數據壓縮得位元速率(每個符號的位元的平均數)比信源的山農熵還小,又不丟失資訊。但是有可能使位元速率任意接近山農熵,且損失的概率極小。

碼符號的信源編碼定理把碼字的最小可能期望長度看作輸入字(看作隨機變量)的和目標編碼表的大小的一個函數,給出了此函數的上界和下界。

陳述

編輯

信源編碼是從資訊源的符號(序列)到碼符號集(通常是bit)的映射,使得信源符號可以從二進制位元(無損信源編碼)或有一些失真(有損信源編碼)中準確恢復。這是在數據壓縮的概念。

信源編碼定理

編輯

在資訊理論中,信源編碼定理[1]非正式地陳述[2][3]為:

N均為 H(X)獨立同分佈的隨機變量N → ∞ 時,可以很小的資訊損失風險壓縮成多於 N H(X) bit;但相反地,若壓縮到少於 N H(X) bit,則資訊幾乎一定會丟失。

碼符號的信源編碼定理

編輯

Σ1, Σ2 表示兩個有限編碼表,並令 Σ
1
Σ
2
(分別)表示來自那些編碼表的所有有限字的集合

X 為從 Σ1 取值的隨機變量,令 f 為從 Σ
1
Σ
2
的唯一可譯碼,其中 2| = a。令 S 表示字長 f (X) 給出的隨機變量。

如果 f 是對 X 擁有最小期望字長的最佳碼,那麼(Shannon 1948):

 

證明:碼符號的信源編碼定理

編輯

對於 1 ≤ insi 表示每個可能的 xi 的字長。定義  ,其中 C 會使得 q1 + ... + qn = 1。於是

 

其中第二行由吉布斯不等式推出,而第五行由克拉夫特不等式推出:

 

因此 log C ≤ 0.

對第二個不等式我們可以令

 

於是

 

因此

 

並且

 

因此由克拉夫特不等式,存在一種有這些字長的無前綴編碼。因此最小的 S 滿足

 

參考資料

編輯
  1. ^ C.E. Shannon, "A Mathematical Theory of Communication頁面存檔備份,存於互聯網檔案館)", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948
  2. ^ David J. C. MacKay. Information Theory, Inference, and Learning Algorithms頁面存檔備份,存於互聯網檔案館 Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
  3. ^ Cover, Thomas M. Chapter 5: Data Compression. Elements of Information Theory. John Wiley & Sons. 2006. ISBN 0-471-24195-4.