海明校验码

2023年 9月 4日 27.4k 0

二进制数据在 传送、存取等环节,可能会发生 误码(1变成0或0变成1). 如何发现并纠正 误码? 解决此类问题的思路是在原始数据(数码位)基础上增加几位校验位。常使用的检验码有三种. 分别是 奇偶校验码、海明校验码和循环冗余校验码(CRC)

其中 奇偶校验码 只能查是否有错误而无法纠错,且要求只能有一位出现错误。

为了能找到发生错误的位置,而有了 海明校验码

实际上本质来说, 海明码是升级款的奇偶校验码,其采用了一种非常巧妙的方式,把这串数字(即要传输的内容)分了组,通过分组校验来确定哪一位出现了错误

类似KMP算法,描述起来很麻烦,实际上使用起来却很简单

"海明"也被译为"汉明"

实例

数据位为8的数据 D7D6D5D4D3D2D1D0=01101001D_7D_6D_5D_4D_3D_2D_1D_0=01101001D7​D6​D5​D4​D3​D2​D1​D0​=01101001,求海明码

1.计算校验位的个数

设数据位为n位,校验位P为k位,则n和k必须满足以下关系:

2k−1≥n+k2^k - 1 ≥ n + k2k−1≥n+k

此例中有 2k−1≥8+k2^k - 1 ≥ 8 + k2k−1≥8+k,可得k最小应为4,即 16 - 1 ≥ 8 + 4。

(奇偶校验称为 Parity Check,Parity Bit即奇偶校验位,故用P表示校验位)

2.计算校验位的位置

2.1 海明码的总位数

设校验位为P,数据位为D,海明码为H,则海明码H的位数为数据的位数和校验码的位数相加,

在此即为 8+4 = 12 位

2.2 校验码的位置

校验位P 在海明码的第 2i−12^{i-1}2i−1 位,即 Hj=Pi,j=2i−1H_j = P_i,j=2^{i-1}Hj​=Pi​,j=2i−1,i从1开始计数。

无论是海明码、校验位还是数据位,均从右向左排列,即从低位向高位排列。

可先填入校验码的位置,再将数据位依次从低位到高位填入

如此例,i即为 1,2,3,4, 故有:

3.确定每个数据位 都由哪些校验码进行校验

根据 2i−12^{i-1}2i−1 的公式,可知 P4、P3、P2、P1P_4、P_3、P_2、P_1P4​、P3​、P2​、P1​ 的下标分别为8、4、2、1

确定 D0−D7D_0-D_7D0​−D7​ 每个数据位都是由哪些校验码(P)进行校验的

数据位D的下标,等于其校验位的下标之和

4.计算校验码的值

校验码的值 为有参与校验的数据依次从低到高异或的值。

(异或:相同为0,相异为1)

因为 D7D6D5D4D3D2D1D0=01101001D_7D_6D_5D_4D_3D_2D_1D_0=01101001D7​D6​D5​D4​D3​D2​D1​D0​=01101001

