在数据链路层传送数据时，为了保证数据传输的可靠性，必须采用差错检测措施。目前广泛使用的是循环冗余检验 CRC，Cyclic Redundancy Check 技术。

CRC 的基本原理

CRC 的核心思想是在发送端将数据划分为若干组，假定每组 $k$ 个比特。在每组数据 $M$ 后面添加供差错检测用的 $n$ 位冗余码，然后构成一个帧发送出去。因此，实际发送的帧总长度为 $k+n$ 位。

冗余码的计算方法

CRC 冗余码的计算采用二进制模 2 运算（即不进位的加法，等同于异或运算 XOR）。具体步骤如下：

1. 移位：用二进制模 2 运算进行 $2^n$ 乘 $M$ 的运算。这相当于在数据 $M$ 后面添加 $n$ 个 0。
2. 除法：将得到的数据（$k+n$ 位）除以事先选定好的长度为 $n+1$ 位的除数 $P$。
3. 结果：得出的商是 $Q$，而余数是 $R$。余数 $R$ 比除数 $P$ 少 1 位，即 $R$ 是 $n$ 位。
4. 拼接：将余数 $R$ 作为冗余码拼接在数据 $M$ 后面发送出去。

常用生成多项式

在 CRC 运算中，除数 $P$ 通常由生成多项式 $P(X)$ 决定。广泛使用的生成多项式包括：

• CRC-16：$X^{16}+X^{15}+X^2+1$
• CRC-CCITT：$X^{16}+X^{12}+X^5+1$
• CRC-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$

计算举例

假设待发送的数据 $M=101001$ ($k=6$)，除数 $P=1101$ ($n=3$)。

1. 移位：被除数为 $2^{n}M=101001000$。
2. 模 2 除法：$101001000÷1101$。
3. 结果：商 $Q=110101$，余数 $R=001$。
4. 最终发送：将余数 $001$ 拼接到数据后面，发送的数据为 $101001\text{001}$。

帧检验序列 FCS

在数据后面添加的冗余码称为帧检验序列 FCS ：Frame Check Sequence。需要明确区分 CRC 与 FCS 的概念：

• CRC：是一种常用的检错方法（算法）。
• FCS：是添加在数据后面的冗余码（结果）。
  FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的唯一方法。

接收端的校验逻辑

接收端对收到的每一帧进行 CRC 检验，即用相同的除数 $P$ 除以收到的数据（包含 FCS）。

1. 若余数 $R=0$：判定这个帧没有差错，接受。
2. 若余数 $R\ne 0$：判定这个帧有差错，丢弃。

这种检测方法虽然不能确定具体是哪一个或哪几个比特出现了差错，但只要经过严格挑选并使用位数足够多（如 32 位）的除数 $P$，出现检测不到的差错的概率极小。

“无差错接受”与“可靠传输”

仅使用 CRC 差错检测技术只能做到无差错接受。

• 无差错接受：凡是接收端数据链路层接受的帧，都可以以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错。
• 丢弃机制：有差错的帧会被直接丢弃，不予接受。

因此，单纯的 CRC 并不等同于可靠传输。要做到“可靠传输”（即发送什么就收到什么，不丢失、不重复），必须在 CRC 的基础上，增加确认和重传机制。