数据校验

数据在传输的过程中，会受到各种干扰的影响，如脉冲干扰，随机噪声干扰和人为干扰等，这会使数据产生差错。为了能够控制传输过程的差错，通信系统必须采用有效措施来控制差错的产生，并保证数据的完整性。如下所示的传输错误

Integer Addition Checksum（整数加法校验和）

Fletcher Checksum

Use two running one’s complement checksums

For fair comparison, each running sum is half width
- E.g., 16-bit Fletcher Checksum is two 8-bit running sums
- Initialize: A = 0; B = 0;
- For each byte in data word: A = A + Bytei; B = B + A;
  - One’s complement addition!
- Result is A concatenated with B (16-bit result)
Significant improvement comes from the running sum B
- B = ByteN-1 + 2ByteN-2 + 3ByteN-3 + …
- Makes checksum order-dependent (switched byte order detected)
  - Gives HD=3 until the B value rolls over
For example, 256*ByteN-256 does not affect B

Adler Checksum

旨在改进 Fletcher Checksum。Adler校验和使用素数作为模数

251 instead of 255 for Adler 16 (two 8-bit sums)
65521 instead of 65535 for Adler 32 (two 16-bit sums)

ATN Checksum (AN/466)

Algorithm:

Initialize C0, C1, C2 and C3 to zero
For each Data Word byte: C0 += Bytei; C1 += C0; C2 += C1; C3 += C2; (one’s complement addition, as with Fletcher checksum)
32-bit check sequence is a particular formula of C0…C3

CRC

循环冗余校验（Cyclic Redundancy Codes，CRC）试图通过增加算法的复杂性来改进校验和。与校验和一样，CRC 用于检查大块数据，而不是奇偶校验中使用的单字符检查。CRC在错误检查方面比使用校验和要有效得多。
循环冗余校验（Cyclic Redundancy Check，CRC）是数据通讯中很常用的一种校验方式。尤其是在嵌入式开发中，经常要用到 CRC 算法对各种数据进行校验。通常用法为在传输或者储存之前计算出来的数字（称为校验码）附加到原数据后面，然后接收方进行检验确定数据是否发生变化。
CRC 是数据流采用二进制除法（没有进位，使用来代替减法）相除所得到的余数，这个余数通常被称为 CRC校验码，简称 CRC 码 。其中被除数是需要计算校验和的信息数据流；除数是一个长度为的预定义的二进制数（用多项式的系数来表示）。在做除法之前，要在信息数据之后先加上 n 个 0。当 CRC 的校验值为 n 位长时，CRC 称为 n 位CRC，通常写为。
CRC 由 W. Wesley Peterson 于 1961 年发明。CRC 经常被叫做“校验和”，但是这样的说法严格来说并不是准确的，因为技术上来说，校验“和”是通过加法来计算的，而不是 CRC 这里的除法。

模 2 除法

CRC 算法中使用的除法为模 2 除法。模 2 除法与算术除法类似，但每一位除的结果不影响其它位，即不向上一位借位，所以实际上就是异或运算。模 2 除法:
假设被除数 X，除数 P，余数 R

被除数 X 除以 P，被除数首位为 1 时，商1；为 0 时，商 0 。这里与普通的算术除法不同！
所得余数去除首位(左移一位):
- R 第一位为 0，将其作为新的被除数，除以 0，此时其首位为 0，商即为 0
- R 第一位为 1，将其作为新的被除数，除以 P，此时其首位为 1，商即为 1
重复第 2 步直到 R 位数少于 P 位数

关于模 2 除法，有篇博文写的挺好：《模2除法(CRC校验码计算) 》。有兴趣的可以去看看！

原理

CRC 基于循环纠错码理论，是基于（即除以 2 的同余）的多项式环。简单的来说，就是所有系数都为 0 或 1 的多项式系数的集合，并且集合对于所有的代数操作都是封闭的。
在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。任意一个由二进制位串组成的代码都可以和一个系数仅为 ‘0’ 和 ‘1’ 取值的多项式一一对应。例如：代码 1010111 对应的多项式为 1 * x⁶ + 0 * x⁵ + 1 * x⁴ + 0 * x³ + 1 * x² + 1 * x¹ + 1 * x⁰，即： x⁶ + x⁴ + x² + x + 1。而多项式为 x⁵ + x³ + x² + x + 1 对应的代码 101111。