P1P_1P1​ 参与了 D0、D1、D3、D4、D6D_0、D_1、D_3、D_4、D_6D0​、D1​、D3​、D4​、D6​ 等数据位的校验。
P2P_2P2​ 参与了 D0、D2、D3、D5、D6D_0、D_2、D_3、D_5、D_6D0​、D2​、D3​、D5​、D6​ 等数据位的校验。
P3P_3P3​ 参与了 D1、D2、D3、D7D_1、D_2、D_3、D_7D1​、D2​、D3​、D7​ 等数据位的校验。
P4P_4P4​ 参与了 D4、D5、D6、D7D_4、D_5、D_6、D_7D4​、D5​、D6​、D7​ 等数据位的校验。
所以:(D7D6D5D4D3D2D1D0=01101001D_7D_6D_5D_4D_3D_2D_1D_0=01101001D7​D6​D5​D4​D3​D2​D1​D0​=01101001)
P1=D0⊕D1⊕D3⊕D4⊕D6=1⊕0⊕1⊕0⊕1=1P_1 = D_0⊕D_1⊕D_3⊕D_4⊕D_6 = 1⊕0⊕1⊕0⊕1 = 1P1​=D0​⊕D1​⊕D3​⊕D4​⊕D6​=1⊕0⊕1⊕0⊕1=1
P2=D0⊕D2⊕D3⊕D5⊕D6=1⊕0⊕1⊕1⊕1=0P_2 = D_0⊕D_2⊕D_3⊕D_5⊕D_6 = 1⊕0⊕1⊕1⊕1 = 0P2​=D0​⊕D2​⊕D3​⊕D5​⊕D6​=1⊕0⊕1⊕1⊕1=0
P3=D1⊕D2⊕D3⊕D7=0⊕0⊕1⊕0=1P_3 = D_1⊕D_2⊕D_3⊕D_7 = 0⊕0⊕1⊕0 = 1P3​=D1​⊕D2​⊕D3​⊕D7​=0⊕0⊕1⊕0=1
P4=D4⊕D5⊕D6⊕D7=0⊕1⊕1⊕0=0P_4 = D_4⊕D_5⊕D_6⊕D_7 = 0⊕1⊕1⊕0 = 0P4​=D4​⊕D5​⊕D6​⊕D7​=0⊕1⊕1⊕0=0

5.错误校验

确定错误校验 G4G3G2G1G_4G_3G_2G_1G4​G3​G2​G1​,校验码有几位,错误校验就有几位。
如果采用偶校验则结果全为0时没有错误,如果采用奇校验则结果全为1时没有错误
G1=P1D0⊕D1⊕D3⊕D4⊕D6=1⊕1⊕0⊕1⊕0⊕1=0G_1 = P_1D_0⊕D_1⊕D_3⊕D_4⊕D_6 = 1⊕1⊕0⊕1⊕0⊕1 = 0G1​=P1​D0​⊕D1​⊕D3​⊕D4​⊕D6​=1⊕1⊕0⊕1⊕0⊕1=0
G2=P2D0、D2、D3、D5、D6=0⊕1⊕0⊕1⊕1⊕1=0G_2 = P_2D_0、D_2、D_3、D_5、D_6 = 0⊕1⊕0⊕1⊕1⊕1 = 0G2​=P2​D0​、D2​、D3​、D5​、D6​=0⊕1⊕0⊕1⊕1⊕1=0
G3=P3D1、D2、D3、D7=1⊕0⊕0⊕1⊕0=0G_3 = P_3D_1、D_2、D_3、D_7 = 1⊕0⊕0⊕1⊕0 = 0G3​=P3​D1​、D2​、D3​、D7​=1⊕0⊕0⊕1⊕0=0
G4=P4D4、D5、D6、D7=0⊕0⊕1⊕1⊕0=0G_4 = P_4D_4、D_5、D_6、D_7 = 0⊕0⊕1⊕1⊕0 = 0G4​=P4​D4​、D5​、D6​、D7​=0⊕0⊕1⊕1⊕0=0

则 G4G3G2G1=00004G_4G_3G_2G_1 = 00004G4​G3​G2​G1​=00004,表示没有异常。假如结果为0100则转为十进制为8,表示第八位存在异常。

海明码是一种纠错码,其方法是为需要校验的数据位增加若干校验位,使得校验位的值决定于某些被校位的数据,当被校数据出错时,可根据校验位的值的变化找到出错位,从而纠正错误。对于32位的数据,至少需要增加( )个校验位才能构成海明码。

以10位数据为例,其海明码表示为 D(0≤i≤9)表示数据位,P
(1 ≤j≤4)表示校验位,数据位D由( )进行校验。

参考:

软考笔记--海明码

简单理解海明校验码

hamming code通俗易懂的解释

软考-计算机系统知识之海明码

白话——海明校验码及编码过程

理解海明校验法

【软考】校验码之详细总结

软考-海明码-单位错-冗余位数

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论