循环冗余校验(Cyclic Redundancy Check, CRC)是一种根据网路数据包或电脑档案等数据产生简短固定位数校验码的一种散列函式，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。
基本介绍
- 中文名：循环冗余校验
- 外文名：CRC
- 全称：Cyclic Redundancy Check
- 原理：除法及余数的原理来作错误侦测
CRC简介
在数据传输过程中，无论传输系统的设计再怎幺完美，差错总会存在，这种差错可能会导致在链路上传输的一个或者多个帧被破坏(出现比特差错，0变为1，或者1变为0)，从而接受方接收到错误的数据。为儘量提高接受方收到数据的正确率，在接收方接收数据之前需要对数据进行差错检测，若且唯若检测的结果为正确时接收方才真正收下数据。检测的方式有多种，常见的有奇偶校验、网际网路校验和循环冗余校验等。
工作原理
循环冗余校验同其他差错检测方式一样，通过在要传输的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版本：
名称 | 多项式 | 表示法 | 套用举例 |
CRC-8 | X8+X2+X+1 | 0X207 | |
CRC-12 | X12+X11+X3+X2+X+1 | 0X80F | telecom systems |
CRC-16 | X16+X15+X2+1 | 0X8005 | Bisync, Modbus, USB, ANSI X3.28, SIA DC-07, many others; also known as CRC-16 and CRC-16-ANSI |
CRC-CCITT | X16+X12+X5+1 | 0X1021 | ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS |
CRC-32 | X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1 | 0x04C11DB7 | ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS |
CRC-32C | X32+X28+X27+X26+X25+X23+X22+X20+X19+X18+X14+X13+X11+X10+X9+X8+X6+1 | 0x1EDC6F41 | iSCSI, SCTP, G.hn payload, SSE4.2, Btrfs, ext4, Ceph |
选择方案
上面我们提供了很多国际标準的CRC生成多项式版本，但在我们实际的套用当中，我们只需要选择其中的一种作为生成多项式即可，可是我们应该如何做出选择呢？下面我们根据几张8bits-16bits实验仿真图来对不同的标準进行横向和竖向的比较，从而给出一种比较合适的选择方案。
注：
1. 以下几图中，蓝色虚线为实验者提出的标準最小漏检率曲线，下面我们称为最佳性能曲线。
2. 以下图和数据来自《CRC性能分析及生成多项式选取的研究》，硕士学位论文，郑州轻工业学院魏艳。
一、横向比较
8-bits CRC
 8bits-1 | 左图1中，0xD5为CRC-8标準，从以上两图中我们可以看到： 1. 该标準对于8bits-85bits的範围内表现出了优良的性能，贴近最佳性能曲线；当数据帧的长度长于85bits的时候其性能出现了骤变，漏检率提高，性能下降；当数据帧长度达到248bits的时候，性能略微回归，但仍然表现不佳。 2. 相比较CRC-8标準而言，生成多项式0x2F表现出了更好的性能，但仍旧在128bits-256bits区间表现不佳。 3. 从左图2二可见，生成多项式0x4D弥补了上述两个生成多项式在128bits-后表现不佳的缺点。 |
 8bits-2 | 因此，我们可以得出结论，若CRC长度限制在8bits，我们根据所给数据帧的最小长度来确定合适的CRC多项式： 8bits-85bits：选择CRC-8标準，漏检率大概在(1e-27, 1e-24) 8bits-128bits：选择0x2F，漏检率大概在(1e-27, 1e-24) 128bits-2048bits：选择0x4D，漏检率大概在(1e-21, 1e-12) |
12-bits CRC
 12bits | 在12bits下，国际上有CRC-12标準0x80F，我们仍然以横向比较来进行。上图告诉我们： 1. CRC-12标準整体表现不尽如人意，在实验者选取的数据帧长度(我们常用的数据帧长度範围)内，CRC-12标準的漏检率整体高于最佳性能曲线。 2. 就该标準而言，在54bits-2035bits範围内表现较好。 因此我们可以得出结论，若CRC长度限制在12bits，可以选择CRC-12标準，但更倾向于数据帧长度在54bits-2035bits範围内。 |
