3.5　检错和纠错

你永远不知道什么时候就有一束迷路的宇宙射线击中一块内存并破坏数据。如果能知道这种事情发生的时间而且还能修复损坏就好了。当然，这样的改进是需要耗费金钱的，而且在消费级设备中并不常见。

我们希望在不需要存储完整的第二份数据的情况下，检测出错误。但无论如何，这都行不通。因为我们不知道哪个副本是正确的。我们可以存储两个额外的副本，并假设匹配对（如果有的话）是正确的。那些本就是为恶劣环境设计的计算机可以做到这一点，这些计算机中还使用了更昂贵的电路设计，确保被质子击中时不会使电路烧毁。例如，航天飞机有冗余的计算机和在检测到错误时发挥作用的表决系统。

我们可以用一种叫作奇偶校验的方法来测试1位错误。其思想是将设置为1的位数相加，并使用额外的位来存储相加结果是奇数还是偶数。我们可以通过取位的XOR来实现这一点。有两种取位的形式：在偶校验中使用位和，在奇校验中使用位和的补码。这个选择可能看起来很奇怪，但这个术语来自1或0的数目，包括奇偶校验位。

图3-31的左半部分展示了偶校验的计算过程，存在4个1，因此奇偶校验位为0。右半部分同样展示了奇偶校验的检查，输出0表示数据是正确的，或者至少用奇偶校验判断是正确的。奇偶校验的一个大问题是，如果有两个位错误，则看起来像是正确的，它只能捕捉奇数个错误。

图3-31　奇偶校验

还有更为复杂的方法，如美国数学家Richard Hamming（1915—1998）发明的汉明码。汉明码需要占用更多的位，允许检测更多的错误，并允许纠正一些错误。包括汉明码这一电路的检错和纠错（Error Checking and Correcting, ECC）存储芯片是可用的。ECC存储芯片通常用于大数据中心，甚少用于消费级设备。

像奇偶校验这样的方法适合不断变化的数据。也有一些成本较低的方法可以验证静态块数据，例如计算机程序。其中最简单的是校验和，即将每个数据位置的内容累加为某个n位的值，并丢弃溢出位。通常在程序运行之前，可以将校验和与程序进行比较。校验和值越大（即n越大），得到假阳性的概率越低。

循环冗余校验（Cyclic Redundancy Check, CRC）在数学上是校验和的一个更好的替代。哈希码也是校检和很好的替代。循环冗余校检的目标是计算出一个对数据来说足够唯一的验证数字，这样对于大多数的更改，验证数字将不再正确。