1. 奇偶检验码#

奇偶检验码是奇检验码和偶检验码的统称，是最基本的检错码。它由 n 位数据和 l 位检验位组成，检验位的取值(0 或 1)使得整个码字中“1”的个数为奇数(奇校验)或偶数(偶校验)。

1. 奇检验码：附加检验位后，码字中“1”的总数为奇数。
2. 偶检验码：附加检验位后，码字中“1”的总数为偶数。

例如，7位数据1001101中有4个“1”(偶数)，因此：对应的奇检验码为$1001101\underline{1}$(加1使“1”的总数为奇数)，对应的偶检验码为$1001101\underline{0}$(加0使“1”的总数保持为偶数)。

奇偶检验码只能检测奇数位错误，无法发现偶数位错误，也无法定位错误位置。由于任意两个合法码字之间至少有2位不同，其码距为2。根据码距理论，此类编码最多可检测1位错误。而实际上，只要发生奇数位错误，“1”的总数奇偶性必然改变，因此能检测所有奇数位错误。

2. 循环冗余码#

循环冗余码(Cyclic Redundancy Code，CRC)是数据链路层广泛采用的一种高效检错技术，具有检错能力强、实现简单、硬件支持成熟等显著优势，其基本原理如下。

CRC 的核心思想: 将待发送的数据视为一个二进制多项式, 通过与一个预定义的生成多项式 $G(x)$ 进行特定运算, 生成一段冗余校验信息 (称为帧检验序列, FCS), 并将其附加在原始数据之后。接收方则使用相同的 $G(x)$ 对整个接收到的帧进行验证, 从而判断传输过程中是否出现差错。

CRC 校验过程的具体描述如下。

(1) 确定海明码的总位数#

设信息位有 n 位，检验位有 k 位。k 个检验位可表示 $2^{k}$ 种状态：信息位和检验位共有 $n + k$ 种单比特出错的位置，此外还需 1 种表示无错状态。因此，n 与 k 需满足

本例中 n=4，尝试 $k=3:2^{3} \geqslant 4+3+1$ 成立。故取 k=3，海明码共 $n+k=7$ 位。记信息位为 $D_{4}D_{3}D_{2}D_{1}=1010$，检验位为 $P_{3}P_{2}P_{1}$，海明码位号从右至左依次为 $H_{7}H_{6}H_{5}H_{4}H_{3}H_{2}H_{1}$。

(2) 确定检验位的分布#

规定：检验位 $P_i$ 放在海明位号为 $2^{i-1}$ 的位置上，其余各位放置信息位，因此：

$P_{1}$的海明码位号为 $2^{i-1}=2^{0}=1$，即 $H_{1}$为 $P_{1}$。

$P_{2}$ 的海明码位号为 $2^{i-1}=2^{1}=2$，即 $H_{2}$ 为 $P_{2}$。

$P_{3}$ 的海明码位号为 $2^{i-1}=2^{2}=4$，即 $H_{4}$ 为 $P_{3}$。

将信息位按原顺序放在剩余位置，得到海明码的分布如下：

(3) 分组以形成检验关系#

每个信息位由多个检验位共同校验，需满足条件：信息位所在位号 = 其所参与的所有检验位位号之和。另外，检验位不需要再被检验。分组形成的检验关系如下。

(4) 检验位取值#

检验位 $P_{i}$ 的值为其对应校验组中所有位(含信息位)求异或(偶校验结果)。

根据(3)中的分组有

因此，1010 对应的海明码为 $101\underline{0}0\underline{1}\underline{0}$ (下划线为检验位，其余为信息位)。

(5) 海明码的检验原理#

每个检验组分别利用检验位和参与形成该检验位的信息位进行奇偶检验检查，构成 k 个检验方程：

若 $S_{3}S_{2}S_{1}$ 的值为“000”，表示无错误；否则表示出错，且这个数就是错误位的位号，如 $S_{3}S_{2}S_{1}=001$，表示第1位出错，即 $H_{1}$ 出错，直接将其取反即可达到纠错的目的。

海明码的优势在于：通过少量冗余检验位，可实现单比特错误的自动定位与纠正。