循环冗馀校验

循环冗馀校验（英语：Cyclic redundancy check，通称“CRC”）是一种根据网路数据封包或电脑档案等数据产生简短固定位数验证码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者储存之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。此方法是由W. Wesley Peterson（英语：W. Wesley Peterson）于1961年发表^[1]。

CRCs经常被叫做“校验和”，但是这样的说法严格来说并不是准确的，因为技术上来说，校验“和”是通过加法来计算的，而不是CRC这里的除法。

“纠错码”（Error–Correcting Codes，简称ECC）常常和CRCs紧密相关，其语序纠正在传输过程中所产生的错误。这些编码方式常常和数学原理紧密相关。例如常见于通讯或资讯传递上BCH码、前向错误更正、错误检测与纠正等。

简介

CRC是两个字节数据流采用二进制除法（没有进位，使用XOR来代替减法）相除所得到的馀数。其中被除数是需要计算校验和的信息数据流的二进制表示；除数是一个长度为 $(n+1)$ 的预定义（短）的二进制数，通常用多项式的系数来表示。在做除法之前，要在信息数据之后先加上 $n$ 个0。

CRC是基于有限域GF(2)（即除以2的同余）的多项式环。简单的来说，就是所有系数都为0或1（又叫做二进制）的多项式系数的集合，并且集合对于所有的代数操作都是封闭的。例如：

(x^{3}+x)+(x+1)=x^{3}+2x+1\equiv x^{3}+1

2会变成0，因为对系数的加法运算都会再取2的模数。乘法也是类似的：

(x^{2}+x)(x+1)=x^{3}+2x^{2}+x\equiv x^{3}+x

同样可以对多项式作除法并且得到商和馀数。例如，如果用x³ + x² + x除以x + 1。会得到：

{\frac {(x^{3}+x^{2}+x)}{(x+1)}}=(x^{2}+1)-{\frac {1}{(x+1)}}

也就是说，

(x^{3}+x^{2}+x)=(x^{2}+1)(x+1)-1

等价于：

(x^{2}+x+1)x=(x^{2}+1)(x+1)-1

这里除法得到了商x² + 1和馀数-1，因为是奇数所以最后一位是1。

字符串中的每一位其实就对应了这样类型的多项式的系数。为了得到CRC，首先将其乘以 $x^{n}$ ，这里 $n$ 是一个固定多项式的阶数（英语：Degree of a polynomial），然后再将其除以这个固定的多项式，馀数的系数就是CRC。

在上面的等式中， $x^{2}+x+1$ 表示了本来的信息位是111, $x+1$ 是所谓的钥匙，而馀数 $1$ （也就是 $x^{0}$ ）就是CRC. key的最高次为1,所以将原来的信息乘上 $x^{1}$ 来得到 $x^{3}+x^{2}+x$ ，也可视为原来的信息位补1个零成为1110。

一般来说，其形式为：

M(x)\cdot x^{n}=Q(x)\cdot K(x)-R(x)

这里M(x)是原始的信息多项式。K(x)是 $n$ 阶的“钥匙”多项式。 $M(x)\cdot x^{n}$ 表示了将原始信息后面加上 $n$ 个0。R(x)是馀数多项式，即是CRC“校验和”。在通讯中，发送者在原始的信息数据M后附加上 $n$ 位的R（替换本来附加的0）再发送。接收者收到M和R后，检查 $M(x)\cdot x^{n}+R(x)$ 是否能被 $K(x)$ 整除。如果是，那么接收者认为该信息是正确的。值得注意的是 $M(x)\cdot x^{n}+R(x)$ 就是发送者所想要发送的数据。这个串又叫做codeword.

实现

变体

CRC有几种不同的变体：

