形式陈述

设 $X_1,X_2,\dots$ 是熵为 $H(X)<\mathrm{\infty }$ 的离散无记忆信源。对长度 $n$ 的源块，任意二元唯一可译块码的期望码长 $L_n$ 都满足

$$\frac{L_n}{n}\ge H(X).$$

反之，存在二元前缀块码满足 $L_n<nH(X)+1$，故对任意 $\epsilon >0$，取充分大的 $n$ 即有 $L_n/n<H(X)+\epsilon$。这给出无失真变长块编码的精确渐近界；固定码率且允许小错误概率的版本可由 AEP公理库渐近等分性质Asymptotic equipartition property · AEP离散无记忆源的长序列每符号信息量几乎必然收敛到熵。 和 典型集公理库典型集Typical set长随机序列中概率与 2^{-nH} 同阶且总概率趋近一的序列集合。 表述。

直觉

长序列几乎都落在大小约为 $2^{nH(X)}$ 的典型集合中，给这些序列编号约需 $nH(X)$ 位。

例子与边界

偏置硬币序列的熵小于每符号 1 bit，因此可压缩。定理是渐近结论；有限块长、计算成本和格式开销会使实际码率高于熵。

推论与应用

它给 Huffman 编码、算术编码和现代压缩算法提供理论下界与设计目标。

参考资料

• Claude E. Shannon, “A Mathematical Theory of Communication,” 1948.
• Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Chapter 5.