1 定理的数学表述

1.1 离散无记忆信源的定义

离散无记忆信源（DMS，Discrete Memoryless Source）是信息论中最基本的信源模型。它是指一个信源，每次独立地从一个有限符号集\(X = \{x_1, x_2, \ldots, x_n\}\)中产生一个符号，且每次输出符号的概率分布保持不变。用数学语言描述：若信源输出序列\(\{X_1, X_2, \ldots\}\)，则对于任意\(i \neq j\)，有\(P(X_i = a, X_j = b) = P(X_i = a) \cdot P(X_j = b)\)，即符号之间相互独立且同分布。这一假设简化了分析，为后续定理的建立提供了基础模型。

1.2 熵与平均码长

1.2.1 熵的计算公式

信源的熵\(H(X)\)定义为其平均自信息量，表征信源的不确定性或信息含量。对于离散随机变量\(X\)，其概率分布为\(P(X = x_i) = p_i\)，则熵的计算公式为：

\[ H(X) = -\sum_{i=1}^{n} p_i \log_2 p_i \quad (\text{单位：比特/符号}) \]

当对数底数为2时，熵的单位为比特；若使用自然对数，单位则为纳特。熵具有非负性，且当且仅当信源符号等概率分布时达到最大值\(\log_2 n\)。例如，一个公平的硬币（正面概率0.5，反面概率0.5）的熵为1比特；而一个总是出现正面的硬币的熵为0比特。

1.2.2 平均码长的定义

给定一个编码方案\(C\)，它将每个信源符号\(x_i\)映射为一个码字（由码符号组成的序列）。记码字长度为\(l_i\)（码符号个数），则平均码长定义为：

\[ L(C) = \sum_{i=1}^{n} p_i \cdot l_i \]

平均码长衡量了每个信源符号平均需要多少位码符号来表示。若码符号集为二进制（0和1），则平均码长的单位即为“比特/符号”。显然，平均码长越短，压缩效率越高。理想情况下，我们希望平均码长尽可能接近信源的熵。

1.3 定理的严格陈述

无失真信源编码定理（香农第一定理）：对于任意离散无记忆信源，其熵为\(H(X)\)。对于任意给定的\(\epsilon > 0\)，存在一个唯一可译的变长编码（或定长编码），使得编码后的平均码长\(L\)满足：

\[ H(X) \le L < H(X) + \epsilon \]

该定理同时包含两个方向：

  • 可达性（正向）：存在一种编码方式，能使平均码长任意接近但不小于熵。
  • 必要性（逆向）：对于任何唯一可译编码，平均码长不可能小于信源的熵，即\(L \ge H(X)\)。

简而言之，熵是无损压缩的理论极限：压缩后的数据大小不可能低于信源的熵，但可以无限趋近于它。

2 定理的证明思路

2.1 可达性证明（存在性）

2.1.1 随机编码与典型序列

证明可达性通常采用典型序列（Typical Sequences）方法。对于离散无记忆信源，考虑由\(N\)个符号组成的序列。根据渐近等分性（AEP，Asymptotic Equipartition Property），当\(N\)足够大时，所有可能序列中，绝大多数概率集中在典型序列集合上：这些序列的每个符号出现频率接近其概率，因而它们的出现概率大致相等（约为\(2^{-NH(X)}\)），且典型序列的总数约为\(2^{NH(X)}\)。

随机编码的核心思想是：对每个典型序列分配一个唯一的二进制码字，长度为略大于\(NH(X)\)的整数。由于典型序列的数量约为\(2^{NH(X)}\)，因此可以用\(NH(X) + \delta\)个比特唯一地表示它们。对于非典型序列，则可分配稍长的码字或忽略（因概率极小）。这样，平均码长可趋近于\(H(X)\)。

2.1.2 码长分配与渐近等分性

具体地，对长度为\(N\)的信源序列，采用两个阶段的编码策略：

  • 第一阶段：将所有序列分为典型集\(T_\epsilon^{(N)}\)和非典型集。
  • 第二阶段：对典型集中的序列，用定长码编码，每个序列分配\(\lceil N(H(X) + \epsilon) \rceil\)比特；对非典型序列，使用另一种唯一编码（例如添加前缀标记）。

由于典型序列的概率趋近于1（当\(N \to \infty\)），非典型序列的总概率可忽略不计。因此，每个信源符号的平均码长可以控制在\(H(X) + \epsilon\)以内。在极限情况下（\(N\)足够大且\(\epsilon \to 0\)），可达性得证。

2.2 逆定理证明（必要性）

2.2.1 克拉夫特不等式与唯一可译码

逆定理的证明依赖于克拉夫特不等式（Kraft Inequality）。对于由\(D\)进制码符号组成的一棵前缀码（或任何唯一可译码），其码字长度\(l_1, l_2, \ldots, l_n\)必须满足：

