2.2 校验码：奇偶校验、海明码与 CRC

码距与检错纠错能力，奇偶校验码，海明码的编码、检错与纠错，循环冗余校验码的生成与校验。

码距

由若干位代码组成的一个字称为码字。将两个码字逐位进行对比，具有不同的位的个数称为这两个码字间的距离。一种编码方案可能有若干合法码字，各合法码字间的最小距离称为码距 $d$。

奇偶校验码

在有效信息位上添加一位校验位，使整个校验码中”1”的个数为奇数（奇校验）或偶数（偶校验）。

• 偶校验位 = 所有信息位的异或：$P = b_1 \oplus b_2 \oplus \cdots \oplus b_n$；奇校验位为其取反；
• 只能检测奇数位的错误，不能纠错，也不能检测偶数位的错误；
• 实现简单，常用于存储器读写检查或 ASCII 码传送。

海明码

海明码的设计思想：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供依据。

校验位个数：设信息位为 $n$ 位，校验位为 $k$ 位，则需满足

即 $k$ 位校验位能表示 $2^k$ 种状态，其中 1 种表示无错，其余 $2^k - 1$ 种用于指出 $n + k$ 位中哪一位出错。例如 $n = 4$ 时 $k = 3$；$n = 8$ 时 $k = 4$；$n = 16$ 时 $k = 5$。

编码步骤（以偶校验为例）：

1. 校验位 $P_i$ 放在位号为 $2^{i-1}$ 的位置上（$H_1, H_2, H_4, H_8, \ldots$），信息位按顺序放在其余位置；
2. 每个信息位由位号的二进制表示中为 1 的那些校验位共同负责。例如 $H_7$（111）由 $P_1$、$P_2$、$P_3$ 共同校验，$H_6$（110）由 $P_2$、$P_3$ 校验；
3. $P_i$ = 它所负责的所有信息位的异或。

检错与纠错：接收端对每一组（含校验位本身）重新求异或，得到指错字 $S_k \cdots S_2 S_1$。若全为 0 则无错；否则其二进制值就是出错的位号，将该位取反即可纠正。

循环冗余校验码（CRC）

CRC 码的基本思想：在 $K$ 位信息码之后拼接 $R$ 位校验码，整个编码长度为 $N = K + R$ 位。生成规则：

检错：接收端将收到的 CRC 码用同一个 $G(x)$ 进行模 2 除法，若余数为 0，则认为没有错误；若余数不为 0，则说明传输过程中出现了错误（在合理选取生成多项式时，余数与出错位置有一一对应关系，因此 CRC 码也可以纠正 1 位错误，但实际通常只用于检错）。

即时练习