错误检测-海(汉)明码

算法

Hamming code，海明码，汉明码都是一个东西。它是一种编码方式，通常用在网络信息传输中，通过这种编码方式编码出来的二进制数据具有检测一位错误位的能力。

例如：

下面则将具体讲解这些过程。

编码过程 #

第一步是确定冗余位(bit)的数目，这些位将为检错提供必要的信息。

根据算法要求，冗余位的数目(r)必须满足： $$ 2^r \geq m + r + 1 $$ 其中m为原始数据位的数目。

第二步是确定冗余位的位置

同样根据算法设计，冗余位将放在位置编号为2的幂次的位置上。

如：1,2,4,8…

假设要传输的数据为 1011001 ，则编码后各个数据位的排布应如下图所示：

第三步是确定冗余位的值

计算方法如下：

处于第$2^i$位的冗余位的值，将是所有位置编码(二进制表示)中第i位为1的那些位置的原始数据的偶校验。

如R1，它的值将是第1,3,5,7,9,11这些位置上的数据的偶校验，所以

由于3，5，7，9，11中1的个数为偶数，故R1=0（偶校验～1的个数为偶数个）。

假设要传输的数据为 1011001 ，则编码后结果如下：

同上，假设要传输的数据为 1011001 ，编码后为1010 1001 110 。

假设实际传输过去的数据为 1010 1101 110 ，即从右往左第6位由0变为了1。

这时候，如果我们再用计算冗余位值的方法重新计算一遍冗余位的值，我们会发现：

R4R3R2R1 = 0110 即十进制下的6。

这表明从右往左第6位发生错误，这时候我们将其反转即可纠正。

实际上，我们的目标是得到一个数字，这个数字表示数据中出错那一位的位置。

如果我们将其表示为二进制的形式，那么我们的任务即变为了确定各个bit位是0还是1。

在前面我曾要求过这个表达式：

$2^r \geq m + r + 1$

它的含义即在于，如果我们利用r个冗余位确定这个二进制数字（r个冗余位确定r个数字中的bit位），那么我们必须保证这个数字的范围能够表示编码数据串中的所有位置。

可能有人会问，既然如此，那满足这个表达式$2^r \geq m + r$ 不就可以了吗，为什么要+1呢？

因为位置编码必须从1开始，从0开始没法纠错。因此位置编码的最大值位m+r+1。

海明码的巧妙之处就在于它偶校验的分组上，每个冗余位都对应了一个bit位为1的那些位置。

换句话说，海明码将错误位置的确认分散到了各个组上，通过一次能偶校验，能够确定错误位置属不属于这个组，经过r次偶校验后，便能确定其具体位置。