\[ \sum_{i=1}^{n} D^{-l_i} \le 1 \]

反之，若一组正整数满足该不等式，则存在一个前缀码具有这些码长。前缀码是唯一可译码的一种重要形式，它保证了码字与码字之间不会发生前缀冲突，从而可以无歧义地解码。

2.2.2 熵与码长下界的关系

给定一个唯一可译码，其平均码长\(L = \sum p_i l_i\)。利用克拉夫特不等式和吉布斯不等式（Gibbs&#039; Inequality），可以推导出下界：

\[ L = \sum p_i l_i \ge -\sum p_i \log_D p_i = H_D(X) \]

证明思路如下：设\(q_i = D^{-l_i} / \sum_j D^{-l_j}\)，构造一个伪概率分布。通过比较\(p_i\)与\(q_i\)的相对熵，可得\(\sum p_i \log_D (p_i / q_i) \ge 0\)，整理后即得\(L \ge H_D(X)\)。当码符号为二进制（\(D=2\)）时，下界即为\(H(X)\)。

因此，任何唯一可译码的平均码长都不可能低于信源的熵，这是无损压缩不可逾越的理论底线。

3 相关概念与扩展

3.1 定长编码与变长编码

3.1.1 定长编码的局限性

定长编码（Fixed-Length Coding）给每个信源符号分配相同长度的码字。例如，对\(n\)个符号使用\(\lceil \log_2 n \rceil\)比特表示。这种方法的优点是简单、可同步，但缺点是：

  • 当符号概率不均等时，无法利用概率差异来压缩，平均码长固定为\(\log_2 n\)，可能远大于熵。
  • 无法真正达到熵极限，除非信源是等概率分布。

要接近熵，定长编码必须对多个符号（块）一起编码，但块长增加会导致复杂度指数级上升，且仍然存在一个最小误差概率（即无法做到完全无损的无错压缩，除非块长无穷大）。

3.1.2 变长编码的优势

变长编码（Variable-Length Coding）允许为不同符号分配不同长度的码字，概率高的符号用短码字，概率低的用长码字。这样，平均码长可以低于定长编码，甚至接近熵。代表性的算法有：

  • 香农-费诺编码：最早提出按概率排序并划分。
  • 哈夫曼编码：通过二叉树自底向上构造最优前缀码。

变长编码的唯一缺点是需要确保码字唯一可译，通常使用前缀码实现，解码时需逐比特识别码字边界。

3.2 无损压缩的极限与熵率

3.2.1 信源熵率

对于非独立同分布的信源（如有记忆信源），熵的概念需要扩展到熵率（Entropy Rate）。定义\(H(\mathcal{X}) = \lim_{n \to \infty} \frac{1}{n} H(X_1, X_2, \ldots, X_n)\)，若该极限存在。熵率度量了信源每输出一个符号的平均信息量。对于平稳信源，熵率反映了长期压缩极限。香农第一定理可推广至平稳遍历信源：存在一种编码使得平均码长趋于熵率。

3.2.2 渐近最优性

渐近最优性指：随着编码块长\(N\)趋于无穷，存在编码方案使得每符号平均码长以任意精度逼近熵（或熵率）。典型序列方法本质上是渐近最优的——它不保证对任意有限块长都是最优，但在大数定律下逐渐趋近极限。实际编码算法（如算术编码）通常具有“逐符号”的渐近最优性，即在实现过程中逐渐逼近熵。

3.3 与有失真信源编码定理的区别

有失真信源编码定理（香农第三定理）讨论的是在允许一定失真（如均方误差、失真度量）的前提下，信源所需的码率下限。其核心是率失真函数\(R(D)\)，它表示在平均失真不超过\(D\)时，所需的最小码率。与无失真定理的区别在于：

  • 无失真：以熵为下限，强调完全可逆重建，适用于文本、程序代码等“黄金数据”。
  • 有失真：以率失真函数为下限，允许压缩信息丢失，适用于图像、音频等可以容忍少量失真的媒体。

无失真定理是有失真定理在\(D=0\)时的特例，但此时率失真函数的值恰好等于熵（对离散信源）或无穷大（对连续信源）。

4 应用与实例

4.1 哈夫曼编码

4.1.1 算法步骤

哈夫曼编码（Huffman Coding）由David A. Huffman于1952年提出，是一种构造最优前缀码的贪心算法。步骤如下：

  1. 初始化：将每个信源符号看作一个叶子节点，权重为符号概率。
  2. 合并：从节点集合中选出两个权重最小的节点，创建一个新节点作为它们的父节点，新节点权重为两子节点权重之和。
  3. 重复：将新节点加入集合，重复步骤2，直到只剩一个节点（根节点）。
  4. 分配码字：从根节点出发，向左分支赋0，向右分支赋1（或反之），从根到叶子的路径即为符号的二进制码字。

