4.3 Kraft不等式

Kraft不等式

Kraft 不等式（Kraft inequality）是信源编码理论中的基础性结论，它给出了存在前缀码的必要与充分条件。对于 D 进制码，Kraft 不等式表述为：

$$\sum _i{D}^{-l_i}\le 1$$

其中 $l_i$ 是第 i 个码字的长度，D 是码符号集的大小。该不等式表明：如果一组正整数 $\{l_i\}$ 满足上述不等式，则一定存在一个 D 进制前缀码以这些长度为码长；反之，任何一个前缀码的码长必然满足该不等式。更重要的是，McMillan 证明了这个结论对唯一可译码（uniquely decodable code）也同样成立——即任何唯一可译码都必须满足 Kraft 不等式，而满足 Kraft 不等式的码长组合都能被某个前缀码实现。因此，在编码效率的意义上，前缀码已经是最优的选择，不存在比前缀码更好的唯一可译码。

Kraft 不等式的几何意义可以借助 D 叉树来理解：每个码字对应 D 叉树中的一个叶子节点，码长 $l_i$ 对应叶子所在的深度。深度为 $l_i$ 的节点能够覆盖 $D^{-l_i}$ 比例的树空间。所有叶子节点覆盖的总比例不超过 1，即所有码字对应的路径不能重叠，且不能占满整棵树。这一视角不仅直观地解释了不等式的来源，也为构造前缀码提供了具体方法——只要在 D 叉树上选择一组互不为祖先的节点，就能得到一组前缀码。

链接到

• 上一个知识点：4.2 D进制编码
• 下一个知识点：4.4 最优编码长度