信息论

概念

信息论研究三个问题：

问题	定理	结论的形状
信息怎么度量	——	用"不确定性减少多少"来度量，单位是比特
能压缩到什么程度	香农第一定理（信源编码定理）	无损压缩的平均码长有下限，下限就是熵
能传多快、多可靠	香农第二定理（信道编码定理）	传输速率有上限，上限就是信道容量

这门学科最反直觉的一点是：信息的度量与"内容的意思"无关。 一条消息的信息量只取决于它出现的概率——越是不可能出现的消息，一旦出现，携带的信息越多。"明天太阳升起"信息量近乎零；"明天日全食"信息量极大。

它的地位很特殊：信息论给出的是极限，不是算法。定理说"存在一种编码能达到这个极限"，但不说这种编码长什么样。工程上的压缩与纠错码，都是在逼近这些极限。

与本站主线的关系是本门最紧的一处。 408 的计算机网络在物理层直接给出奈奎斯特定理与香农定理两条公式，并规定"实际数据率取两者较小值"。本章做的正是把那两条公式的来源讲清楚——它为什么长这样、信噪比为什么要取对数、以及"极限"到底卡在哪里。

原理

一、自信息与熵

一个概率为 $p$ 的事件，其自信息定义为

$$I=-{\log }_{2}p$$

单位是比特（bit）。这个定义有三个直接推论：

• 必然事件的 $p=1$，自信息为 $0$——不带来任何新信息。
• 概率越小，自信息越大——越意外越值钱。
• 以 2 为底，是因为一个"等概率二选一"的问题恰需要 1 比特来回答。

一个随机变量 $X$ 的熵是它所有取值的自信息的期望：

$$H(X)=-\sum _i{p}_i{\log }_2{p}_i$$

它衡量的是这个变量平均每次取值带来的信息量，也就是"描述它平均需要多少比特"。

熵的三条基本性质：

• 非负：$H(X)\ge 0$，当且仅当结果完全确定时为 $0$。
• 等概率时最大：取值个数为 $n$ 时，最大熵是 ${\log }_{2}n$。
• 分布越平，熵越大；越尖，熵越小。极端地，$p=0.99$ 的硬币熵只有 $0.0808$ 比特——几乎不用猜也知道结果。

一句话：熵是"猜中的难度"，也是"至少要说多少比特"的下界。

二、联合熵、条件熵与互信息

两个变量放在一起，就有三组量：

名称	记号	含义
联合熵	$H(X,Y)$	同时描述 $X$ 与 $Y$ 需要多少比特
条件熵	$H(X\mid Y)$	已知 $Y$ 后，$X$ 还剩多少不确定
互信息	$I(X;Y)$	知道 $Y$ 能消除 $X$ 的多少不确定

三者由一条恒等式串起来：

$$I(X;Y)=H(X)+H(Y)-H(X,Y)=H(X)-H(X\mid Y)$$

互信息是对称的：$I(X;Y)=I(Y;X)$，知道 $Y$ 有助于猜 $X$，反过来也一样。互信息为零意味着两个变量统计独立——这就是"没有关系"的严格定义。

三、信源编码：无损压缩的下限

香农第一定理（信源编码定理）说：对熵为 $H(X)$ 的信源做无损编码，平均码长 $L$ 必定满足

$$H(X)\le L<H(X)+1$$

也就是说：熵是压缩的硬下限，任何无损压缩都不可能低于它；而最优的整数码长编码能保证不超过熵加 1 比特。

为什么不可能更低？直觉版本：若某种编码能把 $N$ 个符号压到平均 0.5 比特，那它一共只用了 $2^{0.5N}$ 种码字；但信源能产生的情形有约 $2^{NH}$ 种。只要 $0.5<H$，码字就不够用——必然有两个不同的消息被编成同一串，无损还原就不可能。（严格版本靠渐近均分性：长序列中只有约 $2^{NH}$ 个"典型序列"会真正出现，其余概率可忽略，于是只需给典型序列编等长码即可。）

工程上最常用的逼近手段是霍夫曼编码：每次取出概率最小的两个结点合并，自底向上建树，高概率符号得到短码，低概率符号得到长码。

四、信道编码：可靠传输的上限

现实信道会出错。最简单的模型是二元对称信道（BSC）：每个比特以概率 $p$ 翻转。

它的容量有闭式解：

$$C=1-H(p)$$

三个点值得注意：$p=0$ 时 $C=1$（无噪声，每符号传 1 比特）；$p=0.5$ 时 $C=0$（完全随机，接收到的与发送的无关，一个比特都传不了）；$p=0.1$ 时 $C=0.5310$ 比特每符号。

连续信道的最著名结果是香农-哈特利公式：

$$C=W{\log }_2(1+\frac{S}{N})$$

$W$ 是带宽（Hz），$S/N$ 是信噪比（功率之比）。三条工程含义：