例如，对符号集\(\{A: 0.4, B: 0.3, C: 0.2, D: 0.1\}\)，哈夫曼编码结果可能为：A→0, B→10, C→110, D→111，平均码长=0.4×1 + 0.3×2 + 0.2×3 + 0.1×3 = 1.9比特/符号，而熵≈1.846比特/符号。

4.1.2 最优性证明

哈夫曼编码的最优性可通过归纳法证明：在所有前缀码中，哈夫曼编码的平均码长最小。核心思路是：对于任何最优码，概率最小的两个符号应具有相同长度的最长码字（且仅最后一位不同），从而可以通过合并它们将问题规模缩减，而哈夫曼算法正好遵循这一原则。

4.2 算术编码

算术编码（Arithmetic Coding）是一种将整个消息序列映射为[0,1)区间内一个实数或二进制分数的编码方法。其基本思想是：

  • 将每个符号的概率区间按顺序排列在[0,1)上。
  • 随着输入符号的出现，不断缩小当前区间，新区间由当前符号对应的子区间决定。
  • 编码结束时，输出区间内的一个足够长的小数（或二进制表示），能唯一确定整个序列。

算术编码的优势在于：

  • 无需整数码字：可以逼近任意分数位的码长，从而在理论上达到熵。
  • 自适应性强：可动态更新概率模型。
  • 适合处理小概率符号：避免哈夫曼编码中长码字引起的浪费。

例如，对二进制信源（P(0)=0.9, P(1)=0.1），输入序列“011”的算术编码可能仅需约3.5位（熵约3.0位），而哈夫曼编码会使用4位。

4.3 LZ系列算法（LZ77/LZ78）

4.3.1 字典编码原理

LZ系列算法（由Jacob Ziv和Abraham Lempel提出）是一种字典编码（Dictionary Coding）方法，不依赖符号的概率统计，而是利用字符串的重复性来压缩。

  • LZ77：维护一个滑动窗口，在已发送的数据中寻找当前字符串的最长匹配，然后输出一个(偏移量, 长度, 下一字符)的元组。
  • LZ78：构建一个动态字典，将新出现的短语（字符串）加入字典并分配一个索引，后续重复时直接输出索引。

LZ77算法广泛应用于gzip、PNG图像格式中；LZ78则是Unix压缩命令compress的基础。

4.3.2 与熵极限的关系

LZ系列算法被证明具有渐近最优性：对于平稳遍历信源，当输入序列无限长时，LZ算法的压缩率收敛于信源的熵率。这意味着，即使不知道信源概率分布，LZ也能在无失真的前提下趋近于理论极限，因此属于通用信源编码（Universal Source Coding）的典范。不过，在短数据或结构严格的信源上，基于统计的哈夫曼/算术编码通常更高效。

5 历史与延伸

5.1 香农的原始论文

1948年，克劳德·香农（Claude Shannon）在《贝尔系统技术期刊》上发表了划时代论文《通信的数学理论》（*A Mathematical Theory of Communication*）。在该文中，香农首次定义了信息熵，并证明了下述结论：对于离散无记忆信源，存在一种编码使得平均码长可以任意接近熵，且不可能低于熵。这就是后来被称为“香农第一定理”的原始表述。该论文也奠定了整个信息论的基石。

香农的证明使用了随机编码和典型序列的思路，但当时较为抽象，后经其他学者（如麦克米伦、费诺等）不断完善。值得一提的是，香农在1948年的论文中主要讨论的是定长码的渐近行为，而变长码的最优性后来由哈夫曼、费诺等人进一步落实为具体算法。

5.2 后续发展

5.2.1 通用信源编码

20世纪70年代，Ziv与Lempel开发了LZ77和LZ78算法，开启了通用信源编码时代。这类算法无需预先知道信源概率分布，却能渐近达到熵率。随后，LZW（Welch改进）、LZMA（7-Zip）、Brotli（Google）等变种不断涌现，成为现代数据压缩的基石。通用编码理论进一步证明了对于任何遍历信源，存在通用编码器，其压缩率渐近趋于熵率。

5.2.2 自适应编码与上下文模型

现代无损压缩技术往往融合了自适应编码与上下文模型（Context Modeling）：

  • 自适应算术编码：编码过程中动态更新符号概率，以适应信源的变化。
  • 上下文模型：根据已编码的上下文（如前几个字符）预测当前字符的概率，例如预测匹配（Prediction by Partial Matching, PPM）和基于上下文树的算法（Context Tree Weighting）。
  • PAQ系列：结合神经网络和数百个上下文模型，在Hutter压缩奖中多次夺冠，压缩率接近理论极限。

自适应编码与上下文模型的发展，使得无损压缩在文本、生物信息、数据存储等领域不断逼近熵的下界，体现了无失真信源编码定理长久而深刻的指导意义。