中财网all黑子 重生强化 完结:海明校验码
来源：百度文库 编辑：中财网 时间：2024/05/02 10:52:57
海明校验关键的一个前提是,数据位中只能有一位出错.这也是海明码产生的依据所在.
海明码的提出者Richard Hamming确实很高明.以至于看过之后,你还摸不着脑袋.其实,只要根据数据中只有一位出错的前提,相信各位读者也能提出所谓的海明码.
海明码到底是怎样提出的呢？我们不妨自己先偿试一下.无非就是要指出数据位中唯一出错的那一位嘛.自己动手吧.
判断是否出错
异或运算可以查错.将各数位的异或结果与各数位进行异或,为0,则正确,否则错误.如对 (1011) 2. 各数位异或结果r = -1⊕0⊕1⊕1=1.你可能会说r再异或上原来的数不就是原来的数自己异或上自己吗？结果一定为0,有什么意义呢？要清楚,你将r跟原来的数一起传出去的时候,可能就出错了,到时候与r异或的就可能不是原数了。而且根据前提，只有一位出错,1的个数就不太为偶数,r与原数异或就为1.
标识哪一位出错
从最笨的方法开始.为每一位配上一个校验位.校验位的值等于对应原数.如要为1011配上校验位.得到1011 1011.验证的时候,校验位与原数异或,若为1.则表明该位或其校验位出错了.很显然,这种方法,不能唯一确定那一位出错了.
再改进一下.我们把数据中的每一位依次独立起来,这样只要出错,那么与它相干的校验结果一定与众不同.配上校验码的算法是:每一位的校验位是除该位外其它各位的异或的结果.以(1011) 2为例.其对就校验码为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) 2的四位数,除了第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）2的海明码.
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）2= （7）10,指示的正是第7位出错了！
海明码的提出者Richard Hamming确实很高明.以至于看过之后,你还摸不着脑袋.其实,只要根据数据中只有一位出错的前提,相信各位读者也能提出所谓的海明码.
海明码到底是怎样提出的呢？我们不妨自己先偿试一下.无非就是要指出数据位中唯一出错的那一位嘛.自己动手吧.
判断是否出错
异或运算可以查错.将各数位的异或结果与各数位进行异或,为0,则正确,否则错误.如对 (1011) 2. 各数位异或结果r = -1⊕0⊕1⊕1=1.你可能会说r再异或上原来的数不就是原来的数自己异或上自己吗？结果一定为0,有什么意义呢？要清楚,你将r跟原来的数一起传出去的时候,可能就出错了,到时候与r异或的就可能不是原数了。而且根据前提，只有一位出错,1的个数就不太为偶数,r与原数异或就为1.
标识哪一位出错
从最笨的方法开始.为每一位配上一个校验位.校验位的值等于对应原数.如要为1011配上校验位.得到1011 1011.验证的时候,校验位与原数异或,若为1.则表明该位或其校验位出错了.很显然,这种方法,不能唯一确定那一位出错了.
再改进一下.我们把数据中的每一位依次独立起来,这样只要出错,那么与它相干的校验结果一定与众不同.配上校验码的算法是:每一位的校验位是除该位外其它各位的异或的结果.以(1011) 2为例.其对就校验码为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) 2的四位数,除了第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）2的海明码.
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）2= （7）10,指示的正是第7位出错了！