本页目录

信息论进阶 II · 信道编码定理的证明

对标：Cover & Thomas §7 ｜ 前置：it2-01、本科信息论 II–III 本科信息论 III 只陈述了信道编码定理；本页给出 Shannon 的证明——随机编码 + 联合典型译码：不构造任何具体的码，而是证明"随机抓一把码字平均而言就能工作"。这是概率方法（图论组合线见过）最辉煌的一次出手，也是"存在性证明改变工业"的孤例级案例。

有噪信道：输入→转移矩阵→输出，容量 C=\max I(X;Y)。

图 it2-02.1有噪信道：输入→转移矩阵→输出，容量 \(C=\max I(X;Y)\)。

1. 设置与联合典型性

离散无记忆信道 \(p(y\mid x)\)；码率 \(R\)：用 \(n\) 次信道传 \(nR\) 比特（\(2^{nR}\) 个消息）。目标：证明 \(R < C = \max_{p(x)}I(X;Y)\) 时错误率可任意小。

联合典型集 \(A_\varepsilon^{(n)}\)：序列对 \((x^n, y^n)\) 的经验熵三项（\(x\) 的、\(y\) 的、联合的）都 \(\varepsilon\)-贴近真熵。三条性质【骨架，均为 it2-01 性质的二维版】： ① 真实配对 \((X^n, Y^n) \sim \prod p(x,y)\) 落入 \(A_\varepsilon^{(n)}\) 的概率 \(\to 1\)（AEP 三次）； ② \(|A_\varepsilon^{(n)}| \leq 2^{n(H(X,Y)+\varepsilon)}\)； ③ 独立配对（\(\tilde X^n \perp Y^n\)，各自边缘正确）误落联合典型的概率

\[ P\big((\tilde X^n, Y^n) \in A_\varepsilon^{(n)}\big) \leq 2^{-n(I(X;Y) - 3\varepsilon)} \]

（证：逐点 \(p(x^n)p(y^n) \approx 2^{-n(H(X)+H(Y))}\)，集合大小 ≈ \(2^{nH(X,Y)}\)，相乘得 \(2^{-nI}\)——互信息 = "假配对装真"的指数难度：这一行是整个定理的灵魂。）

2. 可达性（正向定理）的证明

【证明骨架（四步，结构完整）】 ① 随机造码：按最优输入分布 \(p^*(x)\) 独立随机生成 \(2^{nR}\) 个码字——码本是抽签抽出来的； ② 译码规则：收到 \(y^n\)，找唯一与之联合典型的码字；无或不唯一则报错； ③ 错误分析（对随机码本取平均）：发送消息 1——

\[ P(\text{B}) \leq 2^{nR}\cdot 2^{-n(I - 3\varepsilon)} \to 0 \quad \text{当 } R < I(X;Y) - 3\varepsilon \]

④ 去随机化：平均错误率 \(\to 0\) ⇒ 存在一个码本达到平均错误率；再删掉最差一半码字，把"平均错误小"升级为"最大错误小"（牺牲的码率 \(\frac1n \to 0\)）。\(\blacksquare\)

读法：③ 是"两个指数赛跑"——假码字的数量 \(2^{nR}\) 对撞装真难度 \(2^{-nI}\)，\(R < I\) 则真相赢；取 \(p^* = \arg\max I\) 即达容量。随机码字在高维中彼此"远离"（hdp 的近正交现象在编码空间的重演）——好码不难存在、难在可实现译码：从 1948 到 Turbo/LDPC/Polar 的七十年正是在补"多项式时间译码"这个洞（Polar 码是首个可证达容量 + 高效译码的构造【引用 Arıkan】）。

3. 逆定理（\(R > C\) 不可能）

【骨架】 Fano 不等式（本科信息论 II 提名的那位）把错误率与条件熵挂钩：\(P_e \geq \frac{H(W\mid\hat W) - 1}{nR}\)；数据处理不等式链 \(W \to X^n \to Y^n \to \hat W\) 给 \(I(W;\hat W) \leq I(X^n;Y^n) \leq nC\)（无记忆信道逐次使用的互信息可加性【一行】）；两者合并：\(R > C\) ⇒ \(P_e\) 有正下界，不随 \(n\) 消失。\(\blacksquare\) ——容量之上不是"难"，是不可能（信息论的"物理定律"品格；与 slt 线 NFL、JL 下界同属"不可能定理"家族——DPI 是三者共同的引擎之一）。

4. 微分熵与高斯信道（连续世界一页速通）

微分熵 \(h(X) = -\int f\ln f\)（本科信息论 III 已警告可负）；高斯信道 \(Y = X + Z\)，\(Z \sim N(0, N)\)、功率约束 \(EX^2 \leq P\)：

\[ C = \frac12\log\Big(1 + \frac PN\Big) \]

【骨架】 \(I = h(Y) - h(Z)\)；给定方差高斯最大化 \(h(Y)\)（最大熵，本科信息论 III）⇒ 输入取高斯达界。\(\blacksquare\)——香农极限公式：通信工程的北极星（5G 的编码即在逼近它）；带宽版 \(C = W\log(1 + \mathrm{SNR})\) 是无线容量规划的日用公式。

5. 练习与要点

例 1（赛跑的数感） BSC(\(\varepsilon = 0.1\))：\(C \approx 0.531\)。取 \(R = 0.4\)：假码字 \(2^{0.4n}\) 个、单个装真概率 \(2^{-0.531n}\) ⇒ 错误 \(\lesssim 2^{-0.131n}\)——\(n = 500\) 时 \(\sim 10^{-20}\)：块长是可靠性的燃料（实际 LDPC 码块长数千的原因）。

例 2（Fano 的独立价值） 用 Fano 证明：二元均匀消息、任何基于 \(Y\) 的猜测，\(P_e \geq \frac{H(X\mid Y) - 1}{\log|\mathcal{X}|}\) 型下界——统计学习的下界证明（slt-02 的 NFL 精细版）与多臂老虎机遗憾下界都用这套"Fano 方法"【引用】：一个不等式跨三个学科。

例 3（容量公式的边际直觉） 功率翻倍：\(C\) 只增 \(\frac12\log 2 \approx 0.35\) 比特——对数收益递减：通信系统"加功率不如加带宽/天线"的经济学，一阶导数就是答案。\(\blacksquare\)

下一页：信息论进阶收官——率失真理论（有损压缩的极限）与大偏差（Sanov 定理）：熵在"压缩"与"稀有事件"两个方向的完全体。