夏農–菲諾–以利亞碼

在訊息理論中，夏農–菲諾–以利亞碼是算術編碼的先導，其機率被用於決定碼字。

基本介紹

• 中文名：夏農–菲諾–以利亞碼
• 領域：套用數學、資訊理論
• 套用：無損壓縮算法

算法描述

給定一離散隨機變數 ，令 為 發生之機率。

定義

算法如下：

對每個X中的x,

令Z為 之二次展開

令x之編碼長度

選定x之編碼， 為 在Z之小數點後之第一個最高有效位。

算法舉例

令 X = {A, B, C, D} ，其發生機率分別為 p = {1/3, 1/4, 1/6, 1/4} 。

（1）對於 A

在二進制中， Z(A) = 0.0010101010...

code(A) 為 001

（2）對於 B

在二進制中， Z(B) = 0.01110101010101...

code(B) 為 011

（3）對於 C

在二進制中， Z(C) = 0.101010101010...

code(C) 為 1010

（4）對於 D

在二進制中， Z(D) = 0.111

code(D) 為 111

算法分析

前綴碼

夏農–菲諾–以利亞碼之輸出為二進制前綴碼，因此可被直接解碼。

令 bcode(x) 為二進制表示法最左側加入小數點而成之小數。舉例而言， code(C)=1010 ，則 bcode(C) = 0.1010 。 對所有 x ，如果沒有任何 y 存在使得

則所有的碼可構成前綴碼。

此性質可透過比較 F 和 X 之累積分布函式，以圖1表示出：

圖1 編碼圖解

由 L 之定義可得

並且由於 code(y) 是由 F(y) 從 L(y) 之後的位元截短而得，故

因此 bcode(y) 必不比 CDF(x) 小。

上圖說明了 ，因此前綴碼定理成立。

編碼長度

此碼之平均長度為 。
因隨機變數 X 之熵H(X) 滿足

夏農–菲諾–以利亞碼之長度約比代編碼資料之熵長約一到二額外位元，故甚少被實用。