纠错码入门：数据出错以后，电脑怎样把它改回来

一张二维码被弄脏了一小块，手机仍然可能扫出原来的内容。SSD 中某些存储单元的状态发生变化，读出的文件也未必跟着损坏。地铁里手机信号一路反射、衰减和混入噪声，视频流大多数时候仍能连续播放。

难点在于，接收方拿到的通常已经是受损后的结果，设备不能把原文重新调出来对照。它要判断哪里错了、该改成什么，只能依赖写入或发送时预先留下的线索。

这些线索就是纠错码。系统会给原始内容增加一些有规律的额外信息，让接收方能够检查数据是否满足约定，并在一定范围内恢复错误。纠错码的英文是 Error-Correcting Code，常缩写为 ECC。

纠错码容易被低估，恰恰因为它成功时不会跳出来邀功。操作系统拿到的是已经恢复过的数据，扫码器显示的是解出来的文本，浏览器收到的是网络协议继续交付的字节流。真正发生在底层的，是电荷、电压、无线波形、纸面污损这些并不干净的物理状态，被编码规则和解码算法重新约束回可以使用的数字结果。

从重复码看清纠错码的基本动作

我们先从最简单的重复码开始。它的核心思想是把每个原始二进制位重复多次。这个办法很浪费空间，也经不起太密集的错误，但规则足够直观，接收方能看见冗余怎样暴露异常，又怎样把少量错误改回来。

没有冗余时，错误看不出来

假设要保存的数据是 1011，读出来却成了 1001。如果接收方只看得到后者，就无法知道它有没有出错，因为 1001 本身也是合法的四位二进制数。

四位二进制一共有 16 种组合。如果这 16 种组合全都可以作为原始数据，那么任何一位发生变化，结果仍会落进这 16 种组合中。接收方没有理由把其中某个结果视为异常。

比特 是二进制的一位，取值为 0 或 1。

字节 通常由 8 个比特组成。纠错码讨论的错误，可以按单个比特计，也可以按一组比特组成的符号计，具体要看编码方式。

加了约束以后，恢复才有依据

要识别错误，就必须引入额外约束，让某些组合成为不应该出现的结果。最容易想到的办法，是把每一位重复三遍：

原始数据位    实际保存或发送
    0            000
    1            111

这样，三位组合中只有 000 和 111 合法。如果读到 101，就知道有些地方出了问题。它和 111 只差一位，和 000 差两位；在「最多出错一位」的条件下，原始数据只能是 1。

这就是三次重复码，多数表决是它的一种解码方法。它已经具备了纠错码的基本结构：

• 编码：把原始数据按照规则变成带有冗余的数据。
• 解码：根据收到的结果和编码规则，估计并恢复原始数据。
• 能力边界：错误不能超过这套规则和解码方法能够处理的范围。

原始数据编码后得到的完整序列，叫作码字。重复码里的 000 和 111 就是两个码字；它们都代表一位内容，但各占三位空间。

纠错需要的信息已经在编码阶段加进去了。保存或传输以后，即使其中一部分受损，剩下的部分仍可能足够确定原始内容。

可靠性提升，也伴随成本

假设每一位独立地以 1% 的概率出错，而且只考虑 0、1 互相翻转。单独保存一位时，读错概率就是 1%。保存三份并多数表决，则要至少错两份才会判断错。

恰好错两份有三种位置组合，三份全错又是一种情况，因此错误概率是：

3 × 0.01² × 0.99 + 0.01³
= 0.000298
= 0.0298%

在这个假设下，错误概率下降到原来的约三十四分之一。代价也很直接，一位内容占用了三位空间，或者需要发送三位。

码率是原始信息量与编码后长度的比值。三次重复码的码率为 1/3；后面要用到的汉明码，将四位内容编码成七位，码率为 4/7。在其他条件相同时，冗余越多，留给有效内容的比例就越小。

「独立」是这笔计算的前提。如果三份数据都受同一次故障影响，出错概率就不能直接相乘。即使错误独立，多数表决也没有把风险变成零，比如 111 错成 001 时，算法仍会按规则给出错误答案 0。MIT 对重复发送与可靠性的解释也用这类方法引出了编码效率的问题。

汉明码怎样找到出错的位置

