有噪信道编码定理 | Codeboy's Blog

形式陈述

本页所有对数以 $2$ 为底，固定无反馈、无输入成本约束、有限字母表上的 DMC $W(y\mid x)$ ，其信道容量与 $n$ 次使用满足

W^n(y^n\mid x^n)=\prod_{i=1}^nW(y_i\mid x_i), \qquad C=\max_{P_X}I(X;Y).

一个 $(n,M_n)$ 信道码由编码器与译码器

f_n:[M_n]\to\mathcal X^n, \qquad g_n:\mathcal Y^n\to[M_n]

组成。消息 $M$ 在 $[M_n]$ 上均匀时，码率和平均块错误概率为

R_n=\frac1n\log_2M_n,

\bar P_e^{(n)} =\frac1{M_n}\sum_{m=1}^{M_n} \Pr[g_n(Y^n)\ne m\mid X^n=f_n(m)].

平均错误版本的定理分成两项。

Achievability（可达性）：对每个 $0\le R<C$ ，存在一列码使

\liminf_{n\to\infty}R_n\ge R, \qquad \bar P_e^{(n)}\to0.

Converse（逆定理）：若一列码满足 $\bar P_e^{(n)}\to0$ ，则

\limsup_{n\to\infty}R_n\le C.

有限字母表 DMC 还有强逆定理：若 $R_n\ge C+\delta$ 对某个固定 $\delta>0$ 最终成立，则 $\bar P_e^{(n)}\to1$ 。基本的弱 converse 只排除错误趋零；强逆需要更强论证，参见文末 Polyanskiy–Wu 作者稿 Theorem 22.1。

最大错误概率

P_{e,\max}^{(n)} =\max_m\Pr[g_n(Y^n)\ne m\mid X^n=f_n(m)]

在单用户 DMC 中给出同一渐近容量：删除条件错误大于 $2\bar P_e^{(n)}$ 的消息，至少保留 $M_n/2$ 个码字，最大错误至多 $2\bar P_e^{(n)}$ ，码率损失至多 $1/n$ bit/次。

直觉

长码把每条消息映成整个输入块，而不是逐 bit 独立保护。低于容量时，可以让不同码字对应的典型输出区域几乎不重叠；高于容量时，输出所能保留的互信息不足以区分指数多条消息。可靠指整块消息译码错误趋零，不要求信道中的每个符号都未被扰动。

“低于容量”只断言存在一列越来越长的好码。“高于容量”则断言没有任何码列能让错误趋零。可达性与逆定理的量词方向不同，缺一项都不能把 $C$ 称为精确阈值。

有限块随机编码：先证明一个可计算的界

固定输入分布 $P_X$ ，令 $P_Y(y)=\sum_xP_X(x)W(y\mid x)$ 。对 $P_Y(y)>0$ 定义信息密度

\imath(x;y)=\log_2\frac{W(y\mid x)}{P_Y(y)},

其中 $W(y\mid x)=0$ 时取 $-\infty$ 。 $P_Y(y)=0$ 的输出在以下随机试验中不会出现，可任意规定译码。真实联合分布 $P_XW$ 的正概率支持有限，信息密度在该支持上都是有限实数，均值恰为 $I(X;Y)$ 。对乘积输入和信道，块信息密度为

\imath(x^n;y^n)=\log_2\frac{W^n(y^n\mid x^n)}{P_Y^n(y^n)} =\sum_{i=1}^n\imath(x_i;y_i).

独立抽取 $M$ 条码字 $C_1,\ldots,C_M\sim P_X^n$ 。抽码只是证明方法；找到一个好码本后就将它固定，实际通信不必重新抽码。取 $\tau>0$ ，阈值 $t=\log_2M+\tau$ 。收到 $y^n$ 时，若恰好一个索引 $j$ 满足 $\imath(C_j;y^n)>t$ ，就输出 $j$ ；没有候选或有多个候选时，统一输出固定消息 $1$ 。这仍是 $g:\mathcal Y^n\to[M]$ ，没有新增拒绝符号。

发送消息 $m$ 时，只要真实码字越过阈值且所有其他码字都未越过阈值，就一定判对。因此错误事件满足包含关系

\{g(Y^n)\ne m\} \subseteq \{\imath(C_m;Y^n)\le t\} \cup\bigcup_{j\ne m}\{\imath(C_j;Y^n)>t\}.

不能把它写成等号：例如消息 $1$ 发送时，默认输出 $1$ 可能碰巧正确。平均于随机码本后，真实对 $(C_m,Y^n)$ 服从 $P_X^nW^n$ ；错误码字 $C_j$ 与 $Y^n$ 独立。对每个 $P_Y^n(y^n)>0$ 的固定输出，直接求和得

\begin{aligned} &\Pr[\imath(C_j;y^n)>t]\\ &=\sum_{x^n:\,\imath(x^n;y^n)>t}P_X^n(x^n)\\ &\le 2^{-t}\sum_{x^n}P_X^n(x^n) \frac{W^n(y^n\mid x^n)}{P_Y^n(y^n)} =2^{-t}. \end{aligned}

