问题：比特会被翻转

前面的课都在压缩：怎样用更少的比特传同样的信息。这一讲换成相反的方向——信道本身会出错。

二元对称信道（binary symmetric channel，BSC）有一个参数 $p$：每输入一位，以概率 $p$ 翻转，以概率 $1-p$ 原样输出，而且每一位独立。接收方不知道哪几位被翻转了。

取 $p=1/3$ 作为具体例子。把消息压缩到最短之后发出去，每一位都有三分之一的概率出错，还能可靠地恢复原消息吗？

重复码：能纠错，但代价太大

最直接的办法是重复码：每个比特重复 $T$ 次，解码时对每块做多数表决。

取 $T=100\log_2 k$（$k$ 是原消息长度）。每块有 $T$ 位，被翻转的位数服从二项分布，期望是 $Tp=T/3$。只有当翻转超过一半时多数表决才会错。由 Chernoff 界，这个概率随 $T$ 指数下降；选足够大的常数，可以让单块出错概率低于 $1/k^2$。再对所有 $k$ 块用并集界，整条消息出错的概率不超过 $1/k$。

所以错误率确实趋于 0。但看速率：

$$R=\frac{\text{消息长度}}{\text{传输长度}}=\frac{k}{kT}=\frac{1}{T}=\frac{1}{100\log_2 k}\xrightarrow[k\to\infty]{}0 .$$

也就是说，为了把错误率压到零，每传一个信息比特要发 $100\log_2 k$ 个信道比特，真正传过去的信息可以忽略。这不是我们想要的。

本讲的核心问题：能不能在错误率趋于 0 的同时，保持一个不随 $k$ 衰减的恒定速率？

Shannon 的回答是能，而且能到多快有一个精确的界线。

时间轴

速率与编解码

把消息写成长度 $k=Rn$ 的比特串，编码后变成长度 $n$ 的串发出去。形式化地：

• 编码 $\mathrm{Enc}:\{0,1\}^{Rn}\to\{0,1\}^{n}$；
• 解码 $\mathrm{Dec}:\{0,1\}^{n}\to\{0,1\}^{Rn}$；
• 速率 $R=k/n\in(0,1)$。

消息 $m$ 经编码得到 $c=\mathrm{Enc}(m)$，通过信道后收到 $\tilde c$，解码得到 $\hat m=\mathrm{Dec}(\tilde c)$。对固定的 $R$ 与 $n$，定义最优的最坏情况错误率

$$\lambda^*(R,n)=\min_{\mathrm{Enc},\mathrm{Dec}}\ \max_{m\in\{0,1\}^{Rn}}\ \Pr\big[\hat m\ne m\big].$$

两个 $\min$ 与 $\max$ 的顺序很关键：我们要求同一个编解码方案对所有消息都好，而不是平均来说好。Shannon 定理就是关于 $\lambda^*(R,n)$ 在 $n\to\infty$ 时的行为。

Shannon 噪声编码定理

设二元熵 $H(p)=-p\log_2 p-(1-p)\log_2(1-p)$，称

$$C=1-H(p)$$

为信道的容量。定理包含两个方向。

逆定理（converse）。 若 $R>C$，则 $\lambda^*(R,n)\to1$。

也就是说，速率超过容量时，无论设计什么编解码方案，都存在一些消息，其成功解码的概率趋于 0——错误率反而趋于 1，通信彻底失败。

可达性（achievability）。 若 $R<C$，则 $\lambda^*(R,n)\to0$。

也就是说，存在一个编解码方案，使所有消息的错误率同时趋于 0，而速率保持恒定。

两个方向合起来：容量 $C$ 是可靠通信的精确速率上限。

数值与直觉

取 $p=1/3$：

$$H\!\left(\tfrac13\right)=-\tfrac13\log_2\tfrac13-\tfrac23\log_2\tfrac23\approx0.918, \qquad C\approx0.082 .$$

容量很小，但严格为正——重复码的速率趋于 0，而最优方案能以约 0.082 比特/信道使用的速率可靠传输。

几个边界情形：

• $p=0$：信道不翻转，$H(0)=0$，$C=1$，可以满速传输。
• $p=1$：每一位都翻转，$H(1)=0$，$C=1$。接收方把每一位取反即可，容量同样是满的。
• $p=1/2$：$H(1/2)=1$，$C=0$。输出与输入完全独立，信道只是随机吐比特，不可能传信息。
• $p=2/3$：$H(2/3)=H(1/3)<1$，$C\approx0.082>0$。多数表决失效，但少数表决有效：因为翻转概率大于一半，取与多数相反的那个值。

注意 $H(p)=H(1-p)$，所以容量关于 $p=1/2$ 对称。

证明策略：随机码本

重复码失败的原因是码本太小、结构太规整。Shannon 证明的思路相反：让码本随机。

具体地，令

$$M=2\cdot 2^{Rn}$$

并从 $\{0,1\}^n$ 中独立均匀地抽取 $M$ 个向量 $c_1,\dots,c_M$，作为 $M$ 条消息的码字。多出来的因子 2 是留给后面筛选的余量。

随机码本的妙处在于：分析「另一个随机码字是否落在某个区域里」时，不需要知道任何结构，只需要数区域的大小。

环

对向量 $c\in\{0,1\}^n$ 与宽度参数 $\gamma>0$，定义环

