随机编码论证

概述

Shannon 在证明信道编码定理时使用的极具原创性的方法：不需要构造任何具体的编码方案，只需证明在所有可能的随机码本中，"好的方案"以压倒性概率存在。这是概率方法在信息论中的首次重大应用。

关键内容

证明思路

Shannon 的随机编码论证分为四步：

随机生成码本：独立地、随机地生成 $2^{nR}$ 个长度为 $n$ 的码字（$R$ 是传输速率），每个码字中的每个符号按照使互信息最大化的分布独立选取
联合典型解码：解码器寻找与接收序列"联合典型"的码字
计算平均错误概率：对所有可能的随机码本求平均，Shannon 证明当 $R < C$ 时，平均错误概率随 $n$ 指数衰减趋近于零
存在性结论：由于平均错误概率趋于零，必然存在至少一个具体的码本，其错误概率不超过平均值

为什么出人意料

在 Shannon 之前，工程师的直觉是：噪声信道中的可靠通信必须以降低传输速率为代价，而且速率越接近极限，错误率就越高。Shannon 颠覆了这个直觉——他表明，只要不超过信道容量，就可以同时实现高速率和高可靠性。代价不是速率，而是编码和解码的复杂度。

存在性 vs 构造性

随机编码论证是存在性证明而非构造性证明： - 它证明了好的编码方案存在 - 但没有告诉我们如何找到它们 - 随机选择的码本在实际中既不可行（存储量巨大），解码计算量也过于庞大

后续影响

如何构造接近 Shannon 极限且计算可行的编码方案，成为此后半个多世纪编码理论研究的核心驱动力： - Hamming 码（1950）、BCH 码（1959-1960）、Reed-Solomon 码（1960） - Turbo 码（1993）、LDPC 码（1962 提出，1996 重新发现） - Polar 码（2009）—— 第一个在理论上证明可达 Shannon 极限的构造性编码

与组合数学的联系

随机编码论证是概率方法（probabilistic method）的早期典范——后来被 Paul Erdős 等人在组合数学中推广为一种强大的证明工具：要证明某对象存在，不需要构造它，只需证明随机选取时它以正概率出现。

来源

raw/books/计算机科学/02-shannon-mathematical-theory-of-communication.md