408海明码的解算思路

一、什么是海明码（*）

在电信领域中，汉明码（英语：hamming code），也称为海明码，是 (7,4)汉明码推广得到的一种线性纠错码，由理查德·卫斯里·汉明于1950年发明。相比而言，简单的奇偶检验码除了不能纠正错误之外，也只能侦测出奇数个的错误。汉明码是完备码，它在于它分组长度相同、最小距离为3的码中能达到最高的码率。

用数学术语来说，汉明码是一种二元线性码。对于所有整数 r ≥ 2，存在一个分组长度 n = 2r − 1、k = 2r − r − 1 编码。因此汉明码的码率为 R = k / n = 1 − r / (2r − 1)，对于最小距离为3、分组长度为 2r − 1 的码来说是最高的。汉明码的奇偶检验矩阵的是通过列出所有长度为 r 的非零列向量构成的。

二、编码

1.先来算需要几个校验位

假设校验位有k位，因为每一位都是二进制数据表示，那么校验码最多有可以表示2^k种情况（组合），由于以上所有情况里面有一种组合用来标志该数据正确时的情况， 因此有如下公式：

(2^k) - 1 ≥　n+k

2.计算过程

假如待编码的数据是：1010011

1. 算k值（结果是4）

2. 得到数据一共有11位（检验4 + 原数据7）

3. 画出标识表格。
这其中将第 i 个校验位按照2^(i - 1)的位置插入到原数据中（本方法是从右往左，比如第4个校验位是：2的3次方=8，因此P4在H8的位置），H表示最终数据位，D表示原数据位，P表示插入的校验位。

H11	H10	H9	H8	H7	H6	H5	H4	H3	H2	H1
1	0	1	x4	0	0	1	x3	1	x2	x1
D7	D6	D5	P4	D4	D3	D2	P3	D1	P2	P1

上表格中我们就是要求出x1, x2, x3, x4的值。

4. 把 数据位 对应的位置号（H标识的那个）转成二进制，竖着排版，方便以后计算（例如D5对应的H9，就把9写成二进制1001），
几个校验位就有几组，计算结果对应x1, x2, x3, x4的值

5. 计算

计算每一组的结果规则：拿出该组值为1的对应的数据位的数据进行异或运算。
例如P1组计算：值为1的数据位分别为：H3，H5，H7，H9，H11，那么我们取出这几个位置对应的数据进行运算，我们可以对照上面画好的标识表格，H3对应1，H5对应1，H7对应0，H9对应1，H11对应1，即：
第一组： x1 = H3⊕H5⊕H7⊕H9⊕H11 = 1 ^ 1 ^ 0 ^ 1 ^ 1 = 0
同理可得：
第二组： x2 = H3⊕H6⊕H7⊕H10⊕H11 = 1 ^ 0 ^ 0 ^ 0 ^ 1 = 0
第三组： x3 = H5⊕H6⊕H7 = 1 ^ 0 ^ 0 = 1
第四组： x4 = H9⊕H10⊕H11 = 1 ^ 0 ^ 1 = 0

把算得的结果填回去就可以得到1010011海明码：
10100011100

三、解码

现在假如我们拿到了海明码：10100011100
同理给这串数字从右往左编号。

H11	H10	H9	H8	H7	H6	H5	H4	H3	H2	H1
1	0	1	0	0	0	1	1	1	0	0
D7	D6	D5	P4	D4	D3	D2	P3	D1	P2	P1

然后，同理找出数据位的位号的二进制数据：

四组就有四个结果(以下H取值也是看值为1的项)：

S1 = P1(x1)⊕H3⊕H5⊕H7⊕H9⊕H11 = 0 ^ 1 ^ 1 ^ 0 ^ 1 ^ 1 = 0
S2 = P2(x2)⊕H3⊕H6⊕H7⊕H10⊕H11 = 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 1 = 0
S3 = P3(x3)H5⊕H6⊕H7 = 1 ^ 1 ^ 0 ^ 0 = 0
S4 = P4(x4)H9⊕H10⊕H11 = 0 ^ 1 ^ 0 ^ 1 = 0

如果四个结果均为0，说明数据没有出错。如果有存在不为0的项，表示有错。
如S1 = 0，S1 = 1，S2 = 0，S3 = 0，把他们放一起即0010表示第2（转成十进制）位有错误。