有噪信道编码定理

有噪信道编码定理是信息论的一项基本结论，确定了信息通过有噪通信信道可靠传输时所能达到的最高速率。对于离散无记忆信道，只要速率严格低于其信道容量，就存在随码长增加而使译码错误概率趋于零的编码；严格高于容量的速率则无法做到这一点。克劳德·香农在1948年的论文《通信的数学理论》中提出了这一结论。该定理表明，即使噪声存在，也可以实现可靠通信，而不要求噪声本身消失。(web.njit.edu)

信道模型与编码

该定理的标准表述针对输入字母表 $\mathcal X$ 和输出字母表 $\mathcal Y$ 均为有限集的离散无记忆信道。信道的行为由条件概率 $W(y\mid x)$ 描述。“无记忆”意味着，在给定发送序列的条件下，各次输出相互独立，且每次输出仅取决于对应的输入：

W^n(y^n\mid x^n)=\prod_{i=1}^{n}W(y_i\mid x_i).

每次使用信道时，都遵循相同的转移规律。这一假设并不要求码字内部的各个符号相互独立。(ocw.mit.edu)

一个 $(n,M)$ 码由编码器和译码器组成：编码器将 $M$ 个消息中的每一个映射为长度为 $n$ 的输入序列，称为码字；译码器则将每个接收序列映射为一个估计消息。其速率为

R_n=\frac{\log_2 M}{n},

单位为每次信道使用传输的比特数。若消息 $U$ 按均匀分布选取，则平均块错误概率为 $P_e^{(n)}=\Pr(\widehat U\ne U)$ 。块错误关注的是整个消息是否被正确译码，而非译码错误的比特所占比例。纠错码通过牺牲一部分潜在的消息传输速率，使不同消息在经过信道传输后仍可区分。(ocw.mit.edu)

数学表述

对于上述有限字母表信道，容量为

C=\max_{P_X} I(X;Y),

其中，最大化是在所有输入概率分布上进行的，输入和输出随机变量的联合分布为 $P_X(x)W(y\mid x)$ 。二者的互信息为

I(X;Y)= \sum_{x,y}P_X(x)W(y\mid x) \log_2 \frac{W(y\mid x)} {\sum_{x'}P_X(x')W(y\mid x')}.

等价地， $I(X;Y)=H(X)-H(X\mid Y)$ ，即输入的信息熵减去观测输出后剩余的条件熵。(ocw.mit.edu)

该定理包含两部分：

可达性： 对每个 $0<R<C$ ，都存在一列码，其极限速率至少为 $R$ ，且 $P_e^{(n)}\to0$ 。
逆定理： 任何错误概率趋于零的码序列，都必须满足 $\limsup_{n\to\infty}R_n\le C$ 。

因此，容量是所有可可靠实现的速率的上确界。这一基本表述并不声称某个固定正码长的码能够完全无错，也不声称恰好以速率 $C$ 工作时，错误概率总能趋于零。对于有限字母表的离散无记忆信道，强逆定理进一步指出：如果速率始终比容量高出一个固定的正值，那么错误概率将趋于一。(ocw.mit.edu)

证明原理

可达性可以通过随机编码来证明。先选择一个满足 $I(X;Y)>R$ 的输入分布，再按照其乘积分布，独立生成约 $2^{nR}$ 个码字。译码器寻找与接收序列在统计意义上相容的唯一码字。大数定律保证，实际发送的输入与输出序列对通常是相容的，而无关码字看似与接收序列相容的概率则大致按 $2^{-nI(X;Y)}$ 衰减。由于 $R<I(X;Y)$ ，对整个随机码集合取平均得到的错误概率趋于零。因此，至少存在一个错误概率很小的确定性码本；在实际运行中，无须不断生成新的随机码本。(ocw.mit.edu)

逆定理的证明使用法诺不等式和数据处理不等式。对于均匀分布的消息，

H(U\mid Y^n)\le 1+P_e^{(n)}\log_2 M.

经过编码器和信道处理后，有 $I(U;Y^n)\le I(X^n;Y^n)\le nC$ 。结合这些界限可得

(1-P_e^{(n)})R_n\le C+\frac1n.

如果错误概率趋于零，极限速率就不能超过容量。这一论证证明的是弱逆定理，单凭它还不能证明强逆定理。(ocw.mit.edu)

典型信道

二元对称信道以概率 $p$ 独立地翻转每个传输的比特。其容量为

C=1-h_2(p),\qquad h_2(p)=-p\log_2p-(1-p)\log_2(1-p).

当 $p=1/2$ 时，输出与输入相互独立，容量为零。当 $p=0$ 时，容量为每次使用一比特。二元擦除信道以概率 $\epsilon$ 将每个比特替换为可识别的擦除标记，其容量为 $1-\epsilon$ 。与位置未知的比特翻转不同，擦除会明确显示信息丢失的位置。(ocw.mit.edu)

对于理想的带限加性白高斯噪声信道，相关的香农–哈特利定理给出

C=B\log_2(1+P/N)

比特每秒，其中 $B$ 为带宽， $P$ 为平均信号功率， $N$ 为该带宽内的噪声功率。其连续信道假设和功率约束，使其不同于有限字母表信道的表述。(web.njit.edu)

适用范围与局限

该定理是一个渐近的存在性结论，而不是高效的编码或译码算法。它不具体说明达到目标错误概率所需的码长、译码成本或可接受的时延。有限码长理论研究这些额外的速率与可靠性之间的权衡；信道色散量化了相对于容量的一项重要二阶偏离。(ocw.mit.edu)

在标准的点对点无记忆假设下，信道编码与信源编码定理共同支持信源–信道分离：无损数据压缩去除信源冗余，而信道编码引入冗余以保护信息。当每次信道使用所对应的信源熵严格低于容量时，这两个阶段可以实现渐近可靠的传输。在短时延约束下，或在一般的多用户场景中，这种分离未必是最优的。(ocw.mit.edu)

参考来源

A Mathematical Theory of Communicationweb.njit.edu
Lecture Notes — Information Theory, Spring 2016ocw.mit.edu
Information Theory Reviewweb.mit.edu