在消息理論中,夏農–菲諾–以利亞碼是算術編碼的先導,其概率被用於決定碼字。
演算法描述[編輯]
給定一離散隨機變數 X ,令
為 X=x 發生之概率。
定義
![{\displaystyle {\bar {F}}(x)=\sum _{x_{i}<x}p(x_{i})+{\frac {1}{2}}p(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee74893ef9cc8c6e61f45bbe12586e099c3c7b01)
演算法如下:
- 對每個 X 中的 x,
- 令 Z 為
之二次展開
- 令 x 之編碼長度
![{\displaystyle L(x)=\left\lceil \log _{2}{\frac {1}{p(x)}}\right\rceil +1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/773e39bfba544177c72038c35675a385f38b6174)
- 選定 x 之編碼,
為
在 Z 之小數點後之第一個最高有效位。
令 X = {A, B, C, D} ,其發生概率分別為 p = {1/3, 1/4, 1/6, 1/4} 。
- 對於 A
![{\displaystyle {\bar {F}}(A)={\frac {1}{2}}p(A)={\frac {1}{2}}\cdot {\frac {1}{3}}=0.1666...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/634c99c27aa344b6ba6687fc205f8e8353da6c23)
- 在二進位中, Z(A) = 0.0010101010...
- L(A) =
= 3
- code(A) 為 001
- 對於 B
![{\displaystyle {\bar {F}}(B)=p(A)+{\frac {1}{2}}p(B)={\frac {1}{3}}+{\frac {1}{2}}\cdot {\frac {1}{4}}=0.4583333...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eee49184801cf150c50fae513be5b9f92d439cda)
- 在二進位中, Z(B) = 0.01110101010101...
- L(B) =
= 3
- code(B) 為 011
- 對於 C
![{\displaystyle {\bar {F}}(C)=p(A)+p(B)+{\frac {1}{2}}p(C)={\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{2}}\cdot {\frac {1}{6}}=0.66666...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aef46fc1679022e9215388cfa2aa330c93d41206)
- 在二進位中, Z(C) = 0.101010101010...
- L(C) =
= 4
- code(C) 為 1010
- 對於 D
![{\displaystyle {\bar {F}}(D)=p(A)+p(B)+p(C)+{\frac {1}{2}}p(D)={\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{6}}+{\frac {1}{2}}\cdot {\frac {1}{4}}=0.875}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61f17ff24840f4472539542d49a3f536d237031a)
- 在二進位中, Z(D) = 0.111
- L(D) =
= 3
- code(D) 為 111
演算法分析[編輯]
前綴碼[編輯]
夏農–菲諾–以利亞碼之輸出為二進位前綴碼,因此可被直接解碼。
令 bcode(x) 為二進位表示法最左側加入小數點而成之小數。舉例而言, code(C)=1010 ,則 bcode(C) = 0.1010 。 對所有 x ,如果沒有任何 y 存在使得
![{\displaystyle bcode(x)\leq bcode(y)<bcode(x)+2^{-L(x)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9d0e1ac15a0d55236abbb0f128e4e05801deaf8)
則所有的碼可構成前綴碼。
此性質可透過比較 F 和 X 之累積分佈函數,以圖表示出:
由 L 之定義可得
![{\displaystyle 2^{-L(x)}\leq {\frac {1}{2}}p(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b7ef0b073990f953d588ab5898764f9533c5fcd)
並且由於 code(y) 是由 F(y) 從 L(y) 之後的位元截短而得,故
![{\displaystyle {\bar {F}}(y)-bcode(y)\leq 2^{-L(y)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f59b40fa02f6c599a25389bb4d096e71acae29b)
因此 bcode(y) 必不比 CDF(x) 小。
上圖說明了
,因此前綴碼定理成立。
編碼長度[編輯]
此碼之平均長度為
。
因隨機變數 X 之 熵 H(X) 滿足
![{\displaystyle H(X)+1\leq LC(X)<H(X)+2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d6236bd1c7e0bab9aa461fd3a29c72b5047fb55)
夏農–菲諾–以利亞碼之長度約比代編碼資料之熵長約一到二額外位元,故甚少被實用。
參考書目[編輯]
T. M. Cover and Joy A. Thomas (2006). Elements of information theory (2nd ed.). John Wiley and Sons. pp. 127–128.