$$\mathrm{Ring}_\gamma(c)=\Big\{\tilde c\in\{0,1\}^n:\ \big|d_H(c,\tilde c)-pn\big|\le\gamma n\Big\},$$

其中 $d_H$ 是 Hamming 距离，即两个串在多少个坐标上不同。

为什么半径取 $pn$？因为发送 $c$ 后，每一位独立地以概率 $p$ 翻转，所以 $d_H(c,\tilde c)$ 的期望正是 $pn$。由弱大数定律，实际距离以极高概率落在期望附近。$\gamma$ 是一个随 $n\to\infty$ 趋于 0 的宽度，用来给「附近」一个容差。

关键引理

引理。 设码本随机抽取，$c_i$ 是其中一条码字，$\tilde c$ 是 $c_i$ 经过 BSC 的输出。则对适当选取的 $\gamma$，当 $n$ 充分大时

$$\Pr\Big[\tilde c\in\mathrm{Ring}_\gamma(c_i)\ \text{且}\ \tilde c\notin\bigcup_{j\ne i}\mathrm{Ring}_\gamma(c_j)\Big]\ \ge\ 1-\varepsilon,$$

其中 $\varepsilon\to0$。

为什么这条引理足够？ 若事件发生，解码就有一个明确的规则：收到 $\tilde c$ 后，检查它落在哪个码字的环里；引理保证恰好只有一个这样的码字，那就是 $c_i$，于是解出 $m_i$。解码器只需要遍历码本、计算 Hamming 距离。

证明引理的三件工具

工具一：Stirling 公式给出环的大小

从 $\binom{n}{pn}$ 出发。用 $n!\approx(n/e)^n\sqrt{2\pi n}$：

$$\binom{n}{pn} =\frac{n!}{(pn)!\,((1-p)n)!} \approx \frac{(n/e)^n}{(pn/e)^{pn}\,((1-p)n/e)^{(1-p)n}}\cdot\frac{\sqrt{2\pi n}}{\sqrt{2\pi pn}\sqrt{2\pi(1-p)n}} .$$

前一个因子化简为

$$\frac{1}{p^{pn}(1-p)^{(1-p)n}}=2^{-n\big(p\log_2 p+(1-p)\log_2(1-p)\big)}=2^{nH(p)} .$$

后一个因子是 $\Theta(1/\sqrt n)$，取对数后只有 $O(\log n)$。于是

$$\frac1n\log_2\binom{n}{pn}\xrightarrow[n\to\infty]{}H(p).$$

把 $|d-pn|\le\gamma n$ 的所有距离层加起来，层数至多 $2\gamma n+1$，每层不超过最大值，得到

$$\big|\mathrm{Ring}_\gamma(c)\big|\ \le\ 2^{(H(p)+\gamma)n}.$$

这就是熵在信道编码里出现的位置：环的体积由熵决定。

工具二：弱大数定律保证落在自己的环里

$d_H(c_i,\tilde c)$ 是 $n$ 个独立指示变量之和，每个以概率 $p$ 取 1。由 Chebyshev 不等式（或弱大数定律），

$$\Pr\Big[\big|d_H(c_i,\tilde c)-pn\big|>\gamma n\Big]\ \le\ \frac{p(1-p)}{\gamma^2 n}\ \xrightarrow[n\to\infty]{}\ 0 .$$

取 $\gamma$ 适当（例如 $\gamma\to0$ 但 $\gamma^2n\to\infty$），失败概率可以压到 $\varepsilon/2$ 以下。

工具三：并集界控制「落进别人的环」

先固定 $j\ne i$。关键一步是把事件改写：

$$\tilde c\in\mathrm{Ring}_\gamma(c_j) \iff c_j\in\mathrm{Ring}_\gamma(\tilde c),$$

因为环的条件只涉及 Hamming 距离，而距离是对称的。改写之后，$\tilde c$ 已经固定，$c_j$ 是独立均匀抽取的随机向量。于是

$$\Pr\big[\tilde c\in\mathrm{Ring}_\gamma(c_j)\big] =\frac{\big|\mathrm{Ring}_\gamma(\tilde c)\big|}{2^n} \le\frac{2^{(H(p)+\gamma)n}}{2^n}.$$

这一步是整个证明的技巧核心：如果不改写，就要分析「收到的东西恰好落在某个特定随机码字的环里」；改写之后，变成了「一个均匀随机的串落在固定集合里」，概率就是体积比。

对所有 $j\ne i$ 用并集界：

$$\Pr\Big[\tilde c\in\bigcup_{j\ne i}\mathrm{Ring}_\gamma(c_j)\Big] \le M\cdot\frac{2^{(H(p)+\gamma)n}}{2^n} =2^{1+Rn}\cdot 2^{(H(p)+\gamma)n-n}.$$

指数部分是

$$1+n\big(R+H(p)+\gamma-1\big)=1+n\big(R-(1-H(p))+\gamma\big).$$

只要 $R<1-H(p)$，取 $\gamma<\tfrac12\big(1-H(p)-R\big)$，指数以线性速度趋于 $-\infty$，概率趋于 0。

把工具二与工具三合起来，就得到关键引理。

从「平均好」到「存在一个好码本」

引理说的是：对随机抽取的码本、随机选中的消息，解码失败概率平均不超过 $\varepsilon$。但我们要证明的是存在一个固定的码本，对所有消息都好。这两件事不一样，需要两步收尾。

第一步：概率方法

