简洁是智慧的灵魂。 – 哈姆雷特
本章的目的是介绍熵函数，它衡量源发出的信息量。我们将研究这个函数的基本性质，并展示它与源的编码的平均码长之间的关系。
3.1 Information and Entropy
为了量化源 \(S\) 的符号 \(s_i\) 所传递的信息，我们为每个 \(i\) 定义一个数值 \(I(s_i)\)，它表示在知道 \(S\) 发出了 \(s_i\) 时我们所获得的信息量；这也代表了我们在知道 \(s_i\) 是否会被发出之前的先验不确定性（我们不确定该符号是否会出现），以及符号出现后所带来的意外程度(surprise)。因此，我们要求满足以下条件：
\(I(s_i)\) 是 \(s_i\) 的概率 \(p_i\) 的递减函数，当 \(p_i = 1\) 时，\(I(s_i) = 0\)；
\(I(s_is_j) = I(s_i) + I(s_j)\)。
条件 (1) 断言：事件的概率越大，它传递的信息量越少，一个必然发生的事件传递的信息量为零；报社编辑在选择新闻时常常遵循这一原则。条件 (2) 断言，由于源 \(S\) 发出的符号是独立的（正如我们所假设的），通过了解两个连续符号所获得的信息量是这两个符号各自信息量的和。（如果连续符号不是独立的，那么获得的信息量会少于两者之和，因为了解 \(s_i\) 会告诉我们一些关于 \(s_j\) 的信息。）
源 \(S\) 中符号的独立性意味着：
\[ \text{Pr}(s_i, s_j) = \text{Pr}(s_i) \cdot \text{Pr}(s_j) = P_i \cdot P_j \quad \forall \ i, j. \]
因此，如果我们定义信息量为：
\[ I(s_i) = - \log p_i = \log \frac{1}{p_i} \]
则条件 (1) 和 (2) 将得到满足，并且：
\[ I(s_is_j) = \log \frac{1}{p_i p_j} = \log \frac{1}{p_i} + \log \frac{1}{p_j} = I(s_i) + I(s_j) \]
由于：当 \(P_i \to 0\)，\(I(s_i) \to +\infty\) ，我们约定：
\[ I(s_i) = +\infty \quad \text{When} \ \ p_i = 0 \]
该函数的图形如图 3.1 所示。
选择对数的底数并不非常重要。我们通常选择对数底数为 \(r\)，其中 \(r\) 是编码符号的数量，因此在最常见的二进制情况下，我们有：\(log = lg = \log_2\)。对数底数的变化只是单位的变化，因为：
\[ x = r^{log_r x} \ , \ \forall x > 0 \]
取对数时，改变底数为 \(s\) 会得到：
\[ \log_s x = log_sr \cdot log_rx \]
在二进制情况下，信息的单位称为比特（binary digits）。如果 \(r\) 不重要或已被理解，我们将写作 \(I(s_i) = -\log(p_i)\)；如果我们希望强调 \(r\) 的值，则写作 \(I_r(s_i) = -\log_r(p_i)\)。
例 3.1
设 \(S\) 是一个公平的硬币，\(s_1\) 和 \(s_2\) 分别表示正面和反面。则 \(p_1 = p_2 = \frac{1}{2}\)，所以如果我们取 \(r = 2\) ，则 \(I_2(s_1) = I_2(s_2) = 1\)。因此，信息的标准单位就是从一次公平的硬币投掷中所获得的信息量。
由于源 \(S\) 的每个符号 \(s_i\) 以概率 \(p_i\) 发射，因此，源 \(S\) 传递的平均信息量（每个源符号的平均信息量）由以下函数给出，称为 \(r\) -进制熵：
\[ H_r(S) = \sum_{i=1}^{q} p_i I_r(s_i) = - \sum_{i=1}^{q} p_i \log_r p_i \]
与函数 \(I\) 类似，换底 \(r\) 相当于单位的变化，具体为：
\[ H_s(S) = log_sr \cdot H_r(S) \]
当 \(r\) 被理解或不重要时，我们通常写作：
\[ H(S) = - \sum_{i=1}^{q} p_i \log p_i \]
由于当 \(p \to 0\) 时 \(p \log \left( \frac{1}{p} \right) = -p \log p\) 趋近于 0（见图 3.2），我们采用约定 \(p \log \left( \frac{1}{p} \right) = 0\) 当 \(p = 0\)，这样使得 \(H(S)\) 是概率 \(p_i\) 的连续函数。
例 3.2
设 \(S\) 有 \(q = 2\) 个符号，概率分别为 \(p\) 和 \(1 - p\)；因此，\(S\) 可以表示一次投掷硬币的结果，可能是有偏的。我们将经常使用这个概率分布，为了方便，我们引入符号
\[ \bar{p} = 1 - p, \quad \text{where} \quad 0 \leq p \leq 1 \]
这里的符号 \(P\) 不应与复共轭操作混淆，本书中并不使用复共轭。然后，
\[ H(S) = -p \log p - \bar{p} \log \bar{p} \]
我们也将这个重要的函数记为 \(H(p) = H_r(p) = -p \log p - \bar{p} \log \bar{p}\)。
图3.3给出了函数 \(H_2(p)\) 的图形；对于一般的 \(r\) ，我们只需要将垂直尺度乘以 \(\log_r2\) 的因子。由此可以看出，\(H(p)\) 在 \(p = \frac{1}{2}\) 时最大（即 1），在 \(p = 0\) 或 \(p = 1\) 时最小（即 0）。因此，关于 \(S\) 的不确定性最大和最小时，意味着 \(S\) 传递的信息也分别最大和最小。请注意，图形关于垂直线 \(p = \frac{1}{2}\) 对称，也即是 \(H(p) = H(\bar{p})\)。
如果我们在例3.2中，令 \(p = \frac{2}{3}\) ，我们可以得到：
\[ H_2(S) = \frac{2}{3} log_2\frac{3}{2} + \frac{1}{3} log_23 = 0.918 \]
因此，这个偏置硬币所传递的信息少于在示例3.1中讨论的公平硬币，后者 \(H_2(S) = 1\)。
例 3.3
如果源 \(S\) 有 \(q = 5\) 个符号，其概率分别为 \(p_1 = 0.3\)、\(p_2 = 0.2\)、\(p_3 = 0.2\)、\(p_4 = 0.2\)、\(p_5 = 0.1\)，如在 §2.2 例2.5中所示，我们可以得出 \(H_2(S) \approx 2.246\)。
我们还可以将这些源 \(S\) 的熵与通过二进制霍夫曼编码得到的平均字长进行比较。例如，在例3.2中，当 \(p = \frac{2}{3}\) 时，我们发现对于 \(n = 1, 2, 3\) ，通过二进制霍夫曼编码源 \(S^n\) 得到的平均字长分别为 \(L \approx 1, \ 0.944, \ 0.938\)，这些值接近熵 \(H_2(S) \approx 0.918\)。在例2.5中得到的平均字长 \(L(C) = 2.3\) 接近于我们在例3.3中计算的熵 \(H_2(S) \approx 2.246\)。平均字长与熵之间的紧密关系展示了香农第一定理，我们将在第3.6节中陈述并证明该定理。
例 3.6
通过使用字母表中已知字母的频率，英语文本的熵值被计算为大约 4.03。
最后这一例子似乎表明，读一本书所传递的信息大约是投掷硬币的四倍，这说明了信息论并不关心消息的有用性或趣味性，因为这些因素很大程度上依赖于接收信息的个人。因此，一个统计学家可能会很高兴收到一本包含随机数字或字母的书，而普通人则可能更喜欢一本小说，即便它的熵值较低。
3.2 Properties of the Entropy Function
在 §3.1 中，我们定义了具有概率 \(p_i\) 的信源 \(S\) 的熵为：
\[ H_r(S) = \sum_i p_i \log_r \frac{1}{p_i}. \]
由于 \(p \log_r (1/p) \geq 0\)，并且当且仅当 \(p = 0\) 或 \(p = 1\) 时等号成立，我们有：
定理 3.7
\(H_r(S) \geq 0\)，并且，当且仅当存在某个 \(i\) 使得 \(p_i = 1\)（从而对于所有 \(j \neq i\) 有 \(p_j = 0\)）时等号成立。
因此，当信源 \(S\) 发出的符号没有不确定性时，即某个符号总是出现，从而不传递任何信息时，熵最小。那么，熵何时最大呢？要回答这个问题，我们需要：
引理 3.8
对于所有 \(x > 0\) ，有 \(\ln x \leq x - 1\)，并且当且仅当 \(x = 1\) 时等号成立。
将其转换为以某个其他底 \(r\) 的对数，我们有：\(\log_r x \leq (x - 1) \log_r e\)，并且当且仅当 \(x = 1\) 时等号成立。这个结果看起来有些技术性，但它具有许多非常有用的推论。
推论 3.9
设 \(x_i \geq 0\) 且 \(y_i > 0\) ，其中 \(i = 1, \dots, q\)，并且满足：
\[ \sum_{i=1}^q x_i = \sum_{i=1}^q y_i = 1 \]
因此 \((x_i)\) 和 \((y_i)\) 可被视为概率分布，且 \(y_i \neq 0\)。则有：
\[ \sum_{i=1}^q x_i \log_r \frac{1}{x_i} \leq \sum_{i=1}^q x_i \log_r \frac{1}{y_i} \]
即：
\[ \sum_{i=1}^q x_i \log \frac{y_i}{x_i} \leq 0 \]
当且仅当对于所有 \(i\) ，\(x_i = y_i\) 时，等号成立。
证明
如果对于所有 \(i\)，\(x_i \neq 0\) ，则不等式左侧 (LHS) 与右侧 (RHS) 之差为：
\[ \begin{aligned} \text{LHS} - \text{RHS} & = \sum_{i=1}^q x_i \log_r \frac{y_i}{x_i}\\ & = \sum_{i=1}^q x_i \cdot \frac{\ln (y_i / x_i)}{\ln r} \quad (\text{因为} \log_r x = \frac{\ln x}{\ln r})\\ & \leq \frac{1}{\ln r} \sum_{i=1}^q x_i \left( \frac{y_i}{x_i} - 1 \right)\\ & = \frac{1}{\ln r} \left( \sum_{i=1}^q y_i - \sum_{i=1}^q x_i \right) \quad (\text{由引理 3.8，应用 } q \text{ 次})\\ & = 0\\ \end{aligned} \]
等号成立的条件是对于每个 \(i\) ，\(\frac{y_i}{x_i} = 1\)，即 \(y_i = x_i\)。当某些 \(x_i = 0\) 时，论证类似。因为我们约定 \(X_i \log_r (1 / x_i) = 0\)（当 \(x_i = 0\) 时），可以忽略这些项的影响。\(\square\)
定理 3.10
如果一个信源 \(S\) 有 \(q\) 个符号，则 \(H_r(S) \leq \log_r q\) ，当且仅当所有符号的概率相等时，等号成立。
证明
设 \(x_i = p_i\)（\(S\) 的各个符号的概率），\(y_i = \frac{1}{q}\)，则满足推论 3.9 的条件。因此，我们有：
\[ H_r(S) = \sum_{i=1}^q p_i \log_r \frac{1}{p_i} \leq \sum_{i=1}^q p_i \log_r q = \log_r q \sum_{i=1}^q p_i = \log_r q \]
当且仅当每个 \(p_i = \frac{1}{q}\) 时，等号成立。 \(\square\)
因此，当信源发出的符号具有最大不确定性时，熵值最大，传递的信息量也最多。
3.3 Entropy and Average Word Length
在 §3.1 接近尾声时，我们考虑了几个信源，并比较了它们的熵与哈夫曼编码的平均字长。我们现在将更详细地探讨熵与平均字长之间的关系。
定理 3.11
如果 \(C\) 是信源 \(S\) 的一个唯一可解码的 \(r\) 进制码，则 \(L(C) \geq H_r(S)\)。
证明
我们定义：
\[ K = \sum_{i=1}^q r^{-l_i} \]
其中 \(C\) 的字长为 \(l_1, \dots, l_q\)。根据 McMillan 不等式（定理 1.21），有 \(K \leq 1\)。现在应用推论 3.9，定义 \(x_i = p_i\)（信源 \(S\) 的符号概率），\(y_i = \frac{r^{-l_i}}{K}\)，满足 \(y_i > 0\) 且 \(\sum_{i=1}^q y_i = 1\)。则：
\[ \begin{aligned} H_r(S) & = \sum_{i=1}^q p_i \log_r \frac{1}{p_i}\\ & \leq \sum_{i=1}^q p_i \log_r \frac{1}{y_i} \quad \text{根据推论 3.9} \\ & = \sum_{i=1}^q p_i \log_r \left( {r^{l_i}K} \right)\\ & = \sum_{i=1}^q p_i (l_i + \log_r K)\\ & = \sum_{i=1}^q p_i l_i + \log_r K \sum_{i=1}^q p_i\\ & = L(C) + \log_r K \quad (\text{因为} \sum_{i=1}^q P_i = 1)\\ & \leq L(C) \quad (\text{因为} K \leq 1) \end{aligned} \]
因此，\(L(C) \geq H_r(S)\) 。\(\square\)
这一定理可以如下理解：
信源 \(S\) 发出的每个符号平均携带 \(H_r(S)\) 个单位的信息。为了在编码过程中不丢失任何信息，编码 \(C\) 必须是唯一可解码的。每个编码符号传递一个单位的信息，因此 \(C\) 的每个编码词平均必须至少包含 \(H_r(S)\) 个编码符号，即 \(L(C) \geq H_r(S)\)。特别地，传递更多信息的信源需要更长的编码词。
推论 3.12
给定一个具有概率 \(p_i\) 的信源 \(S\)，存在一个唯一可解码的 \(r\) 进制码 \(C\) 使得 \(L(C) = H_r(S)\)，当且仅当对于每个 \(i\)，\(\log_r p_i\) 是一个整数，即每个 \(p_i = r^{e_i}\)，其中 \(e_i \leq 0\) 是一个整数。
证明
(\(\Rightarrow\)) 如果在定理 3.11 的证明中 \(L(C) = H_r(S)\)，那么其中的两个不等号必须同时取等号。根据推论 3.9，这意味着对于每个 \(i\)，\(p_i = y_i\)，并且 \(\log_r K = 0\)。由此得出 \(K = 1\)，且：\(p_i = \frac{r^{-l_i}}{K} = r^{-l_i}\)，因此：\(\log_r p_i = -l_i\)，这是一个整数。
(\(\Leftarrow\)) 假设对于每个 \(i\)，\(-\log_r p_i\) 是一个整数 \(l_i\)。由于 \(p_i \leq 1\)，我们有 \(l_i \geq 0\)。现在：\(r^{l_i} = \frac{1}{p_i}\)。所以：
\[ \sum_{i=1}^q \frac{1}{r^{l_i}} = \sum_{i=1}^q p_i = 1 \]
这满足 McMillan 不等式（定理 1.21），因此存在一个唯一可解码的 \(r\) 进制码 \(C\)，其字长为 \(l_i\)。此码的平均字长为：
\[ L(C) = \sum_{i=1}^q p_i l_i = H_r(S) \]
\(\square\)
推论 3.12 中条件 \(p_i = r^{e_i}\) 是非常苛刻的。对于大多数信源，每一个唯一可解码的编码都满足 \(L(C) > H_r(S)\)。
例 3.13
如果信源 \(S\) 有 \(q = 3\) 个符号 \(s_i\)，其概率分别为 \(p_i = \frac{1}{4}, \frac{1}{2}, \frac{1}{4}\)（如例 1.2 和 2.1），则 \(S\) 的二进制熵为：
\[ H_2(S) = \frac{1}{4} \log_2{4} + \frac{1}{2} \log_2{2} + \frac{1}{4} \log_2{4} = \frac{1}{4} \cdot 2 + \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 = \frac{3}{2} \]
考虑二进制哈夫曼编码 \(C\)：\(s_1 \mapsto 00\) ，\(s_2 \mapsto 1\) ，\(s_3 \mapsto 01\)。这是 \(S\) 的一个最优编码，其平均字长为：
\[ L(C) = \frac{1}{4} \cdot 2 + \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 = \frac{3}{2} \]
因此，在此情况下，对于某个唯一可解码的二进制码 \(C\) ，\(L(C) = H_2(S)\) 。这是因为所有的概率 \(p_i\) 均为 2 的幂次。
例 3.14
设信源 \(S\) 有 \(q = 5\) 个符号，其概率分别为 \(p_i = 0.3, 0.2, 0.2, 0.2, 0.1\)（参见 §2.2，例 2.5）。我们在示例 3.3 中看到 \(H_2(S) \approx 2.246\)，在例 2.5 中看到 \(S\) 的二进制哈夫曼编码的平均字长为 2.3。因此，根据定理 2.8，对于 \(S\) 的每一个唯一可解码的二进制码 \(C\)，有：
\[ L(C) \geq 2.3 > H_2(S) \]
这表明不存在满足 \(L(C) = H_2(S)\) 的唯一可解码二进制码。原因在于，此例中概率 \(p_i\) 并非全都为 2 的幂次。
根据推论 3.12，如果某些 \(p_i = 0\)，则必然有 \(L(C) > H_r(S)\)。然而，通过删除这些符号 \(s_i\)，我们可能实现等号成立，即通过允许使用更短的编码词来减少 \(L(C)\)，而熵 \(H_r(S)\) 保持不变。
例 3.15
设信源 \(S\) 有三个符号 \(s_i\)，其概率分别为 \(p_i = \frac{1}{2}, \frac{1}{2}, 0\)。则：\(H_2(S) = 1\)，但 \(S\) 的二进制哈夫曼编码 \(C\) 的字长为 1, 2, 2，其平均字长为：\(L(C) = 1.5\)。然而，如果去掉概率为 0 的符号 \(s_3\)，则 \(H_2(S) = 1\)，此时可以使用编码 \(C = \{0, 1\}\)，其平均字长为：\(L(C) = 1\)，从而 \(H_2(S) = 1 = L(C)\)。在这里可以实现等号，是因为剩余的非零概率 \(p_i\) 均为 \(r = 2\) 的幂次。
如果 \(C\) 是信源 \(S\) 的一个 \(r\) 进制码，我们定义其效率为：
\[ \eta = \frac{H_r(S)}{L(C)} \tag{3.4} \]
根据定理 3.11，对于每个唯一可解码的编码 \(C\)，有 \(0 \leq \eta \leq 1\)。编码 \(C\) 的冗余定义为：\(\bar{\eta} = 1 - \eta\)。因此，冗余的增加会降低效率。在示例 3.13 和 3.14 中，效率分别为 \(\eta = 1\) 和 \(\eta \approx 0.977\)。
3.4 Shannon-Fano Coding
Huffman 码是最优的，但计算其平均字长可能较为繁琐。Shannon-Fano 码接近最佳，且其平均字长的估计更为简单。
首先，假设我们的信源 \(S\) 的所有概率 \(p_i \neq 0\)。根据推论3.12，如果一个唯一可解码的 \(r\) 进制码 \(C\) 对于信源 \(S\) 的平均字长 \(L(C)\) 要达到下界 \(H_r(S)\)，则其字长必须满足以下条件：
\[ l_i = \log_r(1/p_i), \quad \forall i \]
然而，这通常是不可能的，因为 \(\log_r(1/p_i)\) 的值通常不是整数。在这种情况下，我们采取次优的解决方法，即：
\[ l_i = \lceil \log_r(1/p_i) \rceil, \quad \forall i \]
其中，\(\lceil x_1 \rceil = \min \{ n \in \mathbb{Z} \mid n \geq x \}\) 表示大于等于 \(x\) 的最小整数。因此，\(l_i\) 是唯一满足以下条件的整数：
\[ \log_r\frac{1}{p_i} \leq l_i < \log_r\frac{1}{p_i} + 1 \tag{3.6} \]
于是，对于每个 \(i\)，有 \(p_i \ge r^{-l_i}\)。将此关系对所有 \(i\) 求和，我们得到：
\[ K = \sum_{i=1}^q r^{-l_i} \leq \sum_{i=1}^q p_i = 1 \]
根据定理 1.20（Kraft不等式），存在一个具有这些字长 \(l_i\) 的瞬时 \(r\) 进制码 \(C\)。我们将这样的码 \(C\) 称为信源 \(S\) 的 Shannon-Fano 码。需要注意的是，我们并未描述如何构造这类码，只是证明了它们的存在性。
如果我们将公式 (3.6) 乘以 \(p_i\)，然后对所有 \(i\) 求和，得到：
\[ \sum_{i=1}^q p_i \log_r \frac{1}{p_i} \leq \sum_{i=1}^q p_i l_i < \sum_{i=1}^q p_i \left(1 + \log_r \frac{1}{p_i}\right) = 1 + \sum_{i=1}^q p_i \log_r \frac{1}{p_i} \]
这表明：
\[ H_r(S) \leq L(C) < H_r(S) + 1 \tag{3.7} \]
我们可以将这一论证推广到某些 \(p_i = 0\) 的情形，只需令 \(p_i \to 0\)（此处省略细节）。然而，取极限会影响这个不等式的”好用”，因此现在我们得到的是一个稍弱的结果：
\[ H_r(S) \leq L(C) \leq H_r(S) + 1 \tag{3.8} \]
因此，我们证明了定理 3.16：
定理 3.16
对于信源 \(S\) 的任意 \(r\) 元 Shannon-Fano 码 \(C\) ，均满足：
\[ H_r(S) \leq L(C) \leq H_r(S) + 1 \]
推论 3.17
对于信源 \(S\) 的任意最优 \(r\) 进制码 \(D\) ，均满足：
\[ H_r(S) \leq L(D) < H_r(S) + 1 \]
这意味着即使无法达到下界 \(H_r(S)\)，我们仍能找到与之足够接近的编码。
例 3.18
设信源 \(S\) 有 5 个符号，其概率分布为 \(p_i = 0.3, 0.2, 0.2, 0.2, 0.1\)（如例 2.5），因此 \(1/p_i = 10/3, 5, 5, 5, 10\)。此时 \(S\) 的二元 Shannon-Fano 码 \(C\) 的码长为
\[ l_i = \lceil \log_2 (1/p_i) \rceil = \min \{ n \in \mathbb{Z} \mid 2^n \geq 1/p_i \} = 2, 3, 3, 3, 4 \]
其平均码长 \(L(C) = \sum p_i l_i = 2.8\)。作为对比，\(S\) 的 Huffman 码 \(D\) 的平均码长 \(L(D) = 2.3\)（见 §2.2）。由例 3.3 可知 \(H_2(S) \approx 2.246\)，因此 \(C\) 满足定理 3.16。\(C\) 的效率 \(\eta \approx 2.246/2.8 \approx 0.802\)，而 \(D\) 的效率 \(\eta \approx 2.246/2.3 \approx 0.977\)。
例 3.19
若 \(p_1 = 1\) 且对所有 \(i > 1\) 有 \(p_i = 0\)，则 \(H_r(S) = 0\)。此时 \(S\) 的 \(r\) 元最优码 \(D\) 的平均码长 \(L(D) = 1\)，上界 \(1 + H_r(S)\) 恰好达到。
Shannon-Fano 码通常接近最优。若用于信源的扩展编码（见 §2.6），其性能将更接近最优。我们将在下一节研究信源扩展的熵，以便为 §3.6 中的证明做准备。
3.5 Entropy of Extensions and Products
回忆第 2.6 节的内容，源 \(S^n\) 有 \(q^n\) 个符号 \(s_{i_1}s_{i_2}\cdots s_{i_n}\)，其对应的概率为 \(p_{i_1}p_{i_2}\cdots p_{i_n}\)。如果我们将 \(S^n\) 看作 \(n\) 个相互独立的 \(S\) 的副本，那么我们应该期望它产生的信息量是单个 \(S\) 的 \(n\) 倍。这启发我们得到如下定理：
定理 3.20
对于任意信息源 \(S\)：
\[ H_r(S^n)=nH_r(S) \]
在证明这个定理之前，我们需要先推广扩展（extension）的概念，引入信息源乘积（product of sources）。设 \(S\) 和 \(T\) 是两个信息源：\(S\) 的符号为 \(s_i\)，对应概率为 \(p_i\)；\(T\) 的符号为 \(t_j\)，对应概率为 \(q_j\)。
我们定义它们的乘积：
\[ S \times T \]
为一个新的信息源。该信息源的符号由符号对组成：
\[ (s_i,t_j) \]
为了简化记号，我们将其写作：
\[ s_it_j \]
其概率为：
\[ P(s_i,t_j) \]
也就是说，\(S \times T\) 可以看作两个信息源同时产生符号：\(S\) 输出符号 \(s_i\)，\(T\) 输出符号 \(t_j\)。然后将二者组合成一个新的符号。
如果对于所有 \(i,j\)：
\[ P(s_i,t_j)=p_iq_j \]
则称 \(S\) 和 \(T\) 是独立的（independent）。
例如：两个相距很远的城市的每日天气可以看作两个独立的信息源。但是，如果两个城市距离很近，它们的天气可能相互影响，因此不再独立.
引理 3.21
如果 \(S\) 和 \(T\) 是独立的信息源，则：
\[ H_r(S \times T)=H_r(S)+H_r(T) \]
证明
由于 \(S\) 和 \(T\) 独立：\(P(s_it_j)=p_iq_j\)。
因此：
\[ \begin{aligned} H_r(S\times T) &=-\sum_i\sum_j p_iq_j\log_r(p_iq_j)\\ &=-\sum_i\sum_j p_iq_j(\log_r p_i+\log_r q_j)\\ &=-\sum_i\sum_j p_iq_j\log_r p_i -\sum_i\sum_j p_iq_j\log_r q_j\\ &=\left(-\sum_i p_i\log_r p_i\right) \left(\sum_j q_j\right) +\left(\sum_i p_i\right) \left(-\sum_j q_j\log_r q_j\right)\\ &=\left(-\sum_i p_i\log_r p_i\right) +\left(-\sum_j q_j\log_r q_j\right)\\ &=H_r(S)+H_r(T) \end{aligned} \]
证毕。\(\square\)
我们可以利用数学归纳法（induction），将信息源乘积的定义推广到任意有限个信息源。
定义：
\[ S_1\times\cdots\times S_n = (S_1\times\cdots\times S_{n-1})\times S_n \]
也就是说，多个信息源的乘积可以递归地定义为：
- 先计算前 \(n-1\) 个信息源的乘积；
- 再将结果与第 \(n\) 个信息源进行乘积。
由此，我们不难得到：
推论 3.22
如果：
\[ S_1,S_2,\cdots,S_n \]
是相互独立的信息源，则：
\[ H_r(S_1\times\cdots\times S_n) = H_r(S_1)+\cdots+H_r(S_n) \]
回到本节 §3.5 开篇提出的定理 3.20，它可以被推论 3.22 直接证明。
3.6 Shannon’s First Theorem
定理 3.11 指出，对于信息源 \(S\) 的任意唯一可译（uniquely decodable）的 \(r\) 元码 \(C\)，其平均码长满足：
\[ L(C)\geq H_r(S) \]
而推论 3.12 表明，这个下界通常无法达到。
然而，我们将证明，在第 2.6 节末尾提出的思想——使用 \(S^n\) 的最优码（optimal code）作为 \(S\) 的编码方式，可以使我们对 \(S\) 进行编码，并且当 \(n\rightarrow\infty\) 时，时，平均码长无限接近 \(H_r(S)\)。
回忆一下，如果 \(S^n\) 的某个码具有平均码长 \(L_n\)，那么当它作为 \(S\) 的编码方式时，其平均码长为 \(\frac{L_n}{n}\)。
根据推论 3.17，\(S^n\) 的最优 \(r\) 元码具有平均码长 \(L_n\)，满足：
\[ H_r(S^n)\leq L_n\leq 1+H_r(S^n) \]
由定理 3.20：
\[ H_r(S^n)=nH_r(S) \]
因此：
\[ nH_r(S)\leq L_n\leq 1+nH_r(S) \]
两边同时除以 \(n\)：
\[ H_r(S)\leq \frac{L_n}{n} \leq \frac{1}{n}+H_r(S) \]
因此：
\[ \lim_{n\rightarrow\infty}\frac{L_n}{n} = H_r(S) \]
这证明了 Shannon 第一理论（Shannon’s First Theorem），也称为无噪声编码定理（Noiseless Coding Theorem）。
定理 3.23（Shannon 第一理论）
通过对 \(S^n\) 进行编码，当 \(n\) 足够大时，可以找到信息源 \(S\) 的唯一可译 \(r\) 元编码，使其平均码长能够任意接近熵 \(H_r(S)\)。
使用这个定理的代价在于，许多时候：
\[ \frac{L_n}{n}\rightarrow H_r(S) \]
的收敛速度相当缓慢，因此为了实现高效编码，我们可能需要取一个非常大的 \(n\)。
假设信息源 \(S\) 有 \(q\) 个符号，则 \(S^n\) 拥有：\(q^n\) 个符号。随着 \(n\) 增大：\(q^n\) 会快速增长。这意味着：构造对应的编码会变得复杂；编码过程会变得耗时。此外，解码过程也会产生延迟，因为我们必须等待完整的长度为 \(n\) 的符号块被接收之后，才能进行解码。
因此，在实际应用中，我们可能需要在效率和复杂度之间权衡，选择一个较小的 \(n\)。
3.7 An Example of Shannon’s First Theorem
设信息源 \(S\) 有两个符号 \(s_1,s_2\)，其概率分别为：\(p_1=\frac23\)、\(p_2=\frac13\)，如例 3.2 所示。我们在第 3.1 节中看到 \(H_2(S)=\log_2 3-\frac23\approx 0.918\)，并且在第 2.6 节中，通过对 \(S^n\) 使用二元 Huffman 编码，当 \(n=1,2,3\) 时，我们得到平均码长 \(\frac{L_n}{n}\approx 1,\ 0.944,\ 0.938\)
对于更大的 \(n\)，使用 Shannon-Fano 编码比 Huffman 编码更加简单。
虽然 Shannon-Fano 编码效率略低，但是更容易处理，且同样满足：当 \(n\rightarrow\infty\) 时，
\[ \frac{L_n}{n}\rightarrow H_r(S) \]
对于 \(S^n\)，共有 \(2^n\) 个符号。每个符号都是长度为 \(n\) 的符号块：
\[ s=s_1s_2\cdots s_n \]
其中每个位置上的符号为 \(s_1\) 或 \(s_2\)。
假设某个符号块 \(s\) 中包含 \(k\) 个符号 \(s_1\)，则剩余 \(n-k\) 个符号为 \(s_2\)。因此：
\[ \Pr(s) = \left(\frac23\right)^k \left(\frac13\right)^{n-k} = \frac{2^k}{3^n} \]
对于每个 \(k=0,1,\cdots,n\)，满足条件的符号 \(s\) 的数量为 \(\binom nk\)。
因为这表示从 \(n\) 个位置中选择 \(k\) 个位置放置 \(s_1\)。
根据第 3.4 节的 Shannon-Fano 编码方法，我们给每个这样的符号 \(s\) 分配码字长度：
\[ l_k = \left\lceil \log_2\frac1{\Pr(s)} \right\rceil = \left\lceil \log_2\frac{3^n}{2^k} \right\rceil = \left\lceil n\log_2 3-k \right\rceil \]
令 \(a_n=\lceil n\log_2 3\rceil\)，则：
\[ l_k=a_n-k \]
编码 \(S^n\) 时的平均码长为：
\[ L_n = \sum_{k=0}^{n} \binom nk \Pr(s)l_k \]
代入 \(l_k\) 和 \(\Pr(s)\)：
\[ L_n = \sum_{k=0}^{n} \binom nk \frac{2^k}{3^n} (a_n-k) \]
整理：
\[ L_n = \frac1{3^n} \left( a_n\sum_{k=0}^{n} \binom nk2^k - \sum_{k=0}^{n} k\binom nk2^k \right) \tag{3.9} \]
根据二项式定理：
\[ (1+x)^n = \sum_{k=0}^{n} \binom nkx^k \tag{3.10} \]
我们得到：
\[ \sum_{k=0}^{n} \binom nk2^k = 3^n \]
此外，对式 (3.10) 求导：
\[ n(1+x)^{n-1} = \sum_{k=1}^{n} k\binom nkx^{k-1} \]
两边乘以 \(x\)：
\[ nx(1+x)^{n-1} = \sum_{k=0}^{n} k\binom nkx^k \]
再次令 \(x=2\)，得到：
\[ \sum_{k=0}^{n} k\binom nk2^k = 2n3^{n-1} \]
代入式 (3.9)：
\[ \begin{aligned} L_n &= \frac1{3^n} (a_n3^n-2n3^{n-1}) \\ &= a_n-\frac{2n}{3} \end{aligned} \]
所以：
\[ \begin{aligned} \frac{L_n}{n} &= \frac{a_n}{n}-\frac23 \\ &= \frac{\lceil n\log_23\rceil}{n} -\frac23 \end{aligned} \]
由于：
\[ n\log_23 \leq \lceil n\log_23\rceil < 1+n\log_23 \]
两边除以 \(n\)：
\[ \log_23 \leq \frac{\lceil n\log_23\rceil}{n} < \frac1n+\log_23 \]
因此，当 \(n\rightarrow\infty\) 时：
\[ \frac{\lceil n\log_23\rceil}{n} \rightarrow \log_23 \]
于是：
\[ \frac{L_n}{n} \rightarrow \log_23-\frac23 \approx0.918 \]
因此，我们验证了 Shannon 第一理论对于该信息源成立。
对于 \(n=1,\dots,10\)，平均码长 \(L=\frac{L_n}{n}\) 以及编码效率 \(\eta=\frac{H}{L}\) 如下表：
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| \(a_n\) | 2 | 4 | 5 | 7 | 8 | 10 | 12 | 13 | 15 | 16 |
| \(L\) | 1.333 | 1.333 | 1 | 1.083 | 0.933 | 1 | 1.048 | 0.958 | 1 | 0.933 |
| \(\eta\) | 0.689 | 0.689 | 0.918 | 0.848 | 0.984 | 0.918 | 0.876 | 0.959 | 0.918 | 0.984 |
这说明 \(\eta\rightarrow1\)，也就是说：当 \(n\rightarrow\infty\) 时，\(L\rightarrow H\)。不过，该收敛过程相当缓慢且不规则。
如果不使用 Shannon-Fano 编码，而对 \(S^n\) 使用 Huffman 编码，则得到（\(n\le5\)）：
| \(n\) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| \(L\) | 1 | 0.944 | 0.938 | 0.938 | 0.923 |
| \(\eta\) | 0.918 | 0.972 | 0.979 | 0.979 | 0.995 |
可以看到，在这种情况下 \(\eta\rightarrow1\) 更快。
不过，对于某些 \(n\)，例如 \(n=5\)，Shannon-Fano 编码的效率几乎与 Huffman 编码相同。原因是 \(3^5=243\approx256=2^8\)，因此，\(S^5\) 中符号概率的倒数 \(\frac1{\Pr(s)} = \frac{3^n}{2^k}\) 接近某个 \(2\) 的整数次幂略小于 \(2\) 的幂。所以使用向上取整函数 \(\lceil\log_2\frac1{\Pr(s)}\rceil\) 时产生的影响很小。