信道容量：噪声中能传多少信息

一条线路每次发送一个比特，却有 10% 的概率把它翻转。直接发送时，接收者平均每十个比特会读错一个；把每个比特重复三次，错误会减少，但发送同一份消息要占用三倍的线路。信道容量回答的是：允许设计编码方式时，每次使用这条线路，最多能以任意小的错误概率传多少信息？

信息论与熵给出了条件熵、互信息与压缩的基础。这里把它们用于通信：压缩考察如何减少表示信源所需的比特，信道编码则安排冗余，使消息能从噪声中恢复。所有对数都以 2 为底，离散信道的容量单位是“比特/次使用”。

用条件分布描述信道

MacKay 的《Information Theory, Inference, and Learning Algorithms》在第 9 章的 Noisy channels 一节中，用输入字母表、输出字母表和条件概率定义离散无记忆信道。设发送符号是 $X$，接收符号是 $Y$，信道规律为

$$W(y\mid x)=P(Y=y\mid X=x),\qquad \sum_y W(y\mid x)=1.$$

每个输入 $x$ 对应一组输出概率。发送者选择输入分布 $P_X$ 后，联合分布和输出分布才随之确定：

$$P_{X,Y}(x,y)=P_X(x)W(y\mid x),\qquad P_Y(y)=\sum_x P_X(x)W(y\mid x).$$

下面先限定为有限字母表、规律不随时间变化、没有反馈的无记忆信道。无记忆意味着给定整段输入，各次输出条件独立：

$$P(y_1,\ldots,y_n\mid x_1,\ldots,x_n) =\prod_{i=1}^n W(y_i\mid x_i).$$

编码后的输入符号可以相互关联；“无记忆”约束的是信道的噪声机制。突发噪声或随时间变化的信道，需要不同的模型。

对输入分布最大化互信息

对于给定的 $P_X$，互信息衡量一次输出平均带来了多少输入信息。MacKay 第 9 章的 Maximizing the mutual information 一节定义容量为

$$C=\max_{P_X} I(X;Y) =\max_{P_X}\bigl[H(Y)-H(Y\mid X)\bigr].$$

最大化时固定 $W$，调整的是输入符号的使用比例，不是噪声概率。只发送同一个符号，即使接收者能认出它，也没有消息选择可供区分，互信息为零。对称信道往往由均匀输入达到容量，但不能把这个结论套到所有信道上。

二元对称信道：推导并计算容量

二元对称信道（BSC）以概率 $p$ 翻转每个输入比特，以概率 $1-p$ 原样传递；不同次使用的翻转独立。这是 MacKay 第 9 章列出的模型。下表把输入放在行、输出放在列：

输入	$Y=0$	$Y=1$
$X=0$	$1-p$	$p$
$X=1$	$p$	$1-p$

定义二元熵

$$H_2(t)=-t\log_2 t-(1-t)\log_2(1-t),\qquad 0\log_2 0:=0.$$

设 $q=P(X=1)$。无论输入是 0 还是 1，输出都面对同样的翻转概率，因此 $H(Y\mid X)=H_2(p)$。而

$$P(Y=1)=p(1-q)+(1-p)q=p+(1-2p)q,$$

所以

$$I(X;Y)=H_2\bigl(p+(1-2p)q\bigr)-H_2(p).$$

二元输出的熵至多为 1。取 $q=1/2$，输出也均匀，恰好达到这个上界，得到

$$C_{\mathrm{BSC}}=1-H_2(p).$$

取开头的 $p=0.1$，逐项计算：

$$\begin{aligned} H_2(0.1)&=-0.1\log_2 0.1-0.9\log_2 0.9 \approx 0.468996,\\ C_{\mathrm{BSC}}&\approx 0.531004\ \text{bits/use}. \end{aligned}$$

容量不是“正确收到的比例” $0.9$。输出不会告诉接收者哪些比特被翻转了，编码必须提供足够的结构来消除这种歧义。公式对已知的 $0\le p\le1$ 都成立：$p=0$ 时容量为 1；$p=1/2$ 时输出与输入独立，容量为 0；$p=1$ 时每次都翻转，接收者反转即可恢复，容量又为 1。

二元擦除信道：缺失的位置是已知的

