校验码 码距 · 奇偶 · 海明 · CRC
软考 · 计算机组成原理 ｜ 1.1.4 ｜ 从「为什么要校验」讲到能自己算海明码和 CRC
⓪ 三种校验码，先有个印象
数据在传输/存储时可能出错（0 变 1、1 变 0）。校验码就是在原始数据里掺入一些“校验位”，让接收方能发现错误、甚至把错误改回来。
| 校验码 | 能做什么 | 开销 | 典型用途 |
|---|
| 奇偶校验 | 只能发现奇数个位出错，不能纠错 | 1 位 | 简单场合、串口 |
| 海明码 | 能发现并纠正 1 位错（能定位到哪一位） | k 位校验 | 内存 ECC |
| CRC | 检错能力很强，但不能纠错 | r 位 | 网络通信、磁盘存储 |
🔑 三个都要用到一个根本概念：码距。先搞懂它，后面全都顺。
① 码距：合法编码之间“隔多远” 最核心的概念
先学会一件事：怎么比较两个码？ 把它们上下对齐，一位一位比，数出不同的位数。
例：比较 0001 和 0101
0 0 0 1
0 1 0 1
↑
只有第 2 位不同 → 差 1 位
例：比较 0001 和 0010
0 0 0 1
0 0 1 0
↑ ↑
第 3、4 位都不同 → 差 2 位
那“码距”又是什么？
定义：一个编码系统里，任意两个合法编码之间，最少差多少位。
🔑 关键在“最少”两个字：不是随便挑一对，而是要把所有合法编码两两比较一遍，找出最像的那一对，那个最小的差值才是码距。
看一个具体例子。假设某个编码系统规定，只有这 4 个编码是合法的：
合法编码： 0000 0011 1100 1111
两两比较，全部列出来：
0000 vs 0011 → 差 2 位
0000 vs 1100 → 差 2 位
0000 vs 1111 → 差 4 位
0011 vs 1100 → 差 4 位
0011 vs 1111 → 差 2 位
1100 vs 1111 → 差 2 位
最像的一对（0000/0011）差 2 位 → 这套编码的码距 = 2
对比：如果合法编码是全部 16 个（就是普通二进制），那 0000 和 0001 只差 1 位，所以码距 = 1。教材说的“4 位 8421 码码距为 1”就是这个意思。
🔑 为什么码距 = 1 很危险？
因为任意一位出错，结果都会变成另一个合法编码——接收方一看“这是个正常码”，以为没错，完全发现不了。
🔑 码距决定检错、纠错能力（背这 3 条）：
· 要检测出 e 个位出错 → 码距 ≥ e + 1 （码距2→检1位；码距3→检2位）
· 要纠正 t 个位出错 → 码距 ≥ 2t + 1 （纠1位至少码距3）
· 要同时检测 e 个、纠正 t 个 → 码距 ≥ e + t + 1
直观理解：两个合法编码离得越远（中间隔着越多的“错误点”），出错后就越不容易误撞到另一个合法编码。要纠错 1 位，码距至少得 3——这样即使偏了 1 位，离原来那个也还是最近的，能认回来。
自查：某编码系统码距为 4，最多能检测几位错？最多能纠正几位错？
点击看答案
检测：d ≥ e+1 → 4 ≥ e+1 → 最多检 3 位错。
纠正：d ≥ 2t+1 → 4 ≥ 2t+1 → 2t ≤ 3 → t ≤ 1.5 → 最多纠 1 位错。
（口诀：检错能力 = 码距 − 1；纠错能力 = 码距 ÷ 2 向下取整）
② 奇偶校验：最简单，只会“报错”不会“治病”
做法：在数据后面加 1 位校验位，让整个码里 1 的个数变成奇数（奇校验）或偶数（偶校验）。
数据 1011（数一数：1、0、1、1 → 有 3 个 1）
偶校验：要凑成偶数个 1 → 3 是奇数，还差 1 → 校验位补 1 → 码 = 10111（3+1 = 4 个 1，偶数）✓
奇校验：要凑成奇数个 1 → 3 已经是奇数 → 校验位补 0 → 码 = 10110（3+0 = 3 个 1，奇数）✓
⚠️ 最容易搞混的一点：“偶校验”是让【数据 + 校验位】加起来 1 的总数是偶数，不是让校验位本身是偶数。
所以 1011 的偶校验位是 1（因为 3 是奇数，要补 1 才变偶数），数字看起来是 1，但总数 4 是偶数。
加了这个校验位，码距就从 1 变成了 2。按公式 d≥e+1，码距 2 能检测 1 位错。
⚠️ 能力边界：只能发现“奇数个”位出错（1、3、5…位），发现不了“偶数个”位出错（2 位同时错，1 的个数奇偶性不变）。而且不能纠错——只知道“有错”，不知道错在哪。
⚠️ 别和“二维奇偶校验”搞混（一个常被问懵的点）
“奇偶校验”其实有两种形态，能力完全不同：
| 类型 | 校验位 | 码距 | 能纠错吗 |
|---|
| 简单奇偶（一维） | 只有 1 个 | 2 | ❌ 不能纠错（本文讲的就是这个） |
| 二维奇偶（水平垂直） | 每行每列都有 | 4 | ✅ 能纠 1 位错 |
二维为什么能纠错？行、列两个方向交叉定位：
列1 列2 列3 行校验
行1: 1 0 1 | 0
行2: 0 0* 1 | 0 ← 行2 校验对不上
行3: 1 1 0 | 0
-----------------
列校验: 0 1* 0 ← 列2 校验对不上
↑
行2报警 + 列2报警 → 交叉点 = 行2列2 = 出错位置 → 翻回来即可 ✅
🔑 记法：考试说“奇偶校验码距=2”，默认指一维简单奇偶 → 结论是“不能纠错”。
只有明确说“水平垂直/二维奇偶”，码距才是 4、才能纠 1 位。
③ 海明码：能发现、还能定位纠正 1 位错 考试计算重点
思路：在数据位之间插入 k 个校验位，让每个校验位“管”一群数据位（做异或）。出错时，几个校验位的结果组合起来，就能指出出错位置。
先搞懂公式 2k − 1 ≥ n + k（一步一步推）
① 每个校验位 = 一个侦探。它盯着自己管的那群位，最后报告一位结果：管的位都正常报 0，有问题报 1。
② k 个侦探 → k 位报告 → 共 2k 种组合。（k=4 时就是 16 种：0000~1111）
③ 为什么减 1？因为 0000 这一种被“没出错”占用了，不能再拿去表示“某位错”。所以只剩 2k − 1 种地址可用。
④ 要覆盖多少种“某位错”？一共 n+k 个位置（校验位自己也会错，也要能被定位），所以需要 n+k 个地址。
⑤ 两边对上：2k − 1 ≥ n + k。
代入 n = 8 试算：
k=3： 2³−1 = 7 要覆盖 8+3 = 11 个位 → 7 ≥ 11 ？ ✗ 不够
k=4： 2⁴−1 = 15 要覆盖 8+4 = 12 个位 → 15 ≥ 12 ？ ✓ 够
→ 所以 8 位数据需要 4 个校验位（16 种报告，扣掉全 0，剩 15 个地址盯 12 个位子，还多 3 个）
🔑 提炼成两句：① 全 0 留给“没出错”，所以要 −1；② 校验位自己也会错，所以是 n+k 不是 n。
再搞懂：校验位为什么放在 2 的幂位置？
因为 任何位置编号，都能拆成 2 的幂之和。拆出来的那几个 2 的幂，正好就是要管它的校验位。
位置 3 = 1 + 2 → 由 P1、P2 管
位置 5 = 1 + 4 → 由 P1、P3 管
位置 6 = 2 + 4 → 由 P2、P3 管
位置 7 = 1 + 2 + 4 → 由 P1、P2、P3 共同管
位置 11 = 1 + 2 + 8 → 由 P1、P2、P4 共同管
换成二进制看得更直观（位置 6）：
6 = 0 1 1 0
↑ ↑ bit 为 1 的位 → 由 P2、P3 管
🔑 一句话：位置编号的二进制里，哪几位是 1，就由哪几个校验位管。
正因为校验位放在 2 的幂位置，它才能“对上号”——P1 管所有编号 bit0=1 的位，P2 管 bit1=1 的位……
🔑 这也解释了纠错原理：位置 7 = 1+2+4，参与它的只有 P1/P2/P3 三个组。所以一旦位置 7 出错，只有这三个组会算出 1，拼起来 0111 = 7 —— G 值正好指回位置 7。
🔑 公式：2k − 1 ≥ n + k（n = 数据位数，k = 校验位数）。
即：总共 n+k 个位置，用 k 个校验位能区分出「没出错 + 每一位出错」共 n+k+1 种情况。
三条规则（背下来）
| 规则 | 内容 |
|---|
| ① 位置 | 校验位 P 放在编号是 2 的幂的位置：第 1、2、4、8… 位；数据位按顺序填剩下的位置 |
| ② 管辖 | 第 i 个校验位，管所有「位置编号的二进制第 i 位是 1」的位 |
| ③ 校验 | 偶校验：让每个校验位管的那些位异或结果为 0；按此反推校验位的值 |
以 8 位数据举例（k=4，因为 2⁴−1=15 ≥ 8+4=12）。位置对应关系：
📝 手把手：用 5 位数据走完整流程（比 8 位好算）
设数据 D4 D3 D2 D1 D0 = 1 0 1 1 0（即 D0=0, D1=1, D2=1, D3=0, D4=1）。跟着 5 步走：
第 1 步 · 定 k 和位置：n=5 → 2k−1≥5+k → k=4。校验位占 1、2、4、8 号，数据填其余：
位置: 1 2 3 4 5 6 7 8 9
内容: P1 P2 D0 P3 D1 D2 D3 P4 D4
第 2 步 · 每个位置号转二进制，拆出"谁管谁"（第 1 位=1→P1，第 2 位=1→P2，第 3 位=1→P3，第 4 位=1→P4）：
位置 3 = 0 0 1 1 → P1,P2 管（D0）
位置 5 = 0 1 0 1 → P1,P3 管（D1）
位置 6 = 0 1 1 0 → P2,P3 管（D2）
位置 7 = 0 1 1 1 → P1,P2,P3 管（D3）
位置 9 = 1 0 0 1 → P1,P4 管（D4）
汇总（去掉校验位自己那几行）：
P1 管：D0, D1, D3, D4 ← 出现 P1 的那些行
P2 管：D0, D2, D3
P3 管：D1, D2, D3
P4 管：D4 ← 位置9=1001，第4位=1→P4
第 3 步 · 校验位 = 它管的数据位异或（异或：相同得0，不同得1）：
P1 = D0⊕D1⊕D3⊕D4 = 0⊕1⊕0⊕1
= (0⊕1)⊕0⊕1 = 1⊕0⊕1 = 1⊕1 = 0
P2 = D0⊕D2⊕D3 = 0⊕1⊕0 = 1
P3 = D1⊕D2⊕D3 = 1⊕1⊕0 = (1⊕1)⊕0 = 0⊕0 = 0
P4 = D4 = 1
第 4 步 · 填回座位，得到海明码：
位置: 1 2 3 4 5 6 7 8 9
内容: P1 P2 D0 P3 D1 D2 D3 P4 D4
值: 0 1 0 0 1 1 0 1 1
海明码（位置1→9）= 0 1 0 0 1 1 0 1 1
第 5 步 · 接收方验证（把每组重新异或，G 值十进制 = 出错位置，全 0 = 没错）：
G1 = P1⊕D0⊕D1⊕D3⊕D4 = 0⊕0⊕1⊕0⊕1 = 0
G2 = P2⊕D0⊕D2⊕D3 = 1⊕0⊕1⊕0 = 0
G3 = P3⊕D1⊕D2⊕D3 = 0⊕1⊕1⊕0 = 0
G4 = P4⊕D4 = 1⊕1 = 0
→ G4G3G2G1 = 0000 → 无错 ✓
自己练一个：数据 D4 D3 D2 D1 D0 = 0 1 0 1 1（D0=1, D1=1, D2=0, D3=1, D4=0），求 P1~P4。
点击看答案
P1 = D0⊕D1⊕D3⊕D4 = 1⊕1⊕1⊕0 = 1
P2 = D0⊕D2⊕D3 = 1⊕0⊕1 = 0
P3 = D1⊕D2⊕D3 = 1⊕0⊕1 = 0
P4 = D4 = 0
（异或从左到右一路算，顺序无所谓）
怎么检出并纠正错误？接收方把每个校验组重新异或一遍，得到 G4 G3 G2 G1：
🔑 G4G3G2G1 的十进制值 = 出错的位置；若全为 0，说明没出错。找到位置后，把那一位取反，就纠正了。
点一位模拟“传输中出错”（再点一次取消）：
④ CRC：检错能力最强，通信/存储的常客
做法：选一个生成多项式 G(x)，用它在数据后面算出若干个校验位，拼成 CRC 码。
记号：生成多项式 G(x) = x³ + x + 1 ←→ 二进制 1011（有几项，对应位就是 1）
数据 k 位 + 校验 r 位 = 总共 n 位，记作 (n, k) 码
本例 r=3（多项式最高次是 x³），所以校验位 3 位
关键：模 2 运算（就是异或）
🔑 模 2 加减 = 按位异或，不进位、不借位：
0⊕0=0 1⊕1=0 0⊕1=1 1⊕0=1。所以“减”和“加”在这里是一回事。
编码三步
- 补 0：数据后面补 r 个 0（r = 生成多项式位数 − 1）
- 做模 2 除法：补 0 后的数 ÷ 生成多项式（用异或，不借位）
- 取余数：余数就是校验位；把它替换掉刚才补的那 r 个 0 → 得到 CRC 码
🐣 小白版手把手：数据 1101 到底怎么算出 CRC 码
先建立直觉：CRC 本质就是一次「带余数的除法」，只不过和小学除法有一点不同。
小学带余数除法：
13 ÷ 4 = 3 …… 余 1 （用「减法」）
CRC 除法：形状一样，但「减法」换成「异或」
1 1 0 1 （异或：相同得0，不同得1）
1 0 1 1
───────
0 1 1 0
🔑 为什么用异或？因为电路做异或特别简单——一位一位算，不用管进位/借位。
第 1 步 · 数据后面补 3 个 0（校验位几位？看多项式最高次：G(x)=x³+x+1 最高 3 次 → 补 3 个 0）：
数据: 1 1 0 1
补0: 1 1 0 1 0 0 0 ← 先占好 3 个位置，等会儿用余数填
第 2 步 · 异或长除法（规则：看当前最左位，是 1 就把除数对齐异或一次；是 0 就跳过往右挪）：
第1次 最左位是1 → 异或
1 1 0 1 0 0 0
1 0 1 1
─────────────
0 1 1 0 0 0 0 (1101⊕1011=0110)
第2次 最左的1在第2位 → 对齐异或
0 1 1 0 0 0 0
1 0 1 1
─────────────
0 0 1 1 1 0 0 (1100⊕1011=0111)
第3次 最左的1在第3位 → 对齐异或
0 0 1 1 1 0 0
1 0 1 1
─────────────
0 0 0 1 0 1 0 (1110⊕1011=0101)
第4次 最左的1在第4位 → 对齐异或
0 0 0 1 0 1 0
1 0 1 1
─────────────
0 0 0 0 0 0 1 (1010⊕1011=0001)
停下！剩下的位数不足 4 位（除数是4位），不能再除了
第 3 步 · 取余数 = 最后 3 位：
剩下的: 0 0 0 0 0 0 1
└─┬─┘
最后 3 位 = 0 0 1 ← 这就是校验位
第 4 步 · 把余数填回去，拼成 CRC 码：
数据 : 1 1 0 1
校验位 : 0 0 1
─────────────────────────
CRC 码 : 1 1 0 1 0 0 1 = 1101001
接收方怎么查错？拿整串再除以同一个多项式：
1101001 ÷ 1011（异或除法）
余数 = 000 → 能整除 → 没出错 ✓
余数 ≠ 000 → 除不尽 → 出错了 ✗
🐣 验证的「异或除法」到底怎么除？（一步步）
规则只有一个动作，反复做：瞄当前最左位，是 1 就把除数对齐异或；是 0 就跳过往右挪一位。
被除数：1 1 0 1 0 0 1 除数：1 0 1 1
第1步 最左位是1 → 对齐异或
1 1 0 1 0 0 1
1 0 1 1
─────────────
0 1 1 0 0 0 1 (1⊕1=0, 1⊕0=1, 0⊕1=1, 1⊕1=0)
第2步 最左是0，跳过；下一个1在第2位 → 除数右移1格异或
0 1 1 0 0 0 1
1 0 1 1
─────────────
0 0 1 1 1 0 1 (1⊕1=0, 1⊕0=1, 0⊕1=1, 0⊕1=1)
第3步 前两位是0，跳过；1在第3位 → 右移异或
0 0 1 1 1 0 1
1 0 1 1
─────────────
0 0 0 1 0 1 1 (1⊕1=0, 1⊕0=1, 1⊕1=0, 0⊕1=1)
第4步 前三位是0，跳过；1在第4位 → 右移异或
0 0 0 1 0 1 1
1 0 1 1
─────────────
0 0 0 0 0 0 0 (1⊕1=0, 0⊕0=0, 1⊕1=0, 1⊕1=0)
停！除数4位，已到第4位，再往右不够对齐了
最后 3 位（校验位位数）= 0 0 0 → 余数 = 000 → 能整除，没出错 ✓
对比：如果某一位真的出错了，余数就会非 0（脚本实测）：
正确码 1101001 ÷ 1011 → 余数 000 → 没出错 ✓
第3位错 → 1111001 ÷ 1011 → 余数 110 → 出错 ✗
第1位错 → 0101001 ÷ 1011 → 余数 101 → 出错 ✗
🔑 「整除」的准确含义：不是数学上除尽，而是做异或长除法，最后余数全为 0。
发送方造的码天生余数为 0；接收方一除，余数变非 0 就说明中途被破坏了。
🔑 为什么「补0」这招管用？因为 数据补0 = 商×除数 ⊕ 余数，移项得 数据补0 ⊕ 余数 = 商×除数。
而「数据补0 ⊕ 余数」正好就是「把补的 0 换成余数」→ 所以「数据+余数」一定能被整除。
⚠️ CRC 只能检错，不能纠错——除不尽只告诉你「坏了」，不告诉你是哪一位。（这点和海明码相反）
自查：数据 1101、G(x)=x³+x+1（1011），CRC 码是多少？
点击看答案
① 补 3 个 0 → 1101000
② 模 2 除法（异或）得余数 001
③ CRC 码 = 数据 + 校验位 = 1101 + 001 = 1101001
验证：1101001 ÷ 1011 模 2 余数为 000（能整除）✓
（点上面的“逐步计算”能看到每一步）
⑤ 一页总结
| 考点 | 记住这一句 |
|---|
| 码距 | 任意两个合法编码最少差几位 |
| 检错 e 位 | 码距 ≥ e + 1 |
| 纠错 t 位 | 码距 ≥ 2t + 1 |
| 奇偶校验（一维） | 码距 2，检 1 位错，不能纠错（偶数个错检不出）；二维（水平垂直）码距 4、可纠 1 位 |
| 海明码 | 2k−1 ≥ n+k；校验位在 2 的幂位置；G 值 = 出错位置 |
| CRC | 补 r 个 0 → 模 2 除（异或）→ 余数即校验位 |