海明校验码（纠错码到底是个啥?）

前言

有些硬件未使用ECC内存，在大量数据中，内存中出现了单比特翻转（Single-Bit Flip）这个传说中的硬件错误。

由于内存中的一个整数字符，遇到一次单比特翻转转化而来。 ASCII码二进制表示是0010 0100，所以它完全可能来自 0011 0100 遇到一次在第4个比特的单比特翻转，也就是从整数“4”变过来的。但也只能推测是这错误，而不能确信。因为单比特翻转是个随机现象。

ECC内存

Error-Correcting Code memory，纠错内存，就是在内存出现错误时，能自我纠正。

奇偶校验 && 校验位

捕捉错误的好办法。内存里的单比特翻转或错误，并非罕见现象。无论因内存制造质量造成的漏电，还是外部射线，都有概率造成单比特错误。而内存层面的数据出错，软件工程师不会知道，而且这出错很可能随机的。

那到底如何避免这问题？

ECC发明前，工程师已经开始通过奇偶校验发现这些错误：把内存里的N位比特当成一组。如8位就是一字节。然后，用额外一位记录这8比特里有奇数个1还是偶数个1：

奇数个1，则额外一位就记录为1偶数个1，则额外一位就记录成0

额外那一位，就称为校验码位。

若这字节不幸发生单比特翻转，则数据位计得的校验码，就和实际校验位里数据不同，就知道出错了！

校验位计算非常快，只需遍历一遍待校验数据，通过O(N)时间复杂度。

校验码思路有很多应用场景：下载一些软件时，除了下载的包文件，还有对应MD5这样的哈希值或循环冗余编码（CRC）的校验文件。当把软件下载后，可计算一下对应软件校验码，和官方校验码比对，不一样，则不要轻易安装这软件。有可能软件包是坏的。更危险的，可能被人植入后门。

奇偶校验的缺陷

只能解决遇到单个位的错误或奇数个位的错误

如出现2个位翻转，则该字节的校验位计算结果其实没变，校验位也无法发现这错误。

只能发现错误，但是不能纠正错误

即使在内存里面发现数据错误，只能中止程序，而不能让程序继续正常运行。

所以，还需更好解决方案：

能发现更多位的错误能够把这些错误纠正过来

这就是ECC内存:

能捕捉到错误能纠正发生的错误

这就是纠错码（Error Correcting Code）。升级版叫纠删码（Erasure Code），不仅能够纠正错误，还能够在错误不能纠正的时候，直接把数据删除。无论ECC内存，还是网络传输，硬盘的RAID都利用纠错码和纠删码技术。

无论奇偶校验码 or CRC循环校验码，都只能通知你的数据出错了。所以，校验码也称为检错码（Error Detecting Code）。

但无法回答“错哪儿了”，导致处理方式只有一种：当成“哪儿都错了”。若是下载一个文件，发现校验码不匹配，只能重新下载程序计算后放到内存里的数据，只能再重新算一遍。

这效率也太低了吧！所以得有新的方案，能告诉我们：

“我错了”“错哪儿了”

于是，计算机科学家们就发明了

纠错码

需更多冗余信息，通过这些冗余信息，可知哪里数据错了，还能直接把数据改对。

海明码

最知名的纠错码。海明码（Hamming Code），以发明人Richard Hamming（理查德·海明）命名，上世纪四十年代发明。至今的ECC内存也还在使用海明码纠错。

最基础的海明码叫7-4海明码：

“7”，实际有效的数据，共7位（Bit）“4”，额外存储了4位数据，用来纠错

纠错码的纠错能力有限。不是错了多少位都能纠正。不然就不需要那7个数据位，只需要那4个校验位。这意味着可不用数据位就能传输信息了，就不科学了。7-4海明码里，只能纠正某1位错误。4位的校验码，一共可以表示 2^4 = 1624=16 个不同的数。根据数据位计出的校验值，是确定的。所以，若数据位出错，计出的校验码一定和确定的那个校验码不同。可能的值就在 2^4 - 1 = 1524−1=15 那剩下的15个可能的校验值当中。

15个可能的校验值，可对应15个可能出错的位。这个时候你可能就会问了，既然数据位只有7位，为啥要用4位校验码？3位不就够？2^3 - 1 = 723−1=7，正好对上7个不同数据位！

单比特翻转的错误，不仅可能出现在数据位，也可能在校验位。所以，7位数据位和3位校验位，若只有单比特出错，可能出错的位数就是10位，2^3 - 1 = 723−1=7 种情况是不能帮我们找到具体哪位出错。

若：

数据位有K位校验位有N位

则需满足下面这个不等式，才能确保能对单比特翻转的数据纠错：K + N + 1 <= 2^NK+N+1<=2N