shiftRegister可以逆向使用，这样就需要检测最低位的值，每次向右移动一位。这就要求polynomial生成逆向的数据位结果。实际上这是最常用的一个变体。
可以先将数据最高位读到移位寄存器，也可以先读最低位。在通讯协议中，为了保留CRC的突发错误检测特性，通常按照物理层发送数据位的方式计算CRC。
为了检查CRC，需要在全部的码字上进行CRC计算，而不是仅仅计算消息（Message）的CRC并把它与CRC比较。如果结果是0，那么就通过这项检查。这是因为码字 $M(x)\cdot x^{n}+R(x)=Q(x)\cdot K(x)$ 可以被 $K(x)$ 整除。
移位寄存器可以初始化成1而不是0。同样，在用算法处理之前，消息的最初 $n$ 个数据位要取反。这是因为未经修改的CRC无法区分只有起始0的个数不同的两条消息。而经过这样的取反过程，CRC就可以正确地分辨这些消息了。
CRC在附加到消息数据流（Message stream）的时候可以进行字节取反。这样，CRC的检查可以用直接的方法计算消息的CRC、取反、然后与消息数据流中的CRC比较这个过程来完成，也可以通过计算全部的消息来完成。在后一种方法中，正确消息的结果不再是0，而是 $\sum _{i=n}^{2n-1}x^{i}$ 除以 $K(x)$ 得到的结果。这个结果叫作核验多项式 $C(x)$ ，它的十六进制表示也叫作幻数。

按照惯例，使用CRC-32多项式以及CRC-16-CCITT多项式时通常都要取反。CRC-32的核验多项式是
$C(x)=x^{31}+x^{30}+x^{26}+x^{25}+x^{24}+x^{18}+x^{15}+x^{14}+x^{12}+x^{11}+x^{10}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x+1$ 。

对于要处理的资料M(x)有前置0时，用 $x^{m}L(x)$ 与 $M(x).x^{n}$ 两式相加作反相运算，使得前置的0变成1后，再作mod 2运算得到CRC。公式：

$M(x)\cdot x^{n}+x^{m}L(x)=Q(x)\cdot K(x)+R(x)$
$L(x)\,\!$ $=\sum _{i=0}^{n-1}x^{i}$
$T(x)=M(x)\cdot x^{n}+L(x)+R(x)$
例： $M(x)=01111$
$K(x)=x^{3}+x^{2}+1=1101$ ，这里可知 $n=3$
$M(x).x^{3}=01111000$
因 $\sum _{i=0}^{n-1}x^{i}$ ， $n=3$ 故L(x)阶数从2开始
$L(x)=x^{2}+x^{1}+x^{0}=111$
用 $x^{m}L(x)$ 求得一组n个1及m个0以便与 $M(x).x^{n}$ 相加
令m = 5， $X^{m}L(x)=X^{5}L(x)=11100000$ （bitwise shift）
$M(x).x^{n}+x^{m}L(x)=01111000+11100000=10011000$ （使M前置的0变成1）
用 $10011000$ mod2 $K(x)$ 求得馀R(x)= 011
$T(x)=M(x).x^{n}+L(x)+R(x)=01111000+111+011=01111100$ 送出
接收端L(x) = 111且开头不为1 => m = 5
可反推 $M(x).x^{n}+x^{m}L(x)+R(x)=01111000+11100000+011=10011011$
用10011011 mod2 1101可验证能被K(x)整除。

错误检测能力

CRC的错误检测能力依赖于关键多项式的阶次以及所使用的特定关键多项式。误码多项式 $E(x)$ 是接收到的消息码字与正确消息码字的异或结果。当且仅当误码多项式能够被CRC多项式整除的时候CRC算法无法检查到错误。

由于CRC的计算基于除法，任何多项式都无法检测出一组全为零的数据出现的错误或者前面丢失的零。但是，可以根据CRC的变体来解决这个问题。
所有只有一个数据位的错误都可以被至少有两个非零系数的任意多项式检测到。误码多项式是 $x^{k}$ ，并且 $x^{k}$ 只能被 $i\leq k$ 的多项式 $x^{i}$ 整除。
CRC可以检测出所有间隔距离小于多项式阶次的双位错误，在这种情况下的误码多项式是

 $E(x)=x^{i}+x^{k}=x^{k}\cdot (x^{i-k}+1),\;i>k$ 。

如上所述， $x^{k}$ 不能被CRC多项式整除，它得到一个 $x^{i-k}+1$ 项。根据定义，满足多项式整除 $x^{i-k}+1$ 的 ${i-k}$ 最小值就是多项式的阶次。最高阶次的多项式是本原多项式，带有二进制系数的 $n$ 阶多项式

