形式陈述

对 $D$$D$ 元字母表，任一唯一可译码的码长 $\ell_1,\ldots,\ell_m$${\ell }_1,\dots ,{\ell }_m$ 满足 McMillan 不等式

$$ \sum_iD^{-\ell_i}\le1. $$$$\sum _i{D}^{-{\ell }_i}\le 1.$$

反之，只要一组正整数码长满足该不等式，就存在具有这些码长的前缀码。因而对码长可实现性而言，前缀码并不比一般唯一可译码损失。

直觉

深度为 $\ell$$\ell$ 的码字占据前缀树中比例 $D^{-\ell}$$D^{-\ell }$ 的叶空间，不相交码字占用的总空间不能超过整棵树。

例子与边界

二元码长 $1,2,2$$1,2,2$ 的和为 $1/2+1/4+1/4=1$$1/2+1/4+1/4=1$，可构造完整前缀树。码长 $1,1,2$$1,1,2$ 的和大于 1，不可能唯一可译。该不等式只判定码长集合，不指定哪个符号应配哪一长度；最优分配还要结合概率。

推论与应用

它把编码结构转化为数值约束，是无失真源编码下界和 Huffman 最优性的基础。

参考资料

• Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006，Chs. 2–8。
• Claude E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal 27, 1948，Parts I–II。