海明码
原理
在数据位中插入若干校验位，每个校验位负责检验特定位置的数据位。当出现 1 位错误时，将各校验结果组合起来可以直接得到出错位的编号，从而纠正。
校验位的个数
设数据位为 n 位，需要 r 个校验位，满足：
2^r ≥ n + r + 1
| 数据位 n | 校验位 r |
|---|---|
| 1 | 2 |
| 2~4 | 3 |
| 5~11 | 4 |
| 12~26 | 5 |
校验位的位置与分工
校验位放在编号为 2^0, 2^1, 2^2, … 的位置（第 1, 2, 4, 8, … 位），其余位放数据。
每个校验位 P_i 负责所有编号的第 i 个二进制位为 1 的位：
- P₁（位1，二进制 001）：负责位 1, 3, 5, 7, 9, 11, …
- P₂（位2，二进制 010）：负责位 2, 3, 6, 7, 10, 11, …
- P₄（位4，二进制 100）：负责位 4, 5, 6, 7, 12, 13, …
每个校验位的值 = 其负责的所有位异或的结果（使该组 1 的个数为偶数）。
例子（4位数据 → 7位海明码）
数据 D = d₄d₃d₂d₁ = 1 0 1 1
码字位置：P₁ P₂ d₁ P₄ d₂ d₃ d₄
填入数据：P₁ P₂ 1 P₄ 0 1 1
计算校验位（偶校验）：
- P₁：位1,3,5,7 = P₁, 1, 0, 1 → P₁ = 1 XOR 0 XOR 1 = 0
- P₂：位2,3,6,7 = P₂, 1, 1, 1 → P₂ = 1 XOR 1 XOR 1 = 1
- P₄：位4,5,6,7 = P₄, 0, 1, 1 → P₄ = 0 XOR 1 XOR 1 = 0
最终码字：0 1 1 0 0 1 1（位1~7）
纠错过程
接收方对每组重新计算校验，若结果不全为 0，将各非零校验位的编号相加即为出错位编号，将该位取反即可纠正。
例：校验结果 P₄=1, P₂=1, P₁=0 → 出错位 = 4+2 = 第6位。
能力总结
| 能力 | 说明 |
|---|---|
| 检测 1 位错 | ✅ 并能纠正 |
| 检测 2 位错 | ✅ 但不能纠正（需额外加 1 位全局校验位） |
| 检测 3 位及以上 | ❌ 不可靠 |