对码本 $\mathcal C$ 与消息 $i$，令 $E_i(\mathcal C)$ 为「第 $i$ 条消息顺利解码」的事件，$\lambda_i(\mathcal C)=1-\Pr[E_i(\mathcal C)]$ 是它在该码本下的失败概率。引理给出

$$\mathbb E_{\mathcal C}\left[\frac1M\sum_{i=1}^{M}\lambda_i(\mathcal C)\right]\le\varepsilon .$$

一个非负随机变量的期望不超过 $\varepsilon$，必然存在某个具体取值不超过 $\varepsilon$。所以存在一个码本 $\mathcal C$，使它的平均失败概率不超过 $\varepsilon$。

第二步：Markov 界剪掉坏码字

现在有了一个「平均好」的码本，但个别码字可能很糟。设坏码字（$\lambda_i>2\varepsilon$）的比例为 $\alpha$。平均值至少是 $\alpha\cdot2\varepsilon$，而已知平均值不超过 $\varepsilon$，于是 $\alpha\le1/2$：至少一半码字的失败概率不超过 $2\varepsilon$。

把坏码字全部删掉，保留至少 $M/2=2^{Rn}$ 个码字。这仍然是一个 $(Rn,n)$ 编码：消息数正好是 $2^{Rn}$。对保留下来的每个码字，失败概率都不超过 $2\varepsilon$。重命名消息后，得到一个对所有消息失败概率都不超过 $2\varepsilon$ 的编解码方案。

令 $n\to\infty$ 使 $\varepsilon\to0$，就得到 $\lambda^*(R,n)\to0$。可达性证完。

逆定理：为什么超过容量必败

逆定理的完整证明需要一些技术引理，课程只给直觉。设存在一个速率 $R$、成功概率至少为 $\varepsilon$ 的方案。

考虑发送 $c_i$ 时收到的向量。它落在 $\mathrm{Ring}_\gamma(c_i)$ 内的概率接近 1（工具二）。既然整体成功概率至少是 $\varepsilon$，那么在环内也必须有一批被正确解码的输出，至少占环的 $\varepsilon/2$ 比例（丢掉环外的部分，比例只会略降）。

现在看不同 $i$ 的这些「被解码为 $i$ 的环内向量」集合。它们必须两两不交：解码函数把每个收到的向量映到唯一一条消息，不可能同时属于两条消息的解码集。

于是总体积满足

$$M\cdot\frac{\varepsilon}{2}\cdot\big|\mathrm{Ring}_\gamma(c)\big|\ \le\ 2^n .$$

代入 $|\mathrm{Ring}_\gamma(c)|\approx2^{H(p)n}$：

$$M\ \le\ \frac{2^{n(1-H(p))}}{\varepsilon/2}, \qquad\text{即}\qquad R=\frac{\log_2 M}{n}\ \le\ 1-H(p)+o(1).$$

所以速率一旦超过 $1-H(p)$，假设的成功概率 $\varepsilon$ 就无法维持，矛盾。

这个证明的局限

随机码本让证明变得干净，但它在工程上同样不可行：码本有 $2^{Rn}$ 条码字，每条长 $n$，存下来就是指数级空间；解码要遍历整个码本算距离，时间也是指数级。

这正是下一讲转向线性码的动机：不再逐条列出码字，而是用矩阵描述——消息是向量，编码就是矩阵乘法，码本由矩阵隐式给出。存储只需 $O(n^2)$，解码可以用线性代数加速。

另一个隐含假设是信道随机翻转。若换成对手模型——对手有预算地挑选至多 $pn$ 个位置破坏——同样的定理不再成立，需要另作分析。

本节结论

• BSC(p) 以概率 $p$ 独立翻转每一位；重复码能把错误率压到零，但速率趋于零。
• 速率 $R=k/n$；$\lambda^*(R,n)$ 是对所有消息取最坏、对所有编解码方案取最优的失败概率。
• 容量 $C=1-H(p)$：$R>C$ 时失败概率趋于 1，$R<C$ 时可以趋于 0。
• $p=1/2$ 时 $C=0$（信道不看输入）；$p=2/3$ 时仍可通信，改用少数表决。
• 可达性证明用随机码本：码字随机抽取，解码找「环」。
• 环的体积是 $2^{H(p)n}$，这是熵在信道编码中的来源。
• 关键技巧是把 $\Pr[\tilde c\in\mathrm{Ring}(c_j)]$ 改写成 $\Pr[c_j\in\mathrm{Ring}(\tilde c)]$，从而利用 $c_j$ 的均匀性。
• 概率方法 + Markov 界把「平均好」转成「存在固定码本，对所有消息都好」。

理解检验

1. 重复码为什么不可取？请给出速率与错误率的具体权衡。

参考答案：重复 $T$ 次后，单块多数表决的错误概率由 Chernoff 界随 $T$ 指数下降。取 $T=100\log_2 k$ 可使单块错误率低于 $1/k^2$，再对 $k$ 块用并集界，整条消息的错误率不超过 $1/k$，确实趋于 0。

但速率是

$$R=\frac{k}{kT}=\frac{1}{T}=\frac{1}{100\log_2 k}\to0 .$$

传输长度里绝大部分是冗余，每传一个信息比特要发约 $100\log_2 k$ 个信道比特。可靠性与速率不可兼得——这正是 Shannon 定理要打破的直觉。

2. 为什么 $p=1/2$ 时容量为 0？$p=2/3$ 时又为什么仍能通信？

