校验码？校验，也需要码？【底层的世界——计算机组成原理】

这是本人系列《底层的世界 —— 计算机组成原理》的第三章 —— 校验与纠错，用于记录分享和期末复习，欢迎讨论！

引言：数据在路上跑的时候，难免被电磁干扰 “踹一脚”，0 变 1、1 变 0，好好的数据就坏了。就像你寄情书，我爱你变成了我曹你，收件人收到了那不出大事了？为了解决 “数据有没有坏” 甚至 “坏了能不能修” 的问题，人们发明了校验码 —— 往原始数据里塞点特殊的比特，让接收方能自己查错、甚至改错。

校验码？校验，还需要码？

导弹维修？导弹，还需要维修？

好了不引用雪峰老师的名言了当然是不可能的。
我是Hikari，我就在这，不紧不慢稳稳接住你。今天科普最经典的校验码：奇偶校验、海明码、CRC 循环冗余校验，从怎么来的到怎么算的，扒一扒背后的设计哲学。

奇偶校验：你验不过我你气不气

历史的必然 —— 奇偶校验

20 世纪 40 年代，第一代电子计算机和数字通信系统出现后，比特错误成为常态。哎呀怎么老被炸啊
早期的继电器、真空管器件稳定性差，数据在传输和内存读写中经常出错。工程师需要一种成本极低、计算极快的方法来快速判断 “数据有没有错”。

奇偶校验正是在这一背景下被广泛应用，它几乎不增加计算开销，只需要 1 个额外比特就能实现基础检错，成为早期计算机内存、电报通信、串口通信的标准配置。

异或的轮椅 —— 奇校验 & 偶校验

奇偶校验的核心逻辑非常朴素：统计一组二进制数据中 1 的个数，通过增加 1 位 “校验位”，让 1 的总数保持为奇数或偶数。

以原始数据 1011001（共 7 位，其中有 4 个 1）为例：

偶校验：已有 4 个 1（偶数），因此校验位为 0，最终编码：1011001 0
奇校验：已有 4 个 1（偶数），需要补 1 个 1 变成奇数，校验位为 1，最终编码：1011001 1

接收方收到数据后，重新统计 1 的总数，判断奇偶性是否符合约定，即可检测是否出错。
这就是奇校验和偶校验，但是光这里是没办法体现出轮椅之处，为什么轮椅呢，因为：偶校验位就是所有数据位的异或结果；奇校验位就是异或结果取反。
$$ X = d0 ⊕ d1 ⊕ ... ⊕ dn-1 $$
这不论是在硬件设计还是软件检验都是非常简单的。同时由于只有一位校验码让他冗余度极低，信息密度极高。

能力边界与设计哲学

优势：

冗余度极低：n 位数据仅需 1 位校验位
计算速度极快：仅需统计 1 的个数，硬件上用异或门即可实现

神也有缺点：

局限性：

只能检测奇数个比特错误，无法检测偶数个比特同时翻转的情况
只能检错，不能纠错 —— 知道错了，但不知道哪一位错了
错误漏检率较高，仅适用于对可靠性要求不高的场景

码距与老牧师公式

这里有个老牧师公式：

$$ 2ʳ ≥ m + r + 1 $$

其中：

m 是数据位
r 是校验位

为什么能这样计算？这要开始码距的讲解了。

什么是码距（汉明距离）？

码距（Hamming Distance） 是指两个合法编码之间，对应二进制位不同的个数。

最小码距 $d_{min}$：在一个编码系统中，任意两个合法码字之间码距的最小值。这是衡量编码抗干扰能力的核心指标。

你可以将最小码距 $d_{min}$想象成半径，半径内的数据他都能允许出错，半径越大，容错越高。
举例：

假定数据 0000 0001 0010 … 1111为一组我们约定的合法数据，他们任何一位错误都会变成我们约定的合法数据，因此它们的码距为 1，他们不具有任何容错。
假定数据 0000 0011 0101 0110 1001 1010 1100 1111为一组我们约定的合法数据，他们任何一位错误都有容错，容错位数为 1，因此它们的码距为 2。

