循环冗余校验

循环冗余校验，是一种为数据确定校验值的方法，以便能够在传输或存储过程中检测错误。 理想情况下，该过程甚至可以独立纠正接收到的数据以避免重传。

在存储或传输数据之前，以所谓的 CRC 值的形式将附加冗余添加到用户数据的每个数据块。 这是根据特定程序计算的测试值，可用于识别在存储或传输过程中可能发生的任何错误。 为了验证数据，将相同的计算方法应用于包括附加的 CRC 值的数据块。 如果结果为零，则可以假定数据块未损坏。 然而，各种技术应用都偏离了该方案，例如通过使用特定值初始化计算或通过在传输之前反转CRC值。

CRC 的设计方式使得数据传输中的错误（例如由线路上的噪声引起的错误）很有可能被检测到。 串行数据传输的 CRC 可以很容易地在硬件中实现。 例如，以太网上的数据传输和大多数硬盘驱动器传输都使用 CRC 程序进行检查。

CRC 方法仅设计用于检测随机错误。 它不适用于确认数据的完整性。 也就是说，通过有意修改创建与给定消息具有相同 CRC 值的数据流相对容易。 如果需要这种安全性，则必须使用加密散列函数（例如 SHA）或签名函数（例如 RSA）。

该方法的名称来源于这样一个事实，即附加值没有不包含在底层数据块中的信息内容。 因此它是多余的。 CRC 基于循环码。 这些是块代码，具有有效代码字的比特的每个循环移位也是有效代码字的属性。

CRC 值的计算基于多项式除法：要传输的位序列被视为二进制多项式。

数据的代码表示的位串除以预定的生成多项式（CRC 多项式）模 mod(2)，留下余数。 这个余数就是 CRC 值。 传输数据块时，CRC 值附加到原始数据块并同时传输。

为了验证数据不包含任何错误，将接收到的带有附加 CRC 值的数据块解释为二进制序列，再次除以 CRC 多项式模并确定余数。 如果没有余数，则要么没有错误发生，要么发生（非常不可能的）错误，该错误将 CRC 多项式作为多项式表示中的一个因素。

需要注意的是，与 CRC 通信的 ones 和 zeros 并不是数字的表示，而是多项式。 这意味着例如用袖珍计算器对二进制数（或一般数字）进行模除法不会得出正确的结果。

数据传输需要某些必要的协议。 一方面，接收者必须意识到原始数据的安全传输是完全发生的。 仅从传入数据流的类型无法识别这一点。 另一方面，接收方必须使用与发送方相同的CRC多项式和计算方法。 最后，接收方必须知道除了数据之外传输的校验和在数据流中的位置。

CRC 方法既可以在简单的硬件组件中实现，也可以在软件中实现。 一个被使用

• n位的移位寄存器，其中n是生成多项式的次数（大约是CRC-32中的32位移位寄存器）和a
• 任意长度的位数据流后跟 n 个零位。

算法伪代码，最高位最左边，乘以2表示左移一位：

crc := 0000 ...（起始值）对于数据流中的所有位 b：如果 crc 的最左边位为 1：crc := (crc * 2 + b) xor CRC 多项式 否则：crc := crc * 2 + bcrc包含结果。

在 CRC-8 的情况下，通过使用包含 256 个可能字节中的每一个的关联 CRC 值的表，上述算法可以加速 8 倍。 这是因为表条目包含 8 位 = 1 字节和基位置 = 2 8 = 256 不同的表条目存在。 速度的提高是通过使用要计算的位序列直接访问表来实现的，因为所寻求的 CRC-8 计算位于表中具有要计算的位序列的二进制值作为索引的位置.

左移和异或操作使 CRC 非常适合在逻辑电路中使用。 数据流的 CRC 可以逐位（或逐字节等）计算，并由发送方附加到数据中。 数据流的接收方可以采用与发送方相同的方式计算 CRC，但包含 CRC。 包括 CRC 的结果必须等于零，否则流包含位错误。

CRC 类型通常通过用作除数的多项式（十六进制格式）来区分。 最常用的 CRC 之一（以太网、FDDI、ZIP 和 PNG 等使用）是 0x04C11DB7 多项式，称为 CRC-32。 事实证明，一些多项式比其他多项式“保护”得更好。 常用于 CRC 的多项式是广泛的数学和经验分析的结果，而不是随机数，尽管它们看起来很像。

如果 0000... 用作起始值，则该实现执行多项式除法。 您经常会发现其他起始值。 如果数据流的前 n 位被反转，则这对应于多项式除法。

起始值不等于 0000... 是更可取的，因为否则将无法识别数据流中前导零内丢失的位（就像普通除法一样，前导零不计入多项式除法）。