香农–法诺–以利亚码

信息论中,香农–法诺–以利亚码算术编码的先导,其概率被用于决定码字。

算法描述

编辑

给定一离散随机变量 X ,令  X=x 发生之概率。

定义

 

算法如下:

对每个 X 中的 x
Z  之二次展开
x 之编码长度  
选定 x 之编码,   Z 之小数点后之第一个最高有效位。

举例

编辑

令 X = {A, B, C, D} ,其发生概率分别为 p = {1/3, 1/4, 1/6, 1/4} 。

对于 A
 
在二进制中, Z(A) = 0.0010101010...
L(A) =   = 3
code(A) 为 001
对于 B
 
在二进制中, Z(B) = 0.01110101010101...
L(B) =   = 3
code(B) 为 011
对于 C
 
在二进制中, Z(C) = 0.101010101010...
L(C) =   = 4
code(C) 为 1010
对于 D
 
在二进制中, Z(D) = 0.111
L(D) =   = 3
code(D) 为 111

算法分析

编辑

前缀码

编辑

香农–法诺–以利亚码之输出为二进制前缀码,因此可被直接解码。

令 bcode(x) 为二进制表示法最左侧加入小数点而成之小数。举例而言, code(C)=1010 ,则 bcode(C) = 0.1010 。 对所有 x ,如果没有任何 y 存在使得

 

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


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

 

由 L 之定义可得

 

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

 

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

上图说明了   ,因此前缀码定理成立。

编码长度

编辑

此码之平均长度为  
因随机变量 X 之 H(X) 满足

 

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

参考书目

编辑

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