码距与检错、纠错能力的关系

码距决定了编码能发现多少位错误，以及能纠正多少位错误（假设错误是随机的）：

检测 $e$ 个错误：需要 $d_{min} \ge e + 1$
- 如果最小码距是 2，那么随意改变 1 位（产生 1 个错误），一定会变成非法码字（被检测出来）。但如果改变 2 位，可能刚好变成另一个合法码字（无法检测）。
纠正 $t$ 个错误：需要 $d_{min} \ge 2t + 1$
- 如果要纠正 1 位错误（$t=1$），需要 $d_{min} \ge 3$。
同时检错和纠错：$d_{min} \ge e + t + 1$（其中 $e > t$）

这里可能很难理解，同样也能视作圆的半径来理解。慢慢梳理和询问请教他人和AI或许是个不错的办法。

海明码：错了！错了！哪错了？错哪了？

海明有个周末难题

1950 年，海明发表论文《Error Detecting and Error Correcting Codes》，正式奠定了纠错码理论的基础，这篇论文来自于他的周末难题。
贝尔实验室的理查德・海明快被周末的破计算机逼疯了。那时候继电器计算机老出错，一到周末没人值班，错了就直接停机，得等周一重来。
海明就吐槽：“机器都能发现错了，就不能自己改过来？” 他就开始琢磨，还真琢磨出来了 —— 不光能查错，还能精准定位到哪一位错了，直接取反就修好。
这就是海明码，人类历史上第一种能自动纠错的编码，直接把校验技术从 “检错” 卷到了 “纠错”。

校验位站 2 的幂次位

初学者的噩梦之一就是不理解为什么校验位站 2 的幂次位。
奇偶校验是一整组只做一次校验，所以只能知道错了，不知道哪错。海明码的思路很巧妙：把数据分到好几个不同的组里，每个组单独做一次奇偶校验。
就像猜数字，你问 “比 8 大吗？”“比 4 大吗？”，几个问题下来就能锁定数字。海明码就是用好几组校验的 “对错组合”，精准定位错误的位置。
还有一个举例，就像是有x,y坐标一样，给出两个位置你就能找到错误的地方了。
哪一位出错，它所在的所有组都会同时出错；反过来，哪几组错了，拼起来就是错误的位置编号。

下面介绍海明码的规则：

所有位置是 2 的幂次的比特，都是校验位：第 1、2、4、8、16…… 位，记为 P₁、P₂、P₃……
剩下的位置塞原始数据位，记为 D₁、D₂、D₃……
第 k 个校验位，管所有二进制编号第 k 位是 1 的位置

比如：

P₁（第 1 位，2⁰）：管 1、3、5、7、9…… 这些位置
P₂（第 2 位，2¹）：管 2、3、6、7、10…… 这些位置
P₃（第 4 位，2²）：管 4、5、6、7、12…… 这些位置

为什么要这么做，我们注意到注意力惊人，2 的幂次正好是像 ...0001 ...0010 ...0100 ...1000这种格式，正好能成为对应幂次的校验组。

这里以 4 位数据 1011 举例，算偶校验的海明码。

步骤 1：先占位置
由于我们要用到上面的老牧师公式，所以这里要深入理解~~老牧师~~公式。
公式本质上是在算 “状态数”够不够用 。

我们总共有 $m + r$ 位（数据位+校验位）。在传输过程中，这 $m+r$ 个位置中任何一个位置都可能发生错误。
加上 “没有发生错误” 这一种情况，总共有 $m + r + 1$ 种状态需要被识别。
我们有 $r$ 个校验位，每个校验位算一次奇偶校验，它们组合起来可以提供 $2^r$ 种不同的校验结果（伴随式 Syndrome）。
因此，$r$ 个校验位必须能够区分出这 $m + r + 1$ 种状态，即 $2^r \ge m + r + 1$。

代入数据：$m=4$。

尝试 $r=2$：$2^2 = 4$，需要区分 $4+2+1 = 7$ 种状态（不够）。
尝试 $r=3$：$2^3 = 8$，需要区分 $4+3+1 = 8$ 种状态（刚好够）。

