CODEX, MEMO

关于Hamming校验纠错算法

Hamming算法可以对任意字长的内存建立起纠正码（注意，是不止可以检验出错误，还可以纠错）。原理如下：
假设原始的数据有m位，向这m位数据里加入r位检验位，就得到m+r位的字长。在这m+r位里，所有2的整数幂的位是检验位，其他的是数据位（注意这里的位都是从1开始计数的，而不是从0开始）。

下列通用算法可以为任意位数字产生一个可以纠错一位的汉明码：
1.从1开始给数字的数据位（从左向右）标上序号, 1，2，3，4，5…
2.将这些数据位的位置序号转换为二进制，1, 10, 11, 100, 101,等。
3.数据位的位置序号中所有为二的幂次方的位（编号1，2，4，8，等，即数据位位置序号的二进制表示中只有一个1）是校验位
4.所有其它位置的数据位（数据位位置序号的二进制表示中至少2个是1）是数据位
5.每一位的数据包含在特定的两个或两个以上的校验位中，这些校验位取决于这些数据位的位置数值的二进制表示
(1) 校验位1覆盖了所有数据位位置序号的二进制表示倒数第一位是1的数据：1（校验位自身，这里都是二进制，下同），11，101，111，1001，等
(2) 校验位2覆盖了所有数据位位置序号的二进制表示倒数第二位是1的数据：10（校验位自身），11，110，111，1010，1011，等
(3) 校验位4覆盖了所有数据位位置序号的二进制表示倒数第三位是1的数据：100（校验位自身），101，110，111，1100，1101，1110，1111，等
(4) 校验位8覆盖了所有数据位位置序号的二进制表示倒数第四位是1的数据：1000（校验位自身），1001，1010，1011，1100，1101，1110，1111，等
(5) 简而言之，所有校验位覆盖了数据位置和该校验位位置的二进制与的值不为0的数。

例如，一个16位的字就需要加入5位的校验位，即第1、2、4、8、16位为校验位。此时的实际字长达到21位。第一个校验位负责检验第1、3、5、7、9、11、13、15、17、19、21位，第二个校验位负责检验第2、3、6、7、10、11、14、15、18、19  ……..
具体如下：
第1位负责检验：1、3、5、7、9、11、13、15、17、19、21(即检验以上所有bit位状态为1的个数，若为偶数，偶检验将检验位设为0，反之为1。下同)
第2位负责检验：2、3、6、7、10、11、14、15、18、19
第4位负责检验：4、5、6、7、12、13、14、15、20、21
第8位负责检验：8、9、10、11、12、13、14、15、
第16位负责检验：16、17、18、19、20、21
 
那么，怎么知道一个检验位都负责检验哪些位呢？
Hamming校验码的设置原则是：第B位通常由第b1,b2,b3,…,bj位来检验，其中B=b1+b2+b3+…+bj.
比如，第5位由第1位和第4位一起校验（5=1+4），第6位由第2位和第4位一起校验(6=2+4)。
为了说明纠错过程，下面假设有一个这样的16位字：
1 1 1 1 0 0 0 0 1 0 1 0 1 1 1 0
假设使用偶检验，则加入第1、2、4、8、16位校验码后得到的21位字就如下所示：
(测试办法：画21个框，除去检验位，把原始数据填入数据框，然后再填写校验位)
0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 0
假设第五位出错了，变成：
0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 0
那么，检验位1和检验位4所在的那个检验列的1的个数都不是偶数个了，所以就知道出错了。
这时，只要知道哪一位出错了就可以将它纠正回来。
想要知道哪一位出错，有两种方法：
第一个是对比分析。比如，上面的例子中，由于第1个检验位和第四个验位所检验的队列都出错了，那么，出错位肯定是他们所共有，而其他队列所没有的。对比一下就知道那就是第5位了。
第二种方法就是，将出错队列的检验位相加，就得到出错位。上面例子中，1+4=5.
 
需要说明的是，这种算法纠错的前提是，它假设出错的位数为1位。也就是说，如果错了3位，这个算法也会以为它只有一位出错（错了2位就检验不出来了,因为奇偶检验的Hamming码距是2）