海明码校验分析

设数据有 m 位，校验码有 p 位；

我们设数据为 1010

由上述的例子我们可以知道：

校验码一共有2^p种取值；

若想通过校验码指出任意一位上发生的错误必须满足：

1	2^p -1 >= m + p

由数据1010知：m = 4 ，得出 p >= 3

	1 001	2 010	3 011	4 100	6 110
	P1	P2	1	P3	1
奇	0	1	1	0	1
偶	1	0	1	1	1

校验码的位置放在 $2^n$ （n = 0,1,2 …）的位置上，即1 2 4 8 …

如何分组？

p1对应的是 1 二进制是 001，则寻找最后一位和它相同的位数，即 011(m3) 101(m5) 111(m7)

分组情况：

1
2
3

p1 ==> m3 m5 m7  = 100  0奇1偶   再补 0 个1就可以是奇数个1，故 0奇 ， 再补1个1就是偶数个1，故 1偶
p2 ==> m3 m6 m7  = 110  1奇0偶
p3 ==> m5 m6 m7  = 010  0奇1偶

设发送方发送的是奇校验海明码，即 0110010

假设接收端接收到的是 0110110

1	2	3	4	5	6	7
0	1	1	0	1	1	0

得到一个新的

1
2
3

e1 = p1 m3 m5 m7  = 0110 = 1  再补 1 个1就可以是奇数个1  
e2 = p2 m3 m6 m7  = 1110 = 0  再补 0 个1就可以是奇数个1
e3 = p3 m5 m6 m7  = 0110 = 1  再补 1 个1就可以是奇数个1

最后序列为 e3 e2 e1 : 101 即第五位出错，取反即可

若最终序列为 000，则无错

码距（海明距离）

同一编码规则下的两码字之间对应的位置上的不同二进制的个数

例如： 1101111 和 1101010 ，码距为2

编码的码距为其中任意两码字间的最小码距

纠错理论： L - 1 = D + C , D >= C

L 为编码码距， D 为检错码距， C 为纠错位数

1
2

2^p -1 >= m + p  码距为 3 有发现两位错误(D = 2, C = 0) 或 纠错一位的能力(D = 1 , C = 1)
对于码距为4 的海明码，有 2^(p-1) - 1 >= m + p，有发现两位错误并纠错一位错误的能力 (D = 2 , C = 1)

常用的（n，k）海明码中，冗余位的位数是

位数是 n - k 位

n代表总位数，k代表数据位

用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位至少是

至少是 4位

要纠正一位错误，所以海明距为 1*2 + 1 = 3 位，当海明码距为 3 时，计算的公式为 2^p - 1 = m + p

使用上述公式计算即可得到 p 最小值为 4