1、16 位 CRC 校验原理与算法分析这里，不讨论 CRC 的纠错原理以及为什么要选下面提及的生成多项式，只是针对以下的生成多项式，如何获得 CRC 校验码，作一个比较详细的说明。标准 CRC 生成多项式如下表：名称 生成多项式 简记式* 标准引用CRC-4 x4+x+1 3 ITU G.704CRC-8 x8+x5+x4+1 0x31 CRC-8 x8+x2+x1+1 0x07 CRC-8 x8+x6+x4+x3+x2+x1 0x5ECRC-12 x12+x11+x3+x+1 80FCRC-16 x16+x15+x2+1 8005 IBM SDLCCRC16-CCITT x16+x12+x5+
2、1 1021 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCSCRC-32 x32+x26+x23+.+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCSCRC-32c x32+x28+x27+.+x8+x6+1 1EDC6F41 SCTP生成多项式的最高位固定的 1，故在简记式中忽略最高位 1 了，如 0x1021 实际是 0x11021。I、基本算法（人工笔算）：以 CRC16-CCITT 为例进行说明，CRC 校验码为 16 位，生成多项式 17 位。假如数据流为 4 字节：
3、BYTE3 、BYTE2、BYTE1、BYTE0；数据流左移 16 位，相当于扩大 256256 倍，再除以生成多项式 0x11021，做不借位的除法运算（相当于按位异或） ，所得的余数就是 CRC 校验码。发送时的数据流为 6 字节： BYTE3、BYTE2、BYTE1、BYTE0、CRC1、CRC0；II、计算机算法 1（比特型算法）：1)将扩大后的数据流（ 6 字节）高 16 位（BYTE3、BYTE2）放入一个长度为16 的寄存器；2)如果寄存器的首位为 1，将寄存器左移 1 位( 寄存器的最低位从下一个字节获得)，再与生成多项式的简记式异或；否则仅将寄存器左移 1 位( 寄存器的最低
4、位从下一个字节获得)；3)重复第 2 步，直到数据流（6 字节）全部移入寄存器；4)寄存器中的值则为 CRC 校验码 CRC1、CRC0。III、计算机算法 2（字节型算法）：256n 表示 256 的 n 次方把按字节排列的数据流表示成数学多项式，设数据流为 BYTEnBYTEn1BYTEn2、 、 、BYTE1BYTE0 ，表示成数学表达式为 BYTEn256n+BYTEn-1256(n-1)+.+BYTE1*256+BYTE0，在这里+表示为异或运算。设生成多项式为G17（ 17bit） ，CRC 码为 CRC16。则，CRC16 (BYTEn256n+BYTEn-1256(n-1)+.
5、+BYTE1256+BYTE0)2562/G17，即数据流左移 16 位，再除以生成多项式G17。先变换 BYTEn-1、BYTEn-1扩大后的形式，CRC16 BYTEn256n2562/G17+BYTEn-1256(n-1)2562/G17+.+BYTE12562562/G17+BYTE02562/G17(Zn+Yn/G17)256n+BYTEn-1256(n-1)2562/G17+.+BYTE12562562/G17+BYTE02562/G17Zn256n+Yn256/G17+BYTEn-12562/G17256(n-1)+.+BYTE12562562/G17+BYTE02562/G17
6、Zn256n+(YH8n256+YHLn)256/G17+BYTEn-12562/G17256(n-1)+.+BYTE12562562/G17+BYTE02562/G17Zn256n+YHLn256/G17+(YH8n+BYTEn-1)2562/G17256(n-1)+.+BYTE12562562/G17+BYTE02562/G17这样就推导出，BYTEn-1字节的 CRC 校验码为YHLn256/G17+(YH8n+BYTEn-1)2562/G17，即上一字节 CRC 校验码Yn的高 8 位（YH8n）与本字节 BYTEn-1异或，该结果单独计算 CRC 校验码（即单字节的 16 位 CRC
7、 校验码，对单字节可建立表格，预先生成对应的 16 位 CRC 校验码） ，所得的 CRC 校验码与上一字节CRC 校验码 Yn的低 8 位（YL8n）乘以 256（即左移 8 位）异或。然后依次逐个字节求出 CRC，直到 BYTE0。字节型算法的一般描述为：本字节的 CRC 码，等于上一字节 CRC 码的低8 位左移 8 位，与上一字节 CRC 右移 8 位同本字节异或后所得的 CRC 码异或。字节型算法如下：1)CRC 寄存器组初始化为全 “0“(0x0000)。 （注意：CRC 寄存器组初始化全为1 时，最后 CRC 应取反。 ）2)CRC 寄存器组向左移 8 位, 并保存到 CRC 寄
8、存器组。3)原 CRC 寄存器组高 8 位（右移 8 位）与数据字节进行异或运算，得出一个指向值表的索引。4)索引所指的表值与 CRC 寄存器组做异或运算。5)数据指针加 1，如果数据没有全部处理完，则重复步骤 2)。6)得出 CRC。unsigned short GetCrc_16(unsigned char * pData, int nLength)/函数功能：计算数据流* pData 的 16 位 CRC 校验码，数据流长度为nLengthunsigned short cRc_16 = 0x0000; / 初始化while(nLength0)cRc_16 = (cRc_16 8) *pD
9、ata) /cRctable_16 表由函数 mK_cRctable 生成nLength-;pData+;return cRc_16; void mK_cRctable(unsigned short gEnpoly)/函数功能：生成 0255 对应的 16CRC 校验码，其实就是计算机算法 1（比特型算法）/gEnpoly 为生成多项式/注意，低位先传送时，生成多项式应反转(低位与高位互换 )。如 CRC16-CCITT 为 0x1021，反转后为 0x8408unsigned short cRc_16=0;unsigned short i,j,k;for(i=0,k=0;i0;j-)if(cRc_16cRctable_16k = cRc_16;
