Shannon 編碼定理

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

信源編碼定理表明（在極限情況下，隨著獨立同分布隨機變數數據流的長度趨於無窮）不可能把數據壓縮得碼率（每個符號的比特的平均數）比信源的香農熵還小，不滿足的幾乎可以肯定，信息將丟失。但是有可能使碼率任意接近香農熵，且損失的機率極小。

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

基本介紹

• 中文名：Shannon 編碼定理
• 外文名：Shannon's source coding theorem
• 別稱：信源編碼定理

陳述

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

信源編碼定理

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

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

碼符號的信源編碼定理

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

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

如果 f 是對X擁有最小期望字長的最佳碼，那么：

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

對於1≤i≤n令s_i表示每個可能的x_i的字長。定義 ，其中C會使得q₁+...+q_n=1。於是

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

因此logC≤0。

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

於是

因此

並且

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