# 夏農–菲諾–以利亞碼

## 演算法描述

${\displaystyle {\bar {F}}(x)=\sum _{x_{i}

Z${\displaystyle {\bar {F}}(x)}$ 之二次展開
x 之編碼長度 ${\displaystyle L(x)=\left\lceil \log _{2}{\frac {1}{p(x)}}\right\rceil +1}$

### 舉例

${\displaystyle {\bar {F}}(A)={\frac {1}{2}}p(A)={\frac {1}{2}}\cdot {\frac {1}{3}}=0.1666...}$

L(A) = ${\displaystyle \left\lceil \log _{2}{\frac {1}{\frac {1}{3}}}\right\rceil +1}$ = 3
code(A) 為 001

${\displaystyle {\bar {F}}(B)=p(A)+{\frac {1}{2}}p(B)={\frac {1}{3}}+{\frac {1}{2}}\cdot {\frac {1}{4}}=0.4583333...}$

L(B) = ${\displaystyle \left\lceil \log _{2}{\frac {1}{\frac {1}{4}}}\right\rceil +1}$ = 3
code(B) 為 011

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

L(C) = ${\displaystyle \left\lceil \log _{2}{\frac {1}{\frac {1}{6}}}\right\rceil +1}$ = 4
code(C) 為 1010

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

L(D) = ${\displaystyle \left\lceil \log _{2}{\frac {1}{\frac {1}{4}}}\right\rceil +1}$ = 3
code(D) 為 111

## 演算法分析

### 前綴碼

${\displaystyle bcode(x)\leq bcode(y)

${\displaystyle 2^{-L(x)}\leq {\frac {1}{2}}p(x)}$

${\displaystyle {\bar {F}}(y)-bcode(y)\leq 2^{-L(y)}}$

### 編碼長度

${\displaystyle H(X)+1\leq LC(X)

## 參考書目

T. M. Cover and Joy A. Thomas (2006). Elements of information theory (2nd ed.). John Wiley and Sons. pp. 127–128.