博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
海明校验
阅读量:5878 次
发布时间:2019-06-19

本文共 1486 字,大约阅读时间需要 4 分钟。

转自:

做了调整与补充

 

【定义】

     海明码(Hamming Code)是利用奇偶性来检错和纠错的校验方法。海明码的构成方法是在数据位之间的确定位置插入k个校验位,通过扩大吗距来实现检错和纠错。
对于数据位m的数据,加入k位的校验码,它应满足香农第二定理:
n=m+k ≤ 2k-1
说明:这里的m是指我们待编有效信息的位数,例如110101就是m=6,然后代入m,6+k ≤2
k-1得到m=6,k≥4(取最小值),这样组成10位海明校验码。
 
【例子】
     设数据为01101001,试采用校验位求其偶校验方式的海明码。
根据上面的公式得到,m=8,k≥4
(1)确定数据位D和校验位P在海明码中的位置:
由海明码编码规则可知: p
i在海明码的第
2i-1,比如P4=2^(4-1)=8,所以位于第8位
海明码H 1 2 3 4 5 6 7 8 9 10 11 12
校验位 P1 P2   P3       P4        
数据位     D0   D1 D2 D3   D4 D5 D6  D7

(2)确定校验关系

         这个难点在于如何确定校验位组。
         举一个例子来说:H3=D0,海明码下标为3,我们必须用已知的校验位(P1,P2,P3,P4)来表示3,这里3就可以等于1+2。
 
          
       
比如P1 的校验位为表格中红色标记出来所对应的海明码的位数
(3)故:P1校验:P1,D0,D1,D3,D4,D6
 
P1=D0⊕D1⊕D3⊕D4⊕D6=0⊕1⊕0⊕1⊕0=0
 
P2=D0⊕D2⊕D3⊕D5⊕D6=0⊕1⊕0⊕0⊕0=1
 
P3=D1⊕D2⊕D3⊕D7=1⊕1⊕0⊕1=1
 
P4=D4⊕D5⊕D6⊕D7=1⊕0⊕0⊕1=0
  
⊕符号:代表异或,相同则为0,不同则为1。只要仔细一定可以计算正确。
 
我们按照表格海明码的位置插入P1~P4到数据中,所以海明校验码:
010
1110
01001
 
(4)设置指错字G4,G3,G2,G1
G4=P4⊕D4⊕D5⊕D6⊕D7
 
G3=P3⊕D1⊕D2⊕D3⊕D7
 
G2=P2⊕D0⊕D2⊕D3⊕D5⊕D6
 
G1=P1⊕D1⊕D3⊕D4⊕D6
 
G1G2G3G4为0000,则数据传输没有错误。
 
以上面的数据传输为例子:
G4=0  G3=0  G2=0  G1=0
 
若数据传输之后变成01011100100
0
G4=P4⊕D4⊕D5⊕D6⊕D7=0⊕1⊕0⊕0⊕
0=1
 
G3=P3⊕D1⊕D2⊕D3⊕D7=1⊕1⊕1⊕0⊕
0=1
 
G2=P2⊕D0⊕D2⊕D3⊕D5⊕D6=1⊕0⊕1⊕0⊕0⊕0=0
 
G1=P1⊕D1⊕D3⊕D4⊕D6=0⊕0⊕1⊕0⊕1⊕0=0
 
G4G3G2G1组成的二进制数为:1100,也就是12,说明第12位出现的错误
 
 
(5)海明校验缺点
1)海明校验的每一步还是使用的奇偶校验,因此当G中同时出现两个错误时,G1G2G3G4依然为0000,例如D1,D2出错,
010
10
00
01001
G4=P4⊕D4⊕D5⊕D6⊕D7=0⊕1⊕0⊕0⊕0⊕1=0
 
G3=P3⊕D1⊕D2⊕D3⊕D7=1⊕
0
0⊕0⊕1=0
 
G2=P2⊕D0⊕D2⊕D3⊕D5⊕D6=1⊕0⊕
0⊕0⊕0⊕0=1
 
G1=P1⊕D1⊕D3⊕D4⊕D6=0⊕
0⊕0⊕1⊕0=1

 

2)同时,G4G5G6G1=0000不一定数据传输过程中就没有错误,只有当只有一位发生错误时,才能检测出来。

G1G2G3G4=0011,也就是第3位出现错误,很明显这是不准确的。

转载于:https://www.cnblogs.com/Mayfly-nymph/p/11098213.html

你可能感兴趣的文章
springmvc 日期转换器
查看>>
java String-StringBuffer-StringBuilder
查看>>
python使用matplotlib:subplot绘制多个子图
查看>>
第二次作业
查看>>
汉字unicode码表范围和常用汉字unicode码
查看>>
Web API总结
查看>>
jquery.min.js v1.10.3版本autocomplete方法会在text前添加搜索出多少项的文本信息 要去除...
查看>>
数据结构堆排序
查看>>
Mysql怎么判断繁忙 checkpoint机制 innodb的主要参数
查看>>
MyGeneration学习笔记(11) :dOOdad的架构(Architectures)
查看>>
数据库模块41题作业
查看>>
《携程的技术演进之路》读后感
查看>>
IE8正式版引发VS2005和VS2008添加变量向导出错的解决方案
查看>>
[BZOJ 2243][SDOI2011] 染色
查看>>
Visual Studio 2010中文旗舰版+大家所关心的
查看>>
LeetCode-78-Subset
查看>>
libtiff.so.3
查看>>
人生感悟
查看>>
CSS transitions深入理解
查看>>
KDTree 板子
查看>>