汉明码的来历正好说明了这个转向。MacTutor 的 Hamming 传记提到，1947 年 Richard Hamming 曾把一批计算任务交给 Bell Labs 的机器在周末运行，周一发现计算很早就因为错误中断，结果没有可用输出。那时的机器已经能用校验发现错误，但发现错误以后，计算流程仍常常只能停下来等人介入；无人值守时，检测到错误并不等于完成了工作。

有了这个背景，我们自然会想到，如果机器已经能判断数据不符合规则，能不能让这些检查结果进一步指出错误位置，并把它改回来？Hamming 后来在 1950 年的论文 Error Detecting and Error Correcting Codes 中系统发表了这套思路。

前面把内容重复三遍很直观，但占用空间较多。想减少冗余并定位错误，就需要让同一条额外信息约束多个位置。奇偶校验是一个合适的起点。

一个校验位只能提供有限的线索

1011 中有三个 1。在末尾添加一个校验位 1，就能让整个序列中 1 的数量变成偶数：

数据       校验位
1011         1

双方事先约定总数必须是偶数。只要其中一位翻转，1 的个数就会增加或减少一个，偶数变成奇数，接收方就能发现不符合规则。

但「总数变成奇数」没有说明哪一位错了。数据位可能错，校验位也可能错。如果两位同时翻转，总数的奇偶性又可能保持不变。

发现错误与定位错误需要不同的信息量。一个检查结果只能表达「符合」或「不符合」；要在多个位置中找到一个，就需要更多彼此配合的检查结果，并让每个可能出错的位置留下不同的检查指纹。

校验位的位置和含义

汉明 (7,4) 码里的两个数字分别表示码字总长和原始数据位数，它把四位原始数据扩展成七位码字。

这两个数字由校验位数决定。标准二进制汉明码先选校验位数 r，再让 r 位检查结果承担定位任务。r 位一共有 2^r 种组合，其中全零组合留给「没有发现错误」，剩下 2^r - 1 种非零结果要分别指向每一个可能出错的位置，所以码字总长是 n = 2^r - 1。再扣掉 r 个校验位，原始数据位数就是 k = 2^r - r - 1。

按这个关系往下排，会得到几组标准二进制汉明码。它们的最小距离都是 3。

校验位数 r	码字总长 n	原始数据位数 k	标准汉明码	最小距离
2	3	1	(3,1)	3
3	7	4	(7,4)	3
4	15	11	(15,11)	3
5	31	26	(31,26)	3
6	63	57	(63,57)	3

我们后面继续用 (7,4)。r = 3 时，检查结果有 8 种。000 表示没有发现错误，001 到 111 这七种非零结果，刚好可以指向第 1 到第 7 位中的某一位。这个例子够小，也能看清汉明码怎样定位一位错误。

校验位放在第 1、2、4 位，也就是 2^0、2^1、2^2 这些 2 的幂次位置。它们分别负责检查位置编号中的一位：

校验位	所在位置	覆盖规则	覆盖位置
P1	1	位置编号最低位为 1	1、3、5、7
P2	2	位置编号中间位为 1	2、3、6、7
P4	4	位置编号最高位为 1	4、5、6、7

把位置编号写成三位二进制后，P1 看最低位，P2 看中间位，P4 看最高位。例如第 6 位是 110，所以参加 P4、P2 两组检查，不参加 P1。接收方重新检查时，把失败记成 1、通过记成 0，按 P4、P2、P1 排列，这个三位结果就是校验综合，英文是 syndrome。

现在再放入原始数据 1011。数据位是第 3、5、6、7 位，先填好这些位置：

位置	1	2	3	4	5	6	7
用途	校验	校验	数据	校验	数据	数据	数据
初始值	待算	待算	1	待算	0	1	1

三组检查都要求各自覆盖的位置中，1 的个数为偶数。按照上面的覆盖规则计算校验位：

校验位	覆盖位置	已知数据中 1 的个数	应填值
P1	1、3、5、7	2	第 1 位填 0
P2	2、3、6、7	3	第 2 位填 1
P4	4、5、6、7	2	第 4 位填 0

最终码字是 0110011。如果第 6 位从 1 变成 0，读出的结果会成为 0110001。重新检查时，P1 通过，P2、P4 失败。按 P4、P2、P1 排列，校验综合就是 110，正好指向第 6 位。校验位自身出错也适用同样的定位规则，但前提仍是这次传输里只有一位翻转。