MacKay 第 9 章还给出二元擦除信道（BEC）：输出以概率 $1-\varepsilon$ 等于输入，以概率 $\varepsilon$ 变成专用符号 ?；擦除概率与输入值无关，各次使用独立。这里没有把 0 误报成 1 的情况。

仍设 $q=P(X=1)$。收到 0 或 1 时，输入已完全确定；收到 ? 时，输入仍服从原分布。因此

$$H(X\mid Y)=\varepsilon H_2(q),\qquad I(X;Y)=(1-\varepsilon)H_2(q).$$

均匀输入使 $H_2(q)=1$，所以

$$C_{\mathrm{BEC}}=1-\varepsilon.$$

取 $\varepsilon=0.1$，容量为 $0.9$ 比特/次使用。同为 10% 的受损概率，擦除信道比翻转信道的 $0.531004$ 更容易恢复信息：接收者知道缺了哪些位置，其余比特完全可信；翻转信道还要判断哪里出了错。这个比较依赖两种模型各自给接收者的信息，不能只看“10%”就把它们视为同一条信道。

噪声信道编码定理的保证

Shannon 1948 年论文的第 13–14 节建立了噪声信道编码定理及其长消息表述。针对上面的有限离散无记忆模型，MacKay 第 9–10 章给出以下形式。

编码器把 $M$ 种消息映射到长度为 $n$ 的输入码字，解码器从输出估计消息。码率是

$$R_n=\frac{\log_2 M}{n}\ \text{bits/use}.$$

若有 $k$ 个消息比特，则 $M=2^k$，码率为 $k/n$。块错误指整条消息没有被正确恢复，与某一个传输符号是否出错不同。

对任意固定的目标速率 $0<R<C$ 和任意容许块错误概率 $\delta>0$，只要块长足够大，就存在码率至少为 $R$ 的块码及解码器，使最坏消息的块错误概率小于 $\delta$。所以可以让块错误概率趋于零，同时维持正的、低于容量的速率。反过来，固定速率高于 $C$ 时，无法让块错误概率趋于零。

这是编码方案的存在性结论。它没有说任意码都有效，也没有指定要多长的块、怎样高效解码，或保证某个有限块绝不出错。上面的可达性表述要求严格的 $R<C$，不能据此断言恰好在 $R=C$ 时也有相同保证。对 $p=0.1$ 的 BSC，目标速率 $R=0.5$ 低于 $0.531004$，因此满足可达条件；$R=0.6$ 则超过容量。

重复码：算出剩余误差和代价

MacKay 第 1 章从三次重复码开始：把 0 编成 000，把 1 编成 111，接收端按多数表决。比如发送 000，收到 010 仍解码为 0；收到 011 就误判为 1。

每个码字只携带一个消息比特，却使用三次信道，码率为 $R=1/3$。对独立翻转概率 $p=0.1$，至少两个比特翻转才会出错：

$$\begin{aligned} P_{\mathrm{err}}&=\binom32 p^2(1-p)+p^3\\ &=3(0.1)^2(0.9)+(0.1)^3\\ &=0.027+0.001=0.028. \end{aligned}$$

这里一个消息块就是一个消息比特，所以解码后的比特错误概率与块错误概率相同。错误从 10% 降到 2.8%，代价是速率降到约 $0.333333$ 比特/次使用。

对奇数 $n$ 的重复码，使用二项分布计算多数翻转的概率：

$$R=\frac1n,\qquad P_{\mathrm{err}}=\sum_{j=(n+1)/2}^{n}\binom nj p^j(1-p)^{n-j}.$$

重复次数 $n$	码率（比特/次使用）	解码错误概率，$p=0.1$
1（直接发送）	1.000000	0.10000000
3	0.333333	0.02800000
5	0.200000	0.00856000
9	0.111111	0.00089092

当 $0<p<1/2$、重复次数趋于无穷时，多数表决的错误概率趋于零，但码率 $1/n$ 也趋于零，远离固定的正容量。容量附近的编码需要随着块长增长携带越来越多的消息比特。

