循环冗余校验

维基百科，自由的百科全书

循环冗余校验（CRC）是一種根據網路數據封包或電腦檔案等数据產生少数固定位數的一种散列函数。用来检测或校验数据传输或者保存后可能出现的错误。生成的數字在传输或者储存之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。由于本函數易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干擾引起的错误，因此獲得廣泛應用。

[编辑] 简介

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

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

$(x^3 + x) + (x + 1) = x^3 + 2x + 1 \equiv x^3 + 1$

2会变成0，因为对系数的加法都会模2. 乘法也是类似的：

$(x^2 + x)(x + 1) = x^3 + 2x^2 + x \equiv x^3 + x$

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

$\frac{(x^3 + x^2 + x)}{(x+1)} = (x^2 + 1) - \frac{1}{(x+1)}$

也就是说，

(x 3 + x 2 + x) = (x 2 + 1)(x + 1) - 1

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

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

在上面的等式中， $x 2 + x + 1$ 表示了本来的信息位是111, $x + 1$ 是所谓的钥匙, 而余数 $1$ （也就是 $x 0$ ）就是CRC. key的最高次為1, 所以我們將原來的信息乘上 $x 1$ 來得到 $x 3 + x 2 + x$ ，也可視為原來的信息位補1個零成為1110。

一般来说，其形式为：

$M(x) \cdot x^{n} = Q(x) \cdot K(x) + R (x)$

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

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

“错误纠正编码”常常和CRCs紧密相关，其语序纠正在传输过程中所产生的错误。这些编码方式常常和数学原理紧密相关。

[编辑] 实现

[编辑] 变体

CRC 有几种不同的变体

shiftRegister 可以逆向使用，这样就需要检测最低位的值，每次向右移动一位。这就要求 polynomial 生成逆向的数据位结果。实际上这是最常用的一个变体。
可以先将数据最高位读到移位寄存器，也可以先读最低位。在通讯协议中，为了保留 CRC 的突发错误检测特性，通常按照物理层发送数据位的方式计算 CRC。
为了检查 CRC，需要在全部的码字上进行 CRC 计算，而不是仅仅计算消息的 CRC 并把它与 CRC 比较。如果结果是 0，那么就通过这项检查。这是因为码字 $M(x) \cdot x^{n} - R(x) = Q(x) \cdot K(x)$ 可以被 $K (x)$ 整除。
移位寄存器可以初始化成 1 而不是 0。同样，在用算法处理之前，消息的最初 $n$ 个数据位要取反。这是因为未经修改的 CRC 无法区分只有起始 0 的个数不同的两条消息。而经过这样的取反过程，CRC 就可以正确地分辨这些消息了。
CRC 在附加到消息数据流的时候可以进行取反。这样，CRC 的检查可以用直接的方法计算消息的 CRC、取反、然后与消息数据流中的 CRC 比较这个过程来完成，也可以通过计算全部的消息来完成。在后一种方法中，正确消息的结果不再是 0，而是 $\sum_{i=n}^{2n-1} x^{i}$ 除以 $K (x)$ 得到的结果。这个结果叫作核验多项式 $C (x)$ ，它的十六进制表示也叫作幻数。

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

 $C (x) = x 31 + x 30 + x 26 + x 25 + x 24 + x 18 + x 15 + x 14 + x 12 + x 11 + x 10 + x 8 + x 6 + x 5 + x 4 + x 3 + x + 1$ 。

[编辑] 错误检测能力

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

由于 CRC 的计算基于除法，任何多项式都无法检测出一组全为零的数据出现的错误或者前面丢失的零。但是，可以根据 CRC 的变体来解决这个问题。
所有只有一个数据位的错误都可以被至少有两个非零系数的任意多项式检测到。误码多项式是 $x k$ ，并且 $x k$ 只能被 $i \le k$ 的多项式 $x i$ 整除。
CRC 可以检测出所有间隔距离小于多项式阶次的双位错误，在这种情况下的误码多项式是

。

如上所述， $x k$ 不能被 CRC 多项式整除，它得到一个 $x i - k + 1$ 项。根据定义，满足多项式整除 $x i - k + 1$ 的 $i - k$ 最小值就是多项是的阶次。最高阶次的多项式是本原多项式，带有二进制系数的 $n$ 阶多项式

[编辑] 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（按照 ITU-IEEE 规范）

