前缀码与 Kraft 不等式

为使编码可瞬时唯一解码，用前缀码（无码字是另一码字的前缀）。码长 $l_i$ 可行的充要条件是 Kraft 不等式：
$\sum_i 2^{-l_i}\le 1$

香农第一定理（无失真信源编码）

平均码长不可能小于熵，且可任意逼近：
$H(X)\le \bar L < H(X)+1$
对信源分组编码（一次编 $n$ 个符号）可使每符号码长趋于熵 $H(X)$。熵就是无损压缩的极限。

码效率

$\eta=\frac{H(X)}{\bar L}\le 1$
越接近 $1$ 越优；最优码把高频符号配短码、低频配长码。

例题

例　四符号概率 $(\tfrac12,\tfrac14,\tfrac18,\tfrac18)$，熵 $H=1.75$ bit。用码长 $(1,2,3,3)$ 满足 Kraft（$\tfrac12+\tfrac14+\tfrac18+\tfrac18=1$），平均码长 $\bar L=1.75=H$，效率 $100%$。

应用

该定理给出一切无损压缩的下界，是 ZIP、PNG、FLAC 的理论标尺；Kraft 不等式则是构造霍夫曼等前缀码的可行性依据。