CRC检验背后的原理与算法

CRC概述

循环冗余校验（Cyclic Redundancy Check， CRC） 又称多项式码，是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术。

主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用二进制除法及余数的原理来作错误侦测的。

原理

基本思想

发收方与接收方实现选定一个多项式 $P(x)$ ，该多项式可以与二进制码一一对应，我们要求该二进制数最高位和最低位必须为1，而这个二进制数就作为除数。

接下来，我们以需要发送的 $N$ 位 数据序列为被除数，两者进行“模2除法”，得到的 $D$ 位的余数即校验码，也叫 帧检测序列（FCS），将校验码附在数据序列后面生成一个新序列（共 $D+N$ 位）发送给接收端。

到达接收端后，把接收到的新序列除以这个选定的除数，无差错的结果应该是余数为0。如果有余数，则表明该数据在传输过程中出现了差错。

数学解释

现有需要传输的数据流 $M=m_0m_1\cdots m_{N-1}$ ，由 $N=|M|\;bit$ 组成， $m_k\in\{0,1\}$ .
那么，其大小可以用 $2$ 的多项式表示如下（不如说任意二进制数都能如此表示）：

$M=\sum_{k=0}^{N-1}2^{(N-1)-k}\cdot m_k$

更一般地，可表示为对任一单变量 $x$ 的多项式函数：

$M(x)=\sum_{k=0}^{N-1}x^{N-1-k}\cdot m_k\quad m\in GF(2)=\{0,1\}$

其中， $GF(·)$ 表示的是一种 有限域|finite field 又称 伽罗尔域|Galois field。而这里的多项式表示的是模2同余的多项式环。例如有：

$(x^3+x)+(x+1)=x^3+2x+1\equiv x^3+1$

其中 $x^2$ 前的系数因为模二余0，所以消失了。

如果给定一个阶数为 $D:=\text{deg}(P(x))$ 的多项式 $P(x)$ . 那么，我们就可以定义 CRC帧检测序列 为：

$FCS_P(M)=\left(M(x)\cdot x^D\right)\mod P(x)$

显然， $\left(M(x)\cdot x^D+FCS_P(M)\right)\mod P(x)\equiv 0$

以 $M(x)=x^2+x+1,P(x)=x+1$ 为例，由长除法得：

$\begin{aligned} & \quad\;x^2+1 \\ x+1 & \overline{)\;\;\;x^3+x^2+x\quad\quad } \\ & \underline{\;\;\;\;x^3+x^2\quad\quad}\quad\quad\ \\ & \quad\quad\quad\quad \quad \;\;x \\ & \underline{\quad\quad\quad\quad\quad\;\; x+1\quad} \\ & \quad\quad\quad\quad\quad\quad\;\;-1\\ \end{aligned}$

即是： $M(x)\cdot x=P(x)\cdot (x^2+1)-1$ . 这里的 余数 1 即是帧检测序列。
所以有： $M(x)\cdot x+1=P(x)\cdot(x^2+1)\Rightarrow (M(x)·x+1)\mod P(x)=0$

二进制表示

我们将上述示例退化为二进制表示，即 $M(x)\to$ 111, $P(x)\to$ 11.
进而有 $M(x)·x\to$ 1110，相当于将二进制数右补 $D=1$ 个 0（因为 $P(x)$ 的阶数为1）

对二者进行模二除法（加法不进位，减法不借位，事实上正好是对二进制按位异或）：

$\begin{aligned} & \quad\;101 \\ 11 & \overline{)\;\;\;1110\quad\quad } \\ & \underline{\quad\;11\quad}\quad\quad\ \\ & \quad\quad\;10 \\ & \underline{\quad\quad\;11\quad} \\ & \quad\quad\;\;\;1\\ \end{aligned}$

从而余数 1 即为结果。显然有 $M(x)·x+1\to$ 1111 与 11 的模为0.

常用算法选取

CRC算法名称	多项式公式	宽	多项式	初始值	结果异或	输入值反转	输出值反转
CRC-4/ITU	x^4^ + x + 1	4	03	00	00	true	true
CRC-5/EPC	x^4^ + x^3^ + 1	5	09	09	00	false	false
CRC-5/ITU	x^5^ + x^4^ + x^2^ + 1	5	15	00	00	true	true
CRC-5/USB	x^5^ + x^2^ + 1	5	05	1F	1F	true	true
CRC-6/ITU	x^6^ + x + 1	6	03	00	00	true	true
CRC-7/MMC	x^7^ + x^3^ + 1	7	09	00	00	false	false
CRC-8	x^8^ + x^2^ + x + 1	8	07	00	00	false	false
CRC-8/ITU	x^8^ + x^2^ + x + 1	8	07	00	55	false	false
CRC-8/ROHC	x^8^ + x^2^ + x + 1	8	07	FF	00	true	true
CRC-8/MAXIM	x^8^ + x^5^ + x^4^ + 1	8	31	00	00	true	true