两位错误会让定位结果失真

实验默认让第 6 位出错，点击比特按钮可以翻转对应位置。选择「两位错误」，便能看到另一条边界。两位错误会让校验失败，说明收到的序列不是合法码字；但普通汉明解码器如果继续按一位错误去修，就会把失败位置解释成另一个单比特错误。

单独打开汉明码实验。实验只在浏览器本地计算，按钮改变的是示例数据。

如果第 2、6 位同时出错，P2 包含的错误有两个，奇偶性保持不变；P4 只有第 6 位出错，于是只有 P4 失败。校验综合成了 100，它确实暴露了校验失败，但 100 和「第 4 位单独出错」留下的校验综合一样。解码器若按单比特错误的规则去翻转第 4 位，结果又改错一位，输出的数据成了 1001。

所以，标准汉明码不是只能发现一位错误。以 (7,4) 为例，它能纠正一位错误，也能检测两位错误；真正做自动纠正时，需要额外约定「最多只错一位」。没有这个约定，两位错误可能被误纠正。实验中的核对区知道原始数据，才能明确指出它修错了。这两种视角必须区分，否则很容易误以为算法可以先知道错误数量，再决定要不要相信自己的判断。

能力上限来自合法码字之间的距离

两个等长二进制序列有多少个位置不同，就称它们的汉明距离是多少。例如，000 和 111 的距离为 3。一次比特翻转，只改变一个位置。

如果两个合法码字至少相差三位，那么一个结果若距离其中一个码字只有一位，就不可能同时距离另一个码字也只有一位。否则两个码字之间最多只差两位，与前提矛盾。这解释了为什么最近的合法码字能够唯一确定。

MIT 的编码课程用最小汉明距离给出同一条判断。最小距离为 d 时，接收方最多能发现 d - 1 位翻转；要纠正任意位置上的 t 位翻转，码字间的最小距离至少要达到 2t + 1。

前面表里的标准二进制汉明码最小距离都是 3，所以它们都可以检测两位错误，纠正一位错误。这里的「检测两位」只保证接收方知道结果不合法，不保证知道哪两位出错；「纠正一位」才要求定位到具体位置。以 (7,4) 为例，它的每个合法码字周围都有七个只差一位的序列。四位原始数据共有 16 种，连同码字自身计算，16 × (7 + 1) = 128，恰好覆盖七位二进制的全部 128 种组合。

这也解释了误纠正现象。对于这套七位码，任何收到的组合都能归到某个合法码字附近。如果解码器被设计成默认纠正一位错误，就没有剩余组合可以单独当作「超出能力」的信号。

给这套码再增加一个整体奇偶校验位，可以构成最小距离为 4 的扩展汉明码，并采用单比特纠正、双比特检测的解码策略，常称为 SECDED。它仍有明确前提，三位及更多错误不在这一保证内。

SSD 里的原始读数为什么会出错

纠错码在存储系统里之所以重要，是因为「数字」最终要落到物理状态上。数学例子里的比特翻转，只是 0、1 互换；落到硬件上，它来自物理状态与判断结果之间的偏差。电压、电荷、磁性等状态负责承载逻辑符号，这些状态会受到环境和器件变化影响。

以一个假设的二值电路为例，接近 0 伏读成 0，接近 1 伏读成 1，暂用 0.5 伏作为判断界线。1 伏变成 0.95 伏时，仍然能正确读成 1。数字电路本身就可以容忍一定程度的扰动；当变化越过判断界线，才可能变成逻辑错误。这里的数值只用于说明，不代表具体芯片参数。

一个单元保存四位，需要区分十六种状态

SSD 常用的 NAND 闪存，通过保存电荷来影响晶体管的阈值电压，读取电路再根据比较结果判定数据。

阈值电压可以先理解为让晶体管进入相应导通状态所需的栅极电压。它与普通逻辑电路的输出高低电平属于不同概念；在 NAND 中，读取过程利用阈值电压所处的范围区分存储状态。

每个存储单元承载的比特越多，需要区分的状态就越多：

类型	每单元保存的比特数	需要区分的状态数
SLC	1	2
MLC，通常指两位型	2	4
TLC	3	8
QLC	4	16