CRC多项式规范

下面的表格略去了“初始值”、“反射值”以及“最终异或值”。

对于一些复杂的校验和来说这些十六进制数值是很重要的，如CRC-32以及CRC-64。通常小于CRC-16的CRC不需要使用这些值。
通常可以通过改变这些值来得到各自不同的校验和，但是校验和算法机制并没有变化。

CRC标准化问题

由于CRC-12有三种常用的形式，所以CRC-12的定义会有歧义
在应用的CRC-8的两种形式都有数学上的缺陷。
据称CRC-16与CRC-32至少有10种形式，但没有一种在数学上是最优的。
同样大小的CCITT CRC与ITU CRC不同，这个机构在不同时期定义了不同的校验和。

常用CRC（按照ITU-IEEE规范）

名称	多项式	表示法：正常或者翻转
CRC-1	$x+1$ （用途：硬件，也称为奇偶校验位）	0x1 or 0x1 (0x1)
CRC-5-CCITT	$x^{5}+x^{3}+x+1$ （ITU G.704标准）	0xB（0x??）
CRC-5-USB	$x^{5}+x^{2}+1$ （用途：USB信令包）	0x5 or 0x14 (0x9)
CRC-7	$x^{7}+x^{3}+1$ （用途：通信系统）	0x9 or 0x48 (0x11)
CRC-8-ATM	$x^{8}+x^{2}+x+1$ （用途：ATM HEC, PMBUS （参见SMBUS org[1] （页面存档备份，存于互联网档案馆）））	0x7或0xE0 (0xC1)
CRC-8-CCITT	$x^{8}+x^{7}+x^{3}+x^{2}+1$ （用途：1-Wire 总线）	0x8D
CRC-8-Dallas/Maxim	$x^{8}+x^{5}+x^{4}+1$ （用途：1-Wire bus）	0x31或0x8C
CRC-8	$x^{8}+x^{7}+x^{6}+x^{4}+x^{2}+1$	0xD5（0x??）
CRC-10	$x^{10}+x^{9}+x^{5}+x^{4}+x+1$	0x233（0x????）
CRC-12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$ （用途：通信系统）	0x80F或0xF01 (0xE03)
CRC-16-Fletcher	参见Fletcher's checksum	用于Adler-32 A & B CRC
CRC-16-CCITT	$x^{16}+x^{12}+x^{5}+1$ （X25, V.41, Bluetooth, PPP, IrDA）	0x1021或0x8408 (0x0811)
CRC-16-IBM	$x^{16}+x^{15}+x^{2}+1$ （用途：Modbus）	0x8005或0xA001 (0x4003)
CRC-16-BBS	$x^{16}+x^{15}+x^{10}+x^{3}$ （用途：XMODEM协议）	0x8408（0x????）
CRC-32-Adler	参见Adler-32	参见Adler-32
CRC-32-MPEG2	参见IEEE 802.3	参见IEEE 802.3
CRC-32-IEEE 802.3	$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$	0x04C11DB7或0xEDB88320 (0xDB710641)
CRC-32C(Castagnoli)	$x^{32}+x^{28}+x^{27}+x^{26}+x^{25}+x^{23}+x^{22}+x^{20}+x^{19}+x^{18}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+1$	0x1EDC6F41或0x82F63B78 (0x05EC76F1)
CRC-64-ISO	$x^{64}+x^{4}+x^{3}+x+1$ （用途: ISO 3309）	0x000000000000001B或0xD800000000000000 (0xB000000000000001)
CRC-64-ECMA-182	$x^{64}+x^{62}+x^{57}+x^{55}+x^{54}+x^{53}+x^{52}+x^{47}+x^{46}+x^{45}+x^{40}+x^{39}+x^{38}+x^{37}+x^{35}+x^{33}+x^{32}$ $+x^{31}+x^{29}+x^{27}+x^{24}+x^{23}+x^{22}+x^{21}+x^{19}+x^{17}+x^{13}+x^{12}+x^{10}+x^{9}+x^{7}+x^{4}+x+1$ （参见ECMA-182 （页面存档备份，存于互联网档案馆） p.63）	0x42F0E1EBA9EA3693或0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)
CRC-128	IEEE-ITU标准。被MD5 & SHA-1取代
CRC-160	IEEE-ITU标准。被MD5 & SHA-1取代

