引言

数据链路层拥有差错控制的功能,利用检错编码(可以检查出错误的帧数据)和纠错编码(可以检查错误帧并有一定的更正能力)。其中最常见的纠错编码是汉明码(海明码),但是虽然他常见,但是却并不是那么好理解,尤其对于初学者,第一次翻到有关汉明码的篇幅时必定感到大为头疼,那么我这里希望通过简洁的话语来使大家更好更快更准确的理解汉明码。

原理及提示

汉明码的实现原理是(1)在有效信息位中加入几个校验位形成汉明码,(2)并把汉明码的每个二进制位分配到几个奇偶校验组中。当某一位出错时,(3)就会引起有关的几个校验位的值发生变化,这不但可以发现错位,而且能指出错位的位置,为自动纠错提供依据。
tips:(1)汉明码可以发现双比特位错误,纠正单比特位错误(2)汉明码的工作原理可理解为“牵一发而动全身”

实现

引例

首先,举个栗子(*╹▽╹*):我们可爱的信源要向可爱的小信宿发送数据1010,在数据链路层为了保证信宿的数据链路层能够收到正确无误的1010,信源这边在数据链路层上想要通过使用汉明码的方式来“包装”一下我们的1010。好了,最后包装完得到的结果是1010010,其中有下划线的三位是校验位,其他的是原有的信息位。那么这个结果是如何得来的呢?

(1)首先,为什么会有三位校验位?
要发送的数据位数和校验位的位数两者的和要小于等于2的校验位数次方减1:设n为数据位数,k为校验位位数,则n和k应该满足n+k≤2k-1(若要检验两位错误,则需再增加一位校验位,及k+1位)
那么我们在这个例子中就是4+k≤2
k-1,解得k=3,所以我们需要3位校验位,那么我们也就知道“包装完”的数据一共有4+3=7位了。
(2)现在知道有多少校验位了,那么为什么这三个校验位要放在下划线的位置上呢?
因为我们汉明码规定了第i个校验位要放在最终数据的2(i-1)位置上,所以第一位上2(1-1)=2^0=1,那么第一个校验位P1放在二进制最终数据的第1个位置上,以此类推,我们得到最终的数据是D4D3D2P3D1P2P1(D为原数据位,P为校验位)
(3)那么在哪儿也知道了,这些校验位该咋取值呢?
答案就是求异或运算!
但是!
求谁和谁的异或运算啊???
求该校验位牵扯校验的所有信息位的异或运算,也就是说只要这一位信息位的检验用到了这一个校验位,那么这个信息位就要加入到这个校验位的异或运算中。
那么又来了,咋知道这个校验位能校验哪些信息位啊??
好办!D1不是在最终数据第三位上吗,3=1+2吧?好了那就用第一位第二位上这两个信息位来校验,在举一个例子,D4在第七位上,7=1+2+4,所以说要用到这三个校验位来校验,所以最后得出来了:P1牵扯到D1D2D4的校验,P2牵扯到D1D3D4的校验,P3牵扯到D2D3D4的校验,所以说他们三个就通过每一个牵扯到的三个数据位的异或运算来确定值,最后得到P1=0,P2=1,P3=0,所以得出最后的1010010.
(4)汉明码的校验原理
这个我们通过第三步也十分好理解了,每一个校验位的得到都和信息位有着很大的联系,所以说只要有一位信息出错,那么逆向一算就很容易得出是哪里出了错误(具体就是将每一个校验位和该校验位牵扯到的几个数据位放在一起异或运算,若得出来结果都为0,则传输信息正确,若是有1,则有错误!)