《CRC16三种算法及c实现》由会员分享，可在线阅读，更多相关《CRC16三种算法及c实现（5页珍藏版）》请在金锄头文库上搜索。
1、标准CRC生成多项式如下表:名称生成多项式CRC-4x4+ x+ 1CRC-8x8+x5+x4+1CRC* 8x8+ x2+ x1 +1简记式*标准引用3 ITU G.7040x310x07CRC-8x8+ x6+ x4+ x3+ x2+ x10x5ECRC-1 2x12+x11 + x3+x+180FCRC-1 6x16+x15+x2+18005 IBM SDLCCRC16-CCITT x16+x12+x5+ 11021 ISO HDLC, ITU X.25, V.34/V.41 /V.42,PPP- FCSCRC-32x32+x26+x23+ +x2+x+1 04C11DB7 ZIP, R
2、AR, I EEE 802 LAN/FDD I, IEEE1394, PPP-FCSCRC-32c x32+x28+x27+ +x8+x6+1 1EDC6F41 SCTP生成多项式的最高位固定的仁 故在简记式中忽略最高位1 T, $110x1021实际是0x11021oI、基本算法（人工笔算）：以CRC1 6-CCITT为例进行说明，CRC校验码为1 6位，生成多项式1 7位。假如数据流为4字节：BYTE3、BYTE2, BYTE 1 BYTE0；数据流左移16位，相当于扩大256x256倍，再除以生成多项式0x11021,做不借位的除法运算（相当于按位异或），所得的余数就是CRC校验码。发送
3、时的数据流为 6 字节:BYTE3、BYTE2, BYTE 1 . BYTE0、CRC 1 CRC0;注意：使用长除法进行计算式，需要将除数多项式与预置位0x0000或OxFFFF异或以后再进行计算。II、计算机算法1 （比特型算法）：1）将扩大后的数据流（6字节）高16位（BYTE3、BYTE2）放入一个长度为16的寄存器;2）如果寄存器的首位为1,将寄存器左移1位（寄存器的最低位从下一个字节获得），再与生成多项式的简 记式异或；否则仅将寄存器左移1位（寄存器的最低位从下一个字节获得）；3）重复第2步，直到数据流（6字节）全部移入寄存器；4）寄存器中的值则为CRC校验码CRC 1 、CRC0
4、。III、计算机算法2 (字节型算法):256A n表示256的n次方把按字节排列的数据流表示成数学多项式，设数据流为BYTEnBYTEn-1BYTEn-2,.BYTE1BYTE0,表示成数学表达式为 BYTEnx256A n+BYTEn-1 x 256A (n-1)+ .+ BYTE1*256+BYTE0,在这里+表示为异或运算。设生成多项式为G1 7 (17bit) , CRC码为CRC16o则，CRC16 =(BYTEnx256A n + BYTEn- 1x256A (n-1)+.+BYTE 1 x 256+BYTEO) x 256A 2/G17,即数据流左移1 6位，再除以生成多项式G
5、1 7。先变换BYTE n1 、BYTEn-1 扩大后的形式，CRC16 =BYTEnx256A nx256A 2/G17+BYTE n-小256人(n-1)x256A 2/G1 7+.+BYTE 1 x 256x 256A 2/G1 7+ BYTEO x 256A 2/G1 7(Zn + Y n/G17)x256A n+BYTE“256人(n-1)x256A 2/G1 7+.+BYTE 1 x 256x 256A 2/G17+BYTE0x256A 2/G17Znx256A n + Yn x 256/G1 7+ BYTEn-1 x 256A 2/G17 x 256A (n-1)+.+BYTE
6、1 x 256x 2 56A 2/G1 7+ BYTEO x 256A 2/G17Znx256A n + (YH8 n x 256+YHL n) x 256/G1 7+BYTE n-1 x 256A 2/G17 x 256A (n-1)+.+ BYTE1x256x256A 2/G1 7+BYTEO x 256A 2/G17Zn 256人 n + YHLn x 256/G1 7+ (YH8n + BYTE n 1)x256A 2/G17 x 256A (n -1)+.+BYTE1x256x256A 2/G1 7+BYTEO x 256A 2/G17这样就推导出，BYTEn-1字节的CRC校验码为
7、 YHLn x 256/G1 7+(YH8n + BYTEn-1)x 256A 2/G1 7,即上一字节 CRC 校验码 Yn的高 8 位(YH8n)与本字节BYTEn-1异或，该结果单独计算CRC校验码(即单字节的1 6位CRC校验码，对单字节可建立表格，预先生成对应的1 6位CRC校验码）,所得的CRC校验码与上一字节CRC校验码Yn的低8位（YL8n） 乘以256 （即左移8位）异或。然后依次逐个字节求出CRC,直到BYTE0o字节型算法的一般描述为：本字节的CRC码，等于上一字节CRC码的低8位左移8位，与上一字节 CRC右移8位同本字节异或后所得的CRC码异或。字节型算法如下：1）C
8、RC寄存器组初始化为全”O（OxOOOO）。（注嵐CRC寄存器组初始化全为1时，最后CRC应取 反。）2）CRC寄存器组向左移8位，并保存到CRC寄存器组。3）原CRC寄存器组高8位（右移8位）与数据字节进行异或运算，得出一个指向值表的索引。4）索引所指的表值与CRC寄存器组做杲或运算。5）数据指针加1,如果数据没冇全部处理完，则重复步骤2）。6）得出CRCoCRC CCITT1, “1”的意思是CRC的初值为OXffff。方法仁 将存右数据的字节数组进行逐位计算，求得字节形式的CRCtypedef unsigned _inti6 INT16U;#define CRC_SEED OxFFFF
9、/该位称为预置值，使用人工算法(长除法)时需要将除数多项式先与该与职位异或，才能得到域后的除数多项式# define POLY16 0x1021 /该位为简式书写实际为0X11021INT16U crc1 6(unsigned char * but,unsigned short length)INT16U shift,data,val;inti;shift = CRC_SEED;for(i= 0;ilength;i+ +) if(i % 8) = 0)data = (*buf+ + )8;val = shift A data;shift = shift 1;data = data 1;if(v
10、al&0x8000)shift = shift A P0LY16;return shift;2、査表法static unsigned short ccitt_table256 = 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7, 0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, OxDIAD, OxEICE, 0xF1 EF, 0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6, 0x9339, 0x8318, 0
11、xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE, 0x2462, 0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485, 0xA56A, 0xB54B, 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D, 0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695, 0x46B4, 0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7B
12、C, 0x48C4, 0x58E5, 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823, 0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969, 0xA90A, 0xB92B, 0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12, OxDBFD, OxCBDC, OxFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1 A, 0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22,
13、0x3C03, 0x0C60, 0x1C41, OxEDAE, 0xFD8F, OxCDEC, OxDDCD, 0xAD2A, OxBDOB, 0x8D68, 0x9D49, 0x7E97, 0x6EB6, 0x5ED5, Ox4EF4, 0x3E13, 0x2E32, 0x1 E51, 0x0E70, 0xFF9F, OxEFBE, OxDFDD, OxCFFC, OxBFIB, 0xAF3A, 0x9F59, 0x8F78, 0x9188, 0x81 A9, OxBICA, 0xA1 EB, OxDIOC, 0xC12D, OxF14E, 0xE16F, 0x1080, 0x00A1, 0
14、x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067, 0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E, 0x02B1, 0x1290, 0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256, 0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D, 0x34E2, 0x2403, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x440
15、5, 0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C, 0x26D3, 0x36F2, 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615,0x5634, 0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9, 0xB98A, 0xA9AB, 0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3, 0xCB7D, 0xDB5C, 0xEB3F, OxFBIE, 0x8BF9, 0x9BD8, OxABBB, 0xBB9A, 0x4A75, 0x5A54, 0x6A37, 0x7A16, OxOAFI, 0x1 ADO, 0x2AB3, 0x3A9
