![[Note]](../../../doc/src/images/note.png) |
注意 |
|---|---|
部分入门材料基于 Ross N. Williams 在其 The CRC Pitstop 网站上发表的 A Painless Guide to CRC Error Detection Algorithms（CRC 错误检测算法浅显指南）。 |
当二进制数据在传输过程中（通常是电子传输）时，数据可能会发生损坏。检测此类损坏的一种方法是：根据原始数据生成一个编码值，将该值发送给接收方，然后在目的地对接收到的数据进行同样的编码，以确认生成的值是否相同。
接收方校验后会出现以下几种可能：
最大限度减少漏报的方法是选择那些输入变动会导致输出发生剧烈变化的编码算法，特别是具有可变性的算法。
校验值被称为 校验和 (checksum)，因为它们用于 校验 (check) 数据的一致性，且最初的编码算法是基于加法（即 求和 (sum)）的。
循环冗余校验码 (Cyclic Redundancy Codes) 是一种一致性检查，它将消息数据视为模2多项式除法中的（长）被除数。模2算术在组合数字时不使用进位/借位。特定的 CRC 定义了一次处理的固定位数，该位数同时也是作为除数的固定多项式（具有模2系数）的次数。
由于模算术中不存在顺序概念，通过观察被除数最高次项系数是否为1，来决定当前被除数高位部分与试商积（除数与试商系数的乘积）的对比。根据定义，除数的最高次项系数必须为1，因为这是唯一非零的选择。除法完成后的余数被用作 CRC 校验和的基础。
对于模2多项式除数的给定次数 x，余数将最多有 x 项（从 x - 1 次方降至常数项）。系数为模2，意味着它们可以用 0 和 1 表示。因此，余数可以用一个至少 x 位 宽度 (width) 的无符号整数来建模。
除数必须包含其 x 次项且该项系数为 1，这意味着它是已知的，可以在表示时隐含而无需显式包含。其较低的 x 项必须明确指定，因此除数可以像余数一样进行建模。在这种建模方式下，除数的表示可以说是截断的，因为最高项的值是隐含的且未被存储。
余数和 （截断的）除数多项式 存储为基本的计算机整数。这与被除数不同，被除数是根据输入数据流建模的，其中每个新输入的位都是被除数多项式的下一个低次项。长除法可以分片处理，根据需要读取新的高位项。这对应于一次读取一个字节（或位），即时生成更新后的余数，而无需一次性读取（和/或存储！）整个消息数据。
长除法涉及在前面的项被处理为（中间）余数后，附加新的被除数项。因此，余数是每个除法步骤中唯一需要改变的部分；一个新的输入字节（或位）与余数结合形成中间被除数，然后与部分积（基于除数和最高位被除数位）结合，再次成为新的余数。
当除法过程中所有输入数据都已读取完毕时，最后 x 位仍留在中间余数中。它们尚未通过除法步骤；为了处理它们，必须向系统输入 x 个值为零的额外位。这确保了消息的所有数据位都得到处理。处理后的余数即为校验和。系统要求消息必须 扩充 (augmented) x 个额外位以获得结果。
或者，如果期望的结果是除法后的扩充位即为校验和，那么余数将通过与自身“减去”校验和，使最终余数为零。如果数据或校验和（或两者）中存在位错误，余数将不为零。此选项要求校验和首先从最高有效位开始馈入（即大端序）。
利用除法执行方式的特性，可以重新安排步骤，使得不需要后处理的零位；它们的效果被合并到过程的开始。这种系统读取 未扩充 (unaugmented) 的消息，并在此后直接从中间余数中导出校验和。（当然，这种方法不能使用“用校验和及零校验扩充消息”的技术。）
由于长除法是从最高次项向下进行的，因此最简单的方法是将传入的字节视为最高未处理项，并读取字节内的位（从最高位开始，以此类推）。然而，一些硬件实现读取每个字节时从最低位开始并向上递增会更容易。为了在软件中模拟这些系统，程序需要被标记为需要应用 输入反射 (input reflection)。反射一个内置整数会反转其位的顺序，使最低位和最高位交换状态，次低位和次高位交换，等等。输入反射可以通过在每个字节进入时进行反射，或者保持字节不变但反射其他内部功能来实现。后者听起来更难，但却是现实世界中通常的做法，因为它是一次性成本，而不像反射每个字节那样频繁。
同样，一些硬件以相反的顺序处理最终余数，这意味着模拟此类系统的软件需要标记为 输出反射 (output reflection) 处于生效状态。
有些 CRC 不直接返回余数（无论是否反射），而是增加一个补充输出位的额外步骤。补充操作将 1 变为 0，反之亦然。这可以通过使用一个所有位均为 1（与余数长度相同）的 XOR（异或）掩码来模拟。有些系统为了多样性，使用不是全 1 的 最终 XOR 掩码。（此掩码在任何输出反射 之后 执行。）
在另一端，当读取第一个字节时，内置整数寄存器通常从零开始。一些 CRC 系统不是简单地载入输入位进行 x 次步骤，而是使用非零的 初始余数 来增加额外的处理。由于可能与零值扩充位结合，同一个系统的扩充版本和未扩充版本的初始值必须不同。
Rocksoft™ 模型 CRC 算法（简称 RMCA）由 Ross Williams 设计，用于描述给定 CRC 系统的所有规范点（引用如下）：
RMCA 参数
这是算法的宽度，以位为单位。这比 Poly 的宽度小 1。
此参数即多项式 (poly)。这是一个应指定为十六进制数的二进制值。应省略多项式的最高位。例如，如果多项式为 10110，则应指定为 06。此参数的一个重要方面是它代表未反射的多项式；无论所建模的算法是否经过反射，此参数的最低位始终是除法过程中除数的 LSB（最低有效位）。
此参数指定算法开始时寄存器的初始值。这是在直接表算法中分配给寄存器的值。在表算法中，我们可以认为寄存器总是从零开始，并在第 N 次位迭代后将此值与寄存器进行 XOR 运算。此参数应指定为十六进制数。
这是一个布尔参数。如果为 FALSE，则处理输入字节时，第 7 位被视为最高有效位 (MSB)，第 0 位被视为最低有效位。如果此参数为 FALSE，则每个字节在处理前都会进行反射。
这是一个布尔参数。如果设置为 FALSE，则寄存器中的最终值直接馈入 XOROUT 阶段；否则，如果此参数为 TRUE，则最终寄存器值先进行反射。
这是一个 W 位的值，应指定为十六进制数。在值作为正式校验和返回之前，它与最终寄存器值（在 REFOUT 阶段之后）进行 XOR 运算。
他的描述假设字节为八位字节 (octet)。POLY 是（截断的）除数。INIT 是初始余数，前提是使用 CRC 处理的未扩充版本。（如果您使用的是扩充式 CRC，则必须在初始化之前撤销内置零扩充的影响。）
该库中的两个函数模板和两个类模板提供了执行 CRC 计算的方法。您可以将各种 Rocksoft™ 模型 CRC 算法参数作为模板参数和/或构造函数参数提供。然后，您可以一次性（对于函数）或分片（对于类对象）提交所有消息数据字节。
请注意，某些错误检测技术将校验和结果合并在消息数据内，而 CRC 校验和要么位于末尾（当进行扩充时，没有反射，位宽是字节大小的倍数，且没有 XOR 掩码），要么带外传输。
