什么是汉明码
简单来说汉明码就是在简单奇偶数校验的基础上进行的改进后的校验方式.在平时我们所遇到的数据错误一般都是一位数据发生改变,举个简单的例子:
我们假如传输" 1010 “这段数据,发生错误很可能就是"1010"变为"1011”.
汉明码如何进行校验的
简单奇偶校验法
我们先简单介绍一下简单奇偶校验的方法:
例如一段数据为:“1101010”,我们运用偶校验,这是我们的数据就为"11010101"
最后一位数据1就是我们的校验位,当数据传输后我们对数据进行检查我们就只用计算数据中1的个数就能判断出数据是否发生错误,当然我们说的都是数据只发生一位数据错误.
汉明码的分组
OK,我们明白了简单奇偶校验方法后我们再来看看汉明码是怎么进行校验的.
还是这段数据"1101010"首先我们先确定需要多少位校验码,在这里有个公式:
2r-1 >= k+r ,其中r就是我们需要的校验码个数,k就是我们数据的个数,利用这个公式我们就能算出在这段数据中我们需要四位校验码,但这四位校验码放在哪里? 书上给的原话是:幂次方的方位上存放校验位, 什么意思呢?还是1101010这组数据,我们选择校验位就选择1,2,4,8这四位,大家这时应该明白了吧.就是2的次方位.这时我们吧数据写为_ _1_101_010
我们校验位选完了,应该怎么进行分组呢,汉明码首先会把所以数据都进分组,及每一位数据都是一个小组,那么大组应该怎么去分呢?
我们用P1~P4代替这四个校验位
| h1 | h2 | h3 | h4 | h5 | h6 | h7 | h8 | h9 | h10 | h11 |
|---|---|---|---|---|---|---|---|---|---|---|
| ~ | ~ | D1 | ~ | D2 | D3 | D4 | ~ | D5 | D6 | D7 |
| P1 | P2 | 1 | P3 | 1 | 0 | 1 | P4 | 0 | 1 | 0 |
G1=(P1,D1,D2,D4,D5,D7)
G2=(P2,D1,D3,D4,D6,D7)
G3=(P3,D2,D3,D4)
G4=(P4,D5,D6,D7)
这就是这四组的划分方式,那它是按照怎么样的方式进行分组的呢?先看分组的规则:
G1组是满足:XXX1类型
G2组是满足:XX1X类型
G3组是满足:X1XX类型
G4组是满足:1XXX类型
有细心的朋友就会发现我在表格上方也写了H1~H11,它就是分组的关键,举个例子:
D1这个数据是H3,那么把3转换成二进制就是:XX11,那么他就是同时属于G1和G2组,所以明白了把,这组数据是第几位数据(记得要加上校验位),把他转换为二进制,再看满足上面的那种类型就是那一大组的人.
校验位的数据如何确定
校验位的数据究竟是1还是0呢?这与我们选择的校验方式有关,我前面说过汉明码就是在奇偶校验的方式上改编过来的,所以也分为奇校验和偶校验.咱们国人都喜欢偶数,所以在这里我们使用偶校验的方式.
以P1为例,和它一组的数据为11100,1的个数为3那么为了满足偶校验P1的值就需要是1,这里说的奇偶个数不是对于这整段数据而言,是仅限于和P1一组的数据,及G1里面的数据.
ok,依照此方法我们可以算出P2,P3,P4.最后我们得到的数据就是11101011010,黄色的就是校验位.
汉明码是如何纠错的
我们先看上图,这里面的标的1~7仅指数据位,不包含校验码
同时我们所说的错误仅指数据出现一位错误
我们用0和1表示数据的对(0)与错(1)
例如:G1G2G3G4=0101,那么我们看图,仅G2G4所共有的元素是就是6,那么我们就知道是D6这位元素出现了错误.这就是汉明码的纠错
汉明码的优势和局限性
和简单奇偶校验法相比汉明码能够在一定程度上准确找到出现错误的数据对我们纠错有很大的方便.
| h1 | h2 | h3 | h4 | h5 | h6 | h7 | h8 | h9 | h10 | h11 |
|---|---|---|---|---|---|---|---|---|---|---|
| ~ | ~ | D1 | ~ | D2 | D3 | D4 | ~ | D5 | D6 | D7 |
| P1 | P2 | 1 | P3 | 1 | 0 | 1 | P4 | 0 | 1 | 0 |
我说在一定程度上就是有例外,还是上一组数据,我们假设D1和D4同时发生错误
G1=(P1,D1,D2,D4,D5,D7)
G2=(P2,D1,D3,D4,D6,D7)
G3=(P3,D2,D3,D4)
G4=(P4,D5,D6,D7)
那么最后得出来的结果就是G1,G2没有检出错误,G3出现错误,G4没有错误,这和G3的校验位出现错误的结论一样,这就没法检查出是一位错还是两位错.
好了,这就是汉明码的所有内容了.