G(x)： 表示 CRC 的生成多项式，是接收方和发送方的一个约定，也就是一个二进制数，由 CRC 规范给定。在整个传输过程中，这个数始终保持不变。例如 CRC-16-CCITT 的生成多项式为 G(x) = x¹⁶ + x¹² + x⁵ + 1。生成多项式应满足以下条件：
- ***生成多项式的最高位和最低位必须为 1（因此，大多数生成多项式的简记式中将生成多项式的最高位省略）***。
- 当被传送信息（CRC码）任何一位发生错误时，被生成多项式做除后应该使余数不为 0。
- 不同位发生错误时，应该使余数不同。
- 对余数继续做除，应使余数循环。
C(x)： 表示发送的原始数据的多项式。例如 C(x) = x⁵ + x³ + x² + x + 1 表示发送的数据为 101111。
R(x)： 表示 CRC 码的多项式。R(x) = C(x) * (x << R) % G(x)
T(x)： 表示发送的原始数据加上 CRC 码之后的多项式。T(x) = C(x) * (x << R) + R(x)
K：发送数据的长度。其等于 C(x) 中的最高次的幂 + 1。如上例子的 C(x) 中，K = 5 + 1 = 6
R： CRC 码的长度。CRC校验码位数 = 生成多项式位数 – 1。注意：最高位被省略了！！！。例如上例子的 G(x) 中，R = 16。

位信息码后再拼接 R 位的校验码，整个编码长度为 N 位。因此，这种编码也叫 ( N，K ) 码。对于一个给定的 ( N，K ) 码，可以证明存在一个最高次幂为 N – K = R 的多项式 G(x)。根据 G(x) 可以生成 K 位信息的校验码，而 G(x) 叫做这个 CRC 码的生成多项式。基本就是下面这个样子：

（1）évariste Galois ，伽罗华（也译作伽瓦罗），法国数学家，群论的创立者。
（2）元素个数为 p 的有限域一般记为 GF( p )
（3）编码理论： 研究信息传输过程中信编码规律的数学理论。编码理论与信息论、数理统计、概率论、随机过程、线性代数、近世代数、数论、有限几何和组合分析等学科有密切关系，已成为应用数学的一个分支。编码是指为了达到某种目的而对信进行的一种变换。其逆变换称为译码或解码。—— 陈鲁生，沈世镒编．编码理论基础：高等教育出版，2010-07-31

生成多项式

CRC 算法原理很简单，但是在实际使用中要面临很多问题：

位顺序： 某些方案将每个字节的低位视为“第一”位，这与我们对“低阶”的习惯理解相反。当串行端口传输在硬件中进行 CRC 校验时，这种约定是有意义的，因为一些广泛的串行端口传输约定首先传输字节最低有效位。CRC算法不只有软件实现，还有硬件实现！例如，在英特尔处理器的Nehalem微体系结构中引入了CRC-32的实现。
字节顺序： 对于多字节 CRC，可能会混淆首先发送的字节（或存储在最低寻址的存储器字节中）是最低有效字节（LSB）还是最高有效字节（MSB）。例如，一些 16 位 CRC 方案交换校验值的字节。
高阶位的遗漏除数多项式的： 由于高序位始终为 1，并且由于一个位 CRC 必须由（被定义 + 1）位其中除数溢出的位寄存器，大多数 CRC 认为没有必要提到除数的高位，因此给出的 CRC 多项式通常省略高位的 1
省略除数多项式的低阶位： 由于低阶位始终为 1，因此像 Philip Koopman 这样的多项式，其高位完整，但没有低位（x ⁰ 或 1）。
某些专有协议中的 CRC 可能会通过使用特定的值和 CRC 结果进行 XOR 处理

因此，在 CRC 标准中，有许多种 CRC 算法！
CRC 的规范要求定义所谓的生成多项式。该多项式成为多项式长除数中的除数，该除数将消息作为被除数，并且其中商被丢弃而余数成为结果。多项式系数是根据有限域的算法计算的，因此加法运算总是可以按位并行执行（数字之间没有进位）。实际上，所有常用的 CRC 都使用两个元素的伽罗瓦域 。这两个元素通常称为 0 和 1，非常适合计算机体系结构。
RC 的校验值为 n 位长时，CRC 称为 n 位CRC，通常写为。对于给定的 n，也可能有多种 CRC ，因为每个 CRC 具有不同的多项式。这样的多项式具有最高阶数 n，这意味着它具有 n + 1 项。换句话说，多项式的长度为 n + 1 ; 其编码需要 n + 1位。下面给出了常用的 CRC 生成多项式：

声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！

常用算法 之五 数据校验（CRC 原理、LRC、奇偶校验、校验和）详解