信道容量与编码

上一章问怎样用更少的 bit 表示消息。这一章问：⁠线路会出错时，怎样让接收端仍然知道我们发了什么？

把每个比特发送三遍、用多数表决，是一种纠错方法，但速率降到了 $1/3$。继续增加重复次数还会继续降低速率。香农的结论更强：对合适的信道，先固定一个低于容量的正速率，再使用越来越长、设计得当的块码，就能使块解码错误概率趋于零。

这里的“越来越长”会带来延迟、存储和计算成本，也不保证随意选一个长码就能改善性能。以下先讨论无记忆信道，离散公式均以 2 为底，单位为 bit。

信道是一个条件概率模型

信道用 $P(Y=y\mid X=x)$ 表示。⁠输入分布 $P(X)$ 描述发送端如何使用信道，⁠条件分布 $P(Y\mid X)$ 描述线路如何改变输入。两者是不同的对象。

二元对称信道（BSC）可以写成：

$$Y=X\oplus Z,Z\sim \mathrm{Bernoulli}(p)$$

其中 $Z$ 与 $X$ 独立，每次使用的噪声也独立。$p$ 是翻转概率；$1-p$ 是保持原值的概率。

一次使用的平均信息传递由互信息度量：

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

它是给定输入分布下的平均量，不是说收到的每一个具体比特都携带同样的信息。

容量为什么要对输入分布取最大值？

设发送 1 的概率是 $\alpha =P(X=1)$。输出为 1 有两条途径：输入 1 且未翻转，或输入 0 且翻转。因此：

$$\beta =P(Y=1)=\alpha (1-p)+(1-\alpha )p=p+\alpha (1-2p)$$

给定任一输入，输出剩下的不确定性都是翻转噪声的二元熵 $h_2(p)$，所以：

$$I(X;Y)=h_2(\beta )-h_2(p)$$

固定线路参数 $p$ 后，第二项不变。要增大互信息，就要让输出熵 $h_2(\beta )$ 尽量大。

正在呈现知识画面

由于二元输出的熵至多为 1，而均匀输入 $\alpha =1/2$ 可以使 $\beta =1/2$，我们得到：

$$C=\underset{\alpha \in [0,1]}{\max }I(X;Y)=1-h_2(p)$$

曲线上的一点是当前输入分布的互信息，整条曲线的最大值才是容量。若总发送同一个确定比特，$H(X)=0$，即使线路完全无噪声，也没有新的随机消息可供区分。

几个边界能检验这个公式：

翻转概率	容量（bit/次使用）	原因
$p=0$	1	输入可以完整恢复
$p=0.11$	约 0.500	均匀输入时，约一半的输出熵来自不可预测的翻转
$p=0.5$	0	输出与输入独立，任何输入分布的互信息都为零
$p=1$	1	输出必为输入的反值，接收端取反即可恢复

因此随机性最强的 $p=0.5$ 最有破坏性，确定性翻转本身并不丢失信息。对于一般的离散无记忆信道，容量写成 $C={\max }_{P(X)}I(X;Y)$；最优输入不一定均匀。相关定理见 MIT 6.441 第 16 章。

香农定理保证的是怎样的“可靠”？

一个块码把 $M$ 条可能的消息分别映射成长度为 $n$ 的码字。速率为：

$$R=\frac{{\log }_{2}M}{n}\text{bit / 信道使用}$$

解码器根据整段接收序列估计消息。下面用 $P_e$ 表示等概率消息下的块错误概率⁠：整条消息解错的概率，它不同于单个信道比特被翻转的概率 $p$。

对离散无记忆信道，固定 $R<C$，存在速率趋近该值的码序列，使 $n\to \infty$ 时 $P_e\to 0$。反之，固定 $R>C$ 时，不存在块错误概率趋于零的码序列。

圆点代表码字，外围色块示意噪声带来的接收区域：消息更密集时，区域更容易重叠。平面位置不表示汉明距离，圆的大小也不是错误概率；这张图只帮助理解容量的空间直觉。

图中的门槛描述渐近可达性。它没有给出某个有限块长的错误率，也没有说在 $R=C$ 的边界上任意码都可靠。⁠低于容量是存在好码的条件，具体实现还要选择码、解码器和块长。

“加更多冗余也救不了 $R>C$”也要读准确：如果多发送一些信道符号，实际速率 $R$ 就可能下降，甚至降到容量以下。逆定理禁止的是保持速率高于容量，同时还要求错误概率趋于零。

一个计数直觉：为什么 BSC 容量是 $1-h_2(p)$？