把固定的三次重复码拼成更长的消息，也不能代替定理中的长块码：若连续发送 $m$ 个独立编码的消息比特，整条消息至少有一处错误的概率是 $1-(1-0.028)^m$，随 $m$ 增长趋于 1。取 $m=100$，这个概率为 $1-0.972^{100}\approx0.941571$，约 94.16%。重复码说明冗余可以纠错，但冗余怎样分配同样重要。

高斯信道：必须同时指定功率与单位

连续输入也可以用条件分布描述。MacKay 第 11 章的高斯信道模型为 $Y=X+Z$，其中 $Z\sim\mathcal N(0,\sigma^2)$ 独立于输入，各次使用的噪声独立同分布。在平均输入功率约束 $E[X^2]\le P$ 下，允许实数输入时，每次使用一个实数维度的容量为

$$C_{\mathrm{real}}=\frac12\log_2\left(1+\frac{P}{\sigma^2}\right) \ \text{bits/use}.$$

零均值、方差为 $P$ 的高斯输入达到互信息的最大值。这里必须保留功率约束：没有它，增大输入幅度就能无限增大容量。限制输入只能取两个电平时，也不能直接使用这个允许任意实数输入的结果。

Shannon 论文第 25 节的定理 17 则给出带限、加性白高斯噪声信道的形式：带宽为 $B$ Hz，平均信号功率不超过 $S$，该频带内的总噪声功率为 $N$，则

$$C_{\mathrm{band}}=B\log_2\left(1+\frac SN\right) \ \text{bits/s}.$$

这两个公式的单位不同：一个按实数维度计数，一个按秒计数。MacKay 第 11 章把理想带限模型写成每秒 $2B$ 个实数维度，按维度分配信号和噪声功率后，两式中的信噪比相同；乘上 $2B$ 就消去了前式的 $1/2$。取线性信噪比为 9，前者为 $\tfrac12\log_2 10\approx1.660964$ 比特/次使用；再取 $B=10^6$ Hz，后者为 $10^6\log_2 10\approx3321928.094887$ 比特/秒，即约 $3.321928$ Mbit/s。

容量给出模型下的渐近极限。若只能使用短块，还要单独确定给定码率和块长下的错误概率；若要求低延迟或受限算力，还要比较实际编码器、解码器的耗时和存储。Shannon 在第 14 节也指出，证明中逼近理想编码的方法通常并不实用。仅有容量公式，无法算出某个设备能实现的吞吐量。

用 Python 重算

下面的示例使用 math.comb，需要 Python 3.8 或更高版本。代码只用标准库，以浮点运算计算容量和重复码的二项式求和；这些是模型概率，没有随机采样。

from math import comb, log2


def h2(t):
    if not 0 <= t <= 1:
        raise ValueError("Probability must be between 0 and 1")
    if t in (0, 1):
        return 0.0
    return -t * log2(t) - (1 - t) * log2(1 - t)


p = 0.1
epsilon = 0.1
print(f"H2({p}) = {h2(p):.6f}")
print(f"BSC capacity = {1 - h2(p):.6f} bits/use")
print(f"BEC capacity = {1 - epsilon:.6f} bits/use")
for n in (1, 3, 5, 9):
    error = sum(comb(n, j) * p**j * (1 - p)**(n - j)
                for j in range((n + 1) // 2, n + 1))
    print(f"n={n}: rate={1/n:.6f}, error={error:.8f}")
threefold_error = 3 * p**2 * (1 - p) + p**3
print(f"100-bit message error = {1 - (1 - threefold_error)**100:.6f}")
snr = 9.0
bandwidth = 1_000_000
print(f"Real Gaussian capacity = {0.5 * log2(1 + snr):.6f} bits/use")
print(f"Bandlimited capacity = {bandwidth * log2(1 + snr):.6f} bits/s")

输出：

H2(0.1) = 0.468996
BSC capacity = 0.531004 bits/use
BEC capacity = 0.900000 bits/use
n=1: rate=1.000000, error=0.10000000
n=3: rate=0.333333, error=0.02800000
n=5: rate=0.200000, error=0.00856000
n=9: rate=0.111111, error=0.00089092
100-bit message error = 0.941571
Real Gaussian capacity = 1.660964 bits/use
Bandlimited capacity = 3321928.094887 bits/s

我的阅读 · 打开过的笔记会记在当前浏览器里。