海明校验复习总结

由于在网上已有的关于海明校验的解释中找不到通俗易懂的解释，并且有些例子存在前后内容不一致等情况，因此将自己对海明校验的理解进行一个概括。

一、海明校验的步骤

1. 给定公式：$2^r >= k+r+1$2r>=k+r+1。其中，$k$k：传输数据的位数，$r$r：校验位的位数。首先根据给定传输数据，求出$k$k的值，然后根据该公式求出$r$r的值，并求出总共需要传输的位数为$k+r$k+r位；

2. 根据 1 中得到的$r$r值，确定出校验位的索引依次为第$20$20位，第$21$21位，… ，第$2^r-1$2r−1位；

3. 列出进制转换表（表格见下方）；

4. 根据进制转换表，将每个校验位所负责校验的各个被校验位的值做异或运算，得到对应校验位的值，进而得到最终要传输的数据值。

二、举例说明

设：要传输的数据为1000111。

1. 可知，$k=7$k=7，由公式$2^r >= k+r+1$2r>=k+r+1得到$r=4$r=4。总共要传输的数据位数为7+4=11。

2. 由于r的值为4，所以校验位的索引为第1，2，4，8位。

3. 列出进制转换表：

	8	4	2	1
3	0	0	1	1
5	0	1	0	1
6	0	1	1	0
7	0	1	1	1
9	1	0	0	1
10	1	0	1	0
11	1	0	1	1

在上表中，从第二行开始，每一行的第一列代表索引号，后面几列为该索引对应的二进制表示。从列的方向来看，数字1所对应的列里，出现数字1的，就表示可以用第1位完成校验，出现数字0则表示不能用第1位进行校验，因此，由上表可知：

校验位1负责校验：第3，5，7，9，11位（上表高亮显示部分）；

校验位2负责校验：第3，6，7，10，11位；

校验位4负责校验：第5，6，7位；

校验位8负责校验：第9，10，11位。

4. 由于第1，2，4，8位为校验位，因此原始的传输数据1000111只能从左到右依次填入第3，5，6，7，9，10，11位，如下所示：

1	2	3	4	5	6	7	8	9	10	11
		1		0	0	0		1	1	1

现在分别来求第1，2，4，8位的值：

第1位：由于第1位负责校验第3，5，7，9，11位，取出进制转换表中校验位1所在的那一列，有：1⊕1⊕1⊕1⊕1=1。

1	2	3	4	5	6	7	8	9	10	11
1		1		0	0	0		1	1	1

第2位：由于第2位负责校验第3，6，7，10，11位，取出进制转换表中校验位2所在的那一列，有：1⊕1⊕1⊕1⊕1=1。

1	2	3	4	5	6	7	8	9	10	11
1	1	1		0	0	0		1	1	1

第4位：由于第4位负责校验第5，6，7位，取出进制转换表中校验位4所在的那一列，有：1⊕1⊕1=1。

1	2	3	4	5	6	7	8	9	10	11
1	1	1	1	0	0	0		1	1	1

第8位：由于第8位负责校验第9，10，11位，取出进制转换表中校验位8所在的那一列，有：1⊕1⊕1=1。

1	2	3	4	5	6	7	8	9	10	11
1	1	1	1	0	0	0	1	1	1	1

• 因此，最终的传输数据为：11110001111。