海明校验码

海明校验码

海明校验关键的一个前提是,数据位中只能有一位出错.这也是海明码产生的依据所在.

海明码的提出者Richard Hamming确实很高明.以至于看过之后,你还摸不着脑袋.其实,只要根据数据中只有一位出错的前提,相信各位读者也能提出所谓的海明码.

海明码到底是怎样提出的呢？我们不妨自己先偿试一下.无非就是要指出数据位中唯一出错的那一位嘛.自己动手吧.

判断是否出错

异或运算可以查错.将各数位的异或结果与各数位进行异或,为0,则正确,否则错误.如对 (1011) ₂. 各数位异或结果r = ­1⊕0⊕1⊕1=1.你可能会说r再异或上原来的数不就是原来的数自己异或上自己吗？结果一定为0,有什么意义呢？要清楚,你将r跟原来的数一起传出去的时候,可能就出错了,到时候与r异或的就可能不是原数了。而且根据前提，只有一位出错,1的个数就不太为偶数,r与原数异或就为1.

标识哪一位出错

从最笨的方法开始.为每一位配上一个校验位.校验位的值等于对应原数.如要为1011配上校验位.得到1011 1011.验证的时候,校验位与原数异或,若为1.则表明该位或其校验位出错了.很显然,这种方法,不能唯一确定那一位出错了.

再改进一下.我们把数据中的每一位依次独立起来,这样只要出错,那么与它相干的校验结果一定与众不同.配上校验码的算法是:每一位的校验位是除该位外其它各位的异或的结果.以(1011) ₂为例.其对就校验码为r1r2r3r4 = 0100（r1 = 0⊕1⊕1 = 0,r2 = 1⊕1⊕1,依次计算）,这样比如某一位出错,比如第一位,那与第一位相干的r2,r3,r4在做校验时,一定为1,只有r1没有相干,所以为0.表明第一位出错了.若是校验位出错了,如r1出错.那么只有r1的校验结果为1,其它三位校验位都为0.因此,可以辨别是哪一位出错了.这种方法,看起来不错,但在数据位太少,如1位或2位时,就无法指示哪一位出错了.而且需要配上跟原数长度一样的校验位,岂不是浪费空间.

最经济的校验位（Richard Hamming真高明）

上面的的例子中,我们使用0111判断第一位出错了,1011,是第二位,1101第三位,1110第四位.而1000,表示第一位校验出错,0100,第二位校验位,……

这样的话校验结果的4位数只表示了8位状态.而4二进制数,是可以表示16位状态的,这就是冗余所在.

Richard Hamming的高明在于充分利用了配上的校验位.对于4位数,配上3位校验位就足够了.3位二制过有8种状态,正确的情况（为0时）占用一种,刚好剩下7种,指示7位数中的某一位出错.假设,校验结果为S1,S2,S3.怎样校验,使S1S2S3可以表示哪一位出错了呢？算法是：当某一位的二进制数值,在对应的Si（i=1,2,3）中为1时,那么Si的校验表达式中就有它.

	D1	D2	D3	D4	D5	D6	D7
S1				1	1	1	1
S2		1	1			1	1
S3	1		1		1		1

结果是：

S1 = D4⊕D5⊕D6⊕D7

S2 = D2⊕D3⊕D6⊕D7

S3 = D1⊕D3⊕D5⊕D7

那么这7位中，哪些是校验位，哪些是原始数据呢？由前面介绍我们知道,增加的校验位只和原来的数据作异或.因此,挑出那么,只校验过程中,只出现过一次的数.那么就是D1,2D,D4了.

显然，D1是原始数据D3,D5,D7的校验位.

D1 = D3⊕D5⊕D7

同样的有：

D2 = D3⊕D6⊕D7

D4 = D5⊕D6⊕D7

对于数据(1011) ₂的四位数,除了第1,第2,第4位不能安放之外,其它们可以随便放（因为校验位随安放次序而改变）,只要保证出错位只有一位,那么S1S2S3就可以保证指出哪位出错.一般是,将数据顺序安放在D3,D5,D6,D7位置上,再进一步示校验位.得到最后编码：

D1	D2	D3	D4	D5	D6	D7
0	1	1	0	0	1	1

显然,校验位的位数k与原始数据位数n的关系为：

2^k-1 >= n+k

再举一个例子：求5位数（11010）₂的海明码.

1） 确定校验位的位数为4.因为4满足2^4-1>=5+4,且4是满足该条件的最小整数.

2） 确定校验结果Si的算法.

	D1	D2	D3	D4	D5	D6	D7	D8	D9
S1								1	1
S2				1	1	1	1
S3		1	1			1	1
S4	1		1		1		1		1

根据表可以写出：

S1 = D8⊕D9

S2 = D4⊕D5⊕D6⊕D7

S3 = D2⊕D3⊕D6⊕D7

S4 = D1⊕D3⊕D5⊕D7⊕D9

3） 确定校验位次序

在Si表达式中只出现一次的,也就是在Si-Di表格中只有一个“1”的列,为校验位.分别为：

D8=D9

D4=D5⊕D6⊕D7

D2=D3⊕D6⊕D7

D1=D3⊕D5⊕D7⊕D9

4） 填充好编码

D1	D2	D3	D4	D5	D6	D7	D8	D9
1	0	1	0	1	0	1	0	0

5） 验证

以第7位出错为例.即数据更改为：

D1	D2	D3	D4	D5	D6	D7	D8	D9
1	0	1	0	1	0	0	0	0

计算校验结果：

S1 = D8⊕D9 = 0

S2 = D4⊕D5⊕D6⊕D7 = 1

S3 = D2⊕D3⊕D6⊕D7 = 1

S4 = D1⊕D3⊕D5⊕D7⊕D9 = 1

S1S2S3S4 = （0111）₂= （7）₁₀,指示的正是第7位出错了！