1.1.4 校验码

码距

两个合法编码对应位之间比较，有多少位编码不同，又称为海明距离。比如 10101 和 00110 就是(从高到低 1,4,5 位不同，码距为 3)

计算海明距离的一种方法，就是对两个位串进行异或（xor）运算，并计算出异或运算结果中 1 的个数。例如 110 和 011 这两个位串，对它们进行异或运算，其结果是：

$$110 \bigoplus 011=101$$

异或结果中含有两个 1，因此 110 和 011 之间的海明距离就等于 2。

为了使一个系统能检查和纠正一个差错，码间最小距离必须至少是“3”。最小距离为 3 时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。

码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。

模二加法

这是一种二进制的运算，等同于“异或”运算。

规则是两个序列按位相加模二，即两个序列中对应位，相加，不进位，相同为 0，不同为 1。

奇偶校验码（Parity Codes）

是一种通过增加冗余位使得码字中"1"的个数恒为奇数或偶数的编码方法，它是一种检错码。在实际使用时又可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。因为其利用的是编码中 1 的个数的奇偶性作为依据，所以不能发现偶数位错误。（错偶数个奇偶性不变）

海明码（Hamming Code）

贝尔实验室 Richard Hamming 设计，在特定位置插入 k 个校验码，通过扩大码距来检错纠错。

n 位数 k 校验位，则必须符合：

$$2^k-1\geq n+k$$

校验位：

$$P_k, P_{k-1},...p_1$$

数据位：

$$D_{n-1},D_{n-2},...D_0$$

海明码：

$$H_{n+k},H_{n+k-1},...H_1$$

则：

$$H_j=P_i,j=2^{i-1}$$

数据从低到高占据剩下的位置

海明码中的任何一位都是由若干个校验位来校验的：被校验的海明位的下标==所有参与校验该位的校验位的下标之和，校验位由自身校验。

编码过程

对于 8 位数，要 4 个校验位。

• 1.确定 D 与 P 位置

Hamming	D&P
H(12)	D(7)
H(11)	D(6)
H(10)	D(5)
H(9)	D(4)
H(8)	P(4)
H(7)	D(3)
H(6)	D(2)
H(5)	D(1)
H(4)	P(3)
H(3)	D(0)
H(2)	P(2)
H(1)	P(1)

• 2.确定校验关系

海明码	分布	海明码下标	校验位组
H(12)	D(7)	12=4+8	P3,P4
H(11)	D(6)	11=1+2+8	P1,P2,P4
H(10)	D(5)	10=2+8	P2,P4
H(9)	D(4)	9=1+8	P1,P4
H(8)	P(4)	8	P4
H(7)	D(3)	7=1+2+4	P1,P2,P3
H(6)	D(2)	6=2+4	P2,P3
H(5)	D(1)	5=1+4	P1,P3
H(4)	P(3)	4	P3
H(3)	D(0)	3=1+2	P1,P2
H(2)	P(2)	2	P2
H(1)	P(1)	1	P1

根据每个校验位参与校验得

$$P_1=D_0 \bigoplus D_1 \bigoplus D_3 \bigoplus D_4 \bigoplus D_6$$ $$P_2=D_0 \bigoplus D_2 \bigoplus D_3 \bigoplus D_5 \bigoplus D_6$$ $$P_3=D_1 \bigoplus D_2 \bigoplus D_3 \bigoplus D_7$$ $$P_4=D_4 \bigoplus D_5 \bigoplus D_6 \bigoplus D_7$$

若使用奇校验，将校验位的偶校验值取反即可

• 3.检测错误

$$G_1=P_1 \bigoplus D_0 \bigoplus D_1 \bigoplus D_3 \bigoplus D_4 \bigoplus D_6$$ $$G_2=P_2 \bigoplus D_0 \bigoplus D_2 \bigoplus D_3 \bigoplus D_5 \bigoplus D_6$$ $$G_3=P_3 \bigoplus D_1 \bigoplus D_2 \bigoplus D_3 \bigoplus D_7$$ $$G_4=P_4 \bigoplus D_4 \bigoplus D_5 \bigoplus D_6 \bigoplus D_7$$

如果采用偶校验，G4G3G2G1 全为 0 则无错（奇校验全为 1），且其十进制值指出了错误位置，如 1010 说明 H10(D5)出错了，将其取反即可纠正错误。