所以根据老牧师公式 4 位数据需要 3 位校验位，总共 7 位。

位置	1	2	3	4	5	6	7
角色	P₁	P₂	D₁	P₃	D₂	D₃	D₄
填数据	?	?	1	?	0	1	1

步骤 2：挨个算校验位

P₁管 1、3、5、7 位：数据位有 1、0、1 → 2 个 1（偶）→ P₁=0
P₂管 2、3、6、7 位：数据位有 1、1、1 → 3 个 1（奇）→ P₂=1
P₃管 4、5、6、7 位：数据位有 0、1、1 → 2 个 1（偶）→ P₃=0

本质是做异或运算。

步骤 3：拼出最终编码
按位置填进去：0 1 1 0 0 1 1 → 海明码就是 0110011

纠错演示：
假设传的时候第 5 位翻了，收到的是 0110111。
收方重新算每组的奇偶：

P₁组：0,1,1,1 → 3 个 1（奇）→ 错了，记 G₁=1
P₂组：1,1,1,1 → 4 个 1（偶）→ 没错，记 G₂=0
P₃组：0,1,1,1 → 3 个 1（奇）→ 错了，记 G₃=1

把 G 拼起来：S₃S₂S₁ = 101（二进制）= 5（十进制）
所以第 5 位错了，把它取反就修好了，就是这么神奇。

海明码（Hamming Code）的默认最小码距 $d_{min} = 3$。因此，海明码能够纠正 1 位错误，或者检测出 2 位错误（纠1检2）。

海明码的优缺点

优点：

能纠错单比特错误：不用重传，自己就修好，对可靠性提升巨大
冗余度适中：比奇偶校验多几位，但比很多纠错码省
硬件实现简单：使用异或门，电路不复杂

缺点：

只能纠正 1 位错，错 2 位就只能检测不能纠正了
数据短性价比不高：如 4 位数据就要 3 位校验，校验占将近一半
连续好几位错的话，就只能好好享受了

现在电脑里的 ECC 内存，就是海明码的升级版本，服务器、工作站必备，就是为了防止内存比特翻转出错。

CRC 循环冗余校验：走进现代文明

前两位如果说都是 “比特级” 的小打小闹，那么 CRC 就是 “数据块级” 的工业标准。现在很多情况下你上网、插 U 盘、读硬盘，背后全是 CRC 在干活。

诞生

1961 年，MIT 的韦斯利・彼得森发表了论文，正式提出循环冗余校验的理论。
当年通信和存储发展起来了，大家要传一整块一整块的数据，奇偶校验太弱，海明码又只适合短数据。人们需要一种能对付突发错误、算得又快、还能给大块数据 “盖章” 的技术。
CRC 靠着多项式代数的数学 buff，完美踩中了所有需求，慢慢就成了全网通用的标准。
以太网、USB、SATA、蓝牙、ZIP 压缩，很多“块”级别的数据都得需要CRC。

设计原理：多项式模 2 除法

CRC 的核心思路：把一整串二进制数据当成一个多项式的系数，比如 1011 就对应 x³ + x + 1。
通信两边提前约好一个固定的 “生成多项式”，就像约定好一个印章。
发件人把数据多项式左移几位，除以这个生成多项式，得到的余数就是 CRC 校验码，附在数据后面发出去。
收件人把收到的 “数据 + CRC” 整个除以同一个生成多项式，余数是 0 就说明没坏。

这里的除法是 “模 2 除法”，也就是按位异或，加法不进位、减法不借位，0+0=0，0+1=1，1+1=0，硬件上常用移位寄存器，因此有着不错的性能。

计算方式

拿原始数据 1011001，生成多项式 1001（对应 x³+1，3 次，所以校验码 3 位）举例。

步骤 1：数据左移 r 位
原始数据后面补 3 个 0，变成被除数：1011001000

步骤 2：模 2 除法求余数
就跟小学除法竖式一样，只不过减法换成异或：

