循环冗余校验

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

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

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

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

也就是说，

等价于：

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

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

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

一般来说，其形式为：

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

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

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

CRC有几种不同的变体

可以逆向使用，这样就需要检测最低位的值，每次向右移动一位。这就要求生成逆向的数据位结果。实际上这是最常用的一个变体。

可以先将数据最高位读到移位寄存器，也可以先读最低位。在通信协议中，为了保留CRC的突发错误检测特性，通常按照物理层发送数据位的方式计算CRC。

为了检查CRC，需要在全部的码字上进行CRC计算，而不是仅仅计算消息（Message）的CRC并把它与CRC比较。如果结果是0，那么就通过这项检查。这是因为码字可以被整除。

移位寄存器可以初始化成1而不是0。同样，在用算法处理之前，消息的最初个数据位要取反。这是因为未经修改的CRC无法区分只有起始0的个数不同的两条消息。而经过这样的取反过程，CRC就可以正确地分辨这些消息了。

CRC在附加到消息数据流（Message stream）的时候可以进行字节取反。这样，CRC的检查可以用直接的方法计算消息的CRC、取反、然后与消息数据流中的CRC比较这个过程来完成，也可以通过计算全部的消息来完成。在后一种方法中，正确消息的结果不再是0，而是除以得到的结果。这个结果叫作核验多项式，它的十六进制表示也叫作幻数。

按照惯例，使用CRC-32多项式以及CRC-16-CCITT多项式时通常都要取反。CRC-32的核验多项式是
。

对于要处理的数据M(x)有前置0时，用与两式相加作取反运算，使得前置的0变成1后，再作mod 2运算得到CRC。公式：

例：
，这里可知

因，故L(x)阶数从2开始

用求得一组n个1及m个0以便与相加
令m = 5，（bitwise shift）
（使M前置的0变成1）
用 mod2 求得余R(x)= 011
提交
接收端L(x) = 111且开头不为1 => m = 5
可反推
用10011011 mod2 1101可校验能被K(x)整除。

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

由于CRC的计算基于除法，任何多项式都无法检测出一组全为零的数据出现的错误或者前面丢失的零。但是，可以根据CRC的变体来解决这个问题。

所有只有一个数据位的错误都可以被至少有两个非零系数的任意多项式检测到。误码多项式是，并且只能被的多项式整除。

CRC可以检测出所有间隔距离小于多项式阶次的双位错误，在这种情况下的误码多项式是

如上所述，不能被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并不能可靠地校验数据完整性（即数据没有发生任何变化），这是因为CRC多项式是线性结构，可以非常容易地故意改变量据而维持CRC不变，参见中的证明。我们可以用Message authentication code校验数据完整性。

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

理论上来讲，CRC64的碰撞概率大约是每18×10¹⁸个CRC码出现一次。

由于CRC的不分解多项式特性，所以经过合理设计的较少位数的CRC可能会与使用较多数据位但是设计很差的CRC的效率相媲美。在这种情况下CRC-32几乎同CRC-40一样优秀。