循环冗余校验

循环冗余校验（CRC）是一个错误检测码在数字常用网络和存储设备，以检测到的原始数据的意外改变。进入这些系统的数据块将根据其内容的多项式除法运算的余数获得一个简短的校验值。在检索时，将重复计算，如果校验值不匹配，则可以采取纠正措施来防止数据损坏。CRC可用于纠错（请参阅bitfilters）。

之所以称为CRC，是因为校验（数据验证）值是冗余的（它在不添加信息的情况下扩展了消息），并且算法基于循环码。CRC之所以受欢迎，是因为它们易于在二进制硬件中实现，易于数学分析，并且特别擅长检测由传输通道中的噪声引起的常见错误。由于校验值具有固定的长度，因此生成校验值的函数有时会用作哈希函数。
CRC基于循环 纠错码的理论。W. Wesley Peterson于1961 年首次提出使用系统循环码，该编码通过添加固定长度的校验值对消息进行编码，以实现通信网络中的错误检测。循环码不仅易于实现，但具有特别适合检测突发错误的好处：消息中错误数据符号的连续序列。这很重要，因为突发错误是许多通信通道（包括磁性和光学存储设备）中常见的传输错误。通常为n应用于任意长度的数据块的1位CRC将检测不超过n位的任何单个错误突发，并且它将检测到的所有更长的错误突发的分数为（1-2 − n）。

CRC码的规范要求定义所谓的生成多项式。该多项式成为多项式长除法的除数，该除法以消息为被除数，并且其中的商被舍弃，余数成为结果。重要的警告是多项式系数是根据有限域的算法计算的，因此加法运算始终可以按位并行执行（数字之间没有进位）。

实际上，所有常用的CRC都使用两个元素GF（2）的Galois字段。这两个元素通常称为0和1，可以轻松匹配计算机体系结构。

当CRC 的校验值是n位长时，称为n位CRC 。对于给定的n，可能有多个CRC，每个CRC具有不同的多项式。这样的多项式具有最高的次数n，这意味着它具有n +1个项。换句话说，多项式的长度为n +1；其编码需要n +1位。请注意，大多数多项式规范都舍弃了MSB或LSB，因为它们始终为1。CRC 和相关多项式的名称通常为CRC- n -XXX形式，如下表所示。

最简单的错误检测系统奇偶校验位实际上是1位CRC：它使用生成多项式 x + 1（两个项），并具有CRC-1的名称。
这是CRC的CRC-32变体的算法。CRCTable是计算的记忆，对于消息的每个字节都必须重复进行计算。
Function CRC32
Input:
data: Bytes //Array of bytes
Output:
crc32: UInt32 //32-bit unsigned crc-32 value

//Initialize crc-32 to starting value
crc32 ← 0xFFFFFFFF

for each byte in data do
nLookupIndex ← (crc32 xor byte) and 0xFF;
crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex] //CRCTable is an array of 256 32-bit constants

//Finalize the CRC-32 value by inverting all the bits
crc32 ← crc32 xor 0xFFFFFFFF
return crc32