参考答案：$p=1/2$ 时，无论发送 0 还是 1，收到 0 和 1 的概率都是 $1/2$。输出分布与输入无关，信道只是随机产生比特，接收方无法从中获得任何关于消息的信息，所以 $C=1-H(1/2)=0$。

$p=2/3$ 时，每一位有 $2/3$ 的概率被翻转，$H(2/3)=H(1/3)$，容量仍为 $1-H(1/3)\approx0.082>0$。多数表决会错，但少数表决正确：接收方取与多数相反的值，等价于把信道看成翻转概率 $1/3$ 的情形。这说明信道模型里「翻转」与「不翻转」的角色可以互换。

3. 关键引理把 $\Pr[\tilde c\in\mathrm{Ring}(c_j)]$ 改写成 $\Pr[c_j\in\mathrm{Ring}(\tilde c)]$，为什么要这样做？

参考答案：改写前，$\tilde c$ 是随机变量（依赖信道的翻转），$c_j$ 被视为固定的码字；要计算「随机输出落进某个固定码字的环」的概率，需要知道输出的分布，比较麻烦。

改写后，$\tilde c$ 固定下来，$c_j$ 是独立均匀抽取的随机向量。此时概率就是体积比：

$$\Pr[c_j\in\mathrm{Ring}(\tilde c)]=\frac{|\mathrm{Ring}(\tilde c)|}{2^n}.$$

这正好可以用工具一（环的大小）来估计。这一步依赖两个事实：Hamming 距离对称，所以「属于」关系可以互换；码字独立均匀抽取，所以 $c_j$ 与 $\tilde c$ 无关。

4. 关键引理的证明用了哪三件工具？各自负责哪一部分？

参考答案：

1. Stirling 公式：估计二项式系数，得到环的体积 $\le2^{(H(p)+\gamma)n}$；
2. 弱大数定律 / Chebyshev：$d_H(c_i,\tilde c)$ 是 $n$ 个独立指示变量之和，期望 $pn$，所以以概率 $\ge1-\varepsilon/2$ 落在自己的环内；
3. 并集界：对 $M-1$ 个其他码字逐个估计「落进其环」的概率，再求和，得到总失败概率 $\le M\cdot2^{(H(p)+\gamma)n}/2^n$，在 $R<1-H(p)$ 时趋于 0。

三者合起来给出「落在自己环内、且不落在任何别的环内」的概率 $\ge1-\varepsilon$。

5. 已经证明了「随机码本平均好」，为什么还需要概率方法与 Markov 界？

参考答案：引理给的是对随机码本取平均、对随机消息取平均后的失败概率小。但我们要的是一个固定码本，且对每条消息都成立。两个平均都不能直接去掉。

第一步用概率方法：非负随机变量的平均值 $\le\varepsilon$，说明存在某个码本其平均值 $\le\varepsilon$，去掉对码本的平均。

第二步用 Markov 界：在这个码本内，若超过一半的码字失败概率 $>2\varepsilon$，平均值就会超过 $\varepsilon$，矛盾。所以至少一半码字满足 $\lambda_i\le2\varepsilon$。删掉其余码字，剩下 $2^{Rn}$ 条，仍是一个 $(Rn,n)$ 编码，且每条消息的失败率都不超过 $2\varepsilon$。再去掉对消息的平均。

6. 为什么环的半径选在 $pn$ 附近，而不是别的值？$\gamma$ 起什么作用？

参考答案：发送 $c$ 后，每一位独立地以概率 $p$ 翻转，所以 Hamming 距离 $d_H(c,\tilde c)$ 的期望是 $pn$。实际收到的向量几乎必然落在期望附近（弱大数定律），所以把解码区域设为以 $pn$ 为半径的壳层是自然的——大部分概率质量都在这里。

$\gamma$ 是壳层的半宽，随 $n\to\infty$ 趋于 0，但取得足够大以保证 Chebyshev 界有效（典型地 $\gamma^2n\to\infty$）。它给「附近」留出容差，同时在体积估计里只贡献 $2^{\gamma n}$ 的因子；只要 $\gamma$ 小于 $1-H(p)-R$ 的一半，并集界仍然趋于 0。

7. 用计数论证说明：速率超过 $1-H(p)$ 时不可能可靠通信。

参考答案：假设某方案成功概率至少为 $\varepsilon$。发送 $c_i$ 时，输出以接近 1 的概率落在 $\mathrm{Ring}(c_i)$ 内；既然总成功概率是 $\varepsilon$，环内至少 $\varepsilon/2$ 比例的向量被正确解码为 $i$（丢掉环外部分只会让比例略降）。

对不同的 $i$，这些「解码为 $i$」的集合必须两两不交，否则同一个输出会对应两条消息，与解码函数是函数矛盾。

于是所有集合的总体积不超过全部 $2^n$ 个向量：

$$M\cdot\frac{\varepsilon}{2}\cdot|\mathrm{Ring}|\ \le\ 2^n .$$

代入 $|\mathrm{Ring}|\approx2^{H(p)n}$，得 $M\le2^{(1-H(p))n}/\varepsilon$，即 $R\le1-H(p)+o(1)$。所以 $R>1-H(p)$ 会迫使 $\varepsilon\to0$，成功概率消失。

8. 随机码本在理论上最优，为什么实际不能用？下一讲怎么解决？

