海明码校验码计算步骤(海明校验码的计算及检验)

最近和兄弟探讨一个海明校验码的题目,因为学了很久所以有些记不清了,趁着这个机会,复习了一下海明校验码及校验过程,以此为记录。

知识背景

百度百科: “由Richard Hamming于1950年提出、还被广泛采用的一种很有效的校验方法,是只要增加少数几个校验位,就能检测出二位同时出错、亦能检测出一位出错并能自动恢复该出错位的正确值的有效手段,后者被称为自动纠错。”

我们知道,通常情况下使用奇偶校验法可以识别数据是否发生错误,但是并不能知道是哪里的数据发生了问题。有了这个前提,于是我们观察到海明校验码,它增加很少的几个校验位来检测出出错数据的位置,其检测原理概述如下:

百度百科: “它的实现原理,是在k个数据位之外加上r个校验位,从而形成一个k r位的新的码字,使新的码字的码距比较均匀地拉大。”

现在看来或许还是比较不容易看懂,接下来我用过一个做过的实验题目来分析。

计算海明校验码

首先介绍一下海明校验码公式:

海明码校验码计算步骤(海明校验码的计算及检验)(1)

公式中,k为校验码的位数,n为原数据的位数。

2^k表示这k位能够表示的状态数,因为每一个校验码都有0或1两种可能,那么和原数据组合产生的状态数量就是 2^k种,在这么多种可能中有一种状态代表正确校验的情况,而剩下的2^k−1种状态就用来对应错误校验的情况。

通过这个公式,我们就可以计算出一个已知原始数据所需要的最小校验位数。下面举一个我做过的一个实验题目作为例子:

海明码校验码计算步骤(海明校验码的计算及检验)(2)

步骤一:计算校验码位数

这一原始数据0110,n = 4 ,根据海明校验码公式可以得到需要添加的校验码位数k = 3

有话说: 校验码放置的位置应为2的整数次幂,即Pi=2^i

于是我们得到了这样一个待计算的海明码:

海明码校验码计算步骤(海明校验码的计算及检验)(3)

其中,P0、P1、P2为三个我们添加的校验码

步骤二:确定校验组

接下来我们为每一个数据添加校验组,校验组是什么意思呢,就是这一下标对应的数据可以由一个校验组来唯一对应检验。通俗地讲,做法就是将每一个数据位的下标分解成校验码所在下标的和,(校验位不分解),拿我们的例子来看看:

海明码校验码计算步骤(海明校验码的计算及检验)(4)

有话说: 例如下标5还可以分解成2 3那为什么不选2 3呢?这是因为下标3是数据位而不是校验位,所以这里我们选的是1 4的分解。

步骤三:计算校验码的值得出海明校验码

计算海明校验码的最后一个步骤就是得出P0、P2、P3的具体值,其做法为:

计算Pi的值,就在校验组中将与Pi有关的那几组数据做 异或(相同为0,不同为1) 运算拿我们的例子来看看:

海明码校验码计算步骤(海明校验码的计算及检验)(5)

计算结束后,和原来的数据组合我们就得到了海明校验码:

海明码校验码计算步骤(海明校验码的计算及检验)(6)

利用海明校验码校验数据

接下来我们利用海明校验码来校验数据:例如我们有一个待检测的数据:

海明码校验码计算步骤(海明校验码的计算及检验)(7)

海明码校验码计算步骤(海明校验码的计算及检验)(8)

海明码校验码计算步骤(海明校验码的计算及检验)(9)

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页