此條目介紹的是信源編碼的數據壓縮理論。關於計算機編程術語,請見「
原始碼」。
在資訊理論中,夏農的信源編碼定理(或無雜訊編碼定理)確立了數據壓縮的限度,以及夏農熵的操作意義。
信源編碼定理表明(在極限情況下,隨著獨立同分布隨機變量數據流的長度趨於無窮)不可能把數據壓縮得位元速率(每個符號的位元的平均數)比信源的夏農熵還小,又不丟失資訊。但是有可能使位元速率任意接近夏農熵,且損失的概率極小。
碼符號的信源編碼定理把碼字的最小可能期望長度看作輸入字(看作隨機變量)的熵和目標編碼表的大小的一個函數,給出了此函數的上界和下界。
陳述
信源編碼是從資訊源的符號(序列)到碼符號集(通常是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):
![{\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} S<{\frac {H(X)}{\log _{2}a}}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7af710c13eb23a7c771ef38abd9939d3fc71e3e8)
證明:碼符號的信源編碼定理
對於 1 ≤ i ≤ n 令 si 表示每個可能的 xi 的字長。定義
,其中 C 會使得 q1 + ... + qn = 1。於是
![{\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&\leq \mathbb {E} S\log _{2}a\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/169fe13cd5879db40f5ca63e9a73e6d99b6e3b14)
其中第二行由吉布斯不等式推出,而第五行由克拉夫特不等式推出:
![{\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11b1781597af68ac79e69f30c8e40237bc6bc12c)
因此 log C ≤ 0.
對第二個不等式我們可以令
![{\displaystyle s_{i}=\lceil -\log _{a}p_{i}\rceil }](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d4ce1b2b20eab899e13952689f57ae0e7ec84ea)
於是
![{\displaystyle -\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3d69b1c1785dffb4b1df15103823e42e6daf02f)
因此
![{\displaystyle a^{-s_{i}}\leq p_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36657790767da95f5abe28686bc7a957c20d9f74)
並且
![{\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6555a9325950933aaab932fb998351d6fe2497a)
因此由克拉夫特不等式,存在一種有這些字長的無前綴編碼。因此最小的 S 滿足
![{\displaystyle {\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e378e7d9efe7511f0bee22c33d1ead2e80f2e1cb)
參考資料
- ^ C.E. Shannon, "A Mathematical Theory of Communication (頁面存檔備份,存於網際網路檔案館)", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948
- ^ David J. C. MacKay. Information Theory, Inference, and Learning Algorithms (頁面存檔備份,存於網際網路檔案館) Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
- ^ Cover, Thomas M. Chapter 5: Data Compression. Elements of Information Theory. John Wiley & Sons. 2006. ISBN 0-471-24195-4.