参考答案：码本包含 $2^{Rn}$ 条码字，每条长 $n$，存储是指数级的；解码要遍历所有码字计算 Hamming 距离，时间也是指数级的。这与上一讲 Shannon 压缩编码的困境相同：存在性证明不给出高效实现。

下一讲用线性码：码本不再逐条列出，而由一个矩阵 $G$ 定义，编码是 $m\mapsto mG$。存储降到 $O(n^2)$，结构由线性代数保证，解码可以用校验矩阵与综合（syndrome）实现，复杂度是多项式级。代价是需要额外设计好的线性码（如 Hamming 码、Reed–Solomon 码），而不是「随机抽一个就好」。

与前后课的关系

上一讲解决了无噪声压缩，得到 $H\le L\le H+1$；本讲把问题换成有噪声传输，得到容量 $C=1-H(p)$ 与「低于容量即可靠」的定理。两讲的证明共享同一套工具：Stirling 公式把组合计数化成熵，尾界刻画典型性。

下一讲由 Peter Shor 讲线性码：用矩阵隐式描述码本，用最小距离刻画纠错能力，并给出 Hamming 码这一具体构造。再下一讲是 Reed–Solomon 码，用有限域上的多项式达到更大的最小距离。之后课程转向密码学与秘密共享。

The problem: bits get flipped

Earlier lectures compressed: how to send the same information in fewer bits. This one goes the other way — the channel itself makes mistakes.

The binary symmetric channel (BSC) has a parameter $p$: each input bit is flipped with probability $p$ and passed through with probability $1-p$, independently across positions. The receiver does not know which bits were flipped.

Take $p=1/3$ concretely. After compressing the message to its shortest form, every bit has a one-in-three chance of being wrong. Can the original message still be recovered reliably?

Repetition codes: correction at a steep price

The straightforward idea is a repetition code: send each bit $T$ times and decode each block by majority vote.

Choose $T=100\log_2 k$, where $k$ is the message length. A block of $T$ bits has a binomial number of flips with mean $Tp=T/3$, and majority vote fails only when more than half are flipped. Chernoff's bound makes that probability decay exponentially in $T$; a large enough constant gets it below $1/k^2$ per block. A union bound over the $k$ blocks then gives overall failure probability at most $1/k$.

So the error does go to zero. But look at the rate:

$$R=\frac{\text{message length}}{\text{transmission length}}=\frac{k}{kT}=\frac1T=\frac{1}{100\log_2 k}\xrightarrow[k\to\infty]{}0 .$$

To drive the error to zero we spend about $100\log_2 k$ channel bits per information bit, so almost no information gets through. That is not what we want.

The central question: can the error go to zero while the rate stays bounded away from zero?

Shannon's answer is yes, and there is a sharp threshold.

Timeline

Rate, encoding, decoding

Write the message as $k=Rn$ bits and transmit $n$ bits. Formally:

• encoding $\mathrm{Enc}:\{0,1\}^{Rn}\to\{0,1\}^{n}$;
• decoding $\mathrm{Dec}:\{0,1\}^{n}\to\{0,1\}^{Rn}$;
• rate $R=k/n\in(0,1)$.

Message $m$ becomes $c=\mathrm{Enc}(m)$, the channel returns $\tilde c$, and the decoder produces $\hat m=\mathrm{Dec}(\tilde c)$. For fixed $R$ and $n$, define the optimal worst-case error

$$\lambda^*(R,n)=\min_{\mathrm{Enc},\mathrm{Dec}}\ \max_{m\in\{0,1\}^{Rn}}\ \Pr\big[\hat m\ne m\big].$$

The order of $\min$ and $\max$ matters: one encoder-decoder pair must work for every message, not merely on average. Shannon's theorem describes the behaviour of $\lambda^*(R,n)$ as $n\to\infty$.

Shannon's noisy coding theorem

Let $H(p)=-p\log_2 p-(1-p)\log_2(1-p)$ be the binary entropy and call

$$C=1-H(p)$$

the capacity of the channel. The theorem has two directions.

Converse. If $R>C$, then $\lambda^*(R,n)\to1$.

Above capacity, no encoder-decoder pair can do better than fail: some messages have success probability tending to zero, so the error approaches one.

Achievability. If $R<C$, then $\lambda^*(R,n)\to0$.

Below capacity, some pair drives the error of every message to zero while holding the rate constant.

Together: capacity is the exact rate at which reliable communication is possible.

Numbers and intuition

For $p=1/3$,

$$H\!\left(\tfrac13\right)=-\tfrac13\log_2\tfrac13-\tfrac23\log_2\tfrac23\approx0.918, \qquad C\approx0.082 .$$

Small but strictly positive — repetition codes have rate tending to zero, while the optimum reliably sends about $0.082$ bits per channel use.

Boundary cases:

• $p=0$: no flips, $H(0)=0$, $C=1$; transmit at full rate.
• $p=1$: every bit flips, $H(1)=0$, $C=1$; the receiver complements every bit and recovers everything.
• $p=1/2$: $H(1/2)=1$, $C=0$. The output is independent of the input, so no information can pass.
• $p=2/3$: $H(2/3)=H(1/3)<1$, so $C\approx0.082>0$. Majority vote fails, but minority vote works: because more than half the bits flip, take the opposite of the majority.

Note $H(p)=H(1-p)$, so capacity is symmetric about $p=1/2$.

Proof strategy: random codebooks