1011001000
1001        （首位是1，商1，异或除数）
----
 01000
  0000       （首位是0，商0，异或0）
  ----
  10010
  1001       （首位是1，商1，异或除数）
  ----
   00000
    0000      （首位是0，商0，异或0）
    ----
     0000
      000     （首位是0，商0，异或0）
      ----
       011    （最后剩下的余数，3位）

余数是 011，这就是 CRC 校验码。

最终发出去的就是：原始数据 + CRC → 1011001 011
收方把这一整串除以 1001，余数是 0 就说明没问题（出错的概率不高，当然你错到好处正好测不出我就给你了）。

生成多项式

常用的标准多项式有以下几个：

CRC-8：x⁸+x²+x+1（0x07），常用在小型嵌入式
CRC-16-CCITT：x¹⁶+x¹²+x⁵+1（0x1021），串口、Modem 常用
CRC-32：x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1（0x04C11DB7），以太网、文件校验全靠它

生成多项式的次数就是校验码的位数，比如 CRC-32 就是 32 位校验码，不管你数据是 1 字节还是 1GB，校验码都是固定 32 位。

CRC 的优缺点

优点：

检错能力超强：能查所有单比特错、所有奇数个错、所有长度≤r 的突发错误，长突发错误也大概率能查
速度极快：硬件上移位寄存器 + 异或门，流水线跑起来，多大的数据都不卡
开销固定：不管数据多长，校验码就那么长，冗余效率拉满

缺点：

只能检错，不能纠错（当然也有变种能纠错，但主流都是检错）
数学门槛比前两个高，生成多项式不能瞎选，选不好检错能力拉胯
对故意篡改没辙：这是校验不是加密，改数据同时改 CRC 就能骗过

对比

表格

对比维度	奇偶校验	海明码	CRC 循环冗余校验
核心能力	检错（仅奇数位错）	单比特纠错，双比特检错	强检错（多比特、突发错误）
冗余度	1 位 / 任意长度	约 log₂(n) 位	固定 r 位（生成多项式决定）
计算难度	极低（数 1 的个数）	中等（分组算）	低（硬件移位异或）
验错能力	单比特、奇数比特错	单比特错误为主	单比特、多比特、突发错误
硬件成本	极低	中等	低
典型应用	早期内存、串口通信	ECC 内存、嵌入式存储	以太网、USB、SATA、文件校验

现实中的应用

奇偶校验

老设备串口：RS232、PS/2 键盘鼠标这些古董接口
简单嵌入式：资源极度受限的 8 位单片机，偶尔还在用
基础内存校验：早期的内存条奇偶校验位

海明码

ECC 内存：服务器、工作站、工控机的内存，防止单比特翻转
嵌入式存储：NAND Flash 的页校验，很多用海明码
航天级设备：对可靠性要求高，单比特错不能停机的场景

CRC

计算机网络：以太网、USB、PCIe、蓝牙，几乎所有通信协议
存储设备：SATA 硬盘、SSD、光盘、U 盘
文件校验：压缩包、镜像文件的完整性校验
工业控制：Modbus 等工业总线的通信校验

总结

奇偶校验、海明码、CRC，不是谁取代谁的关系，而是不同场景下的三种设计取舍：

奇偶校验是 “成本换够用” 的极致 —— 用最低的冗余和算力，换最基础的错误检测。它诞生于资源匮乏的年代，却在简单设备里一直活到现在。

海明码是 “结构换能力” 的智慧 —— 用分组交叉校验的设计，第一次实现了自动纠错，告诉人们冗余不光能查错，还能修错。

CRC 是 “数学换效率” 的典范 —— 用多项式代数的数学基础，实现了大块数据的高效校验，成为整个数字工业的底层标配。

理解校验码，不光是懂了几个计算机知识点，更能体会到工程里的核心哲学：没有完美的方案，只有最适合场景的权衡。用多少冗余换多少可靠性，用多少复杂度换多少能力，这就是工程师每天都在做的选择题。

小思考： 为什么你下载大文件的时候，官网经常会给一个 CRC32 或者 MD5 值让你校验？为什么网络传输用 CRC 不用海明码？这里面是效率和成本的取舍。