循环冗余检查

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

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

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

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

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

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

也就是说：

等价于：

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

字符串中的每一位其实就对应了这样类型的多项式的系数。为了得到CRC，我们首先将其乘以，这里n是一个固定多项式的阶数，然后再将其除以这个固定的多项式，余数的系数就是CRC。

在上面的等式中，表示了本来的信息位是111, 是所谓的钥匙，而余数1（也就是）就是CRC. key的最高次为1,所以我们将原来的信息乘上来得到，也可视为原来的信息位补1个零成为1110。

一般来说，其形式为：

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

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

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

CRC多项式规范下面的表格略去了“初始值”、“反射值”以及“最终异或值”。

对于一些复杂的校验和来说这些十六进制数值是很重要的，如CRC-32以及CRC-64。通常小于CRC-16的CRC不需要使用这些值。

通常可以通过改变这些值来得到各自不同的校验和，但是校验和算法机制并没有变化。

CRC标准化问题

由于CRC-12有三种常用的形式，所以CRC-12的定义会有歧义

在应用的CRC-8的两种形式都有数学上的缺陷。

据称CRC-16与CRC-32至少有10种形式，但没有一种在数学上是最优的。

同样大小的CCITT CRC与ITU CRC不同，这个机构在不同时期定义了不同的校验和。1

CRC与数据完整性尽管在错误检测中非常有用，CRC并不能可靠地校验数据完整性（即数据没有发生任何变化），这是因为CRC多项式是线性结构，可以非常容易地故意改变量据而维持CRC不变，参见CRC and how to Reverse it中的证明。我们可以用Message authentication code校验数据完整性。1

参见总的分类

纠错码

校验和算法列表

奇偶校验位

特殊技术参考

Adler-32

Fletcher's checksum

本词条内容贡献者为:

张静 - 副教授 - 西南大学