对 Hamming Code(海明码) 的分析和总结

码距:是两组 字码组 之间,位数不同的个数,比如说 1100、1010 他们的码距为2,有2位不同。
我这里统一将:00010 这样的一组二进制称为码组,下面不再重复。
海明码的最短码距为3,这时候有三个校验位。(我不太明白码距和检错,纠错能力的关系,所以不讨论)
先来看一张图,在信息位为4位,海明码3位的时候,每位校验位能覆盖的范围。
海明码简单分析
海明码校验范围

海明码校验范围

上面的内容只是热身,下面是如何计算海明码,很简单,跟我一起学习!

海明码简单分析

确定校验位个数

海明码的码组长度需要符合:2^r – 1 (r代表校验位个数)
为什么是这个公式呢?因为:只有这样才能保证校验位足够覆盖整个需要校验的码组。
比如说:校验位有3位,那就是2^3 = 8 – 1 = 7 这样就可以校验长度为7的码组,如果按实际来说,也就是信息位 4 位,校验码 3 位。
通过上面分析,我们知道校验位 r 加上信息位 k 就等于 2^r – 1 , 这也就是为什么书上有 k + r <= 2^r – 1 的原因,下面是一些 R 和 K的关系表

|信息码位数|1|2~4|5~11|12~26|27~57|58~120|
|——–|-|—|—-|—–|—–|——|
|校验码位数|2| 3| 4| 5| 6| 7|
注:表中数据取自网络

确定校验位的位置

知道了需要多少位校验码,还需要知道把校验码放在哪个位置上才行,这个只要记住,信息位在非2n的位置上,而校验位是在2n的位置上就可以了,条件再严格点就是,书上说的信息位所在海明码中的下标是需要等于前面几个校验组的下标,看到这里不懂没有关系,下面进行简单的例题分析。
举个粟(例)子:
信息字码组 : 1101 , 这时候信息位 k = 4 , 根据 k + r <= 2^r – 1 ,得出 r = 3 , 那就按书上说的,用P1、P2、P3来表示这3位校验码,这时候我们就来做填字格游戏。
>P1 P2 1 P3 1 0 1
位置就这么简单的确定下来了,如果位数更多的话也是一样的,校验位就是在 1、2、4、8、16…….这些位置上。

计算校验位 Pi

上面已经知道要在什么位置插入校验码,现在就差下锅的料了,怎么求校验位实际的值呢?很简单!
根据海明码定义,是通过将信息进行分组,才得以实现检错和纠错的能力,就像一开始的图,每一个Pi都会包含3个信息位。
问题来了,那我怎么知道这些信息位是哪几个?还是书上的定义……
重点
比如说信息 1 1 0 1 ,从上面填字格游戏我们可以看出,被分别安排在 H3,H5,H6,H7的位置(这些位置怎么来的?7位数从1到7给每位编号嘛!)
则:H3 = H1+H2 (这里是等式右边下标相加等于等式左边下标的意思,下面一样)
>H5 = H1+H4
>
>H6 = H2 + H4
>
>H7 = H1 + H2 + H4
通过上面的关系式,我们可以看出,右边在海明码中的数位,正好都是校验码的位置,下面来正式求校验码了。
>P1(H1) = H3 ⊕ H5 ⊕ H7 (⊕表示异或)
>
>P2(H2) = H3 ⊕ H6 ⊕ H7
>
>P3(H4) = H5 ⊕ H6 ⊕ H7
大功告成!啥?还要我算出来?打字很累的,手短打字又慢,行吧行吧,想在以前自己学海明码,怎么看都不会的份上,可能也是自己太笨…….
信息码:1101 对应海明位 H3、H5、H6、H7,不要把海明码,校验位,信息位搞混了哦!虽然我也是经常弄混哈哈!
>P1 = 1 ⊕ 1 ⊕ 1 = 1;
>
>P2 = 1 ⊕ 0 ⊕ 1 = 0;
>
>P3 = 1 ⊕ 0 ⊕ 1 = 0;
啥?异或不懂?没关系,我也经常不懂,相同 = 0 ,不同 = 1,异表示不同,按或的规则,是不是好奇葩!
好了,现在我们可以完成填字游戏了 P1 P2 1 P3 1 0 1 ==> 1010101,这就是我们最后需要得到的海明码,终于完成了!
还没完呢……有了这个海明码还需要知道怎么校验有没有出错啊,简单简单,跟我继续来学习!

海明码纠错和检错

有了上面的校验码和信息码,我们就能借用他们去知道怎么检查,信息在传送的过程中有没有发生错误,废话不多说,下面开始,还是书上的定义,因为校验码有三位,我们这里再申明三位码分别用S1、S2、S3表示,满足下列关系:
>S1 = P1 ⊕ H3 ⊕ H5 ⊕ H7 ;
>
>S2 = P2 ⊕ H3 ⊕ H6 ⊕ H7;
>
>S3 = P3 ⊕ H5 ⊕ H6 ⊕ H7;
这样求出来的S1、S2、S3如果都为0就是没有出错,如果不是0就表示在海明码中出错的位置,将其取反就可以起到纠错的功能了。很简单吧,等等,为什么是上面的关系式?哪来的?可以往上看看求校验码那里,这就是分组的结果,这里我就偷懒下不算了,你们可以自己算算,真的结束了……

写在最后

这些文字都是根据个人所理解,根据自己的语言和思路,希望能对那些还不明白的人有一些帮助,如果我的文章有错误,请无情的给予指出,在此表示感谢!
此条目发表在计算机那些小事分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注