15 重复三遍不是答案

▷ 先猜一下

一条翻位率 10% 的线。用「每一位重复 n 遍 + 多数表决」的办法，要把出错率压到十亿分之一，n 要多大？

A 大约 7B 大约 15C 大约 35D 大约 100

最自然的想法

电话里没听清，你会说「再说一遍」。念一串数字给别人，你会念两遍。这个直觉深到我们几乎不把它当成一个「方法」。

把它写成编码：

# 重复 3 次码
要发的：  1  0  1
实际发：  111  000  111

# 收到的（p=0.1，翻了一位）：
          101  000  111
           ▲

# 多数表决：
          101 → 两个 1 一个 0 → 判为 1  ✓ 救回来了
          000 → 判为 0                 ✓
          111 → 判为 1                 ✓

有效。代价是：你发了 9 个比特，只传了 3 个比特的信息。码率 1/3。

它到底能救多少

重复 3 次之后，一位信息还会出错，当且仅当三位里翻了两位或三位：

P(错) = C(3,2)·p²·(1−p) + C(3,3)·p³
      = 3 × 0.01 × 0.9  +  1 × 0.001
      = 0.027 + 0.001
      = 【0.028】

# 从 10% 降到 2.8%。降了 3.6 倍。
# 代价：速度变成 1/3。

还不够好？那就重复更多次：

重复次数	码率	剩余错误率
1	1.000	1.0 × 10⁻¹
3	0.333	2.8 × 10⁻²
5	0.200	8.6 × 10⁻³
7	0.143	2.7 × 10⁻³
11	0.091	3.0 × 10⁻⁴
21	0.048	4.0 × 10⁻⁶
35	0.029	8.4 × 10⁻¹⁰

◆ 这条曲线的形状，就是 1948 年之前的世界观

看清楚它在说什么：

要让错误率 → 0，码率必须 → 0。

换句话说：可靠性和速度是一场零和交易。你想要几乎不出错？那你几乎就别想传东西。

这在当时是不言而喻的常识。整个通信工程的思路是「在给定的可靠性要求下，尽量少浪费」——没有人认为「既快又几乎不错」是一个可以追求的目标，就像没有人追求永动机。

为什么重复码这么烂

重复码的问题不在于「重复」这个想法，在于它把所有鸡蛋放在同一个位置上。

看这两种花掉 9 个比特的办法：

办法一（重复码）：
   3 个信息位，每个重复 3 遍
   111 000 111
   → 每个信息位由 3 个比特单独保护，各管各的
   → 如果某一组里翻了 2 个，这一位就完了，
      【其它两组一点忙都帮不上】

办法二（下一章的汉明码）：
   4 个信息位 + 3 个校验位 = 7 位
   → 每个校验位【同时监视好几个信息位】
   → 校验位之间的答案【交叉印证】
   → 于是 3 个校验位能定位 7 个位置中的任何一个错

◆ 关键差别：冗余是「各管各的」还是「合伙的」

重复码的冗余是局部的：第 1 组的两个副本只保护第 1 个信息位。

好的编码的冗余是全局的：每一个校验位都参与保护多个信息位，而多个校验位的答案组合起来能给出比单独看更多的信息。

3 个校验位有 8 种组合，正好能表示「没错」+「7 个位置各错一个」这 8 种情况。一位都不浪费。这就是下一章那个「完美码」的意思。

更一般地说，好的编码把信息摊开在整个码字上，让任何一小片损坏都能被其它部分共同推断出来。这个思想在纠错码、分布式存储（纠删码）、甚至神经网络的分布式表示里，是同一个。

▸ 在现实里：重复码没有绝迹

虽然重复码在编码理论里是反面教材，但它在几个地方仍然活着，而且理由充分：

TMR（三模冗余）。航天和核电站的关键控制器会跑三份，投票表决。这里保护的不是比特，是整台计算机——而计算机不像比特那样可以「交叉印证」，你没法让三台机器共享一个「校验位」。
关键控制字段。很多协议的头部里，最关键的那几位（比如「这是不是紧急帧」）会简单重复几遍，因为解码它的时候还来不及做复杂的纠错。
人类语言。「三点、下午三点、也就是十五点」——自然语言里到处是这种重复冗余。而且它比比特级的重复码聪明：它重复的是「意思」而不是「符号」，所以三次表述用的是不同的词，抗的是不同的错误。
DNS 的 anycast、CDN 的多副本。同一份数据放好几个地方——这也是重复码，只是单位是「整份文件」。

共同点：当被保护的单位无法「摊开」时，重复是唯一的办法。比特可以摊开，所以有汉明码；一台运行中的计算机摊不开，所以只能跑三份。

那个 18 倍的缺口

把这一章的结论和上一章放在一起：

翻位率 p = 0.1

香农说的容量：            C = 0.531 比特/次
重复码要达到 1e-9 错误率： 码率 = 0.029 比特/次

差距：0.531 / 0.029 = 【18.6 倍】

也就是说，如果香农是对的，那么在同样的可靠性要求下，存在一种编码方式能比重复码快 18 倍。

而且香农说的还不止这个。他说的是：码率只要低于 0.531，错误率就能压到任意小——不是「压到 1e-9」，是「你说多小就多小，1e-100 也行」，而码率不用继续降。

在 1948 年，这句话听起来像是在说永动机。

✗ 这个直觉是错的

「要更可靠，就必须发更多冗余；要多可靠，冗余就得多到什么程度——这是一个连续的权衡。」在码率低于容量的整个区间里，错误率都可以趋于 0。这不是一个连续权衡，是一个悬崖：容量以下随便走，容量以上寸步难行。

这个「悬崖」形状是香农第二定理最反直觉的部分。它意味着：

如果你的码率是 0.52（略低于容量 0.531），你可以做到几乎零错误；
如果你的码率是 0.54（略高于容量），你的错误率有一个下界，怎么设计都突破不了。

下一章会看到，汉明码的码率是 0.571——它站在悬崖的错误一侧。这不是汉明设计得不好，是算术上不允许。

◇ 结账

C：35 次，码率掉到 0.029

选 A 或 B 的人低估了「多数表决」有多不经济。每多重复两次，错误率大概只降一个数量级不到——而码率是线性往下掉的。

这一章的重点不是这个数字，是它旁边那个对照：香农说的容量是 0.531，是重复码的 18.6 倍。

把这个缺口记住。下一章要填的就是它。

这一章的一句话

重复码把「可靠」和「快」变成了零和交易：错误率要趋于 0，码率就得趋于 0。它烂的原因是冗余各管各的——而好的编码让冗余互相印证。

下一章是这本书里最重要的一个定理，也是二十世纪最反直觉的结论之一。香农在 1948 年证明了：那条零和交易线根本不存在。只要码率低于容量，错误率可以任意小。

而这个证明有一个让当时所有工程师抓狂的性质：它证明了好的编码存在，却不告诉你怎么造。接下来的 45 年，整个编码理论领域都在追那条线——而追上它的那一年是 1993 年。