海明校验码简析与举例

基本思想：
将有效信息按某种规律分成若干组，每组安排一个校验位，做奇偶测试，就能提供多位检错信息，以指出最大可能是哪位出错，从而将其纠正。实质上，海明校验是一种多重校验。
由Richard Hamming于1950年提出、还被广泛采用的一种很有效的校验方法，是只要增加少数几个校验位，就能检测出二位同时出错、亦能检测出一位出错并能自动恢复该出错位的正确值的有效手段，后者被称为自动纠错。它的实现原理，是在k个数据位之外加上n个校验位，从而形成一个k+n位的新的码字，使新的码字的码距比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中，当某一位出错后，就会引起相关的几个校验位的值发生变化，这不但可以发现出错，还能指出是哪一位出错，为进一步自动纠错提供了依据。

0或1构成
101表示5

00表示0
11表示1
传0就会由原先传0变成现在传00，如果对方接收到的数据是01或者10，请表示接收到的数据有误
传1就会由原先传1变成现在传11，如果对方接收到的数据是01或者10，请表示接收到的数据有误

再增加一位
000表示0
111表示1
传0就会由原先传0变成现在传000，对方接收到的情况000，001，010，011，100，101，110，111
如果接收到的是001，010，011，100，101，110六种情况，那么数据是错误的。
如果接收到的数据只有1位出错了。显然001，010，100这三种情况是1出错了，正确的应该是全000
011，101，110这三种情况是0出错了，正确的应该是全111。

码距：是指在一组编码中任何两个编码之间最小的距离。
距离：是指两个编码中相同位值不同的个数。000，001其距离是1，把这个距离称为海明距离。

码距为d，检验的错误个数为e，纠错的个数为t，它们之间存在的关系：
d>=e+1 可检验e个错
d>=2t+1 可纠正t个错
d>=e+t+1 且e>t，可以检验e个错，并纠正t个错。

海明校验判断一位出错满足公式：2^k-1>=n+k
数据位为n，校验位为k

如：数据位为8，那校验位k>=4
位置：校验位放在整个编码的2^i位上（i=0,1,2,…,k-1)
D7 D6 D5 D4 D3 D2 D1 D0
整个编码：（用二进制表示P1~D0位置数）
P1 P2 D7 P4 D6 D5 D4 P8 D3 D2 D1 D0
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100

P1=D7异或D6异或D4异或D3异或D1（位置的二进制数从右往左第一位为1的位置上的数进行异或运算）
P2=D7异或D5异或D4异或D2异或D1（位置的二进制数从右往左第二位为1的位置上的数进行异或运算）
P4=D6异或D5异或D4异或D0（位置的二进制数从右往左第三位为1的位置上的数进行异或运算）
P8=D3异或D2异或D1异或D0（位置的二进制数从右往左第四位为1的位置上的数进行异或运算）

数据位01101101（已知条件）
P1 P2 0 P4 1 1 0 P8 1 1 0 1
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100
P1=0异或1异或0异或1异或0=0
P2=0异或1异或0异或1异或0=0
P4=1异或1异或0异或1=1
P8=1异或1异或0异或1=1
海明校验码为：000111011101

P0=P1异或 P2 异或D7异或P4异或D6异或D5异或D4 异或 P8 异或D3异或D2异或 D1异或 D0=1
检二纠一错的编码是：1000111011101

校验 校验码