名称	多项式	表示法：正常或者翻转
CRC-1	$x + 1$ (用途：硬件，也称为奇偶校验位)	0x1 or 0x1 (0x1)
CRC-5-CCITT	$x 5 + x 3 + x + 1$ (ITU G.704 标准)	0x15 (0x??)
CRC-5-USB	$x 5 + x 2 + 1$ (用途：USB 信令包)	0x05 or 0x14 (0x9)
CRC-7	$x 7 + x 3 + 1$ (用途：通信系统)	0x09 or 0x48 (0x11)
CRC-8-ATM	$x 8 + x 2 + x + 1$ (用途：ATM HEC)	0x07 or 0xE0 (0xC1)
CRC-8-CCITT	$x 8 + x 7 + x 3 + x 2 + 1$ (用途：1-Wire 总线)
CRC-8-Dallas/Maxim	$x 8 + x 5 + x 4 + 1$ (用途：1-Wire bus)	0x31 or 0x8C
CRC-8	$x 8 + x 7 + x 6 + x 4 + x 2 + 1$	0xEA(0x??)
CRC-10	x¹⁰ + x⁹ + x⁵ + x⁴ + x + 1	0x233 (0x????)
CRC-12	$x 12 + x 11 + x 3 + x 2 + x + 1$ (用途：通信系统)	0x80F or 0xF01 (0xE03)
CRC-16-Fletcher	参见 Fletcher's checksum	用于 Adler-32 A & B CRC
CRC-16-CCITT	x¹⁶ + x¹² + x⁵ + 1 (X25, V.41, Bluetooth, PPP, IrDA)	0x1021 or 0x8408 (0x0811)
CRC-16-IBM	x¹⁶ +x¹⁵ + x² + 1	0x8005 or 0xA001 (0x4003)
CRC-16-BBS	x¹⁶ + x¹⁵ + x¹⁰ + x³ (用途：XMODEM 协议)	0x8408 (0x????)
CRC-32-Adler	See Adler-32	参见 Adler-32
CRC-32-MPEG2	See IEEE 802.3	参见 IEEE 802.3
CRC-32-IEEE 802.3	$x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1$	0x04C11DB7 or 0xEDB88320 (0xDB710641)
CRC-32C (Castagnoli)^[1]	$x 32 + x 28 + x 27 + x 26 + x 25 + x 23 + x 22 + x 20 + x 19 + x 18 + x 14 + x 13 + x 11 + x 10 + x 9 + x 8 + x 6 + 1$	0x1EDC6F41 or 0x82F63B78 (0x05EC76F1)
CRC-64-ISO	$x 64 + x 4 + x 3 + x + 1$ (use: ISO 3309)	0x000000000000001B or 0xD800000000000000 (0xB000000000000001)
CRC-64-ECMA-182	$x 64 + x 62 + x 57 + x 55 + x 54 + x 53 + x 52 + x 47 + x 46 + x 45 + x 40 + x 39 + x 38 + x 37 + x 35 + x 33 + x 32$ $+ x 31 + x 29 + x 27 + x 24 + x 23 + x 22 + x 21 + x 19 + x 17 + x 13 + x 12 + x 10 + x 9 + x 7 + x 4 + x + 1$ (as described in ECMA-182 p.63)	0x42F0E1EBA9EA3693 or 0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)
CRC-128	IEEE-ITU 标准。被 MD5 & SHA-1 取代
CRC-160	IEEE-ITU 标准。被 MD5 & SHA-1 取代

[编辑] CRC 与数据完整性

尽管在错误检测中非常有用，CRC 并不能可靠地验证数据完整性（即数据没有发生任何变化），这是因为 CRC 多项式是线性结构，可以非常容易地故意改变数据而维持 CRC 不变，参见CRC and how to Reverse it中的证明。我们可以用 Message authentication code 验证数据完整性。

[编辑] CRC发生碰撞的情况

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

理论上来讲，CRC64 的碰撞概率大约是每 18×10¹⁸ 个 CRC 码出现一次。
由于 CRC 的不分解多项式特性，所以经过合理设计的较少位数的 CRC 可能会与使用较多数据位但是设计很差的 CRC 的效率相媲美。在这种情况下 CRC-32 几乎同 CRC-40 一样优秀。

[编辑] 设计 CRC 多项式

生成多项式的选择是 CRC 算法实现中最重要的部分，所选择的多项式必须有最大的错误检测能力，同时保证总体的碰撞概率最小。多项式最重要的属性是它的长度，也就是最高非零系数的数值，因为它直接影响着计算的校验和的长度。

最常用的多项式长度有

9 位 (CRC-8)
17 位 (CRC-16)
33 位 (CRC-32)
65 位 (CRC-64)

在构建一个新的 CRC 多项式或者改进现有的 CRC 时，一个通用的数学原则是使用满足所有模运算不可分解多项式约束条件的多项式。

这种情况下的不可分解是指多项式除了 1 与它自身之外不能被任何其它的多项式整除。

生成多项式的特性可以从算法的定义中推导出来：

如果 CRC 有多于一个的非零系数，那么 CRC 能够检查出输入消息中的所有单数据位错误。
CRC 可以用于检测短于 2k 的输入消息中的所有双位错误，其中 k 是多项式的最长的不可分解部分的长度。
如果多项式可以被 x+1 整除，那么不存在可以被它整除的有奇数个非零系数的多项式。因此，它可以用来检测输入消息中的奇数个错误，就象奇偶校验函数那样。

[编辑] 参见

总的分类

纠错码
校验和算法列表
奇偶校验位

特殊技术参考

Adler-32
Fletcher's checksum

[编辑] 参考文献

^ 引用错误无效的<ref>标签；无文字提供于名为cast93的参照; $2

[编辑] 外部链接

Tutorial and C++ implementation of CRC
Cyclic redundancy check - a simple guide to what it means for your data, CD and DVD discs. http://www.softwarepatch.com/tips/cyclic-redundancy.html
The CRC Pitstop
Williams, R. (1993-09) A Painless Guide to CRC Error Detection Algorithms
Understanding Cyclic Redundancy Check
Black, R. (1994-02) Fast CRC32 in Software — Algorithm 4 is used in Linux and info-zip's zip and unzip.
Barr, M. (1999-11, 1999-12, 2000-01) checksums, CRCs, and their source code. Embedded Systems Programming
CRC32: Generating a checksum for a file, C++ implementation by Brian Friesen
Online Tool to compute common CRCs (8/16/32/64) from strings
Online CRC calculator
Online CRC Tool: Generator of synthesizable CRC functions
Online Char (ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, CRC, etc. hashing algorithms
CRC16 to CRC64 collision research
Reversing CRC – Theory and Practice.

這是與数学相關的小作品。你可以通过编辑或修订扩充其内容。

分类: 校验和算法

1个隐藏分类: 數學小作品

See also ebooksgratis.com: no banners, no cookies, totally FREE.