海明校验码

在了解海明校验码之前,需要知道一个重要的概念——码距。

概念介绍-码距

码距是指是两个码字中不相同的二进制位的个数,举个例子,有两个编码,分别是01101101和01000101,可以发现,这两个编码有两位值不相同,所以他们的码距为2。 那么,你还有可能听到这么一个说法:“8421码码距d=1”,这里的码距指的是“该数据编码的最小码距”,是整个编码系统中中任意两个码字的码距的最小值。还有一个问题,使用四位二进制的编码系统,码距一定是1吗?显然不是,虽然用的是四位二进制编码系统,但是没有限定编写什么码字。如果我用这个编码系统只编写0000、0011、0101这三个码字,那么这个编码系统的码距就是2,因为这三个码子互相之间的码距最小值为2。

码字的结构

接下来,我还要介绍一下添加校验码后,整个码字的结构。码字包括信息位和校验位,这里设信息位的位数为k,校验位的位数为r,那么整个码字的长度就是k+r。

所需校验位的计算

对于校验位来说,需要有足够的位数来表示信息位中发生的错误,而海明校验码只表示信息位中一位的错误。 举个例子(并不是海明码的结构,不严谨,仅作理解),现在有信息位0110,那么,校验位就需要有四个状态分别表示信息位的第一、二、三或者第四位有误。那么校验位如果只有一位,0和1,并不能表示四种状态。我们试试两位:比如校验位我用00表示信息位第一位发生错误,01表示第二位发生错误,用10表示第三位发生错误,11表示第四位发生错误。看似没有问题,但是忘了一点:校验位如何表示信息位没有错误呢?所以其实我们需要4+1=5种情况来表示信息位的校验信息,即需要3位的校验位。 而对于海明码来说,数据位和校验位穿插,存在校验位可以“我 查 我 自 己”的情况,需要检查的位数就是k+r。所以对于k位的信息位,r位的校验位,需要满足2^r-1>k+r才能检查出1个位的错误。

确定校验码和数据的位置

上节提到,海明码的校验位和信息位是穿插的,所以我们需要确定校验位的各个位置。为了方便说明,我们给校验码定义为P1、P2、P3…;数据为定义为D1、D2、D3…;最终整个码字的编码依次为M1、M2、M3……那对于校验码Pi来说,它的位置是M[2^(i-1)],比如P1的位置是M1、P2的位置是M2,P3的位置是M4,P4的位置是M8……那么剩下的就是数据的位置

求出校验位的值(规律法)

这里以一个例子讲解,比如我们现在掌握如下信息 表里可以看出已经给定了一组信息位的值,现在,我们先计算P1的值: 我们从P1开始,连续1个,中间间隔1个,再连续1个,组合成一个串: 【为了方便理解,我详细说一下上方加粗的过程:从P1(也就是对应的M1)开始,连续一个,就还是P1;然后间隔一个,就跳过M2;再连续一个,取M3的值;然后间隔一个,也就是跳过M4;再连续一个,取M5的值…以此类推,我们取了P1、3、5、7…的值,把它放在一个串里】 然后对这个串进行偶校验,也就是说,保证这个串中1的个数为偶数个,可以看到,已经有两个1了,所以我们在第一位补0: 这也就是我们得到的P1的值

为了加强理解,我们再计算一下P2的值: 我们从P2开始,连续2个,中间间隔2个,再连续2个,组合成一个串:

【为了方便理解,我再详细说一下加粗部分的过程:从P2(也就是对应的M2)开始,连续两个,就是M2、M3,取M3的值;然后间隔2个,跳过M4、M5;再连续两个,取M6、M7的值;再间隔两个,跳过M8、M9;再连续两个,取M10、M11…以此类推,我们取了M3、6、7、10的值】 然后同样进行偶校验,发现已经有4个1,所以补0: 这也就是我们得到的P2的值

同理,计算P3的过程中,我们从P3开始,连续3个,中间间隔3个,再连续3个,也就是取M4、5、6;跳过M7、8、9;取M10、11、12 然后进行偶校验,补0:

P4同理,最后补的是1: 这样,我们就依次获得了校验位的数据,P1-4依次为0、0、0、1

求出校验位的值(数学法)

还是用这一题: 第一步,我们要列出整个码字的编码对应的二进制。比如M1,1对应的就是0001;M2,就是0010;M3就是0011 观察这个二进制编码,以M3为例,0011,第一位和第二位都是1,那么我们称M3和P1、P2有关 第二步,我们要找到还有哪些和P1有关,可以发现,M1、3、5、7、9都和P1有关 第三步,以此类推,找出哪些和P2有关(可以找到M2、3、6、7、10),哪些和P3有关…… 第四步,去掉第一位(因为比如对于P1来说,M1、3、5、7、9中,M1并没有值),列出如下方程式: P1 = M3 ⊕ M5 ⊕ M7 ⊕ M9 = 1 ⊕ 0 ⊕ 1 ⊕ 0 = 0 P2 = M3 ⊕ M6 ⊕ M7 ⊕ M10 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 P3 = M5 ⊕ M6 ⊕ M7 = 0 ⊕ 1 ⊕ 1 ⊕ = 0 P4 = M9 ⊕ M10 = 0 ⊕ 1 = 1 便可以算出校验位的值

接收端校验

参考上一节求出校验位的值(数学法)中求P的过程,我们需要把P,和其相关的数据位相加,比如上面我们计算了P1 = M3 ⊕ M5 ⊕ M7 ⊕ M9 = 1 ⊕ 0 ⊕ 1 ⊕ 0 = 0,这里我们就校验P1 ⊕ M3 ⊕ M5 ⊕ M7 ⊕ M9 是否等于 0,接着,依次计算P2 ⊕ M3 ⊕ M6 ⊕ M7 ⊕ M10、P3 ⊕ M5 ⊕ M6 ⊕ M7、P4 ⊕ M9 ⊕ M10是否都等于0,如果都是0,说明这个数据没有问题。 如果出问题了呢?下面举个例子: 还是上面那一题,如果M5在传输中发生错误,0变成了1 那么计算中就会发现: P1 ⊕ M3 ⊕ M5 ⊕ M7 ⊕ M9 = 1 P2 ⊕ M3 ⊕ M6 ⊕ M7 ⊕ M10 = 0 P3 ⊕ M5 ⊕ M6 ⊕ M7 = 1 P4 ⊕ M9 ⊕ M10 = 0 得出出错位为:0101(2)位,即第五位,那么,只要把M5的值反转,即可得到正确的字串。

海明码的码距

回到一开始说的码距问题,有题目会问,海明码的码距是多少?答案是3。为什么呢,其实我们不妨再观察一下用数学法计算校验位的过程: P1 = M3 ⊕ M5 ⊕ M7 ⊕ M9 = 1 ⊕ 0 ⊕ 1 ⊕ 0 = 0 P2 = M3 ⊕ M6 ⊕ M7 ⊕ M10 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 P3 = M5 ⊕ M6 ⊕ M7 = 0 ⊕ 1 ⊕ 1 ⊕ = 0 P4 = M9 ⊕ M10 = 0 ⊕ 1 = 1 不难发现,即使是靠前的数据位,比如M3、M5,都至少与两个校验位有关,所以变了一个数据位,会更改两个校验位,一共改变三个值。即可得出海明码的码距为3。