信源編碼定理

此條目介紹的是信源編碼的數據壓縮理論。關於計算機編程術語，請見「原始碼」。

在資訊理論中，夏農的信源編碼定理（或無雜訊編碼定理）確立了數據壓縮的限度，以及夏農熵的操作意義。

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

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

陳述

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

信源編碼定理

在資訊理論中，信源編碼定理非正式地陳述為：

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

碼符號的信源編碼定理

令 Σ₁, Σ₂ 表示兩個有限編碼表，並令 Σ∗
1 和 Σ∗
2 （分別）表示來自那些編碼表的所有有限字的集合。

設 X 為從 Σ₁ 取值的隨機變量，令  f  為從 Σ∗
1 到 Σ∗
2 的唯一可解碼，其中 |Σ₂| = a。令 S 表示字長  f (X) 給出的隨機變量。

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

${\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} S<{\frac {H(X)}{\log _{2}a}}+1$

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

對於 1 ≤ i ≤ n 令 s_i 表示每個可能的 x_i 的字長。定義 $q_{i}=a^{-s_{i}}/C$，其中 C 會使得 q₁ + ... + q_n = 1。於是

${\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}}$

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

$C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1$

因此 log C ≤ 0.

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

$s_{i}=\lceil -\log _{a}p_{i}\rceil$

於是

$-\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1$

因此

$a^{-s_{i}}\leq p_{i}$

並且

$\sum a^{-s_{i}}\leq \sum p_{i}=1$

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

${\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}}$