Repetition fails because the codebook is small and rigid. Shannon's proof does the opposite: choose the codebook at random.

Let

$$M=2\cdot 2^{Rn}$$

and draw $M$ vectors $c_1,\dots,c_M$ independently and uniformly from $\{0,1\}^n$ as codewords for $M$ messages. The extra factor of 2 is slack for a pruning step later.

The virtue of randomness is that questions about "does another codeword fall in this region" become pure counting: no structure to analyse.

Rings

For $c\in\{0,1\}^n$ and a width $\gamma>0$, the ring

$$\mathrm{Ring}_\gamma(c)=\Big\{\tilde c\in\{0,1\}^n:\ \big|d_H(c,\tilde c)-pn\big|\le\gamma n\Big\},$$

where $d_H$ is the Hamming distance, the number of coordinates on which the two strings differ.

Why radius $pn$? After sending $c$, each bit flips independently with probability $p$, so $d_H(c,\tilde c)$ has mean exactly $pn$. The weak law puts the actual distance near the mean with overwhelming probability. The parameter $\gamma$ is a tolerance that tends to zero as $n\to\infty$.

The key lemma

Lemma. With a random codebook, if $c_i$ is a codeword and $\tilde c$ is its output through the BSC, then for a suitable $\gamma$ and large $n$,

$$\Pr\Big[\tilde c\in\mathrm{Ring}_\gamma(c_i)\ \text{and}\ \tilde c\notin\bigcup_{j\ne i}\mathrm{Ring}_\gamma(c_j)\Big]\ \ge\ 1-\varepsilon,$$

where $\varepsilon\to0$.

Why this suffices. If the event holds, decoding has a simple rule: on receiving $\tilde c$, check which codeword's ring contains it. The lemma guarantees exactly one such codeword, namely $c_i$, so the message is recovered. The decoder only walks the codebook computing Hamming distances.

Three tools for the lemma

Tool 1: Stirling gives the ring size

Start from $\binom{n}{pn}$ and use $n!\approx(n/e)^n\sqrt{2\pi n}$:

$$\binom{n}{pn} =\frac{n!}{(pn)!\,((1-p)n)!} \approx \frac{(n/e)^n}{(pn/e)^{pn}\,((1-p)n/e)^{(1-p)n}}\cdot\frac{\sqrt{2\pi n}}{\sqrt{2\pi pn}\sqrt{2\pi(1-p)n}} .$$

The first factor simplifies to

$$\frac{1}{p^{pn}(1-p)^{(1-p)n}}=2^{-n\big(p\log_2 p+(1-p)\log_2(1-p)\big)}=2^{nH(p)} .$$

The second is $\Theta(1/\sqrt n)$, contributing only $O(\log n)$ after taking logs. Hence

$$\frac1n\log_2\binom{n}{pn}\xrightarrow[n\to\infty]{}H(p).$$

Summing over the distances with $|d-pn|\le\gamma n$ adds at most $2\gamma n+1$ layers, so

$$\big|\mathrm{Ring}_\gamma(c)\big|\ \le\ 2^{(H(p)+\gamma)n}.$$

This is where entropy enters channel coding: the volume of a ring is governed by entropy.

Tool 2: the weak law keeps us in our own ring

$d_H(c_i,\tilde c)$ is a sum of $n$ independent indicators, each 1 with probability $p$. Chebyshev gives

$$\Pr\Big[\big|d_H(c_i,\tilde c)-pn\big|>\gamma n\Big]\ \le\ \frac{p(1-p)}{\gamma^2 n}\ \xrightarrow[n\to\infty]{}\ 0 .$$

With a suitable $\gamma$ (for instance $\gamma\to0$ but $\gamma^2n\to\infty$), this failure probability drops below $\varepsilon/2$.

Tool 3: a union bound keeps us out of other rings

Fix $j\ne i$. The key step is to rewrite the event:

$$\tilde c\in\mathrm{Ring}_\gamma(c_j) \iff c_j\in\mathrm{Ring}_\gamma(\tilde c),$$

because the ring condition only involves Hamming distance, which is symmetric. After the rewrite, $\tilde c$ is fixed and $c_j$ is an independent uniform vector, so

$$\Pr\big[\tilde c\in\mathrm{Ring}_\gamma(c_j)\big] =\frac{\big|\mathrm{Ring}_\gamma(\tilde c)\big|}{2^n} \le\frac{2^{(H(p)+\gamma)n}}{2^n}.$$

This is the technical heart of the proof. Without the rewrite we would need the distribution of the received vector; with it, the probability is a simple volume ratio.

A union bound over all $j\ne i$ gives

$$\Pr\Big[\tilde c\in\bigcup_{j\ne i}\mathrm{Ring}_\gamma(c_j)\Big] \le M\cdot\frac{2^{(H(p)+\gamma)n}}{2^n} =2^{1+Rn}\cdot 2^{(H(p)+\gamma)n-n}.$$

The exponent is

$$1+n\big(R+H(p)+\gamma-1\big)=1+n\big(R-(1-H(p))+\gamma\big).$$

If $R<1-H(p)$, choose $\gamma<\tfrac12\big(1-H(p)-R\big)$ and the exponent goes to $-\infty$ linearly. The probability vanishes.

Tools 2 and 3 together prove the key lemma.

From "usually good" to "one good codebook"