四位二进制共有 16 种组合，所以 QLC 需要用 16 种状态来表示它们。NAND 类型的差异就在这里，提高每个单元的信息量，会同时提高区分状态的要求。

在可用范围相近的前提下，状态越多，相邻状态之间可留的余量通常就越小。图中的均匀位置仅用于比较状态数量，实际器件的电压、间隔和编码映射取决于设计。

「3D NAND 有多少层」描述存储单元如何纵向堆叠；「TLC、QLC」描述每个单元保存多少比特。两个方向都能影响容量，但不是同一个指标。

原始读错不等于文件损坏

实际 NAND 中，同一目标状态下的各个单元也存在差异，测量结果会形成分布。反复擦写、数据保存时间、温度和相邻单元干扰，都可能让这些分布移动或变宽，进而增加越过判断边界的机会。

控制器需要配合读取和恢复机制。Cai 等人的 NAND 可靠性综述讨论了调整读取参考电压、纠错、重读等多种方法。读出的原始结果可能有错，经过恢复之后交付给系统的数据仍可能正确。

这也是 SSD 可靠性讨论里最容易混淆的一层，设备内部看到的原始读数，本来就可能包含不少错误；用户真正关心的是经过读取重试、参考电压调整、纠错和坏块管理之后，仍然无法恢复的错误有多少。纠错码没有让存储单元变成完美器件，它是在器件不完美的前提下，替上层系统争取一个足够低的失败概率。

原始误码率 描述纠错之前的错误程度。

不可纠正误码率 衡量经过处理后仍无法纠正的错误。

两者所处的阶段不同，不能把原始读错直接等同于文件损坏，也不能把某种磨损和读取条件下的数值套到所有 SSD 上。

更强的纠错也会消耗空间、计算和时间。控制器需要在器件状态、恢复能力和读写延迟之间选择合适策略，具体能修复多少错误，应看相应编码与实现条件。

软判决和 LDPC：把读取的可信程度也用起来

汉明码的例子只告诉解码器收到的是 0 还是 1。真实读取设备常能获得更多线索，比如一个判断离边界很远，另一个判断则刚好处在边界附近，它们的可靠性显然不同。现代存储和通信系统经常面对一批带着不同可信程度的候选结果，而不是已经标好位置的单个错误。

硬判决会丢掉可信程度

假设三个数据位 A、B、C 要满足偶数校验，读出的结果是 0、1、0。其中只有一个 1，检查失败。仅凭这三个值，无法知道该修改哪一个。

如果测量还给出了如下可靠性信息，判断就有了额外依据：

数据位	读出结果	示例可信程度
A	0	99%
B	1	99%
C	0	51%

在这个简化例子中，C 更值得怀疑，改成 1 也恰好能够满足校验。真实解码还要结合其他校验关系，不能一遇到失败就机械地修改可信程度最低的一位。

硬判决 只提供已经判定的符号。

软判决 还利用支持不同候选取值的可靠性信息。

表里的百分比是假设值，实际系统常使用似然或对数似然等形式，把测量结果与噪声模型联系起来。

似然描述在某个候选值成立时，出现当前测量结果有多合理。对两个候选值的似然进行比较，就能同时表达「更倾向哪一个」与「倾向得有多强」。这里不需要先学会概率公式，也能理解它为什么比一个硬性的 0 或 1 包含更多信息。

闪存可以通过额外读取获得更细的判断依据，无线接收机也能从接收信号中提取可靠性信息。取得这些信息本身有成本，实际实现会决定何时启用、使用多少以及怎样量化。

许多条局部约束怎样共同工作

LDPC 是 Low-Density Parity-Check Code，即低密度奇偶校验码。它使用许多条奇偶校验关系，但每条关系只连接相对少量的比特。

如果把「某条检查是否涉及某个比特」写成表格，涉及的格子填 1，其余填 0，这张校验矩阵中大多数格子会是 0。「低密度」描述的是这些连接比较稀疏。

LDPC 的有趣之处在于，它很早就被提出，但真正变成工程里的常见选择，需要等计算能力和实现成本跟上。软信息、稀疏校验关系和迭代计算放在一起，才让它适合在有限时延内处理大量带噪声的数据。

