1.1 Definitions and Examples
信息论关注的是信息从发送者通过信道传输到接收者的过程。发送者和接收者可以是人或者机器。在大多数情况下，发送者和接收者是不同的，但当信息被存储以供日后检索时，接收者可以是未来某个时间的发送者。
我们假设信息来自一个信源 \(S\)，该源发出一个符号序列：
\[ s = X_1 X_2 X_3 \dots \]
例如，\(X_n\) 可能是某个消息中的第 \(n\) 个符号，或某个实验第 \(n\) 次重复的结果。
在现实中，这个序列总是有限的（没有什么是永恒的），但出于理论考虑，有时也会讨论无限序列。我们假设每个符号 \(X_n\) 都是某个固定有限集合 \(S = \{s_1, s_2, \dots, s_q\}\) 的成员，这个集合称为源字母表。为了简化起见，我们还假设，第 \(n\) 个符号 \(X_n\) 为 \(s_i\) 的概率 \(\Pr(X_n = s_i)\) 只依赖于 \(i\)，而与 \(n\) 无关，因此我们写作：
\[ \Pr(X_n = s_i) = p_i \quad \text{for} \quad i = 1, 2, \dots, q \]
因此，不同的符号可能具有不同的概率，但这些概率在时间上保持不变（因此称 \(S\) 是平稳的），并且不依赖于前面的符号 \(X_m\)，其中 \(m < n\)（因此也称 \(S\) 是无记忆的）。在更高级的理论中，这些因素会被考虑进去，但我们在这里忽略它们。与任何概率分布一样，概率 \(p_i\) 必须满足：
\[ p_i \geq 0 \quad \text{and} \quad \sum_{i=1}^q p_i = 1 \]
从统计学的角度看，可以将 \(S\) 看作是一系列独立同分布的随机变量 \(X_n\)，其概率分布为 \((p_i)\)。
例 1.1
\(S\) 是一个公平的骰子，\(S = \{1, 2, 3, 4, 5, 6\}\)，其中 \(q = 6\)，\(s_i = i\) 对于 \(i = 1, 2, \dots, 6\)。\(X_n\) 是第 \(n\) 次掷骰子的结果，且 \(p_i = \frac{1}{6}\) 对于 \(i = 1, 2, \dots, 6\)。一个不公平的骰子类似，但具有不同的概率 \(p_i\)。
例 1.2
\(S\) 是某地的天气，其中 \(X_n\) 代表第 \(n\) 天的天气。为了简化，我们可以让 \(S\) 包含 \(q = 3\) 种天气类型（例如，良好、一般和差），因此 \(p_i\) (\(i = 1, 2, 3\)) 是每种天气类型的概率，假设 \(p_1 = \frac{1}{4}\)，\(p_2 = \frac{1}{2}\)，\(p_3 = \frac{1}{4}\)。（这里我们忽略季节变化，这可能导致概率分布 \((p_i)\) 随时间变化。）
例 1.3
\(S\) 是一本书，\(S\) 包含所有使用的符号（字母、标点符号、数字等）。\(X_n\) 是书中的第 \(n\) 个符号，\(p_i\) 是源字母表中第 \(i\) 个符号的频率。（这里我们忽略前面的符号对概率的影响：例如，在英语中，符号 “q” 几乎总是紧跟着 “u”。）
为了对一个源进行编码，我们使用一个有限的编码字母表 \(T = \{t_1, t_2, \dots, t_r\}\)，它包含 \(r\) 个编码符号 \(t_j\)。
一般来说，编码字母表与源字母表 \(S = \{s_1, s_2, \dots, s_q\}\) 是不同的，因为编码字母表更多地取决于信道的技术，而不是信源本身。我们称 \(r\) 为进制（或者称为基数，意思是“根”），并称这种编码为 \(r\) 进制编码。
在许多例子中，\(r = 2\)，这种编码叫做二进制编码。大多数二进制编码，如 ASCII（计算机中使用），有 \(T = \mathbb{Z}_2 = \{0, 1\}\)，即模 2 的整数集合。进制为 \(r = 3\) 的编码称为三进制编码。
我们通过将每个符号 \(s_i \in S\) 分配一个编码词 \(w_i\)（一个有限的编码符号序列）来对 \(S\) 进行编码。
为了编码 \(s = X_1 X_2 X_3 \dots\)，我们用每个符号 \(X_n = s_i\) 的编码词 \(w_i\) 来表示，从而得到一个由 \(T\) 中的符号组成的序列 \(t\)。为了简洁起见，我们不使用标点符号或空格来分隔编码词；如果使用了，它们必须被视为 \(T\) 的元素，出现在每个 \(w_i\) 的开头或结尾。因此，摩尔斯电码，虽然看起来是二进制的，实际上是一个三进制编码：这三个符号是“.”、“-”和一个空格。
例 1.4
如果 \(S\) 是一个公平的骰子，如例 1.1 所示，取 \(T = \mathbb{Z}_2\)，并让 \(w_i\) 是源符号 \(s_i = i\)（\(i = 1, 2, \dots, 6\)）的二进制表示。因此，\(w_1 = 1\)，\(w_2 = 10\)，\(\dots\)，\(w_6 = 110\)，所以像 \(s = 53214\) 这样的掷骰子序列会被编码为 \(t = 10111101100\)。
我们需要更精确地定义编码。\(T\) 中的一个词 \(w\) 是一个由 \(T\) 的符号组成的有限序列，其长度 \(|w|\) 是符号的数量。所有在 \(T\) 中的词的集合记作 \(T^*\)；它包括长度为 0 的空词，我们将其记作 \(\epsilon\)。所有非空词的集合记作 \(T^+\)。因此，
\[ T^{\ast} = \bigcup_{n=0}^{\infty} T^n \quad \text{and} \quad T^+ = \bigcup_{n=1}^{\infty} T^n \]
其中 \(T^n = T \times T \times \dots \times T\)（有 \(n\) 个因子）是长度为 \(n\) 的词的集合。
一个源编码（或简称为编码）\(C\) 是一个函数 \(C: S \to T^+\)，即将源符号 \(s_i \in S\) 映射到编码词 \(w_i = C(s_i) \in T^+\)。
编码的许多属性仅取决于编码词 \(w_i\)，而与它们与符号 \(s_i\) 之间的具体对应关系无关，因此我们通常也将 \(C\) 视为 \(T^+\) 中的有限词集合 \(\{w_1, w_2, \dots, w_q\}\)。如果 \(S^{\ast}\) 是类比于 \(T^{\ast}\) 定义的，那么可以按照显然的方式将 \(C\) 扩展为一个函数 \(S^{\ast} \to T^{\ast}\)，通过使用 \(C\) 来编码每个 \(s \in S^{\ast}\) 的连续符号：
\[ s = s_{i_1} s_{i_2} \dots s_{i_n} \quad \mapsto \quad w = w_{i_1} w_{i_2} \dots w_{i_n} \in T^{\ast} \]
这个函数的像是集合
\[ C^{\ast} = \{w_{i_1} w_{i_2} \dots w_{i_n} \in T^{\ast} \mid w_{i_k} \in C,\ 1 \leq k \leq n,\ n \geq 0\} \]
我们用 \(|w_i|\) 表示 \(w_i\) 的长度，记作 \(l_i\)，所以每个 \(l_i \geq 1\)。\(C\) 的平均词长为：
\[ L(C) = \sum_{i=1}^q p_i l_i \]
例 1.5
在例 1.4 中的编码 \(C\) 中，有 \(l_1 = 1\)，\(l_2 = l_3 = 2\)，\(l_4 = l_5 = l_6 = 3\)，所以\[ L(C) = \frac{1 + 2 + 2 + 3 + 3 + 3}{6} = \frac{7}{3} \]
我们希望，构造满足以下条件的编码 \(C\)：
- 存在简单且不存在歧义的解码过程 \(t \mapsto S\)。
- 平均词长 \(L(C)\) 尽可能小。
本章讨论准则 (1)，下一章讨论准则 (2)。
1.2 Uniquely Decodable Codes
一个编码 \(C\) 是唯一可解码的（简称 u.d.），如果对于每个 \(t \in T^*\) ，在 \(C\) 下对应至 \(S^*\) 的 \(S\) 最多只有一个；换句话说，函数 \(C: S^* \to T^*\) 是一一对应的，所以 \(C\) 的像 \(C^*\) 中的每个 \(t\) 都可以唯一解码。我们总是假设编码词 \(w_i\) 在 \(C\) 中是不同的，因为如果 \(w_i = w_j\) 且 \(i \neq j\) ，那么 \(t = w_i\) 可能表示 \(s_i\) 或 \(s_j\) ，这样就导致了编码不唯一可解。
在这个假设下，\(C\) 的唯一可解码性的定义是：每当
\[ u_1 u_2 \dots u_m = v_1 v_2 \dots v_n \]
且 \(u_1, \dots, u_m, v_1, \dots, v_n \in C\) ，我们有 \(m = n\) 且对每个 \(i\)，\(u_i = v_i\) 。用代数术语来说，意思是，每个编码序列 \(t \in C^*\) 都可以唯一地分解为编码词的乘积。
定理 1.7
如果编码 \(C\) 中所有编码词 \(w_i\) 具有相同的长度，那么 \(C\) 是唯一可解码的。
证明
设 \(l\) 为编码词的共同长度。如果某个
\(t \in C^*\) 可以分解为 \(u_1 \dots u_m = v_1 \dots v_n\) ，其中每个
\(u_i, v_j \in C\) ，那么 \(|t| = l m = l n\) ，所以 \(m = n\) 。现在，\(u_1\) 和 \(v_1\) 都是 \(t\) 的前 \(l\) 个符号，因此 \(u_1 = v_1\) ，以此类推，\(u_i = v_i\) 对于所有的 \(i\) 。
如果 \(C\) 中的所有编码词都有相同的长度 \(l\)，我们称 \(C\) 为长度为 \(l\) 的块编码。我们将在第 5.7 章详细研究这种编码。
注意到，定理 1.7 的逆命题是错误的：
例 1.8
由以下给出的二进制编码 \(C\)\[ s_1 \mapsto w_1 = 0 , \ s_2 \mapsto w_2 = 01 , \ s_3 \mapsto w_3 = 011 \]
具有可变长度，但仍然是唯一可解码的。
在编码中，每个符号 0 表示一个编码词 \(w_i\) 的开始，并且 \(i\) = 1 + 随后的 1 的数量。
实际上，我们在这里使用符号 0 作为一个标点符号。
我们将给出一个“编码 \(C\) 是唯一可解码的”的充分必要条件。我们使用归纳法定义一个非空词集合的序列
\[ C_0, C_1, \dots \]
对于所有的 \(n\) ，都有 \(C_n \subseteq T^+\) 。具体地，我们定义 \(C_0 = C\) ，并且对于每个 \(n \geq 1\) ，
\[ C_n = \{ w \in T^+ \mid uw = v, \ \exists u \in C, v \in C_{n-1} \text{ or } u \in C_{n-1}, v \in C \} \]
我们定义
\[ C_\infty = \bigcup_{n=1}^{\infty} C_n \]
这个定义一开始可能看起来有些复杂，但如果我们一步一步来，它应该变得会更清晰：我们从 \(C_0 = C\) 开始，然后通过它的前一个集合 \(C_{n-1}\) 来构造每个 \(C_n\)（ \(n \geq 1\) ），最后我们取 \(C_\infty = C_1 \cup C_2 \cup \dots\) 。注意，对于 \(n = 1\) ，\(C_n\) 的定义可以简化：因为 \(C_{n-1} = C_0 = C\) ，所以（式 1.3）中“或”连接的两个条件是相同的，因此
\[ C_1 = \{ w \in T^+ \mid uw = v, \ \exists u, v \in C \text{ 使得 } uw = v \} \]
还注意到，如果 \(C_{n-1} = \emptyset\) ，则 \(C_n = \emptyset\) ，因此通过迭代我们得到 \(C_{n+1} = C_{n+2} = \dots = \emptyset\) 。
根据 \(C_\infty\) 的定义，可以想象构造这个集合可能需要无限多的步骤，对于每个 \(n \geq 1\) 都需要构造一个新的集合 \(C_n\) 。练习 1.1 表明了我们总是可以在有限步内构造出 \(C_\infty\) 。
练习 1.1
求证：如果 \(C\) 的编码词长度为 \(l_1, \dots, l_q\) ，并且对于某个 \(n\) 有 \(w \in C_n\) ，那么 \(|w| \leq l = \max(l_1, \dots, l_q)\) 。从中推导出每个 \(C_n\) 是有限的，并且集合序列 \(C_0, C_1, \dots\) 是最终周期性的。这如何帮助我们构造 \(C_\infty\) ？
证明
对 \(n\) 进行归纳。
如果 \(n = 0\) ，则 \(C_n = C\) ，所以 \(|w| \leq l\) 。
如果 \(n > 0\) ，则 \(uw = v\) ，其中 \(v \in C_{n-1}\) 或 \(v \in C\) ，因此通过归纳或通过定义，\(|w| \leq |v| \leq l\) 。有 \(N = r + r^2 + \dots + r^l = \frac{r(r^l - 1)}{r - 1}\) 个非空的 \(r\) 进制单词 \(w\) ，满足 \(|w| \leq l\) ，因此对于每个 \(n\) ，\(|C_n| \leq N\) 。共有 \(2^N\) 个不同的这样的单词集合，因此在集合 \(C_0, \dots, C_{2^N}\) 中，必定存在一个重复，\(C_i = C_j\) 其中 \(i < j \leq 2N\) 。根据 \(C_n\) 定义，每个 \(C_n\) 仅依赖于 \(C\) 和 \(C_{n-1}\) ，因此对于所有 \(k \geq 0\) ，\(C_{j+k} = C_{i+k}\) ；从而每个 \(C_n = C_0\) 或 \(C_1\) 或 \(\dots\) 或 \(C_{j-1}\) ，因此我们有 \(C_\infty = C_0 \cup C_1 \cup \dots \cup C_{j-1}\) 。因此，一旦我们在连续的集合 \(C_0, C_1, \dots\) 中找到重复，就完成了对所有 \(C_\infty\) 的构造。
我们现在可以给出唯一可解码性的充分必要条件。Sardinas-Patterson 定理如下所示。
定理 1.10 (Sardinas-Patterson Theorem)
\(C\) 是唯一可解码的，当且仅当编码 \(C\) 和 \(C_\infty\) 是互不相交的。另一种表述： 如果一个编码 \(C\) （即一组编码词）是唯一可解码的，那么 \(C\) 中不存在任何编码词能够作为其他编码词的前缀。
由于 Sardinas-Patterson 定理的证明较长，我们将在附录 A 中给出证明；在这里，我们将提供两个典型的论证，以便说明其中涉及的思想。
(=>) 假设 \(C_n \cap C_\infty \neq \emptyset\) ，比如 \(w \in C \cap C_2\) ；因此，\(uw = v\) ，其中 \(u \in C\) 且 \(v \in C_1\) ，或者反之。为了简化起见，我们假设第一种情况成立（第二种情况留作练习）。然后 \(u'v = v'\) ，其中 \(u', v' \in C\) ，因此序列 \(t = u'uw \in T^*\) 可以表示三个源符号的序列（因为 \(u', u, w \in C\) ），也可以表示一个源符号的序列（因为 \(u'uw = u'v = v' \in C\) ）。因此，解码不是唯一的。
(<=) 假设我们有一个非唯一解码的实例，形式为 \(t = u_1u_2 = v_1v_2\) ，其中 \(u_1, u_2, v_1, v_2 \in C\) 。我们不能有 \(|u_1| = |v_1|\) ，因为这将导致 \(u_1 = v_1\) ，从而得到 \(u_2 = v_2\) 。我们可以假设 \(|u_1| > |v_1|\) （如果需要，可以重新编号），因此 \(u_1 = v_1w\) ，其中 \(|w| > 0\) 。然后 \(w \in C_1\) ，所以 \(u_2 \in C_2\) ，因为 \(wu_2 = v_2\) 。因此，\(u_2 \in C \cap C_\infty\) ，所以 \(C\) 和 \(C_\infty\) 不是互不相交的。
定理 1.10 的证明中的一般论证类似于上述的论证，但它们要复杂得多，因为需要处理无限多种不同的情况。幸运的是，对于另一种重要类型的编码，有一个更简单的充分必要的条件，我们将在下一节中讨论。
我们已经定义了唯一解码性，唯一解码性意味着所有有限的编码序列 \(t\) 都可以唯一解码，但也可以考虑更强的要求，即所有编码序列，无论是有限还是无限，都应该满足唯一解码性。由 Even、Levenshtein 和 Riley 提出的一个定理表明，当且仅当存在某个 \(n \geq 1\) 使得 \(C \cap C_\infty = \emptyset\) 且 \(C_n = \emptyset\) 时，才能满足这一要求。（这些也是 \(C\) 有限延迟的唯一解码性的充分必要条件，这意味着存在一个常数 \(d\) ，使得如果两个编码序列在前 \(d\) 个符号上相同，则它们的第一个编码词也相同；因此，解码可以在最多延迟 \(d\) 个符号后开始。我们将在下一节中考虑更强的条件。）
在本书的其余部分，我们将把注意力集中在有限的编码序列上。
1.3 Instantaneous Codes
在定义即时编码之前，我们先看几个例子。
例 1.14
考虑二进制编码 \(C\)，其定义为
\[ s_1 \rightarrow 0, \ s_2 \rightarrow 01, \ s_3 \rightarrow 11 \ \text{。} \]
使用 §1.2 中的符号，我们有 \(C_1 = C_2 = \dots = \{1\}\)，因此 \(C_\infty = \{1\}\)；所以 \(C_n \cap C_\infty = \emptyset\)，根据定理 1.10，\(C\) 是唯一可解码的。现在假设我们收到一个以 \(t = 0111 \dots\) 开头的有限消息。虽然我们知道它可以唯一解码，但在遇到连续的 1 的块的末尾之前，我们无法开始解码：如果这个块中 1 的个数是偶数，\(t\) 的分解必须是 \(0.11.11.11 \dots\)，解码后的消息必须是 \(s = s_1 s_3 s_3 \dots\)；然而，如果 1 的个数是奇数，则分解必须是 \(01.11.11.11 \dots\)，因此 \(s = s_2 s_3 s_3 \dots\)。在实际应用中，这种解码延迟可能会带来困难。我们说该编码 \(C\) 不是瞬时的（instantaneous）。
例 1.16
考虑二进制编码 \(D\)，其定义为
\[ s_1 \rightarrow 0, \ s_2 \rightarrow 10, \ s_3 \rightarrow 11 \ \text{。} \]
它是例 1.14 中编码 \(C\) 的反转。我们可以通过定理 1.10 或者因为 \(C\) 是唯一可解码的，来证明 \(D\) 也是唯一可解码的。它也是即时的，意味着我们可以在接收到消息 \(t\) 时边接收边解码：0 表示 \(w_1\)，我们将其解码为 \(s_1\)，而 1 表示 \(w_2 = 10\) 或 \(w_3 = 11\) 的开始，一旦知道下一个符号，就能解码为 \(s_2\) 或 \(s_3\)。因此，消息中的任何编码词都可以在到达时立即解码，无需延迟。
现在给出正式的定义：一个编码 \(C\) 是即时的，那么，对于每个编码词序列 \(w_{i_1}, w_{i_2}, \dots, w_{i_n}\)，每个以 \(t = w_{i_1} w_{i_2} \dots w_{i_n} \dots\) 开头的编码序列，都会被唯一解码为 \(S = s_{i_1} s_{i_2} \dots s_{i_n} \dots\)，无论后续的符号是什么。
因此，例 1.14 中的编码 \(C\) 不是瞬时的：一个序列 \(t = w_1 w_3 \dots = 011 \dots\) 可能会被解码为 \(s = s_1 s_3 \dots\) 或者 \(s_2 s_3 \dots\)，这取决于后续的符号。例 1.16 中的编码 \(D\) 是瞬时的：一旦接收到 \(w_{i_1} w_{i_2} \dots w_{i_n}\)，我们就知道它表示 \(s_{i_1} s_{i_2} \dots s_{i_n}\)，无论接下来是什么符号。根据定义，每个瞬时编码都是唯一可解码的；例 1.14 表明反过来是错误的。
如果编码 \(C\) 没有任何编码词 \(w_i\) 是任何其他编码词 \(w_j\)（\(i \neq j\)）的前缀（初始段），则称： \(C\) 是前缀编码（prefix code）。等价地表述为，对于任何 \(w \in T^*\)，不存在 \(w_j = w_i w\)，即在 §1.2 中的符号表示为 \(C_1 = \emptyset\)。因此，例 1.14 中的编码 \(C\) 不是前缀编码（因为 0 是 01 的前缀），但在例 1.16 中反转后的编码 \(D\) 是前缀编码。
定理 1.17
一个编码 \(C\) 是瞬时编码，当且仅当它是前缀编码。
证明
(=>) 如果 \(C\) 不是前缀编码，假设 \(w_i\) 是 \(w_j\) 的前缀，那么以 \(t = w_i \dots\) 开头的编码序列，可能会被解码为 \(s = s_i \dots\) 或 \(s = s_j \dots\)，因此 \(C\) 不是瞬时编码。
(<=) 如果 \(C\) 是前缀编码，并且 \(t\) 以 \(w_i \dots\) 开头，那么 \(s\) 必须以 \(s_i\) 开头，因为没有任何编码词 \(w_j\)（\(j \neq i\)）是 \(w_i\) 的前缀，或者有 \(w_i\) 作为前缀。我们可以这样继续，在接收到每个编码词时，逐步解码 \(t\) 中的后续编码词，因此 \(C\) 是瞬时编码。
1.4 Constructing Instantaneous Codes
为了理解即时码（instantaneous codes）的构造，我们可以将编码符号集 \(T^*\) 中的单词看作一个图（graph）。在这种情况下，顶点是 \(T^*\) 中的单词 \(w\)，并且每个 \(w\) 通过一条边连接到 \(r\) 个单词 \(wt_1, \dots, wt_r\)（其中 \(t_i \in T\)），这些单词是通过在 \(w\) 的末尾添加一个符号 \(t_i\) 形成的。可以将这个图想象成向上生长的结构，其中空单词 $ e $ 位于底部，长度为 $ l $ 的单词位于距离 $ e $ 为 $ l $ 的层级上。在图论中，这样的图称为 \(r\)-叉根树（\(r\)-ary rooted tree）。图 1.1 展示了二叉树 $ T^* $（即 $ T = _2 , l = 3 $）。
一个编码 \(C\) 可以看作树 \(T^*\) 的一个有限顶点集。单词 \(w_i\) 是 \(w_j\) 的前缀，当且仅当顶点 \(w_i\) 被顶点 \(w_j\) 所支配，即在 \(T^*\) 中存在一条从 \(w_j\) 到 \(w_i\) 的向上路径。因此，根据定理 1.17，编码 \(C\) 是即时码（instantaneous code）的充要条件是：对于任意两个不同的顶点 \(w_i, w_j \in C\)（其中 \(i \neq j\)），顶点 \(w_i\) 不支配 \(w_j\)，也不被 \(w_j\) 支配。我们可以利用这一判别标准来构造即时码，即在 \(T^*\) 中逐个选择顶点，确保任何选定的顶点间都不会支配（或被支配）。
例 1.18
我们来为一个包含五个符号 \(S = \{s_1, s_2, s_3, s_4, s_5\}\) 的信息源构造一个即时二进制码 \(C\)。
首先，尝试设定 \(s_1 \rightarrow w_1 = 0\)，因此 0 是 \(C\) 中的一个顶点。如果 \(C\) 是一个前缀码（prefix code），那么 \(C\) 中的其他编码不能支配 0，因此它们必须以 1 开头（即，所有其他编码必须以 1 开头）。如果我们尝试设定 \(s_2 \rightarrow w_2 = 1\)，那么无法再添加其他编码，因为它们会支配 \(w_1\) 或 \(w_2\)。因此，我们改为设定 \(s_2 \rightarrow w_2 = 10\)。接下来，如果我们尝试 \(s_3 \rightarrow w_3 = 11\)，那么将无法再添加更多编码。因此，我们改为设定 \(s_3 \rightarrow w_3 = 110\)。继续这一过程，我们可以得到以下可能的编码方案：\(s_4 \rightarrow w_4 = 1110\)，\(s_5 \rightarrow w_5 = 1111\)。这样，我们得到一个即时二进制码：\(C = \{0, 10, 110, 1110, 1111\}\)，其对应的码字长度为 \(l_i = \{1, 2, 3, 4, 4\}\)，如图 1.2 所示。
这并不是唯一的即时编码方案，例如，二进制码 \(C' = \{00, 01, 10, 110, 111\}\) 也是即时的。
例 1.19
是否存在一个满足码字长度为 \(\{1,2,3,3,4\}\) 的即时二进制码（instantaneous binary code）？
同样，我们使用二叉树 \(T^*\) 进行分析。任何长度为 \(l_1 = 1\) 的码字 \(w_1\)（即高度为 1 的顶点）都会消除二叉树 \(T^*\) 中一半的可能码字，也就是排除所有支配 \(w_1\) 的顶点（\(w_2, \dots, w_5\) 能从选择这些顶点）。因此，剩余的比例为：\(1 - \frac{1}{2} = \frac{1}{2}\)。选择长度为 \(l_2 = 2\) 的码字 \(w_2\) 会进一步排除 \(T^*\) 的 \(\frac{1}{4}\) 部分，使剩余的比例变为：\(1 - \frac{1}{2} - \frac{1}{4} = \frac{1}{4}\)。在高度 3 处选择 \(w_3\) 和 \(w_4\) 会再消除 \(\frac{1}{2^3} + \frac{1}{2^3} = \frac{1}{4}\) 的 \(T^*\)，此时二叉树中已无剩余空间用于 \(w_5\)。
所以，问题在于，每个码字在 \(T^*\) 中占据的比例总和超过了 1，因此无法构造这样的即时二进制码。
上述例子中用到的比例（proportion）这一概念在分析无限树 \(T^*\) 时非常有用，但并不精确。通过对其进行精确化，我们可以类似地推出关于即时 \(r\)-进制码（instantaneous \(r\)-ary codes）存在性的充要条件，即我们可以判断是否能构造一个满足给定码字长度的即时码。
1.5 Kraft’s Inequality
受到 §1.4 中示例的启发，我们得到以下结论，被称为 Kraft 不等式：
定理 1.20（Kraft’s Inequality）
对于一个 \(r\)-进制即时码（instantaneous \(r\)-ary code）\(C\)，其码字长度为 \(l_1, l_2, \dots, l_q\)，则该码能够存在的充要条件是：\[ \sum_{i=1}^{q} r^{-l_i} \leq 1 \]
证明 (<=) 我们可以对码字长度重新编号，使其满足以下顺序：\(l_1 \leq l_2 \leq \dots \leq l_q\)。设 \(l = \max(l_1, \dots, l_q)\)，并考虑树 \(T^*\) 的一部分 \(T^{\le l}\)，定义为：\(T^{\le l} = T^0 \cup T^1 \cup \dots \cup T^l\)，即从根到最大高度为 \(l\) 的所有节点组成的部分。显然，该树是一个有限树（finite tree）：
在每个高度 \(h = 0,1, \dots, l\) 处，树具有 \(r^h\) 个顶点（即长度为 \(h\) 的所有可能单词）。
高度为 \(l\) 的所有 \(r^l\) 个顶点，被称为叶子节点。
我们可以为符号 \(s_1\) 分配一个高度为 \(l_1\) 的顶点 \(w_1\)，其长度为 \(l_i\)。接着，我们修剪 \(w_i\) 及其上方的整个子树 \(T^{\le l}\)，因为这些顶点不能再被使用。特别地，这一操作会移除 \(r^{l - l_1}\) 个叶子节点，即所有以 \(w_i\) 开头的长度为 \(l\) 的单词（参见图 1.3）。
如果 \(q > 1\)， \(r^{l-l_1} < r^l\) ，因此，在第一次修剪后，\(T^{\le l}\) 至少有一个叶子节点未被修剪。我们截取该叶子节点的前 \(l_2\) 个符号构造出第二个码字 \(w_2\)，其长度为 \(l_2\)。由于该节点不在 \(w_1\) 之上，我们可以选择它作为新的码字。接着，我们修剪 \(w_2\) 及其上方的整个子树 \(T^{\le l}\)，这样会进一步移除 \(r^{l - l_2}\) 个叶子节点。由于没有叶子节点既位于 \(w_1\) 之上又位于 \(w_2\) 之上，因此两次修剪不会发生重叠。
我们如此循环往复，每次选择一个码字并修剪，使得没有任何一个码字在另一个码字的上方或下方。当已选择了 \(k\) 个码字 \(w_1, w_2, \dots, w_k\) （其中 \(k < q\)）时，我们已经修剪了总计 \(r^{l - l_1} + r^{l - l_2} + \dots - r^{l - l_k}\) 个叶子节点。
由于
\[ \sum_{i=1}^{k} r^{l - l_i} < \sum_{i=1}^{q} r^{l - l_i} \le r^l \]
所以，第k次修剪之后，至少还有一个叶子节点剩余，因此我们可以从该叶子节点的前 \(l_{k+1}\) 个符号构造出新的码字 \(w_{k+1}\)，其长度为 \(l_{k+1}\)。按照这个方法，我们可以不断地选择新的码字，直到选择出 \(w_q\) 为止。
在整个过程中，前缀条件（prefix condition）始终成立，因此根据定理 1.17，最终构造出的编码集 \(C = \{ w_1, w_2, \dots, w_q \}\) 是一个瞬时码（instantaneous code）。
(=>) 如果 \(C\) 是瞬时码，那么根据定理 1.17，它必须是前缀码（prefix code）。因此，树 \(T^{\le l}\) 的每个叶子节点至多位于一个码字的上方。
对于 \(C\) 中的每个码字 \(w_i\)，位于 \(r^{l - l_i}\) 个叶子节点的下方（其中 \(l_i = |w_i|\)）。对所有码字 \(w_i\) 求和，我们得到：\(\sum_{i=1}^{q} r^{l - l_i}\) ，表示所有码字上方的叶子总数。由于树 \(T^*_l\) 总共有 \(r^l\) 个叶子节点，因此必须满足：
\[ \sum_{i=1}^{q} r^{l - l_i} \leq r^l \]
两边同时除以 \(r^l\)，我们得到 Kraft 不等式：
\[ \sum_{i=1}^{q} r^{-l_i} \leq 1 \]
1.6 McMillan’s Inequality
我们已经看到，唯一可译码的码类严格大于瞬时码的类，因此我们可能会期望，对于唯一可译码的 \(r\)-进制码，其存在性的充分必要条件会比 Kraft 不等式 (1.5) 更弱。然而，令人惊讶的是，事实并非如此。McMillan 在 1956 年提出了以下不等式，被称为McMillan 不等式 ：
定理1.21（McMillan 不等式） 存在一个唯一可译码的 \(r\)-进制码 \(C\)，其码字长度为 \(l_1, l_2, \dots, l_q\)，当且仅当满足以下不等式：
\[ \sum_{i=1}^{q} r^{-l_i} \leq 1 \]
证明 (<=) 根据定理 1.20（Kraft 不等式），存在一个瞬时 \(r\)-进制码，其码字长度为 \(l_i\)，则该码也是唯一可译码的，因为瞬时码本身就满足唯一可译码的性质。
(=>) 设 \(C\) 为一个唯一可译码的 \(r\)-进制码，其码字长度为 \(l_1, l_2, \dots, l_q\)。定义：
\[ K = \sum_{i=1}^{q} \frac{1}{r^{l_i}} \]
并设 \(l = \max(l_1, \dots, l_q), \quad m = \min(l_1, \dots, l_q)\)。现在考虑展开式：
\[ K^n = (\sum_{i=1}^{q} \frac{1}{r^{l_i}})^n \]
其中 \(n \geq 1\)。该和式由以下形式的项组成：
\[ \frac{1}{r^{l_{i_1}}} \times \frac{1}{r^{l_{i_2}}} \times \dots \times \frac{1}{r^{l_{i_n}}} = \frac{1}{r^j} \]
其中 \(j = l_{i_1} + l_{i_2} + \dots + l_{i_n}\)。
由于对所有 \(i\) 都有 \(m \leq l_i \leq l\)，所以 \(j\) 的取值范围为：\(mn \leq j \leq ln\) 。将相同 \(j\) 值的项收集在一起，我们可以写成：
\[ K^n = \sum_{j=mn}^{ln} \frac{N_{j,n}}{r^j} \]
\(\frac{l}{r^j}\) 的系数 \(N_{j,n}\) 表示将 \(j\) 写成 \(n\) 个码字长度之和（可能有重复）的方式数；等价地，\(N_{j,n}\) 也是总长度为 \(j\) 的 \(n\) 个码字组成的序列 \(t = w_{i_1} w_{i_2} \dots w_{i_n}\) 的数量。
由于 \(C\) 是唯一可译码的，因此每个 \(t\) 最多只能由一个码字序列生成。因此，\(N_{j,n}\) 小于等于长度为 \(j\) 的码序列的数量，即：\(N_{j,n} \leq r^j\)。
由于 \(K^n\) 是 $ ln - mn + 1 $ 的多个项之和，并且每项满足 \(\frac{N_{j,n}}{r^j} \leq 1\)，我们可以得到：
\[ K^n = \sum_{j=mn}^{ln} \frac{N_{j,n}}{r^j} \leq (l-m)n + 1 \]
对于所有 \(n \geq 1\)，现在 \(K\)、\(l\)、\(m\) 与 \(n\) 无关，因此如果 \(K > 1\)，则该不等式的左边会呈指数级增长，而右边仅会线性增长。对于足够大的 \(n\)，这种增长速度的差异与上式矛盾，因此我们必须有 \(K \leq 1\)。
以上证明来自于 Karush ；原始证明使用了复函数。定理 1.20 和 1.21 立即推导出：
推论 1.22 存在一个码字长度为 \(l_1, \dots, l_q\) 的瞬时 \(r\)-进制码，当且仅当：存在一个具有这些码字长度的唯一可译的 \(r\)-进制码。
1.7 Comments on Kraft’s and McMillan’s Inequalities
注释 1.23
定理 1.20 和 1.21 并未表明：如果一个码是瞬时码或唯一可译码， 其中它的 \(r\)-进制码的码字长度为 \(l_1, \dots, l_q\)，当且仅当 \(\sum r^{-l_i} \leq 1\) 时。
例如，二进制码 \(C = \{0, 01, 011\}\) 具有码字长度 \(l_1 = 1, l_2 = 2, l_3 = 3\)，因此：\(\sum r^{-l_i} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} = \frac{7}{8} \leq 1\) 。然而，该码并不是前缀码，因此它不是瞬时码。同样，可以找到一个具有相同码字长度但不是唯一可译的二进制码，例如：\(C = \{0, 01, 001\}\) 。这个例子显然不是唯一可译码。
注释 1.24
但是，定理 1.20 和 1.21 断言：如果满足 \(\sum r^{-l_i} \leq 1\) ，那么一定存在满足这些参数的码，它既是瞬时码又是唯一可译码。
例如，二进制码 \(C = \{0, 10, 110\}\) 是一个前缀码，因此同时满足瞬时性和唯一可译性。
注释 1.25
如果一个 \(r\)-进制码 \(C\) 是唯一可译码，那么它不一定是瞬时码。但根据推论 1.22，必然存在一个具有相同码字长度的瞬时 \(r\)-进制码。
例如，在例 1.14 中，二进制码：\(C = \{0, 01, 11\}\) 是唯一可译码，但不是瞬时码。
然而，在例 1.16 中，具有相同码字长度的瞬时码：\(V = \{0, 10, 11\}\) 满足瞬时性。
注释 1.26
在和式 \(K = \sum r^{-l_i}\) 中，每一项 \(r^{-l_i}\) 对应于树 \(T^*\) 中高度为 \(l_i\) 的顶点 \(w_i\) 之上的”比例”（proportion）。
这种解释虽然不够严格，但在 §1.4 中已被使用。它有助于理解为何需要满足 \(K \leq 1\)。