对 $0<p<1/2$ 的长 BSC 块，典型噪声模式的数量具有约 $2^{n{h}_2(p)}$ 的指数规模。一个码字经过噪声后，会对应一片可能的接收序列。若有约 $2^{nR}$ 个码字，而接收空间总共只有 $2^n$ 个二元串，要让各消息的高概率接收区域足够容易区分，就会出现计数关系：

$$2^{nR}{2}^{n{h}_2(p)}\lesssim 2^n⟹R\lesssim 1-h_2(p)$$

它把上一章的典型集与容量连接起来。这是指数尺度的直觉，不是有限长度下互不相交区域的完整证明。严格定理需要可达性与逆定理两部分；噪声事件也不要求全部都被纠正。

先在 64 个位置上看清“争用空间”

下面枚举六位接收串。每个码字的半径 $t$ 邻域含 $V_t={\sum }_{j=0}^t\left(\genfrac{}{}{0ex}{}{6}{j}\right)$ 个串；$t=1$ 时是 7 个。若这些邻域要互不重叠，必须有 $M{V}_t\le 64$，但满足计数条件并不保证某个实际码本就能做到。图中直接检查每个位置的归属，而不是把平面距离当成汉明距离。

正在呈现知识画面

邻域重叠、漏掉的噪声尾部和最终解码错误，是不同的对象。 对固定码本，图中用完整 BSC 概率计算平均最大似然（ML）块错误率，邻域半径仅用于观察。即使邻域互不重叠，距离超过 $t$ 的噪声仍可能导致错误。

长块讨论把小图中的有限邻域替换成概率趋近 1 的典型噪声集合，其规模约为 $2^{n{h}_2(p)}$。此时总需求的指数是 $n(R+h_2(p))$，接收空间的指数是 $n$。这解释了容量计数的来源，但并未由六位演示证明随机编码定理；下面的 Hamming 码再展示一个具体的纠错结构。

一个真实小码：为什么距离 3 能纠正 1 位？

两个等长二元串的 Hamming 距离⁠，就是不同位置的数量。一个码的最小距离 $d_{\min }$ 是任意两个不同合法码字之间的最小距离。

若接收串最多偏离原码字 $t$ 位，并且每两个合法码字都至少相距 $2t+1$，原码字就是唯一最近的候选。原因是三角不等式：如果同一个接收串距离两个码字都不超过 $t$，那两个码字之间的距离就不超过 $2t$，与条件矛盾。

$$d_{\min }\ge 2t+1$$

下面使用真正的 Hamming $(7,4)$ 码：4 位消息变成 7 位码字，共有 16 个合法码字，最小距离为 3。点击接收串中的位即可引入翻转，下面同时显示全部候选与它们到接收串的距离。

正在呈现知识画面

这里把数据位放在位置 $3,5,6,7$，三个偶校验位放在位置 $1,2,4$。若四个数据位为 $a,b,c,d$，码字是：

$$(a\oplus b\oplus d,a\oplus c\oplus d,a,b\oplus c\oplus d,b,c,d)$$

固定发送全零码字，只是为了容易看出哪些位被翻转；这个线性码对其他消息也有相同的单错纠正能力。图中采用最近码字解码，它在 BSC 的 $p<1/2$ 且消息等概率时也是最大似然解码。

任意一位翻转都能纠正；两位翻转时，这个码会更接近另一个合法码字，导致误纠正。事实上它的 16 个半径为 1 的邻域恰好覆盖所有 $2^7=128$ 个接收串，所以最近码字总是唯一，但唯一并不等于正确⁠。更高错误重量也不在单错保证之内。

这个小码不是香农极限的证明。其速率固定为 $4/7\approx 0.571$。若 BSC 的 $p=0.1$，最近码字解码成功当且仅当噪声至多翻转一位，因此：

$$P_e=1-(1-p{)}^7-7p(1-p{)}^6\approx 0.1497$$

这时容量约为 0.531，低于这个码的速率。示例展示的是一个有限码怎样纠错，而不是固定此速率就能让错误任意小。

进入高斯信道前：密度与微分熵

前面使用离散概率。实数信号改用概率密度 $f(x)$，区间上的概率是密度的积分；⁠密度的值本身不是某个实数出现的概率⁠，也可以大于 1。微分熵定义为：

$$h(X)=-\int f(x){\log }_{2}f(x)dx.$$

例如 $X$ 均匀分布在宽度为 $a$ 的区间上，密度为 $1/a$，所以 $h(X)={\log }_{2}a$。当 $a<1$ 时它为负；把同一个量换一种单位，其数值也会改变。一般有 $h(cX)=h(X)+{\log }_2|c|$（$c\ne 0$，相关熵存在）。

