用程序实现CRC校验的原理

成都信息工程学院通信工程系 郑郁正（http://zyz.cuit.edu.cn）

以公开此文对我已故父亲表示深深的怀念。与父亲相处最后的时间里，想了很多，父亲的离去，让我学会感恩。尽我所能，将我的一切努力献给你们，感谢所有我能帮助的人。

我们在网上很容易找到CRC的生成表，但我们之中的一部分人并不知道此表是如何计算出来的，本文给出了简单而完整的说明，供各位参考。

以CRC生成多项式：X16+X12+X5+1为例进行说明。

方式一是照硬件方式，按位生成

unsigned char ByteBit[8]={0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01}; { unsigned char *crcBuf = ptr; unsigned short i; crc = 0; for( i=0; i<237; i++ ) { //如果输入位是1，则最高位取反

if( crcBuf[i/8] & ByteBit[i%8] ){ crc ^= 0x8000; }

114125150

//如果最高位为1，则X和X位异或后左移形成X+X，X左环移后成X

if( crc & 0x8000 ) crc = ((crc^0x0810) << 1) | 0x0001; else crc <<= 1; } }

方式二是按字节运算，设原CRC为16位

D15

B7 D14

D13

B6 D12

D11

B5 D10

D9

B4 D8

D7

B3 D6

D5 B2 D4

D3 B1 D2

D1 B0 D0

参与运算的数据为8位

为了描述方便，表达式XY表示X异或Y 则每次每位的运算如下

D15 D14 D13 D12 D11 D10 D9 D8 D7

B7

D14 D13 D12 D11D15B7 D10 D9 D8 D7 D6

B6

D13 D12 D11D15B7 D10 D14 B6 D9 D8 D7 D6 D5

B5

D12 D11D15B7 D10 D14 B6 D9 D13 B5 D8 D7 D6 D5 D4D15B7

B4

D11D15B7 D10 D14 B6 D9 D13 B5 D8 D12 B4 D7 D6 D5 D4D15B7 D3 D14 B6

B3

D10 D14 B6 D9 D13 B5 D8 D12 B4 D7 D11D15B7 B3 D6 D5 D4D15B7 D3 D14 B6 D2 D13 B5

B2

D9 D13 B5 D8 D12 B4 D7 D11D15B7 B3 D6 D10 D14 B6 B2 D5 D4D15B7 D3 D14 B6 D2 D13 B5 D1 D12 B4

B1

D8 D12 B4 D7 D11D15B7 B3 D6 D10 D14 B6 B2 D5 D9 D13 B5 B1 D4D15B7 D3 D14 B6 D2 D13 B5 D1 D12 B4 D0 D11D15B7 B3

B0

D7 D11D15B7 B3 D6 D10 D14 B6 B2 D5 D9 D13 B5 B1 D4D15B7 D8 D12 B4 B0 D3 D14 B6 D2 D13 B5 D1 D12 B4 D0 D11D15B7 B3 D15B7 D10 D14 B6 B2

PDF 文件使用 \"pdfFactory Pro\" 试用版本创建 www.fineprint.com.cn

D6 D5 D4 D3 D2 D1 D0

D5 D4D15B7 D3 D2 D1 D0 D15B7

D4D15B7 D3 D14 B6 D2 D1 D0 D15B7 D14 B6

D3 D14 B6 D2 D13 B5 D1 D0 D15B7 D14 B6 D13 B5

D2 D13 B5 D1 D12 B4 D0 D15B7 D14 B6 D13 B5 D12 B4

D1 D12 B4 D0 D11D15B7 B3 D15B7 D14 B6 D13 B5 D12 B4 D11D15B7 B3

D0 D11D15B7 B3 D15B7 D10 D14 B6 B2 D14 B6 D13 B5 D12 B4 D11D15B7 B3 D10 D14 B6 B2

D15B7 D10 D14 B6 B2 D14 B6 D9 D13 B5 B1 D13 B5 D12 B4 D11D15B7 B3 D10 D14 B6 B2 D9 D13 B5 B1

D14 B6 D9 D13 B5 B1 D13 B5 D8 D12 B4 B0 D12 B4 D11D15B7 B3 D10 D14 B6 B2 D9 D13 B5 B1 D8 D12 B4 B0

为了看清变换的结果，对上表最后一列进行调整，见下表

D15 D14 D13 D12 D11 D10 D9 D8 D7 D6 D5 D4 D3 D2 D1 D0

B0

D7 D11D15B7 B3 D6 D10 D14 B6 B2 D5 D9 D13 B5 B1 D4D15B7 D8 D12 B4 B0 D3 D14 B6 D2 D13 B5 D1 D12 B4 D0 D11D15B7 B3 D15B7 D10 D14 B6 B2 D14 B6 D9 D13 B5 B1 D13 B5 D8 D12 B4 B0 D12 B4 D11D15B7 B3 D10 D14 B6 B2 D9 D13 B5 B1 D8 D12 B4 B0

B7 B6 B5 B4 B7 B6 B5 B4 B7 B6 B5 B4

B0-1

B3 B2 B1 B0 B7 B6 B5 B4 B3 B2 B1 B0

B7 B6 B5 B4 B3 B2 B1 B0

B0-2

D7 D6 D5 D4 D3 D2 D1 D0

D15 D14 D13 D12 D15 D14 D13 D12 D15 D14 D13 D12

B0-3

D11 D10 D9 D8 D15 D14 D13 D12 D11 D10 D9 D8

D15 D14 D13 D12 D11 D10 D9 D8

从上表可见，B0-1只输入数据B7~B0有关，而B0-3只与CRC前值的D15 ~D8 有关，相关数据只有8位，仔细比较B0-1和B0-3，发现两者完全相同，这样就可以生成一张256个16位无符号整数的静态码表CRCLlist，用下标即可直接查到表达式的值，快速完成CRC运算，设dataIn是输入数据，即可得：

CRC = CRClist[CRC>>8] ^ CRClist[ datain ] ^ (CRC<<8)

CRClist可用下面程序自动生成： for( i=0; i<256; i++ ) {

unsigned char high = (i >>4) & 0x0f; unsigned char low = i & 0x0f;

CRClist[ i ] = ( (high<<12) | (high<<5 ) | high ) ^ ( (low<<12) | i ) ^ (i<<5); }

PDF 文件使用 \"pdfFactory Pro\" 试用版本创建 www.fineprint.com.cn