同一组关系也可以画成 Tanner 图。图中一类节点代表比特，另一类节点代表校验规则；某个比特参加某条检查，就在它们之间连线。图把局部计算所需的关系直接表示出来。

在常见的软信息迭代解码中，过程大致是：

1. 读取结果为各个比特提供初始可靠性。
2. 校验节点结合其他相关比特的信息，向某个比特传递约束带来的判断。
3. 比特节点综合测量信息和其他校验节点的反馈，更新传给下一轮的信息。
4. 重复计算，直到满足停止条件，或达到实现设定的迭代上限。

一条校验可能无法定位错误，但许多条交叉约束加上测量可靠性，有机会共同缩小候选范围。NVIDIA 的 LDPC 教程给出了校验矩阵、Tanner 图与消息传递之间的对应关系。

这张图不需要经过训练才开始工作。编码规则决定了它的连接关系，解码算法规定怎样计算和传递信息。实际图中可能有环，有限次数的迭代也可能不收敛，或收敛到错误的合法码字，因而仍然需要考虑失败概率和额外检错。

软判决是一种使用观测信息的方式，LDPC 是一类码，两者属于不同层面。LDPC 可以配合不同解码方式；读取几次、迭代几轮也由具体实现决定，没有通用的固定次数。

二维码怎样利用多项式恢复内容

汉明码、LDPC 通过校验关系连接比特；里德—所罗门码（Reed–Solomon，简称 RS）则可以利用多项式，在一组符号之间建立约束。二维码的纠错就是它的一种应用。

用四个取值保存两个数

假设要保存两个数 2 和 1，将它们作为系数定义直线：

y = 2x + 1

双方约定在 x = 1、2、3、4 四个位置取值，保存的内容便是：

x：1、2、3、4
y：3、5、7、9

原始内容只有两个系数，保存时用了四个数。多出来的取值，都受到「来自同一条直线」的约束。

如果接收到 3、5、100、9，其中三个点仍在原来的直线上。任何另一条直线最多与原直线相交于一个点，所以不可能再有另一条直线同时通过这四个接收点中的三个。根据「最多一个取值错误」的前提，就能找到原直线，恢复系数 2 和 1。

实际 RS 码在有限域上运算。有限域只包含有限个元素，加减乘除都按规定的规则进行，除数不能为零。这让编码与解码能够使用精确的离散计算。直线例子保留了多项式约束的思路；在正式编码中，还需要约定具体的有限域、符号表示和求值位置。

对于含 k 个信息符号、编码后共有 n 个符号的标准 RS 码，增加的 n-k 个冗余符号，可以用于纠正最多 (n-k)/2 个未知位置的符号错误，结果取整数部分。这里按符号计错，同一个符号内多个比特出错，仍属于一个符号错误。

知道哪里丢了，比不知道哪里错了容易恢复。如果设备明确告诉解码器哪些位置无法读取，这类情况叫作擦除。直线例子中，只要还知道两个不同位置上的正确取值，就能确定直线；对于未知位置的错误，则还需要额外信息来识别应该排除哪一个取值。

二维码为什么有四档纠错等级

二维码使用 RS 码恢复部分受损数据，并提供 L、M、Q、H 四种纠错级别。二维码发明方 DENSO WAVE 的说明把这四档解释成按使用环境选择的取舍。

级别越高，能恢复的错误越多，冗余也越多；同样内容可能需要更大的二维码。四档恢复能力约为全部码字的 7%、15%、25%、30%，其中一个码字是 8 比特。

我们可以把这四档理解成四种使用环境，而不是简单的质量排名：

等级	大致恢复率	更像什么场景	主要取舍
L	7%	干净屏幕上的一次性码、数据较多的内部码、印刷质量可控的纸面	容量压力最小，抗污损余量也最小
M	15%	普通菜单码、活动签到码、室内海报、一般网页链接	日常默认平衡点，DENSO WAVE 也提到它最常被选择
Q	25%	可能有折痕的纸质标签、轻微磨损的包装、户外短期张贴	用更少容量换更高容错，适合预期会有局部污损的码
H	30%	中间放 Logo 的营销码、工厂或仓储环境里的标签、需要长期张贴的码	冗余最多，但同样内容更容易推高版本或尺寸