CRC与数据完整性

尽管在错误检测中非常有用，CRC并不能可靠地验证数据完整性（即数据没有发生任何变化），这是因为CRC多项式是线性结构，可以非常容易地故意改变数据而维持CRC不变，参见CRC and how to Reverse it （页面存档备份，存于互联网档案馆）中的证明。可以用讯息鉴别码验证数据完整性。

CRC发生碰撞的情况

与所有其它的散列函数一样，在一定次数的碰撞测试之后CRC也会接近100%出现碰撞。CRC中每增加一个数据位，碰撞机率就会减少接近50%，如CRC-20与CRC-21相比。

理论上来讲，CRC64的碰撞概率大约是每18×10¹⁸个CRC码出现一次。
由于CRC的不分解多项式特性，所以经过合理设计的较少位数的CRC可能会与使用较多数据位但是设计很差的CRC的效率相媲美。在这种情况下CRC-32几乎同CRC-40一样优秀。

设计CRC多项式

生成多项式的选择是CRC算法实现中最重要的部分，所选择的多项式必须有最大的错误检测能力，同时保证总体的碰撞概率最小。多项式最重要的属性是它的长度，也就是最高非零系数的数值，因为它直接影响著计算的校验和的长度。

最常用的多项式长度有

9位（CRC-8）
17位（CRC-16）
33位（CRC-32）
65位（CRC-64）

在构建一个新的CRC多项式或者改进现有的CRC时，一个通用的数学原则是使用满足所有模运算不可分解多项式约束条件的多项式。

这种情况下的不可分解是指多项式除了1与它自身之外不能被任何其它的多项式整除。

生成多项式的特性可以从算法的定义中推导出来：

如果CRC有多于一个的非零系数，那么CRC能够检查出输入消息中的所有单数据位错误。
CRC可以用于检测短于2k的输入消息中的所有双位错误，其中k是多项式的最长的不可分解部分的长度。
如果多项式可以被x+1整除，那么不存在可以被它整除的有奇数个非零系数的多项式。因此，它可以用来检测输入消息中的奇数个错误，就像奇偶校验函数那样。

参见

总的分类

特殊技术参考

参考文献

^ Peterson, W. W. and Brown, D. T. Cyclic Codes for Error Detection. Proceedings of the IRE. January 1961, 49: 228. ISSN 0096-8390. doi:10.1109/JRPROC.1961.287814.

外部链接

Tutorial and C++ implementation of CRC (所引用网址代码运行存在问题)
Cyclic redundancy check - a simple guide to what it means for your data, CD and DVD discs. http://www.softwarepatch.com/tips/cyclic-redundancy.html （页面存档备份，存于互联网档案馆）
The CRC Pitstop
Williams, R.（1993-09）A Painless Guide to CRC Error Detection Algorithms
Understanding Cyclic Redundancy Check
Black, R.（1994-02）Fast CRC32 in Software—Algorithm 4 is used in Linux and info-zip's zip and unzip.
Barr, M.（1999-11, 1999-12, 2000-01）checksums, CRCs, and their source code. Embedded Systems Programming
CRC32: Generating a checksum for a file, C++ implementation by Brian Friesen
Online Tool to compute common CRCs（8/16/32/64）from strings
Online CRC calculator （页面存档备份，存于互联网档案馆）
Online CRC Tool: Generator of synthesizable CRC functions （页面存档备份，存于互联网档案馆）
Online Char(ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, CRC, etc. hashing algorithms
CRC16 to CRC64 collision research （页面存档备份，存于互联网档案馆）
Reversing CRC – Theory and Practice. （页面存档备份，存于互联网档案馆）

[PetersonBrown1961-1] Peterson, W. W. and Brown, D. T. Cyclic Codes for Error Detection. Proceedings of the IRE. January 1961, 49: 228. ISSN 0096-8390. doi:10.1109/JRPROC.1961.287814.

[1]