CRC算法(转载)
2009-04-25 14:41阅读：
CRC算法
利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。
代数学的一般性算法
在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 1100101 表示为
1·x
6+1·x
5+0·x
4+0·x
3+1·x
2+0·x+1，即
x
6+x
5+x
2+1。
设编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k；生成多项式为G(x)，G(x)的最高幂次等于
r；CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x)。
发送方编码方法：将P(x)乘以xr(即对应的二进制码序列左移r位)，再除以G(x)，所得余式即为R(x)。用公式表示为
T(x)=x
rP(x)+R(x)
接收方解码方法：将T(x)除以G(x)，如果余数为0，则说明传输中无错误发生，否则说明传输有误。
举例来说，设信息码为1100，生成多项式为1011，即P(x)=x
3+x
2，G(x)=x
3+x+1，计算CRC的过程为
即 R(x)=x。注意到G(x)最高幂次r=3，得出CRC为010。
如果用竖式除法，计算过程为
因此，T(x)=(x
6+x
5)+(x)=x
6+x
5+x,
即 1100000+010=1100010
如果传输无误，
无余式。回头看一下上面的竖式除法，如果被除数是1100010，显然在商第三个1时，就能除尽。
上述推算过程，有助于我们理解CRC的概念。但直接编程来实现上面的算法，不仅繁琐，效率也不高。实际上在工程中不会直接这样去计算和验证CRC。
下表中列出了一些见于标准的CRC资料：
| 名称 |
生成多项式 |
简记式* |
应用举例 |
| CRC-4 |
x4+x+1 |
|
ITU G.704 |
| CRC-12 |
x12+x11+x3+x+1
|
|
|
| CRC-16 |
x16+x12+x2+1
|
1005 |
IBM SDLC |
| CRC-ITU** |
x16+x12+x5+1
|
1021 |
ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS |
| CRC-32 |
x32+x26+x23+...+x2+x+1
|
04C11DB7 |
ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS
|
| CRC-32c |
x32+x28+x27+...+x8+x6+1
|
1EDC6F41 |
SCTP |
*
生成多项式的最高幂次项系数是固定的1，故在简记式中，将最高的1统一去掉了，如04C11DB7实际上是104C11DB7。
** 前称CRC-CCITT。ITU的前身是CCITT。
注：为什么CRC-16的公式是x
16+x
12+x
2+1
，而其他资料里是
x16+x15+x2+1
（8005）。
CRC-16-IBM的生成多项式为 x^16 +x^15 + x^2 + 1，十六进制为 0x18005，但是很多算法都是简写成
0xA001（去掉左边的1，并且反转过来） ，这种写法主要用于计算CRC校验值。
=================================================================================
常用 CRC（按照 ITU-IEEE 规范）
名称
|
多项式
|
表示法：正常或者翻转
|
CRC-1
|
x + 1
(用途：硬件，也称为奇偶校验位)
|
0x1 or 0x1 (0x1)
|
CRC-5-CCITT
|
x5 + x3 + x + 1 (ITU
G.704 标准)
|
0x15 (0x??)
|
CRC-5-USB
|
x5 + x2 + 1 (用途：USB
信令包)
|
0x25 or 0x14 (0x9)
|
CRC-7
|
x7 + x3 + 1
(用途：通信系统)
|
0x09 or 0x48 (0x11)
|
CRC-8-ATM
|
x8 + x2 + x + 1
(用途：ATM HEC)
|
0x07 or 0xE0 (0xC1)
|
CRC-8-CCITT
|
x8 + x7 +
x3 + x2 + 1 (用途：1-Wire
总线)
|
|
CRC-8-Dallas/Maxim
|
x8 + x5 +
x4 + 1 (用途：1-Wire bus)
|
0x31 or 0x8C
|
CRC-8
|
x8 + x7 +
x6 + x4 + x2
+ 1
|
0xEA(0x??)
|
CRC-10
|
x10 + x9 + x5 + x4
+ x + 1
|
0x233 (0x????)
|
CRC-12
|
x12 + x11 +
x3 + x2 + x + 1
(用途：通信系统)
|
0x80F or 0xF01 (0xE03)
|
CRC-16-Fletcher
|
参见 Fletcher's checksum
|
用于 Adler-32 A & B CRC
|
CRC-16-CCITT
|
x16 + x12 +
x5 + 1 (X25, V.41, Bluetooth, PPP,
IrDA)
|
0x1021 or 0x8408 (0x0811)
|
CRC-16-IBM
|
x16
+x15 + x2 + 1
|
0x8005 or 0xA001 (0x4003)
|
CRC-16-BBS
|
x16 + x15 + x10 +
x3 (用途：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
|
x32 + x26 +
x23 + x22 +
x16 + x12 +
x11 + x10 +
x8 + x7 + x5
+ x4 + x2 + x +
1
|
0x04C11DB7 or 0xEDB88320 (0xDB710641)
|
CRC-32C (Castagnoli)
|
x32 + x28 +
x27 + x26 +
x25 + x23 +
x22 + x20 +
x19 + x18 +
x14 + x13 +
x11 + x10 +
x9 + x8 + x6
+ 1
|
0x1EDC6F41 or 0x82F63B78 (0x05EC76F1)
|
CRC-64-ISO
|
x64 + x4 +
x3 + x + 1
(use: ISO 3309)
|
0x000000000000001B or 0xD800000000000000
(0xB000000000000001)
|
CRC-64-ECMA-182
|
x64 + x62 +
x57 + x55 +
x54 + x53 +
x52 + x47 +
x46 + x45 +
x40 + x39 +
x38 + x37 +
x35 + x33 +
x32
+ x31 + x29 +
x27 + x24 +
x23 + x22 +
x21 + x19 +
x17 + x13 +
x12 + x10 +
x9 + x7 + x4
+ 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 取代
|
|
【来自】维基百科：
http://zh.wikipedia.org/zh-cn/%E5%BE%AA%E7%8E%AF%E5%86%97%E4%BD%99%E6%A0%A1%E9%AA%8C
