3.3 循环冗余校验码的原理（P76 3.1.2）

数据链路层广泛采用了**循环冗余校验 CRC（Cyclic Redundancy Check）**来进行差错检测。

CRC 校验就是给数据部分后面填上 $n$ 位冗余码，并约定一个 $n+1$ 位的除数 $P$ 用于计算冗余码，$n$ 的值决于具体使用的 CRC 校验方法，例如（P77 3.1.1）：

• CRC-3：$n=3$，使用多项式 $X^4+X+1$，除数 $P$ 为 $1011$。
• CRC-16/IBM：$n=16$，使用多项式 $X^{16}+X^{15}+X^{2}+1$，除数 $P$ 为 $1\ 1000\ 0000\ 0000\ 0101$
• CRC-16/CCITT：$n=16$，使用多项式 $X^{16}+X^{12}+X^{5}+1$，除数 $P$ 为 $1\ 0001\ 0000\ 0010\ 0001$
• CRC-32：$n=32$，使用多项式 $X^{32}+X^{26}+X^{23}+X^{22}+X^{16}+X^{12}+X^{11}+X^{10}+X^{8}+X^{7}+X^{5}+X^{4}+X^{2}+X+1$，除数 $P$ 为 $1\ 0000\ 0100\ 1100\ 0001\ 0001\ 1101\ 1011\ 0111$，这也是 Ethernet 所使用的方法。

由于除数 $P$ 最高位必是 $1$，因此常见的表示方式是省略最高位，例如 CRC-16/CCITT 的除数 $P$ 一般表示为 $1\ 0000\ 0010\ 0001$。

首先选定 CRC 校验的算法，假设选中的算法生成 $n$ 位校验码，则除数 $P$ 为 $n+1$ 位，假设待校验的数据为 M 位的二进制数据，则具体计算步骤如下：

1. 首先将原始数据左移 $n$ 位得到数据 $M$，即空出 $n$ 位校验码的位置。

2. 取 $M$ 前 $n+1$ 位，得到被除数 $Q_{in}$。

3. 对被除数 $Q_{in}$ 执行以下操作：

   • 若最高位为 $1$，则与除数 $P$ 进行异或。
   • 若最高位为 $0$，则与 $0$ 进行异或。

   得到 4 位结果 $Q_{tmp}$，取其后 3 位得到 $Q_{out}$（由于这一步计算的特性， $Q_{tmp}$ 的最高位一定是 $0$）。

4. 提取 $M$ 的下一位，追加到结果 $Q_{out}$ 的尾部，得到新的被除数 $Q_{in}$，再次执行步骤 3。

5. 直到计算 $M$ 的最后一位，记最后一次异或的结果 $Q_{out}$ 为 $R$，余数 $R$ 即为冗余码。

具体的，假设使用 CRC-3，则除数为 4 位的 $1011$，需要生成 3 位的冗余码，假设待校验的数据为 $10\ 1001$，则：

101001
---------
101001000
1011
---------
 0010
 0000
---------
  0101
  0000
---------
   1010
   1011
---------
    0010
    0000
---------
     0100
     0000
---------
      100

解释如下：

1. 首先将原始数据左移 3 位，即空出 3 位校验码的位置，得到数据 $M$：$1\ 0100\ 1000$。
2. 取 $M$ 前 4 位：$1010$，记为 $Q_{in}$。
3. 此时 $Q_{in}$ 最高位为 $1$，则将其与除数 $P$ 做异或操作，即 $1010\ XOR\ 1011$，得到结果 $0001$，取其后三位 $001$ 记为 $Q_{out}$。
4. 提取 $M$ 第 5 位（即 $0$），追加到 $Q_{out}$ 尾部，得到 $0010$，记为新的 $Q_{in}$。
5. 此时 $Q_{in}$ 最高位为 $0$，则将其与 $0$ 做异或操作，即 $0010\ XOR\ 0000$，得到结果 $0010$，取其后三位 $010$ 记为 $Q_{out}$。
6. 提取 $M$ 第 6 位（即 $1$），追加到 $Q_{out}$ 尾部，得到 $0101$，记为新的 $Q_{in}$。
7. 此时 $Q_{in}$ 最高位为 $0$，则将其与 $0$ 做异或操作，即 $0101\ XOR\ 0000$，得到结果 $0101$，取其后三位 $101$ 记为 $Q_{out}$。
8. 提取 $M$ 第 7 位（即 $0$），追加到 $Q_{out}$ 尾部，得到 $1010$，记为新的 $Q_{in}$。
9. 此时 $Q_{in}$ 最高位为 $1$，则将其与除数 $P$ 做异或操作，即 $1010\ XOR\ 1011$，得到结果 $0001$，取其后三位 $001$ 记为 $Q_{out}$。
10. 提取 $M$ 第 8 位（即 $0$），追加到 $Q_{out}$ 尾部，得到 $0010$，记为新的 $Q_{in}$。
11. 此时 $Q_{in}$ 最高位为 $0$，则将其与 $0$ 做异或操作，即 $0010\ XOR\ 0000$，得到结果 $0010$，取其后三位 $010$ 记为 $Q_{out}$。
12. 提取 $M$ 第 9 位（即 $0$），追加到 $Q_{out}$ 尾部，得到 $0100$，记为新的 $Q_{in}$。
13. 此时 $Q_{in}$ 最高位为 $0$，则将其与 $0$ 做异或操作，即 $0100\ XOR\ 0000$，得到结果 $0100$，取其后三位 $100$ 记为 $Q_{out}$。
14. 此时已计算到最后一位，记 $Q_{out}$（即 $100$）为 $R$，$R$ 即为冗余码。

得到冗余码为 $100$，发送数据时将冗余码 $100$ 追加到数据结尾即可。

这种方式看似很复杂，但由于网络设备发送数据也是一位一位按顺序发送，因此在硬件上很容易能实现这种算法，当数据发送完的时候，冗余码也就计算完成，直接继续发送冗余码即可。

接收方校验时，直接将接收到的数据记为 $M$，然后从冗余码计算方法的第二步开始计算，若最终结果为 $000$，则代表数据无误。

Ethernet 所使用的 CRC 校验算法为 CRC-32，检测率非常接近 100%，（P77 3.1.1）即：“凡事接收端数据链路层接受的帧，我们都能以非常接近 1 的概率认为这些帧在传输过程中没有产生差错。”