循环冗余校验（Cyclic Redundancy Check， CRC）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。
CRC算法参数模型解释
- NAME：参数模型名称。
- WIDTH：宽度，即CRC比特数。如CRC-8，生成的CRC为8位。
- POLY：多项式的简写，用16进制表示。例如：CRC-8即是0x07，计算时候加上省略最高位的"1"，即完整的多项式是0x107。
- INIT：CRC初始值，Init位数与WIDTH位数相同。
- REFIN：初始数据每个字节是否按位反转，true或false。 如true，数据是0111，反转以后为，1110。
- REFOUT：在计算结果数据，整个数据是否反转，true或false。
- XOROUT：计算结果与此参数异或后得到最终的CRC值。
通常如果只给了一个多项式，其他的没有说明则：INIT=0x00，REFIN=false，REFOUT=false，XOROUT=0x00。
常见CRC参数模型如下
| CRC算法名称 | 多项式公式 | 宽度 | 多项式(16进制) | 初始值(16进制) | 结果异或值(16进制) | 输入反转 | 输出反转 |
|---|---|---|---|---|---|---|---|
| CRC-4/ITU | x4 + x + 1 | 4 | 03 | 00 | 00 | true | true |
| CRC-5/EPC | x5 + x3 + 1 | 5 | 09 | 09 | 00 | false | false |
| CRC-5/ITU | x5 + x4 + x2 + 1 | 5 | 15 | 00 | 00 | true | true |
| CRC-5/USB | x5 + x2 + 1 | 5 | 05 | 1F | 1F | true | true |
| CRC-6/ITU | x6 + x + 1 | 6 | 03 | 00 | 00 | true | true |
| CRC-7/MMC | x7 + x3 + 1 | 7 | 09 | 00 | 00 | false | false |
| CRC-8 | x8 + x2 + x + 1 | 8 | 07 | 00 | 00 | false | false |
| CRC-8/ITU | x8 + x2 + x + 1 | 8 | 07 | 00 | 55 | false | false |
| CRC-8/ROHC | x8 + x2 + x + 1 | 8 | 07 | FF | 00 | true | true |
| CRC-8/MAXIM | x8 + x5 + x4 + 1 | 8 | 31 | 00 | 00 | true | true |
| CRC-16/IBM | x16 + x15 + x2 + 1 | 16 | 8005 | 0000 | 0000 | true | true |
| CRC-16/MAXIM | x16 + x15 + x2 + 1 | 16 | 8005 | 0000 | FFFF | true | true |
| CRC-16/USB | x16 + x15 + x2 + 1 | 16 | 8005 | FFFF | FFFF | true | true |
| CRC-16/MODBUS | x16 + x15 + x2 + 1 | 16 | 8005 | FFFF | 0000 | true | true |
| CRC-16/CCITT | x16 + x12 + x5 + 1 | 16 | 1021 | 0000 | 0000 | true | true |
| CRC-16/CCITT-FALSE | x16 + x12 + x5 + 1 | 16 | 1021 | FFFF | 0000 | false | false |
| CRC-16/X25 | x16 + x12 + x5 + 1 | 16 | 1021 | FFFF | FFFF | true | true |
| CRC-16/XMODEM | x16 + x12 + x5 + 1 | 16 | 1021 | 0000 | 0000 | false | false |
| CRC-16/DNP | x16 + x13 + x12 + x11 + x10 + x8 + x6 + x5 + x2 + 1 | 16 | 3D65 | 0000 | FFFF | true | true |
| CRC-32 | x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 | 32 | 04C11DB7 | FFFFFFFF | FFFFFFFF | true | true |
| CRC-32/MPEG-2 | x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 | 32 | 04C11DB7 | FFFFFFFF | 00000000 | false | false |
计算步骤
- 将数据串第一个1与除数左对齐（数据串左边开始的0被舍弃）
- 按位进行异或操作
- 将数据串未处理的部分搬下来作为新数据串，重复操作
- 直到所有数据串都被处理过（余数位数小于除数位数，停止计算）
- 得到的结果即是CRC校验和（长度为除数-1）
计算实例
使用CRC-4/ITU 算法计算0x1d5。
根据上表可以知道参数如下
POLY = 0x03 = 0b0011
INIT = 0x00
WIDTH = 4
REFIN = true
REFOUT = true
XOROUT = 0x00
- 原始数据0x1d5=0000 0001 1101 0101，以字节为单位，不足高位补0
- 由于REFIN 为 true，需要对原始数据进行每个字节反转：0000 0001 1101 0101 -> 1000 0000 1010 1011
- INIT 为 0x00，已反转数据（高WIDTH位）和0进行异或运算，数据不变
- 已INIT反转数据，左移4（WIDTH）位，结果为1000 0000 1010 1011 0000
- 多项式为0x03 = 0b0011 -> 0b1 0011 （增加省略的高位1）
已左移INIT反转数据1000 0000 1010 1011 0000 与 多项式 1 0011 异或运算
10000000101010110000
⊕10011
00011000101010110000
//下面的异或⊕符号省略
11000101010110000
10011
01011101010110000
1011101010110000
10011
0010001010110000
10001010110000
10011
00010010110000
10010110000
10011
00001110000
1110000
10011
0111100
111100
10011
011010
11010
10011
01001
最后得到余数为1001，（ 如果余数不够4(WIDTH )位， 余数高位补0）
- 由于REFOUT 为 true，需要对整个数据反转，1001 -> 1001
- 由于XOROUT为0x00，与上一步结果异或为1001，即CRC校验和为1001