The lemma says: averaging over random codebooks and random messages, the failure probability is at most $\varepsilon$. What we need is a single fixed codebook that is good for every message. Two steps close the gap.

Step 1: the probabilistic method

For a codebook $\mathcal C$ and message $i$, let $E_i(\mathcal C)$ be the event that message $i$ decodes correctly and $\lambda_i(\mathcal C)=1-\Pr[E_i(\mathcal C)]$ its failure probability. The lemma gives

$$\mathbb E_{\mathcal C}\left[\frac1M\sum_{i=1}^{M}\lambda_i(\mathcal C)\right]\le\varepsilon .$$

A nonnegative random variable with mean at most $\varepsilon$ must take some value at most $\varepsilon$. Hence some codebook $\mathcal C$ has average failure probability at most $\varepsilon$.

Step 2: Markov's bound prunes bad codewords

Now the average is good, but individual codewords may be bad. By Markov's bound, if the average is at most $\varepsilon$, then the indices with $\lambda_i>2\varepsilon$ form at most half of all indices; otherwise the average would exceed $\varepsilon$.

Delete the bad codewords. At least $M/2=2^{Rn}$ remain, which is exactly an $(Rn,n)$ code: the message count is $2^{Rn}$. For every surviving codeword the failure probability is at most $2\varepsilon$. Relabel the messages and we have a code correct for all messages with error at most $2\varepsilon$.

Letting $n\to\infty$ so that $\varepsilon\to0$ gives $\lambda^*(R,n)\to0$. Achievability is proved.

Converse: why exceeding capacity must fail

The lecture sketches the converse; a full proof needs additional technical lemmas. Suppose a scheme with rate $R$ succeeds with probability at least $\varepsilon$.

Send $c_i$. The received vector lies in $\mathrm{Ring}_\gamma(c_i)$ with probability close to 1 (Tool 2). Since the overall success probability is at least $\varepsilon$, at least an $\varepsilon/2$ fraction of the ring must decode correctly to $i$ (discarding the part outside the ring changes the fraction only slightly).

Now consider the sets "ring vectors that decode to $i$" for different $i$. They must be pairwise disjoint: the decoder maps each received vector to a single message, so one vector cannot belong to two messages' decoding sets.

Therefore the total volume is at most the whole space:

$$M\cdot\frac{\varepsilon}{2}\cdot\big|\mathrm{Ring}_\gamma(c)\big|\ \le\ 2^n .$$

Substituting $|\mathrm{Ring}_\gamma(c)|\approx2^{H(p)n}$,

$$M\ \le\ \frac{2^{n(1-H(p))}}{\varepsilon/2}, \qquad\text{so}\qquad R=\frac{\log_2 M}{n}\ \le\ 1-H(p)+o(1).$$

If $R>1-H(p)$, the assumed success probability $\varepsilon$ cannot be maintained — a contradiction.

Limits of this proof

The random codebook makes the proof clean but is just as impractical as Shannon's compression scheme: $2^{Rn}$ codewords of length $n$ require exponential storage, and decoding scans the entire codebook at exponential cost.

The next lecture turns to linear codes: instead of listing codewords, describe them with a matrix. Messages are vectors, encoding is a matrix product, and the codebook is given implicitly, in $O(n^2)$ space, with linear-algebraic decoding.

A second hidden assumption is that the channel flips bits randomly. Under an adversary with a budget of $pn$ corruptions, the same theorem does not hold and needs separate analysis.

What this lecture establishes

• BSC(p) flips each bit independently with probability $p$; repetition codes drive the error to zero but the rate to zero.
• Rate $R=k/n$; $\lambda^*(R,n)$ is the worst-case-over-messages, best-over-codes failure probability.
• Capacity $C=1-H(p)$: above it the error tends to 1, below it the error tends to 0.
• At $p=1/2$, $C=0$ (the channel ignores its input); at $p=2/3$ communication is still possible via minority vote.
• Achievability uses a random codebook with ring decoding.
• A ring has volume $2^{H(p)n}$; this is where entropy enters channel coding.
• The key trick rewrites $\Pr[\tilde c\in\mathrm{Ring}(c_j)]$ as $\Pr[c_j\in\mathrm{Ring}(\tilde c)]$ to exploit uniformity.
• The probabilistic method plus Markov's bound converts "good on average" into "a fixed codebook good for all messages".

Comprehension check

1. Why are repetition codes unsatisfactory? Give the concrete rate-error tradeoff.

Reference answer: Repeating each bit $T$ times makes the per-block majority-vote error decay exponentially in $T$ by Chernoff. With $T=100\log_2 k$, the per-block error is below $1/k^2$, and a union bound over $k$ blocks gives overall error at most $1/k$, which does tend to zero.

But the rate is

$$R=\frac{k}{kT}=\frac1T=\frac{1}{100\log_2 k}\to0 .$$

Almost all transmitted bits are redundancy: roughly $100\log_2 k$ channel bits per information bit. Reliability and rate cannot both be won this way — exactly the intuition Shannon's theorem overturns.

2. Why is capacity zero at $p=1/2$? Why can we still communicate at $p=2/3$?

Reference answer: At $p=1/2$, the received bit is 0 or 1 with equal probability regardless of what was sent. The output distribution is independent of the input, so the receiver learns nothing, and $C=1-H(1/2)=0$.

