数据校验码--汉明码(Hamming code)

汉明码是Richard Hamming于1950年提出的。是目前广泛采用的一种有效的校验码，其中，主存的ECC(Error Correcting Code)采用的就是类似的校验码搜慧。

----摘自百度百科

这个分组的思想有点不是很理解。

以下使用P代表校验位，H代表汉明码，D代表原始信息位，N位信息位的位数，K位校验位的位数。

则N与K的关系为 2^(K-1) >=N+K+1 ,如下表:

假设原始数据信息位的位数为8，那么他需要的K值位5，即需要有5个校验位，组成的汉明码的位数为13.再根据校验位的分桥猜配原则，组成的汉明码如下：

|位|13| 12| 11 |10| 9| 8| 7 |6| 5| 4| 3| 2| 1|

|-|-|-|-|-|-|-|-|-|-|-|-|-|

|汉明码|P5| D8| D7| D6 | D5| P4| D4| D3| D2| P3| D1| P2| P1|

P5本来应该是放在第16位的，但是由于生成的汉明码位数为13所以它就被挪到的第13位了。

那么怎么确定校验呢？最初也困扰我许久。

先看一个表格：

其中H的下标代表在汉明码中的位置，也是P4P3P2P1组成的-十进制数

校验位Pi的偶校验结果就是:

P1 = D1 ^ D2 ^ D4 ^ D5 ^ D7

P2 = D1 ^ D3 ^ D4 ^ D6 ^ D7

P3 = D2 ^ D3 ^ D4 ^ D8

P4 = D5 ^ D6 ^ D7 ^D8

如果是奇校验的话上面的结果取反就是了。

那么还有P5呢？上面的结果中，D4，D7出现了3次，而D1，D2，D3，D5，D6，D8仅出现了2次，为了使其各个信息位在校验中均匀的出现校验，从而定义 P5 = D1 ^ D2 ^ D3 ^ D5 ^ D6 ^D8 ,这样，每一位信息位都均匀的出现在3个Pi值得形成关系中，当任意一位信息位变化的时候都会引起3个P值得变化， 即合法汉明码的码距为4 (前面都懂，这个码距为4有点想不明白)

这就是编码了。

现在再来看看这句话

P1，P2，P3，P4，P5的位数分别为1,2,4,8,13

D1的汉明码位数为3，3 = 2 + 1所以D1会被P1，P2两个校验位所校验。

根据偶校验结果以及上应该就清楚了。

将收到的汉明码进行偶校验(当然也可以进行奇校验，前提是前面编码的时候使用的是奇校敏漏型验)

S1 = P1 ^ D1 ^ D2 ^ D4 ^ D5 ^ D7

S2 = P2 ^ D1 ^ D3 ^ D4 ^ D6 ^ D7

S3 = P3 ^ D2 ^ D3 ^ D4 ^ D8

S4 = P4 ^ D5 ^ D6 ^ D7 ^D8

S5 = P5 ^ D1 ^ D2 ^ D3 ^ D5 ^ D6 ^D8

汉明码出错情况:

记录 S = S5 S4 S3 S2 S1

以上结果分析基于偶校验。

|汉明码||P5| D8| D7| D6 | D5| P4| D4| D3| D2| P3| D1| P2| P1|

|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|

|出错位号||H13| H12| H11 |H10|H9| H8| H7 |H6| H5| H4| H3| H2|H1|

||S5|1|1|0|1|1|0|0|1|1|0|1|0|0|

||S4|0|1|1|1|1|1|0|0|0|0|0|0|0|

||S3|0|1|0|0|0|0|1|1|1|1|0|0|0|

||S2|0|0|1|1|0|0|1|1|0|0|1|1|0|

||S1|0|0|1|0|1|0|1|0|1|0|1|0|1|

如果一条信息中包含更多用于纠错的位，且通过妥善安排这些纠错位使得不同的出错位产生不同的错误结果，那么我们就可以找出出错位了。在一个7位的信息中，单个位出错有7种可能，因此3个错误控制位就足以确定是否出错及哪一位出错了。

汉明码SECDED（single error correction, double error detection）版本另外加入一检测比特，可以侦测两个或以下同时发生的比特错误，并余桐行能够更正单一比特的错误。因此，当发送端与接收端的比特样式的汉明距离（Hamming distance）小于或等于1时（仅有1 bit发生错误），可实现可靠的通信。相对的，简单的奇偶检验码除了不能纠正错误之外，也只能侦测出奇数个的错误。

下列通用算法可以为任意位数字产生一个可以纠错一位的汉明码：

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的数。

采用奇校验还是偶校验都是可行的。偶校验从数学的角度看更简单一些，但在实践中并没有区别。校验位一般的规律可以如下表示：

观察上表可发现一个比较直观的规律：第i个检验位是第2i-1位，从该位开始，检验2i-1位，跳过2i-1位……依次类推。例如上表中第3个检验位p4从第23-1=4位开始，检验4、5、6、7共4位，轮型然后跳过8、9、10、11共4位，再检验12、13、14、15共4位……

---