海明码编码计算和纠错、CRC校检码计算

一、海明码检错/纠错基本思想

海明码（Hamming Code）是一个能够有多个校验位。具有检測并纠正一位错误代码的纠错码，所以也仅用于信道特性比較好的环境中。如以太局域网。它的检错、纠错基本思想例如以下：
（1）将有效信息按某种规律分成若干组，每组安排一个校验位通过异或运算进行校验。得出详细的校验码
（2）在接收端相同通过异或运算看各组校验结果是否正确，并观察出错的校校组。或者多个出错的校验组的共同校验位。得出详细的出错比特位。
（3）对错误位取反来将其纠正。

二、海明码计算

海明码计算要按下面步骤来进行：计算校验码位数→确定校验码位置→确定校验码
1.计算校检码位数
  计算公式: m + k + 1 ≤ 2^k (其中 m 是有效信息位数，k表示加入校检码的位数)

比如：10011101需要的校检码位数?此时，m = 8，带入公式得：8+k+1≤ 2^k,所以 k = 4。（怎么算的？枚举，枚举，枚举......^_,就是估计带入去算！）。101101100又需要多少位校检码呢？（还是4位）。
2.确定校检码位置
  海明码的校检码的位置必须在2ⁿ（n从0开始）。也就是从左边开始第1、2、4、8、16......).
根据第一步我们知道10011101需要4位校检码，那么校检码就在1、2、3、8的位置上。把有效信息按位置填入相应位（不是校检位），校检位暂时留空，于是得到下图：

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

3.计算各位校检码
  为了说明先直接画图。
由于是4位校检位，直接写出4位2进制的表。

	8	4	2	1
1	0	0	0	1
2	0	0	1	0
3	0	0	1	1
4	0	1	0	0
5	0	1	0	1
6	0	1	1	0
7	0	1	1	1
8	1	0	0	0
9	1	0	0	1
10	1	0	1	0
11	1	0	1	1
12	1	1	0	0
13	1	1	0	1
14	1	1	1	0
15	1	1	1	1

（1）第1位要填什么？从上表找出1这列全1对应的十进制数：1、3、5、7、9、11、13、15（1没有就不算），看第一个表中，3、5、7、9、11中分别是1、0、1、1、0为奇数，所以第一位应该填 1（假设采用偶校检）。
（2）第2位要填什么？从上表找出2这列全1对应的十进制数2、3、6、7、10、11（2没有）再对应第一个表中为10110，数1个数为奇数，所以第二位填 1。
（3）第4位看4这列对应全1的 4、5、6、7、12（4没有）对应第一个表0011，1个个数为偶数，所以填 0。
（4）第8位看8这列对应全1的 8、9、10、11、12（8没有）对应第一个表为1101，所以填 1。
（5）最后校检码为 1101。
（6）将校检码插入信息码

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

总结：第n位校检码校检的码位，从自己开始校检n位，然后空n位，在校检n位。
例如：
第2位校检2、3、（空）、（空）、6、7、（空）、（空）、10、11 ......
第4位校检4、5、6、7、（空）、（空）、（空）、（空）、12、13、14、15 ......

【例】二进制码 101101100，求它的海明编码？
1.计算k，m = 9，m + k + 1 ≤ 2^k，所以k = 4。
2.确定校检码位置：

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

3.确定校检码
（1）第1位，找到（1）、3、5、7、9、11、13位，为101010,1为奇数，填1.
（2）第2位，找到（2）、3、6、7、10、11位，为11111,1为奇数，填1.
（3）第4位，找到（4）、5、6、7、12、13位，为01100,1为偶数，填0.
（4）第8位，找到（8）、9、10、11、12、13、（14）、（15）位、为01100,1为偶数，填0，
（5）校检码为1100.

4.所以插入了校检码的信息码：1110011001100。

三、纠错
  依然根据上面的例题，我们将11位上改为0.也就是：

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

<em>由于信息只有13位，下面（）中的位数没有，只是为了方便理解其分组</em>

（1）第1位，找到1、3、5、7、9、11、13位，为1101000,1为奇数，错误.
（2）第2位，找到2、3、6、7、10、11位，为111110,1为奇数，错误.
（3）第4位，找到4、5、6、7、12、13、（14）、（15）位，为001100,1为偶数，正确.
（4）第8位，找到8、9、10、11、12、13、（14）、（15）位、为001000,1为奇数，错误。
所以出错位数应该是 1+2+8=11位，将第11位0改为1即可纠正错误！

<h2>三、CRC校检码</h2>

CRC的实现原理十分易于硬件实现，因此被广泛的应用于计算机网络上的差错控制。CRC校验码需根据CRC生成多项式进行。

1.根据多项式确定代码 P 以及R的位数（R位数 = P位数 -1）。
2.在信息 M 后面加 0，加 0 的个数等于 R位数.
3.用 M 对 P 做模2除法（也就是按位做异或）得到余数r。
4.余数 r 不够 R位数，则在高位补0，得到的数即校检码。

异或：0 ⊕ 0 = 0；0 ⊕ 1 = 1；1 ⊕ 0 = 1；1 ⊕ 1 = 0；运算数相同结果为0，不同结果为1

【例】现假设选择的CRC生成多项式为G（X） = X⁴ + X³ + 1，要求出二进制序列10110011的CRC校验码。
(1)更具多项式确定代码P以及R的位数
多项式为G（X） = X⁴ + X³ + 1，那么

X4	X3	X2	X1	X0(=1)
1	1	0	0	1

也就是代码P = 11001，P为5位，R位数则为5 - 1 = 4位。
（2）在信息 M 后面加 0，加 0 的个数等于 R位数.
M = 10110011，那么加 4 位 0 后得到 101100110000.
（3）用 M 对 P 做模2除法（由于不关心商多少，直接去掉除法上面商部分^_）。

模2除法
（4）将计算出来的CRC校验码添加在原始帧的后面，真正的数据帧为101100110100，再把这个数据帧发送到接收端。
（5）接收端收到数据帧后，用上面选定的除数，用模2除法除去，验证余数是否为0，如果为0，则说明数据帧没有出错。