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

引言：数据在路上跑的时候，难免被电磁干扰 “踹一脚”，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 的个数，硬件上用异或门即可实现

神也有缺点：

局限性：

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

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

海明有个周末难题

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

校验位站 2 的幂次位

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

下面介绍海明码的规则：

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

################################################################写到这里了你个沙雕别push你没写完