文章目录
- CRC 的基本原理
- 冗余码的计算方法
- 常用生成多项式
- 计算举例
- 帧检验序列 FCS
- 接收端的校验逻辑
- “无差错接受”与“可靠传输”
在数据链路层传送数据时，为了保证数据传输的可靠性，必须采用差错检测措施。目前广泛使用的是循环冗余检验 CRC，Cyclic Redundancy Check技术。
CRC 的基本原理
CRC 的核心思想是在发送端将数据划分为若干组，假定每组k kk个比特。在每组数据M MM后面添加供差错检测用的n nn位冗余码，然后构成一个帧发送出去。因此，实际发送的帧总长度为k + n k + nk+n位。
冗余码的计算方法
CRC 冗余码的计算采用二进制模 2 运算（即不进位的加法，等同于异或运算 XOR）。具体步骤如下：
- 移位：用二进制模 2 运算进行2 n 2^n2n乘M MM的运算。这相当于在数据M MM后面添加n nn个 0。
- 除法：将得到的数据（k + n k+nk+n位）除以事先选定好的长度为n + 1 n+1n+1位的除数P PP。
- 结果：得出的商是Q QQ，而余数是R RR。余数R RR比除数P PP少 1 位，即R RR是n nn位。
- 拼接：将余数R RR作为冗余码拼接在数据M MM后面发送出去。
常用生成多项式
在 CRC 运算中，除数P PP通常由生成多项式P ( X ) P(X)P(X)决定。广泛使用的生成多项式包括：
- CRC-16：X 16 + X 15 + X 2 + 1 X^{16} + X^{15} + X^2 + 1X16+X15+X2+1
- CRC-CCITT：X 16 + X 12 + X 5 + 1 X^{16} + X^{12} + X^5 + 1X16+X12+X5+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 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 + 1X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1
计算举例
假设待发送的数据M = 101001 M = 101001M=101001(k = 6 k=6k=6)，除数P = 1101 P = 1101P=1101(n = 3 n=3n=3)。
- 移位：被除数为2 n M = 101001000 2^n M = 1010010002nM=101001000。
- 模 2 除法：101001000 ÷ 1101 101001000 \div 1101101001000÷1101。
- 结果：商Q = 110101 Q = 110101Q=110101，余数R = 001 R = 001R=001。
- 最终发送：将余数001 001001拼接到数据后面，发送的数据为101001 001 101001\textbf{001}101001001。
帧检验序列 FCS
在数据后面添加的冗余码称为帧检验序列 FCS ：Frame Check Sequence。需要明确区分 CRC 与 FCS 的概念：
- CRC：是一种常用的检错方法（算法）。
- FCS：是添加在数据后面的冗余码（结果）。
FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的唯一方法。
接收端的校验逻辑
接收端对收到的每一帧进行 CRC 检验，即用相同的除数P PP除以收到的数据（包含 FCS）。
- 若余数R = 0 R = 0R=0：判定这个帧没有差错，接受。
- 若余数R ≠ 0 R \neq 0R=0：判定这个帧有差错，丢弃。
这种检测方法虽然不能确定具体是哪一个或哪几个比特出现了差错，但只要经过严格挑选并使用位数足够多（如 32 位）的除数P PP，出现检测不到的差错的概率极小。
“无差错接受”与“可靠传输”
仅使用 CRC 差错检测技术只能做到无差错接受。
- 无差错接受：凡是接收端数据链路层接受的帧，都可以以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错。
- 丢弃机制：有差错的帧会被直接丢弃，不予接受。
因此，单纯的 CRC 并不等同于可靠传输。要做到“可靠传输”（即发送什么就收到什么，不丢失、不重复），必须在 CRC 的基础上，增加确认和重传机制。