At $p=2/3$, each bit flips with probability $2/3$ and $H(2/3)=H(1/3)$, so the capacity is $1-H(1/3)\approx0.082>0$. Majority vote fails, but minority vote succeeds: take the opposite of the majority. Equivalently, view the channel as one that flips with probability $1/3$ and invert every received bit. Flipping and not flipping are interchangeable roles.

3. The key lemma rewrites $\Pr[\tilde c\in\mathrm{Ring}(c_j)]$ as $\Pr[c_j\in\mathrm{Ring}(\tilde c)]$. Why?

Reference answer: Before the rewrite, $\tilde c$ is random (it depends on the channel flips) while $c_j$ is treated as fixed; computing "the random output lands in a fixed codeword's ring" requires the output distribution.

After the rewrite, $\tilde c$ is fixed and $c_j$ is an independent uniform vector. The probability becomes a volume ratio:

$$\Pr[c_j\in\mathrm{Ring}(\tilde c)]=\frac{|\mathrm{Ring}(\tilde c)|}{2^n},$$

which Tool 1 can estimate. The rewrite relies on two facts: Hamming distance is symmetric, so membership can be swapped, and the codewords are drawn independently and uniformly, so $c_j$ is independent of $\tilde c$.

4. Which three tools prove the key lemma, and what does each contribute?

Reference answer:

1. Stirling's formula estimates the binomial coefficient, giving ring volume $\le2^{(H(p)+\gamma)n}$;
2. the weak law / Chebyshev shows $d_H(c_i,\tilde c)$, a sum of $n$ independent indicators with mean $pn$, lies in its own ring with probability at least $1-\varepsilon/2$;
3. a union bound over the other $M-1$ codewords bounds the probability of landing in any foreign ring by $M\cdot2^{(H(p)+\gamma)n}/2^n$, which vanishes when $R<1-H(p)$.

Together they give probability at least $1-\varepsilon$ of being in one's own ring and in no other.

5. We already showed "a random codebook is good on average". Why are the probabilistic method and Markov's bound still needed?

Reference answer: The lemma averages over random codebooks and over random messages. We need one fixed codebook good for every message, so both averages must be removed.

The probabilistic method removes the codebook average: a nonnegative random variable with mean at most $\varepsilon$ attains some value at most $\varepsilon$, so some codebook has average failure at most $\varepsilon$.

Markov's bound removes the message average inside that codebook: if more than half the codewords had failure probability above $2\varepsilon$, the average would exceed $\varepsilon$, a contradiction. So at least half satisfy $\lambda_i\le2\varepsilon$. Deleting the rest leaves $2^{Rn}$ codewords — still an $(Rn,n)$ code — with every message's failure probability at most $2\varepsilon$.

6. Why is the ring radius chosen near $pn$? What role does $\gamma$ play?

Reference answer: Each bit flips independently with probability $p$, so $d_H(c,\tilde c)$ has mean $pn$. The weak law puts the received vector near that mean with overwhelming probability, so a shell at radius $pn$ captures almost all the probability mass.

$\gamma$ is the half-width of the shell. It tends to zero as $n\to\infty$ but must be large enough for Chebyshev to apply (typically $\gamma^2n\to\infty$). It contributes only a factor $2^{\gamma n}$ to the volume estimate; as long as $\gamma$ is below half of $1-H(p)-R$, the union bound still vanishes.

7. Use a counting argument to show that rates above $1-H(p)$ cannot be reliable.

Reference answer: Suppose a scheme succeeds with probability at least $\varepsilon$. On sending $c_i$, the output lands in $\mathrm{Ring}(c_i)$ with probability close to 1, so at least an $\varepsilon/2$ fraction of that ring must decode correctly to $i$.

For different $i$, the sets of vectors decoding to $i$ must be pairwise disjoint — otherwise one received vector would map to two messages, contradicting that decoding is a function.

Hence the total volume is bounded by the whole space:

$$M\cdot\frac{\varepsilon}{2}\cdot|\mathrm{Ring}|\ \le\ 2^n .$$

With $|\mathrm{Ring}|\approx2^{H(p)n}$ this gives $M\le2^{(1-H(p))n}/\varepsilon$, i.e. $R\le1-H(p)+o(1)$. So $R>1-H(p)$ forces $\varepsilon\to0$, and success disappears.

8. The random codebook is theoretically optimal but impractical. How does the next lecture fix this?

Reference answer: The codebook holds $2^{Rn}$ codewords of length $n$ — exponential storage — and decoding scans all of them at exponential cost. This mirrors the earlier compression story, where the existence proof did not yield an efficient scheme.

The next lecture introduces linear codes: the codebook is described by a matrix $G$ and encoding is $m\mapsto mG$. Storage drops to $O(n^2)$, structure comes from linear algebra, and decoding uses a parity-check matrix and its syndrome in polynomial time. The price is that one must design good linear codes (Hamming, Reed–Solomon) rather than rely on a random draw.

Relation to neighbouring lectures

The previous lecture solved noiseless compression with $H\le L\le H+1$; this one switches to noisy transmission and obtains the capacity $C=1-H(p)$ together with the threshold theorem. Both proofs share the same machinery: Stirling turns combinatorial counts into entropy, and tail bounds characterise typicality.

The next lecture, by Peter Shor, covers linear codes: a matrix describes the codebook implicitly, minimum distance measures correction capability, and Hamming codes give a concrete construction. After that, Reed–Solomon codes reach larger minimum distance using polynomials over finite fields. The course then moves on to cryptography and secret sharing.