在消息理论中，夏农–菲诺–以利亚码是算术编码的先导，其几率被用于决定码字。

算法描述

给定一离散随机变数 X ，令 ${\displaystyle p(x)}$ 为 X=x 发生之几率。

定义

${\displaystyle {\bar {F))(x)=\sum _{x_{i}<x}p(x_{i})+{\frac {1}{2))p(x)}$

算法如下：

对每个 X 中的 x，

令 Z 为 ${\displaystyle {\bar {F))(x)}$ 之二次展开

令 x 之编码长度 ${\displaystyle L(x)=\left\lceil \log _{2}{\frac {1}{p(x)))\right\rceil +1}$

选定 x 之编码， ${\displaystyle code(x)}$ 为 ${\displaystyle L(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...}$

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

L(A) = ${\displaystyle \left\lceil \log _{2}{\frac {1}{\frac {1}{3))}\right\rceil +1}$ = 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...}$

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

L(B) = ${\displaystyle \left\lceil \log _{2}{\frac {1}{\frac {1}{4))}\right\rceil +1}$ = 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...}$

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

L(C) = ${\displaystyle \left\lceil \log _{2}{\frac {1}{\frac {1}{6))}\right\rceil +1}$ = 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}$

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

L(D) = ${\displaystyle \left\lceil \log _{2}{\frac {1}{\frac {1}{4))}\right\rceil +1}$ = 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)))$

则所有的码可构成前缀码。

此性质可透过比较 F 和 X 之累积分布函数，以图表示出：

由 L 之定义可得

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

并且由于 code(y) 是由 F(y) 从 L(y) 之后的位元截短而得，故

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

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

上图说明了 ${\displaystyle bcode(y)-bcode(x)>p(x)\geq 2^{-L(x)))$ ，因此前缀码定理成立。

编码长度

此码之平均长度为 ${\displaystyle LC(X)=\sum _{x\epsilon X}p(x)L(x)=\sum _{x\epsilon X}p(x)(\left\lceil \log _{2}{\frac {1}{p(x)))\right\rceil +1)}$ 。
因随机变数 X 之 熵 H(X) 满足

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

夏农–菲诺–以利亚码之长度约比代编码资料之熵长约一到二额外位元，故甚少被实用。

参考书目

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