6.6 信道编码定理证明

信道编码定理证明

信道编码定理（又称香农第二定理）的证明由可达性（正向证明）和逆定理（反向证明）两部分组成，其核心在于证明信道容量C是可靠通信的临界值。证明的关键工具是随机编码、联合典型集译码以及联合典型集的渐进等分性（AEP）性质。

可达性证明的编码方案如下：固定速率R < C，码长n，从使互信息最大化的输入分布p^*(x)中独立同分布地随机生成2^{nR}个码字c_1, c_2, …, c_{M}，其中M = 2^{nR}，每个码字c_i = (c_{i1}, c_{i2}, …, c_{in})为长度为n的序列。接收端采用联合典型译码：给定接收序列y^n，在码本中寻找与y^n构成联合典型对(x^n, y^n)的码字x^n。若存在唯一这样的码字，则判定为该码字对应的消息；否则宣告译码错误。定义错误事件E_0为发送码字与接收序列不构成联合典型对，事件E_i（i≠1）为错误码字与接收序列构成联合典型对。由联合典型集的AEP性质，P(E_0) → 0当n → ∞；由码字的随机独立性，P(E_i) ≤ 2^{-n(I(X;Y)-3ε)}。利用联合界，平均错误概率满足：

$${\bar{P}}_e\le P(E_0)+\sum _{i=2}^{M}P(E_i)\le \epsilon +2^{nR}\cdot 2^{-n(I(X;Y)-3\epsilon )}$$

当 $R<I(X;Y)=C$ 时，通过适当选择 $\epsilon$ 可使指数为负，从而平均错误概率随 $n$ 增大而趋于零。更精细的分析表明，错误概率以指数速率下降：$P_e\le 2^{-n{E}_r(R)}$，其中 $E_r(R)$ 为随机编码误差指数。

逆定理（反向证明）利用了Fano不等式和数据处理不等式。设某编码方案的速率为 $R$，译码错误概率为 $P_e^{(n)}$。由Fano不等式可得 $H(W|\hat{W})\le 1+P_e^{(n)}\log M$，其中 $W$ 为发送消息。结合数据处理不等式和互信息链式法则，可以推导出 $R\le C+P_e^{(n)}\log |\mathcal{X}|/n+1/n$。当 $n$ 固定且 $R>C$ 时，$P_e^{(n)}$ 必须远离零，从而证明了 $R>C$ 时不可能实现任意小的错误概率。这一正一反两个方向共同构成了信道编码定理的完整证明，确立了信道容量作为可靠通信极限的严格数学基础。

链接到

• 上一个知识点：6.5 噪声信道编码定理
• 下一个知识点：无（本章最后一个知识点）