16-bits CRC
 16bits | 同样利用实验者的数据，我们对16-bits的国际标準美国标準CRC-16(0x8005)和欧洲标準CRC-CCITT(0x1021)进行比较： 1. 在漏检率方面，欧洲标準略低于美国标準。 2. 上述两种标準的生成多项式性能表现不是很理想，在8bits-247bits範围内校验性能较差。 由此，我们得出： 16-bits的美国标準和欧洲标準更适合于长度大于256bits的帧。 |
二、 纵向比较
上面，我们利用实验者提供的实验数据对限长的CRC国际标準码的性能表现做了横向比较，下面我们进行部分纵向比较，仅考虑数据帧长度，而不限制CRC长度。
从实验者提供的数据我们可以发现，对于国际标準CRC-8，CRC-12，CRC-16，CRC-CCITT：
1. 当数据帧长度在8bits-128bits範围内时，CRC-8有更好的表现；
2. 当数据帧长度大于128bits时，CRC-12，CRC-16，CRC-CCITT均有较好的表现，且其漏检率基本相近。
三、结论
基于上述简单的分析，以及更多的实验，实验者给出了选择CRC生成多项式的具体步骤，并提供了一张对应于不同长度数据帧的相对比较好的CRC生成多项式的选择表。
生成多项式最小码距 | CRC Size(bits) | |||||||||||||
3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
HD=2 | 2048+ 0X5 | 2048+ 0X9 | 2048+ 0X12 | 2048+ 0X21 | 2048+ 0X48 | 2048+ 0x4D | 2048+ 0X2CF | 2048+ 0x64F | 2048+ 0X64D | |||||
HD=3 | 11 0X9 | 26 0X12 | 57 0X21 | 120 0X48 | 247 0X4D | 502 0X2CF | 1013 0X64F | 2036 0X64D | 2048 0x6EB | |||||
HD=4 | 10 0X15 | 25 0X2C | 56 0X5B | 119 0x2F | 246 0x297 | 501 0X319 | 1012 0xB07 | 2035 0x80F | 2048 0x2055 | 2048 0x43D1 | 2048 0x92ED | 2048 0x755B | ||
HD=5 | 9 0x39 | 13 0x3AB | 21 0X2B9 | 25 0xBAF | 53 0x1F1 | none | 113 0x4256 | 136 0xD51B | 241 0x5935 | |||||
HD=6 | 8 0x279 | 12 0X28E | 22 0xA65 | 27 0x683 | 52 0x3213 | 57 0x6E57 | 114 0xAE75 | 135 0X486C | ||||||
HD=7 | 12 0xAE3 | None | 12 0x254B | 13 0x5153 | 16 0x67AB | 19 0x2D17 | ||||||||
HD=8 | 11 0xa47 | 11 0x216F | 11 0x46E3 | 12 0xC617 | 15 0x1FB7 | |||||||||
注：上表每一个单元格中有两个数字，其中上面的数字表示的是数据帧能达到码重最大值时地最长的长度，下面的数字就代表在达到这个码重时採用的具体的生成多项式。
四、方案
从上面的分析我们看到，国际上提供的标準也并不是在任何情况下都能提供很好的差错检测性能，因此，针对不同的情况来选择适当的CRC生成多项式是有必要的，根据以上，我们提供下面的CRC国际标準选择方案：
1. 当数据帧长度在8bits-128bits範围内时，推荐CRC-8(CRC-8能够减少额外比特的开销，且有更好的性能表现)；
2. 当数据帧长度在128bits-2048bits範围内时，推荐CRC-12，CRC-16，CRC-CCITT(CRC-12额外比特的开销更小，且用于6bit字元流的传输；对于16bits的标準，更推荐美国标準CRC-16，性能略优于CRC-CCITT)；
3. 当因数据帧长度更长、信道不稳定等情况而需要更高的性能时，CRC-32、CRC-32C(Castagnoli等人于1993年左右提出的具有更好性能的CRC标準，并被iSCSI、SCTP使用)将是更好的选择；
4. 选择其他更多国际标準。
差错检测能力
利用多项式，我们定义误码多项式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是最着名的一种。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值。
参考资料
1.《数据与计算机通信》(第十版)，William Stallings着，电子工业出版社
2. Wikipedia - 循环冗余校验
3.《CRC性能分析及生成多项式选取的研究》，硕士学位论文，郑州轻工业学院魏艳
