信道容量与编码定理

信道容量（channel capacity）是 Shannon 1948 年《通信的数学理论》的核心概念：一条信道每次使用平均最多可靠传递的比特数，等于输入输出间互信息对输入分布的极大值。噪声信道编码定理断言：速率低于容量时存在码使误差任意小，高于容量时误差不可能消失。这一定界把此后五十年的编码理论变成一部"逼近 Shannon 极限"的构造史，终点是 2001 年距容量仅 0.0045 dB 的 LDPC 码。量子信道的量子容量至今没有这样的闭式，是经典与量子的鲜明对照。

熵与互信息

随机变量 $X$ 的（香农）熵

$H(X)=-{\sum }_{x}p(x){\log }_{2}p(x)$

度量其不确定度（比特）。互信息度量收到 $Y$ 后对 $X$ 不确定度的削减：

$I(X;Y)=H(X)-H(X\mid Y)={\sum }_{x,y}p(x,y){\log }_2\frac{p(x,y)}{p(x)p(y)},$

第二个等式说明互信息是联合分布对独立分布的相对熵，恒非负Shannon 1948 (Bell Syst. Tech. J.)。

容量的定义与三个标准信道

离散无记忆信道的容量定义为对输入分布取极大的互信息：

$C={\max }_{p(x)}I(X;Y)(\text{bit}/\text{信道使用}).$

• BSC（二进制对称信道），翻转率 $p$：取 $Y=X\oplus E$，噪声 $E$ 与 $X$ 独立，则 $H(Y\mid X)=H_2(p)$（二元熵函数），而 $H(Y)\le 1$ 取等当输入均匀。故

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

  数例：$p=0.11$ 时 $H_2(p)\approx 0.50$，容量约 $1/2$ bit——每用两次信道可靠传一比特。

• BEC（二进制擦除信道），擦除率 $ϵ$：被擦除的位置接收方知道位置，容量 $C_{\mathrm{BEC}}=1-ϵ$——只有未擦除的使用在传信息。

• AWGN（加性高斯白噪声信道）（第二篇，连续情形）：带宽 $W$、信噪比 $S/N$ 时

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

  （bit/s），即著名的香农公式Shannon 1948 (Bell Syst. Tech. J. Part II)。

编码定理（正定理）：R < C 可达

定理：任意 $R<C$，存在速率 $R$ 的码族使差错概率随块长 $n$ 趋于零。Shannon 的证明是随机编码 + 联合典型译码的思路Shannon 1948 (Bell Syst. Tech. J.)：

1. 随机编码：按容量达到时的输入分布独立生成 $2^{nR}$ 个长度 $n$ 的码字——好码在平均意义下存在；
2. 典型性：大数定律使 $(x^n,y^n)$ 以高概率落入约 $2^{nH(X,Y)}$ 个联合典型序列中；错误只来自”别的码字也与 $y^n$ 联合典型”，单个候选的概率约 $2^{-nI(X;Y)}$，候选共 $2^{nR}$ 个；
3. 联合界：$R<I(X;Y)$ 时总错误概率 $\sim 2^{-n(I-R)}\to 0$。

证明是优美的，但非构造：随机码书要指数存储、译码要指数搜索。把”存在”变成”可构造、可译码”花了五十年（见下节）。

逆定理：R > C 不可达

定理：$R>C$ 时差错不可能趋于零。思路（Fano 不等式）：若 $P_e\to 0$，则 $H(X\mid Y)\to 0$，信息只能经互信息流通，$nR=H(X)\le I(X^n;Y^n)+o(n)\le nC$，与 $R>C$ 矛盾；定量地，平均差错概率被压在约 $1-C/R$ 之上——超容量通信必然丢比例的信息Shannon 1948 (Bell Syst. Tech. J.)。

逼近史：从存在到 0.0045 dB

Shannon 界定的 $C$ 之后，编码理论的历史就是逼近它的构造史：Hamming/BCH/RS（1950s）给出代数结构与快速译码但离容量很远（见hamming-codes、bch-codes、reed-solomon）；Forney 级联（1966）第一个以多项式复杂度达到任意 $R<C$（见concatenated-classical）；turbo（1993）与 LDPC 复兴（1996–99）把迭代译码推到实用（见ldpc-classical）；密度演化设计（2001）之后，Chung 等人的码率 1/2、块长 $10^7$ 不规则 LDPC 在 BIAWGN 信道上把门限做到距 Shannon 限 0.0045 dBChung et al. 2001 (IEEE Commun. Lett.)——Shannon 极限不是渐近寓言，而是工程可达的刻度。

图:迭代译码的"瀑布"行为示例——girth-16 与 girth-12 两种构造的帧错误率随噪声下降急剧走低,在错误地板区分出优劣(来源:QE030)

量子对照：没有闭式的量子容量

经典容量由单字母互信息的极大值给出，而量子信道的量子容量 $Q$（每次使用可可靠传递的量子比特数）由量子相干信息的正则化定义，至今没有单字母闭式——其深层障碍是量子信息度量的非加性。这使得”量子 Shannon 理论”仍是有待完成的理论（相关讨论见quantum-bounds）。反过来说，本类的全部经典装备——线性码、界、代数构造、稀疏图码、级联——正是量子编码理论借以起步的参照系。

延伸阅读

• classical-bounds
• ldpc-classical
• belief-propagation
• concatenated-classical
• quantum-bounds