• 带宽加倍，容量加倍（线性）。
• 信噪比加倍，容量只多一点（对数）——把功率堆上去的收益递减得很厉害。
• 信噪比用分贝表示时要先换回比值：$S/N={10}^{\text{dB}/10}$。

香农第二定理（信道编码定理）说：只要传输速率 $R$ 小于容量 $C$，就存在一种编码使错误率任意小；而 $R>C$ 时错误率必然有正的下界。这是一个存在性定理——它保证"能做到"，但不告诉你"怎么做"。从此之后，通信工程的任务从"能不能可靠传输"变成了"怎样逼近容量"。

五、与计算机网络的接口

物理层：奈奎斯特、香农、编码、传输介质一章给出两条公式，本章正好缺它不可：

对比项	奈奎斯特定理	香农定理
前提	理想无噪声	有噪声
变量	带宽、码元种类数	带宽、信噪比
给出	无码间串扰的码元速率上限	信息速率上限
角色	编码方案能达到的上限	物理上不可能超过的天花板

联合使用的固定答法：实际数据率取两者中的较小值。原因是香农给的是"物理不可能超过"，奈氏给的是"给定编码方案能达到"，通道的瓶颈总是二者中更紧的那一个。

还有一处极易混：奈奎斯特定理与奈奎斯特采样定理不是同一个东西。前者讲"带宽能支持多快的码元速率"，后者讲"采样频率要不低于信号最高频率的 2 倍才不丢信息"。两条都姓奈奎斯特，考场上常被并排放在一起——数字信号处理讲的是后者。

示例

import math
import heapq

# 例 1：熵 —— 不确定性就是所需的比特数
def H(ps):
    return -sum(p * math.log2(p) for p in ps if p > 0)

print(f"公平硬币 {H([.5, .5]):.4f} bit")
print(f"均匀 4 面 {H([.25] * 4):.4f} bit")
print(f"均匀 256 面 {H([1 / 256] * 256):.4f} bit")
print(f"偏硬币 p=0.9 {H([.9, .1]):.4f} bit")
print(f"天气(晴 .5 / 阴 .25 / 雨 .25) {H([.5, .25, .25]):.4f} bit")

# 例 2：霍夫曼编码 —— 平均码长逼近熵
def huffman(probs):
    heap = [(p, [i]) for i, p in enumerate(probs)]
    heapq.heapify(heap)
    lens = [0] * len(probs)
    while len(heap) > 1:
        p1, s1 = heapq.heappop(heap)
        p2, s2 = heapq.heappop(heap)
        for i in s1 + s2:
            lens[i] += 1
        heapq.heappush(heap, (p1 + p2, s1 + s2))
    return lens

P = [0.4, 0.2, 0.2, 0.1, 0.1]
L = huffman(P)
avg = sum(p * l for p, l in zip(P, L))
print(f"码长 {L} 平均 {avg:.4f} bit 熵 {H(P):.4f} bit 效率 {H(P) / avg:.4f}")
print(f"定长编码需 {math.ceil(math.log2(len(P)))} bit，上界 H+1 = {H(P) + 1:.4f}")

# 例 3：BSC 容量与香农公式
for p in (0.01, 0.1, 0.5):
    print(f"BSC p={p:.2f} -> C = {1 - H([p, 1 - p]):.4f} bit/符号")
W, snr = 3000, 1000
print(f"W={W} Hz  S/N={snr} (30 dB) -> C = {W * math.log2(1 + snr):.2f} bps")

# 例 4：互信息
J = {(0, 0): .4, (0, 1): .1, (1, 0): .1, (1, 1): .4}
px = [sum(v for (a, _), v in J.items() if a == x) for x in (0, 1)]
py = [sum(v for (_, b), v in J.items() if b == y) for y in (0, 1)]
hxy = -sum(v * math.log2(v) for v in J.values())
print(f"H(X)={H(px):.4f} H(Y)={H(py):.4f} H(X,Y)={hxy:.4f} I(X;Y)={H(px) + H(py) - hxy:.4f} bit")

公平硬币 1.0000 bit
均匀 4 面 2.0000 bit
均匀 256 面 8.0000 bit
偏硬币 p=0.9 0.4690 bit
天气(晴 .5 / 阴 .25 / 雨 .25) 1.5000 bit
码长 [2, 2, 2, 3, 3] 平均 2.2000 bit 熵 2.1219 bit 效率 0.9645
定长编码需 3 bit，上界 H+1 = 3.1219
BSC p=0.01 -> C = 0.9192 bit/符号
BSC p=0.10 -> C = 0.5310 bit/符号
BSC p=0.50 -> C = 0.0000 bit/符号
W=3000 Hz  S/N=1000 (30 dB) -> C = 29901.68 bps
H(X)=1.0000 H(Y)=1.0000 H(X,Y)=1.7219 I(X;Y)=0.2781 bit

