华为网络基础 | 数据链路层_检错与纠错——海明码

  • 内容
  • 相关

昨天的篇章中,我们讲解了数据链路层_检错与纠错——基本概念,我们对基本概念有了简单的认识,今天继续讲解海明码知识,包括确定海明码校验位长度和计算校验位知识。

海明码是一种多重奇偶检错系统,具有检错和纠错的功能。海明码中的全部传输码字是由原来的信息和附加的奇偶校验位组成的,每一个奇偶校验位和信息位被编在传输码字的特定位置上。这种系统组合方式能找出错误出现的位置,无论是原有信息位还是附加校验位。

设海明码校验位为k信息位为m,则它们之间的关系应该满足

m+k+1≤2K

(具体的为什么是这个关系,请自行百度吧!不然又是一大堆….)

下面以原始信息1010110为例,讲解海明码的推导与校验的过程。

(1)确定海明码校验位长

m是信息位长,则m=7。根据关系式m+k+1≤2K,得到8+k≤2K。解不等式,得到最小k为4,即校验位为4。信息位加校验的总长度为11位。

(2)确定校验码的位置

从理论上讲,海明码校验位可以放在任何位置,但习惯上校验位被从左至右安排在1,2,4,8,…(即:2的整数幂)位置上。原始信息则从左至右填入剩下的位置,如图所示。

(3)求出校验位的值

可以根据公式得到校验位的,但是死记硬背比较困难,可以换个方式进行理解记忆。

把除去1、2、4、8(校验位位置值编号,上图蓝色背景)之外的3、5、6、7、9、10、11值转换成二进制位。

为了求出x1,要使红色背景位置的第1位为1的数据(形如***1的位置的数据)进行“异或”操作,再把结果填入x1中。同理求出x2、x3、x4。

如上图所示,已经用蓝色标记了红色背景位置的第1位为1的位置,接着就把位置对应的内容进行“异或”操作,得出X1。(⊕表示异或,即:相同=0,不同=1

X1=1⊕0⊕0⊕1⊕0=1⊕0⊕1⊕0=1⊕1⊕0=0⊕0=0,把0放入X1位置。

同理可以求出:X2=1,X4=1,X8=0。

填入校验位后如图所示:

(4)校验

将所有信息位的位置编号(这儿是1~11)的值转换为二进制位,如图所示

对所有信息编号的的二进制的第1位为1的位置对应的内容值,进行“异或”操作,得到X1。
对所有信息编号的的二进制的第2位为1的位置对应的内容值,进行“异或”操作,得到X2。
对所有信息编号的的二进制的第3位为1的位置对应的内容值,进行“异或”操作,得到X4。
对所有信息编号的的二进制的第4位为1的位置对应的内容值,进行“异或”操作,得到X8。

最后,得到一个形式为X8X4X2X1的二进制,转换为十进制时,结果为0,则无错;结果非0(假设为Y),则错误发生在第Y位。

(5)海明码纠错和检错

假设起始端发送数据时,加了上述校验码信息,目的端收到的信息为01111100110,如图所示

从上图中,我们能看出来是第5位数据错了,我们通过实际运算,来验证前面说讲的知识点

根据上面(4)校验中所提的方法,得到

X1=0⊕1⊕1⊕0⊕1⊕0=1
X2=1⊕1⊕1⊕0⊕1⊕0=0
X4=1⊕1⊕1⊕0=1
X8=0⊕1⊕1⊕0=0

X8X4X2X1=0101的二进制转换为十进制等于5。结果为5,则错误发生在第5位,对比上图看看,确实在第5位位置发生了错误。在出错的位置,将其取反就可以起到纠错的功能了

(6)总结

海明码(Hamming Code)是一个可以有多个校验位,具有检测并纠正一位错误代码的纠错码,所以它也仅用于信道特性比较好的环境中,如以太局域网中,因为如果信道特性不好的情况下,出现的错误通常不是一位。

 您阅读这篇文章共花了:

上一篇:华为网络基础 | 数据链路层_检错与纠错——基本概念

下一篇:Windows | 端口占用查看及处理

本文标签:    

版权声明:本文依据CC-BY-NC-SA 3.0协议发布,若无特殊注明,本文皆为《fishyoung》原创,转载请保留文章出处。

本文链接:华为网络基础 | 数据链路层_检错与纠错——海明码 - http://www.fishyoung.com/post-169.html