Kraft–McMillan 不等式

在无限 $D$ 叉树中，深度 $\ell$ 的一个码字封锁其全部后代，占据总边界空间的 $D^{-\ell }$。前缀码对应互不相交的子树，所以占用比例之和不能超过一。反过来，只要总占用不超过一，就能按长度从短到长把这些子树塞进尚未使用的树空间。

这个不等式只看到长度多重集，看不到具体码符号，也看不到哪个源符号获得哪一长度。可行性与概率加权的最优分配是两个不同问题。

前缀码部分的证明机制 ​

令 $L=\underset{i}{max}{\ell }_i$。把每个长度 ${\ell }_i$ 的码字延伸到深度 $L$，会得到 $D^{L-{\ell }_i}$ 个后代。前缀自由使这些后代集合互不相交，而深度 $L$ 总共只有 $D^L$ 个节点，因此

两边除以 $D^L$ 即得 Kraft 不等式。充分性可把长度排序后按字典序依次选择最左侧尚未被占用的节点；$K\le 1$ 保证每一步都有足够的树空间。

McMillan 部分的证明机制 ​

令 $K=\sum _i{D}^{-{\ell }_i}$。串联 $N$ 个源符号后，全部长度权重之和是 $K^N$。唯一可译性保证不同源串产生不同码串；若最短、最长码长为 $a,b$，总长度只能落在 $Na,ldots,Nb$。对每个总长度 $r$，至多有 $D^r$ 个不同码串，故该组对 $K^N$ 的贡献至多为 $D^r{D}^{-r}=1$。于是

取 $N$ 次方根并令 $N\to \mathrm{\infty }$，得到 $K\le 1$。

可复算例：可行与不可行长度 ​

二元长度 $(1,2,3,3)$ 满足

可由 0,10,110,111 实现。长度 $(1,2,2,2)$ 则给

所以不存在具有这些长度的二元前缀码，甚至不存在唯一可译码。

边界与失败情形 ​

$K<1$ 仍可行，只表示码树未满；$K=1$ 也不说明码对给定概率分布最优。对 $D$ 元代码必须使用 $D^{-{\ell }_i}$，不能沿用二元的 $2^{-{\ell }_i}$。

允许长度零时，空码字占用 $D^0=1$ 的全部容量，因此只能有这一个码字；这对应单符号源。码长还必须是整数，实数解 ${\ell }_i=-{\log }_D{p}_i$ 即使满足形式上的等式，也未必是实际逐符号码长。

把 Kraft 约束与概率 $p_i$ 结合，令 $q_i=D^{-{\ell }_i}/K$，可用 KL 非负性证明任意唯一可译码的平均长度满足

Huffman 编码公理库Huffman 编码Huffman coding反复合并最低概率符号构造期望码长最小前缀码的算法。在整数可行长度中求精确的逐符号最优解；无噪声编码定理公理库无噪声编码定理Source coding theorem · Noiseless coding theorem独立同分布信源的无损压缩平均码率可以逼近但不能低于其熵。则对长块应用同一约束，把每符号整数舍入损失压到零。