最后一个等号用的正是输出边缘分布的定义。再对输出平均，对错误码字使用并集界，最后平均消息，得到

\begin{aligned} \mathbb E_{\rm code}[\bar P_e] &\le\Pr[\imath(X^n;Y^n)\le\log_2M+\tau] +(M-1)2^{-\log_2M-\tau}\\ &\le\Pr[\imath(X^n;Y^n)\le\log_2M+\tau]+2^{-\tau}. \end{aligned}

码本空间有限，故至少有一个确定码本的平均错误不超过右端；否则所有码本都超过右端，其平均也会超过。结论是存在一个好码本，并非每次抽样都成功，也没有给出高效寻找它的方法。

从有限界到固定正率，再到最大错误

给定 $0\le R<C$ ，选择输入分布及中间速率，使

R<R'<I(X;Y)\le C, \qquad \delta=\frac{I(X;Y)-R'}2>0.

令 $M_n=\lfloor2^{nR'}\rfloor$ 、 $\tau=n\delta$ 。真实联合分布下的各项信息密度独立同分布，由大数定律，

\begin{aligned} \bar P_e^{(n)} &\le\Pr\!\left[\frac1n\sum_{i=1}^n\imath(X_i;Y_i) \le R'+\delta\right]+2^{-n\delta}\\ &\longrightarrow0. \end{aligned}

这里 $R'+\delta<I(X;Y)$ 是尾概率趋零的原因，而 $R_n\to R'>R$ 保留了速率余量。若只要求零速率，一条消息即有零错误； $C=0$ 时没有 $0\le R<C$ 的非平凡可达性要求，逆定理仍排除正率可靠通信。

对每个选定码本，删去条件错误超过 $2\bar P_e^{(n)}$ 的消息，至少保留 $\lceil M_n/2\rceil$ 条。原来译成已删消息的输出，统一改为某条保留消息，再重新编号。每条保留消息的正确判决区都被保留，所以新最大错误至多 $2\bar P_e^{(n)}$ ，码率减少至多 $1/n$ ；前面预留的 $R'-R$ 足以吸收这点损失。若平均错误为零，则无需删码。随机抽样允许码字重复，但最大错误小于 $1/2$ 的保留码不能有重复码字，理由见信道码。

有限块逆界：为什么信息总量不超过 $nC$

令 $U$ 均匀分布于 $M\ge2$ 条消息， $\widehat U=g(Y^n)$ ，平均块错误为 $P_e$ ，记 $h_2(e)=-e\log_2e-(1-e)\log_2(1-e)$ ，端点按连续延拓。任意确定编码器给出 $U\to X^n\to Y^n\to\widehat U$ 。由Fano 不等式与数据处理不等式，

\begin{aligned} \log_2M &=I(U;\widehat U)+H(U\mid\widehat U)\\ &\le I(X^n;Y^n)+h_2(P_e)+P_e\log_2(M-1). \end{aligned}

不能假设输出坐标独立，因为码字坐标可以相关。无条件熵只满足次可加性，而给定整个输入块后，信道的乘积律提供精确分解：

H(Y^n)\le\sum_{i=1}^nH(Y_i), \qquad H(Y^n\mid X^n)=\sum_{i=1}^nH(Y_i\mid X_i).

第二式可先对每个固定输入块计算乘积分布的熵，再对输入块平均；第 $i$ 项只依赖 $X_i$ 的边缘分布。因此

I(X^n;Y^n) \le\sum_{i=1}^n[H(Y_i)-H(Y_i\mid X_i)] =\sum_{i=1}^nI(X_i;Y_i)\le nC.

代回便得到精细的有限块必要条件

\boxed{\log_2M-nC\le h_2(P_e)+P_e\log_2(M-1).}

再用 $h_2(P_e)\le1$ 、 $\log_2(M-1)\le\log_2M$ 放松，得到

(1-P_e)R_n\le C+\frac1n.

当 $P_e\to0$ 时，直接除以最终为正的 $1-P_e$ 并取上极限，得 $\limsup R_n\le C$ ，无需预先假定码率有界。这只证明弱逆；由此不能推出高于容量时错误趋一。

例子与边界

可复算例：BSC $(0.1)$

该信道容量为

C=1-h_2(0.1)\approx0.5310\ \text{bit/次使用}.

所以任意固定 $R=0.5<C$ 都存在块错误趋零的码列；固定 $R=0.6>C$ 则不可能可靠，强逆定理还给出错误趋一。

码率低于容量，并不保证任意编码方案都可靠。三重重复码以 000,111 传一个 bit，码率 $1/3$ ，多数译码错误概率为

\binom32(0.1)^2(0.9)+(0.1)^3=0.028.

若把长消息的每一 bit 独立使用这段码，含 $k$ 个消息 bit 的块错误概率为

1-(1-0.028)^k\longrightarrow1,

尽管 $1/3<C$ 。定理承诺的是存在设计得当的长块码，不是重复任意短码就会可靠。

例如 $k=20$ 时该块错误约为 $0.4333364$ ， $k=100$ 时约为 $0.9415713$ 。单个消息比特错误仍是 $0.028$ ，但“所有消息比特都对”的要求越来越难满足。

长度 $1000$ 、码率 $0.4$ 的存在上界

随机码本采用公平输入，取 $n=1000$ 、 $M=2^{400}$ 、 $\tau=20$ 。若真实传输中翻转数为 $K$ ，则 $K\sim\operatorname{Binomial}(1000,0.1)$ ，且

\imath(X^{1000};Y^{1000}) =(1000-K)\log_2(1.8)+K\log_2(0.2) =1000\log_2(1.8)-K\log_2 9.

阈值为 $400+20=420$ 。真实码字未严格越过阈值的事件 $\{\imath(X^{1000};Y^{1000})\le420\}$ 等价于

K\ge\frac{1000\log_2(1.8)-420}{\log_2 9} \approx135.0179914,

由于 $K$ 为整数，这一事件就是 $K\ge136$ ，尾和必须从 $136$ 开始。它是随机编码界中的第一项，并不等于译码错误事件；还需计入其他候选越过阈值的可能性。因此存在一个确定 $(1000,2^{400})$ 码，满足精确上界

\bar P_e\le B:= \sum_{k=136}^{1000}\binom{1000}{k} \left(\frac1{10}\right)^k\left(\frac9{10}\right)^{1000-k} +2^{-20}.

二项尾约为 $0.0001693452442$ ，故 $B\approx0.0001702989185$ 。十进制是精确和的近似值。删码后保留至少 $2^{399}$ 条消息，码率至少 $0.399$ ，最大错误至多 $2B\approx0.0003405978371$ 。这是存在保证，并不是某个显式码的实测错误率。

长度 $100$ 、码率 $0.6$ 的必要错误

同一信道改取 $n=100$ 、 $M=2^{60}$ 。粗逆界给出

P_e\ge 1-\frac{100C+1}{60}\approx0.0983259893.

精细界则要求

h_2(P_e)+P_e\log_2(2^{60}-1) \ge60-100[1-h_2(1/10)].

令 $e_*$ 为下列方程在 $[0,1-2^{-60}]$ 上的唯一根：

h_2(e_*)+e_*\log_2(2^{60}-1) =60-100[1-h_2(1/10)].

左端从 $0$ 严格增至 $60$ ，因为在区间内部导数为 $\log_2((1-e)(2^{60}-1)/e)>0$ ，且端点处连续。右端约为 $6.89955936$ ，故此根存在且唯一。任何 $P_e<e_*$ 都违反有限块不等式，所以所有码都有 $P_e\ge e_*$ ；更大错误区间当然也满足这一结论。数值求根得到 $e_*\approx0.1068217504$ 。精确答案是根方程，不能把舍入小数当作严格下界。这比粗界更强，仍不声称它是最优可达错误率。

边界与失败情形

定理不规定 $R=C$ 时的所有边界行为，也不从 $R<C$ 自动推出指定 $n$ 的错误率。有限块长要同时分析速率、目标错误概率和时延；编码与译码复杂度也不在 Shannon 存在性定理中。

有记忆、连续、多用户或带输入代价的信道必须重写容量与证明假设。单用户 DMC 的平均错误到最大错误 expurgation 也不能未经验证直接移植到多用户网络。

二用户多址容量定理沿这份阈值证明继续展开：错误候选分成只错第一人、只错第二人和两人都错，分别产生两个条件互信息界及一个总率界。时间共享保留给定日程后的独立输入，而分离编码所需的消息矩形解释了为何不能直接移植删码步骤。

推论与应用

定理确立了信道容量的操作意义，并为纠错码设计给出目标。LDPC、Turbo 与极化码等构造不仅要接近容量，还要控制复杂度、有限长度错误和时延；这些是基本定理之外的额外保证。

与源编码结合时，还要换算每个源符号使用多少次信道。只有在模型满足相应独立性与渐近条件时，才可用“源率低于信道可供率”连接两条编码定理。

参考资料

Yury Polyanskiy and Yihong Wu, Information Theory: From Coding to Learning，2024-08-16 作者稿，Theorem 18.5（印刷 pp. 354–355，阈值随机编码界）、Theorems 19.8–19.9（pp. 376–377，无记忆容量）、Theorem 22.1（p. 422，强逆）。本文使用 bit，并把拒绝输出改为固定消息以保持译码字母表不变。
Claude E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal 27, 1948, Part II, §§13–17.
Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006, §§7.5–7.9.
Robert G. Gallager, Information Theory and Reliable Communication, Wiley, 1968, Chapters 5 and 7.
Imre Csiszár and János Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd ed., Cambridge University Press, 2011, Chapters 6–7.

形式陈述 ​

有限块随机编码：先证明一个可计算的界 ​

从有限界到固定正率，再到最大错误 ​

有限块逆界：为什么信息总量不超过 nC ​

可复算例：BSC(0.1) ​

长度 1000、码率 0.4 的存在上界 ​

长度 100、码率 0.6 的必要错误 ​

边界与失败情形 ​

反向链接