这里的百分比是「相对于全部码字的恢复率」，不是「二维码图片可以随便遮住多少面积」。二维码还需要定位图形、帮助扫描器对齐网格的时序线，以及外圈留白的静区；如果污损刚好破坏这些结构，或者打印尺寸太小、扫码距离太远，即使选择 H 级也可能读不出来。

因此，在二维码上添加图案或 Logo 时，H 级只能提高余量，不能替代实测。比较稳妥的做法是用最终尺寸、最终材质和真实扫码距离测试，并且尽量不要碰定位图形与这圈静区。

香农极限约束了可靠传输的速度

纠错可以提高可靠性，却要占用空间、带宽、计算时间和能量。三次重复码已经展示了最直观的代价，在每秒发送的总比特数不变时，真正的新信息只占三分之一。

对于给定的信道模型、噪声和资源约束，存在一个可以可靠传递信息的速率上限，称为信道容量。这里的信道可以是一段无线链路，也可以抽象成「写入存储器后，再从中读出」的过程。

香农的信道编码定理说明，在相应模型下，当信息速率低于信道容量时，可以通过合适的编码和足够长的码块，把错误概率做得任意小；超过容量，就无法靠编码将错误概率任意压低。

「任意小」是理论中的极限性质。一个实际设备只能处理有限长度的码块，芯片有面积、功耗和时延限制，因此无法直接把理论存在性当成产品保证。码长增加以后，缓冲、计算和等待的代价也可能增加。

所谓某种编码「接近香农极限」，需要同时说明信道模型、码率、码长和目标错误率。脱离这些条件，只比较还差多少分贝，无法判断两个方案谁更适合实际系统。

5G 为什么会使用不止一种码

无线通信把同一个问题换成了另一种物理形态。电磁波会衰减、反射、叠加和受到其他信号干扰，接收机拿到的是带噪声的测量结果，再从中恢复符号。大块业务数据和较短控制信息，对长度、延迟和解码计算的要求不同，通信标准可以为它们选择不同编码。

在 5G NR 的信道编码标准 TS 38.212中，上下行共享数据信道使用 LDPC，下行控制信息使用 Polar 码；上行控制信息还会依据长度采用不同方式。

Polar 码，也叫极化码，通过特定编码变换，使对应的虚拟比特信道逐渐表现出不同的可靠性。信息放在较可靠的位置，较不可靠的位置使用双方已知的固定值，帮助接收方解码。这是另一种安排冗余的方法，其理论依据可见 Arıkan 提出的信道极化论文。

纠错同时还要与天线、信号处理、调制和重传配合。即使某种码具有很好的理论性能，也需要整个系统把可用测量结果交给它，并承担其计算和时延成本。

看懂「支持 ECC」还需要问保护哪一段

ECC 是一类技术名称。它出现在 SSD、内存和通信资料中时，保护的数据范围、编码方法和错误模型可能不同。

例如，DDR5 的片上 ECC处理 DRAM 芯片内部的相关比特错误，无法覆盖数据离开芯片后、在模组与处理器内存控制器之间传输时产生的错误。内存里的软错误也不只来自一种原因，粒子撞击、器件噪声、串扰和工艺边界都可能影响电荷状态；系统级 ECC 内存则需要相应模组、控制器和平台支持，不能仅凭「DDR5 自带 ECC」就认定具备同等保护。

检错、纠错、重传、备份的职责也应分别理解：

机制	主要解决的问题	依赖的条件
检错	判断数据是否违反校验规则	需要校验信息，仍有检测范围与漏检边界
纠错	利用冗余恢复一定范围内的错误	需要合适的编码、解码和错误条件
重传或重读	再尝试取得一份可用结果	对方或介质仍能提供数据，且允许等待
备份	从另一个保存版本中找回内容	备份版本可用，并覆盖需要恢复的数据

如果程序把错误内容交给存储器，纠错码保护的就是这份错误内容。文件正常删除或覆盖，也不属于比特损坏。判断可靠性时，需要看故障发生在哪一段，恢复机制是否覆盖那一段。

这也是纠错码最值得保留的工程启发，系统可以允许底层有一定概率出错，再通过提前设计的约束把风险降低到目标范围。看到「可以纠错」时，继续确认冗余在哪里、能处理哪类错误、超出能力以后怎样报告失败，比记住一种算法的名字更有用。