《CCITTCRC-16计算原理与实现》由会员分享，可在线阅读，更多相关《CCITTCRC-16计算原理与实现（13页珍藏版）》请在金锄头文库上搜索。
1、CCITT CRC-16 计算原理与实现CRC 的全称为 Cyclic Redundancy Check，中文名称为循环冗余校验。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。实际上，除数据通信外，CRC 在其它很多领域也是大有用武之地的。例如我们读软盘上的文件，以及解压一个 ZIP 文件时，偶尔会碰到“Bad CRC”错误，由此它在数据存储方面的应用可略见一斑。 差错控制理论是在代数理论基础上建立起来的。这里我们着眼于介绍 CRC 的算法与实现，对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理，可以阅读有
2、关资料。 利用 CRC 进行检错的过程可简单描述为：在发送端根据要传送的 k 位二进制码序列，以一定的规则产生一个校验用的 r 位监督码(CRC 码)，附在原始信息后边，构成一个新的二进制码序列数共 k+r 位，然后发送出去。在接收端，根据信息码和 CRC 码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。 1 代数学的一般性算法 在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 1100101 表示为 1x6+1x5+0x4+0x3+1x2+0x+1，即 x6+x5+x2+1。 设编码前的原始信息多项式为 P(x)
3、，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)=xrP(x)+R(x) 接收方解码方法：将 T(x)除以 G(x)，如果余数为 0，则说明传输中无错误发生，否则说明传输有误。 举例来说，设信息码为 1100，生成多项式为 1011，即 P(x)=x3+x2，G(x)=x3+x+1，计算 CRC 的过程为 xrP(x) x3(x3+x2) x
4、6+x5 x - = - = - = (x3+x2+x) + - G(x) x3+x+1 x3+x+1 x3+x+1 即 R(x)=x。注意到 G(x)最高幂次 r=3，得出 CRC 为 010。 如果用竖式除法，计算过程为 1110 - 1011 /1100000 (1100 左移 3 位) 1011 - 1110 1011 - 1010 1011 - 0010 0000 - 010 因此，T(x)=(x6+x5)+(x)=x6+x5+x, 即 1100000+010=1100010 如果传输无误， T(x) x6+x5+x - = - = x3+x2+x, G(x) x3+x+1 无余式。
5、回头看一下上面的竖式除法，如果被除数是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,
6、 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。 4.CRC 算法的实现 - 要用程序实现 CRC 算法，考虑对第 2 节的长除法做一下变换，依然是 M = 11100110，G
7、 = 1011， 其系数 r 为 3。 11001100 - 1011 )11100110000 1011. -. 1010. 1011. -. 1110. 1011. -. 1010. 1011. - 100 1 110 0110000 011 101 0110000 101第一位为 1，移位且计算 1 010 110000 011 001 110000001第一位第二位均为 0，移位 2 次 00 111 0000111第一位为 1，移位且计算 1 110 000 011 101 000101 第一位为 1，移位且计算 1 010 00 011 001 00移位 2 次得 100 用 CR
8、C16-CCITT 的生成多项式 0x1021，其 C 代码(本文所有代码假定系统为 32位，且都在 VC6 上编译通过)如下： unsigned short do_crc(unsigned char *message, unsigned int len) int i, j; unsigned short crc_reg; crc_reg = (message0 (7 - i) 0x1021; else crc_reg = (crc_reg (7 - i); else for (j = 0; j 1) 0x8408; 14. else 15. crc_reg = 1; 16. current
9、= 1; 17. 18. 19. return crc_reg; 20. 该算法使用了两层循环，对消息逐位进行处理，这样效率是很低的。为了提高时间效率，通常的思想是以空间换时间。考虑到内循环只与当前的消息字节和crc_reg 的低字节有关，对该算法做以下等效转换： Java 代码 1. unsigned short do_crc(unsigned char *message, unsigned int len)2. 3. int i, j; 4. unsigned short crc_reg = 0; 5. unsigned char index; 6. unsigned short to_x
10、or; 7. 8. for (i = 0; i 1) 0x8408; 16. else 17. to_xor = 1; 18. 19. crc_reg = (crc_reg 8) to_xor; 20. 21. return crc_reg; 22. 现在内循环只与 index 相关了，可以事先以数组形式生成一个表crc16_ccitt_table，使得 to_xor = crc16_ccitt_tableindex，于是可以简化为： Java 代码 1. unsigned short do_crc(unsigned char *message, unsigned int len)2. 3.
11、unsigned short crc_reg = 0; 4. 5. while (len-) 6. crc_reg = (crc_reg 8) crc16_ccitt_table(crc_reg *message+) & 0xff; 7. 8. return crc_reg; 9. crc16_ccitt_table 通过以下代码生成： Java 代码 1. int main() 2. 3. unsigned char index = 0; 4. unsigned short to_xor; 5. int i; 6. 7. printf(unsigned short crc16_ccitt_t
12、able256 =n); 8. while (1) 9. 10. if (!(index % 8) 11. printf(n); 12. 13. to_xor = index; 14. for (i = 0; i 1) 0x8408; 18. else 19. to_xor = 1; 20. 21. printf(0x%04x, to_xor); 22. 23. if (index = 255) 24. 25. printf(n); 26. break; 27. 28. else 29. 30. printf(, ); 31. index+; 32. 33. 34. printf(;); 35. return 0; 36. nt