例 1 给出熵的直觉刻度。 公平硬币 1.0000 比特——正好是一个是非题的答案量；均匀 4 面 2.0000；均匀 256 面恰好 8.0000 比特，也就是一个字节——这解释了为什么一个字节能表示 256 种取值。偏硬币 $p=0.9$ 只有 0.4690 比特，不到公平硬币的一半：绝大部分时候结果都能猜到，所以每次取值的"新消息量"少了很多。天气那个例子 1.5000 比特落在 1 与 2 之间，符合"三种取值、但不等概率"的位置。

例 2 是压缩的实际账。 五个符号的概率是 $0.4,0.2,0.2,0.1,0.1$，霍夫曼给出码长 $[2,2,2,3,3]$，平均码长 2.2000 比特；而熵是 2.1219 比特。两件事同时成立：平均码长没有低于熵（$2.2000>2.1219$），也没有越过熵加 1（$2.2000<3.1219$）——与香农第一定理的夹逼完全吻合，效率 96.45%。作为对照，定长编码需要 3 比特，比霍夫曼多出 0.8 比特每符号。变量长编码换来的是可观的压缩。

例 3 是容量的两个刻度。 BSC 上：$p=0.01$ 时容量 0.9192（几乎无损）；$p=0.1$ 时降到 0.5310；$p=0.5$ 时容量恰好为 0——接收端完全无法区分发送的是 0 还是 1，信道彻底作废。香农公式那一行 $W=3000$ Hz、$S/N=1000$（即 30 dB）给出 29901.68 bps，与物理层一章的算例逐位一致——同一个公式、同一组参数，两条课程线索在这里合上。

例 4 是互信息。 联合分布 $\{0.4,0.1,0.1,0.4\}$ 看起来对称，两个边缘分布都是均匀的（$H(X)=H(Y)=1.0000$），但联合熵只有 1.7219 比特，于是互信息 $I(X;Y)=0.2781$ 比特——知道 $Y$ 能替我们省掉约 0.28 比特的不确定性。这也说明"边缘分布相同"完全不能推出"独立"：若二者独立，联合熵应当是 $1+1=2$ 比特。

要点

要点与常见误区

1. 信息量取决于概率，不取决于内容。 "这句话有多重要"与"这句话有多意外"是两回事，信息论只度量后者。
2. 熵是下界，不是平均值。任何无损压缩的平均码长都不可能低于熵；宣称"压到熵以下还无损"的方案，一定在某个环节偷换了条件。
3. 信噪比加一倍，容量只多一点。香农公式里 $S/N$ 在真数位置、外面套了对数，堆功率的收益急剧递减；要明显提速，加带宽比加功率更划算。
4. 分贝要先换回比值。$30$ dB 对应 $S/N=1000$，不是 $30$。这是计算题里最常见的失分点。
5. 香农第二定理是存在性定理。它说"存在这样的编码"，但不给出构造方法；"逼近容量"是随后几十年的编码工程任务。
6. 两个奈奎斯特不要混。奈奎斯特定理管"码元速率上限"（信道容量侧），奈奎斯特采样定理管"采样频率下限"（信号采集侧）。
7. 奈氏与香农要一起用。实际数据率取两者较小值，瓶颈在更紧的那一条。
8. $p=0.5$ 的二元对称信道容量为零。"完全随机"不是"有一半信息"，而是"一点信息都没有"。
9. 条件熵与互信息不要搞反。$H(X\mid Y)$ 是"知道 $Y$ 后还剩多少不确定"，$I(X;Y)$ 是"省掉多少不确定"，两者互补，和恰好是 $H(X)$。

小结

• 信息 = 不确定性的消除，度量单位是比特；自信息 $-{\log }_{2}p$ 越意外越大。
• 熵是平均信息量，也是无损压缩的硬下限；等概率时取最大值 ${\log }_{2}n$。
• 互信息 $I(X;Y)=H(X)+H(Y)-H(X,Y)$ 是对称的，为零即统计独立。
• 信源编码：$H(X)\le L<H(X)+1$；霍夫曼编码是最常用的逼近手段。
• 信道编码：BSC 的容量是 $1-H(p)$；连续信道是 $C=W{\log }_2(1+S/N)$；速率低于容量就能可靠传输。
• 验算锚点：公平硬币 1.0000 比特、偏硬币 $p=0.9$ 0.4690 比特、均匀 256 面 8.0000 比特；霍夫曼平均码长 2.2000 比特对熵 2.1219 比特（效率 96.45%，定长需 3 比特）；BSC $p=0.01/0.1/0.5$ → 容量 0.9192 / 0.5310 / 0；香农公式 $W=3000$ Hz、$S/N=1000$ → 29901.68 bps；互信息 0.2781 比特。
• 主线呼应：本章与 408 的物理层共用同一组公式，与差错控制共用同一个目标——在噪声中把比特可靠地送过去；数字信号处理的采样定理是"另一个奈奎斯特"；信息论也是压缩与加密的共同底座，见数字音频与密码学。

下一篇：科学方法论 —— 有了信息的度量，还得回答"怎样才算证明了"。