有7位数据位，即K=7时，N最小值4。4位校验位最多可支持到11位数据位。

数据位数和校验位数的对照表

海明码纠错原理

数据位数确定时，如何计算所需的校验位？

算个4-3海明码（4位数据位，3位校验位）。

4位数据位，分别记作d1、d2、d3、d4。d取的是数据位data bits首字母3位校验位，分别记作p1、p2、p3。p取的是校验位parity bits首字母

从4位数据位拿走1位，计算个对应校验位。这校验位的计算用之前讲过的奇偶校验就可以了。如用d1、d2、d4计算出一个校验位p1d1、d3、d4计算出一个校验位p2d2、d3、d4计算出一个校验位p3对应表格：

d1这位数据出错，p1和p2和校验的计算结果不一样d2出错，是因p1和p3的校验的计算结果不同d3出错，则是因为p2和p3d4出错，则p1、p2、p3都不一样

所以，当数据码出错，至少有2位校验码计算不一致。

反过来思考，若p1的校验码出错，则只有p1的校验结果出错。p2和p3的出错结果也一样，只有一个校验码计算不一致。

所以校验码不一致，共 2^3-1=723−1=7种情况，正对应7个不同位数的错误：

可见海明码这纠错过程，像推理探案的过程。通过出错现场的额外信息，一步一步缕，到底哪位数据出错，还原出错时的快照。

如何生成海明码？

确定编码后，要传输的数据是多少位。比如7-4海明码，共11位。给这11位数据从左到右进行编号，并且也把它们的二进制表示写出来。

接着，先把这11个数据中的二进制整数次幂找出。7-4海明码里就是1、2、4、8。这些数就是校验码位，记为p1～p4。从二进制角度看，它们是这11个数当中，唯四的，在4个比特里，只有一个比特是1的数值。

剩下7个数就是d1-d7的数据码位。

对于校验码位，还是用奇偶校验码。但每个校验码位，不是用所有7位数据计算校验码。而是p1用3、5、7、9、11来计算。也就是，在二进制表示下，从右往左数的第一位比特是1的情况下，用p1作为校验码。

剩下的p2，我们用3、6、10、11来计算校验码，也就是在二进制表示下，从右往左数的第二位比特是1的情况下，用p2。那么，p3自然是从右往左数，第三位比特是1的情况下的数字校验码。而p4则是第四位比特是1的情况下的校验码。

任一数据码出错，至少有对应两或三个校验码对不上，这就能反找到哪个数据码出错。若校验码出错，则只有校验码这一位对不上，就知道是这校验码出错。

海明距离：形象理解海明码的作用

其实，我们还可以换一个角度来理解海明码的作用。对于两个二进制表示的数据，他们之间有差异的位数，我们称之为海明距离。比如 1001 和 0001 的海明距离是1，因为他们只有最左侧的第一位是不同的。而1001 和 0000 的海明距离是2，因为他们最左侧和最右侧有两位是不同的。

一位纠错，即所有和要传输数据的海明距离为1的数，都能被纠正回来。

而任何两个实际想传输的数据，海明距离都至少要是3。为什么不能是2？如果是2，就会有个出错的数，到两个正确的数据的海明距离都是1。看到这个出错的数时，就不知道究竟应该纠正到哪个数。

引入海明距离后，可形象理解纠错码。无纠错功能时，看到的数据就像是空间里的一个个点。这时，可让数据之间距离很紧凑，但若这些点的坐标稍有错，就可能搞错是哪个点。

在有了1位纠错功能后，就好像把一个点变成以该点为中心，半径为1的球。只要坐标在这个球范围内，都知道实际要的数据就是球心坐标。而各数据球不能距离太近，不同数据球之间要有3个单位距离。

总结

若对计算机组成原理有所了解，并能够意识到硬件存储层有数据验证和纠错需求，就能定位到问题。

奇偶校验，即如何通过冗余的一位数据，发现在硬件层面出现的位错误。但奇偶校验及其他校验码，只能发现错误，无法纠正错误。

通过在数据中添加多个冗余的校验码位，海明码不仅能够检测到数据中的错误，还能够在只有单个位的数据出错的时候，把错误的一位纠正过来。在理解和计算海明码的过程中，有一个很重要的点，就是不仅原来的数据位可能出错。我们新添加的校验位，一样可能会出现单比特翻转的错误。这也是为什么，7位数据位用3位校验码位是不够的，而需要4位校验码位。

海明码编码，通过用不同的校验位，匹配多个不同数据组，确保任一数据位出错，都会产生一个或多个校验码位出错的唯一组合。这在出错时，就能反过来找到出错的数据位，并纠正。只有一个校验码位出错时，就知道实际出错的是校验码位了。

参考

CRC，校验码算法《计算机组成与设计：软件/硬件接口》的5.5章节，可信存储器