在信息论中,香农–法诺–以利亚码是算术编码的先导,其概率被用于决定码字。
给定一离散随机变量 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.