因此微分熵不是“精确编码一个实数需要多少 bit”。实际编码必须说明量化精度；而下一节比较相同坐标和单位下的高斯输出与噪声，熵差中的共同尺度项会抵消。KL 和互信息在适当可逆坐标变换下保持不变。

AWGN：对数与 $1/2$ 从哪里来？

实数加性高斯白噪声信道写作：

$$Y=X+N,N\sim \mathcal{N}(0,{\sigma }^2),\mathbb{E}[X^2]\le P$$

噪声与输入独立，${\sigma }^2>0$，每次使用的噪声独立。必须给出平均功率约束，否则允许无限增大信号功率就没有有限容量上界。

给定 $X$ 后，$Y$ 只是噪声的平移，所以 $h(Y\mid X)=h(N)$。这里 $h$ 是微分熵。高斯噪声的熵是：

$$h(N)=\frac{1}{2}{\log }_2(2\pi e{\sigma }^2)$$

而 $\mathrm{Var}(Y)\le P+{\sigma }^2$。给定方差时高斯分布的微分熵最大，因此：

$$I(X;Y)=h(Y)-h(N)\le \frac{1}{2}{\log }_2\frac{P+{\sigma }^2}{{\sigma }^2}$$

取独立的零均值高斯输入 $X\sim \mathcal{N}(0,P)$ 可达到等号，于是：

$$C=\frac{1}{2}{\log }_2(1+\mathrm{SNR})={\log }_2\frac{{\sigma }_Y}{{\sigma }_N},\mathrm{SNR}=\frac{P}{{\sigma }^2}$$

后一种写法尤其直观：⁠高斯分布的标准差扩大多少倍，微分熵就增加这个倍数的对数。 用方差比表达时，因为标准差是方差的平方根，对数前出现 $1/2$。

正在呈现知识画面

图中固定噪声方差为 1，并使用达到容量的高斯输入。$P=0$ 时，输出分布等于噪声，容量为 0；$P=3$ 时标准差比是 2，熵差为 1 bit；$P=15$ 时比值是 4，熵差为 2 bit。两条完整密度曲线下的积分都是 1，容量不是它们的面积差。

这个推导也解释了功率收益的对数增长。高 SNR 下把功率翻倍，每次实数信道使用的容量大约只增加 0.5 bit。若限制为二元输入或其他星座，通常不能直接取得这里高斯输入的容量。参阅 MIT 6.441 第 17 章。

连续时间、带宽为 $B$ 的标准实数 AWGN 模型，若双边噪声功率谱密度为 $N_0/2$，带内噪声功率为 $N_{0}B$，常写成 $C=B{\log }_2(1+P/(N_{0}B))$ bit/s。它与上面的“每次实数使用”单位不同，不能直接比较系数。

从理论极限到工程实现

编码定理给出可达速率的边界，实际系统还需要指定块长、目标块错误率、译码延迟、功耗和计算预算。Hamming、Reed–Solomon、turbo、LDPC、polar 等码针对不同结构和约束取舍；不能仅凭“码字更长”或某个码族名称就断言已经接近容量。

随机编码论证说明好码存在，但直接存储庞大码本并穷举译码通常不实用。工程的重要工作，是找到有结构、能高效编码和解码、并且满足有限长度性能要求的码。

信源—信道分离：先对齐单位，再比较速率

源编码消除信源的可预测冗余，信道编码再有目的地加入纠错冗余。对于经典点对点、有限字母表平稳遍历信源与离散无记忆信道，在允许长块的条件下，可以先压缩再纠错，实现渐近最优的可靠传输条件。

如果信源每秒产生 $f_s$ 个符号，熵率为 $\bar{H}$ bit/信源符号；信道每秒使用 $f_c$ 次，容量为 $C$ bit/次使用，那么应比较：

$$f_s\bar{H}<f_{c}C$$

例如每秒 1000 个源符号、熵率 0.4 bit/符号，需要约 400 bit/s 的渐近信息率；每秒使用 1000 次、容量 0.5 bit/次的信道提供 500 bit/s 的理论预算，可以在两者之间选择压缩输出率和信道码率。有限块的开销与目标可靠性仍须单独计算。

分离结论有适用条件。短延迟、多用户网络或其他严格约束下，独立优化压缩和纠错可能不再最合适。相关边界见 MIT 6.441 第 20 章。下一篇讨论允许一定信息损失时的率失真与信息瓶颈。

参考

• MIT 6.441，第 16 章：线性码与信道容量、第 17 章：输入约束与高斯信道、第 20 章：信源—信道分离。
• Cover & Thomas，Elements of Information Theory，第 7 章：信道容量；第 9 章：高斯信道。
• Ben Lynn，Perfect Codes：Hamming 码与纠错直觉。