循环冗余校验

循环冗余校验（Cyclic Redundancy Check， CRC）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。^[1]

工作原理

循环冗余校验同其他差错检测方式一样，通过在要传输的k比特数据D后添加(n-k)比特冗余位(又称帧检验序列，Frame Check Sequence，FCS)F形成n比特的传输帧T，再将其发送出去。特别的，循环冗余校验提供一个预先设定的(n-k+1)比特整数P，并且要求添加的(n-k)比特F满足：

T mod P == 0 ……(1)

其中 T =2n-kD + F

基于上述要求，实际应用时，发送方和接收方按以下方式通信：

1. 发送方和接收方在通信前，约定好预设整数P。

2. 发送方在发送前根据数据D确定满足(1)式的F，生成CRC码 T，T 即为数据位D与校验位F的拼接，发送T。

3. 接收方收到CRC码 T，进行 result = T mod P 运算，当且仅当result = 0时接收方认为没有差错。

发送方在发送数据前需要确定填充的(n-k)比特F，以下提供了两种等价的方式来确定F。

模二运算

模二运算采用无进位的二进制加法，恰好为异或(XOR)操作。(以下运算均为模2运算)

CRC码 T 需要满足(1)式，即(2n-kD + F)/P结果为某一整数对此表达式进行恒等变换，可得：(2n-kD + F)/P = 2n-kD / P + F / P …… (2)继续对等式中2n-kD / P 进行恒等变换，将其整数部分 Q 分离，即 Q=(2n-kD - R)/P，有2n-kD / P = Q + R / P …… (3)

将(3)式带入(2)式得到：(2n-kD + F) / P = Q + R / P+ F / P …… (4)由于采用无进位的二进制加法(等价于XOR操作)，因此当我们令 F = R 时，有(2n-kD + F) / P = Q + R / P+ F / P = Q …… (5)

当Q为整数时，T =(2n-kD + F)满足T mod P == 0。故我们只要找到 F = R 使得(3)式中 Q 恒为整数即可。

由 Q=(2n-kD - R)/P，可知（1）当2n-kD modP ≠ 0 时R=2n-kD modP可使等式恒成立。（2）当2n-kD modP == 0 时F = R = n * P （n ∈ Z）可使等式恒成立。R=2n-kD modP 即为 n = 0 时情况。综上，令R=2n-kD modP 时可使等式Q=(2n-kD - R)/P 中Q恒为整数。

因此我们需要添加的帧检验序列F为：F = R=2n-kD modP …… (6)

二进制系数多项式该种方法，我们试图对任意的二进制数都构造与其对应的一个二进制系数多项式，构造如下：

对于任意k位二进制数D =dk-1…d2d1d0，其对应的多项式为D(X) = ∑di*Xi，i∊[0， k) …… (7) 例如，D = 110101，则D(X) = X5 + X4 + X2 + 1。

运算过程依然是模二的，则此时的CRC过程可描述如下：

Xn-kD(X) / P(X) = Q(X) + R(X) / P(X) …… (8)

T(X) = Xn-kD(X) + R(X) …… (9)

即，此时的F(X)满足：

F(X) = Xn-kD(X) mod P(X) …… (10)

常用CRC版本

上面我们介绍了F(X)的求法，但F(X)依赖于P(X)，因此选取一个合适的P(X)也是CRC的一个关键问题。通常，一个m位的CRC多项式P(X)是由如下两种形式的多项式之一产生的：

P(X) = q(X) …… (12)

P(X) = (X + 1)q(X) …… (13)

其中q(X)是一种特殊类型的多项式，称为本原多项式。且P(X)满足：

最高位和最低位都是1

当被传送信息任何一位发生错误时，P(X)不被T(X)整除

不同位发生错误时，余数应该不同

对余数继续做模二除法时，应该使余数循环

下面展示常用CRC版本：

差错检测能力

利用多项式，我们定义误码多项式E(X)是接收到的消息码字与正确码字的异或。即

E(X) = Trecv(X) XOR Tcorrect(X) …… (14)

则我们容易知道，当且仅当E(X)能够被CRC多项式P(X)整除的时候CRC算法无法检查到错误。当我们选择一个适当的P(X)时，以下所有差错E(X)都不能被P(X)整除，因此可以检测出：

单比特差错，只要P(X)含有一个以上的非零项。

双比特差错，只要P(X)满足上述两种形式((12)(13)式)。

任意奇数个比特差错，只要P(X)含有因式(X - 1)。

任意突发差错，当突发差错长度小于或等于帧检验序列(F(X))的长度(n - k)。

长度为(n - k + 1)的突发差错片段，这个片段等于(1-2-(n-k-1))。

长度大于(n - k + 1)的突发差错片段，这个片段等于(1 - 2-(n-k))

应用场合

在数据存储和数据通讯领域，为了保证数据的正确，就不得不采用检错的手段。在诸多检错手段中，CRC是最著名的一种。CRC的全称是循环冗余校验，其特点是：检错能力强，开销小，易于用编码器及检测电路实现。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，CRC无处不在：著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。下面介绍硬件生成与计算CRC的过程。

硬件生成与计算过程

下面以最常用的CRC-16为例来说明其生成过程。

CRC-16码由两个字节构成，在开始时CRC寄存器的每一位都预置为1，然后把CRC寄存器与8-bit的数据进行异或，之后对CRC寄存器从高到低进行移位，在最高位（MSB）的位置补零，而最低位（LSB，移位后已经被移出CRC寄存器）如果为1，则把寄存器与预定义的多项式码进行异或，否则如果LSB为零，则无需进行异或。重复上述的由高至低的移位8次，第一个8-bit数据处理完毕，用此时CRC寄存器的值与下一个8-bit数据异或并进行如前一个数据似的8次移位。所有的字符处理完成后CRC寄存器内的值即为最终的CRC值。

1．设置CRC寄存器，并给其赋值FFFF(hex)。

2．将数据的第一个8-bit字符与16位CRC寄存器的低8位进行异或，并把结果存入CRC寄存器。

3．CRC寄存器向右移一位，MSB补零，移出并检查LSB。

4．如果LSB为0，重复第三步；若LSB为1，CRC寄存器与多项式码相异或。

注意：该步检查LSB应该是右移前的LSB，即第3步前的LSB。

5．重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。

6．重复第2至第5步直到所有数据全部处理完成。

7．最终CRC寄存器的内容即为CRC值。