引言
CRC循环冗余校验方式是通信领域中最为常用的校验方式。正好最近手上有个项目需要对传输数据进行循环冗余的校验，就借着这个机会，系统的整理一下循环冗余校验的知识。
2 数据校验
当数据在通信信道传输时，并不能保证终端接收的数据与发送端数据完全一致。常见的数据通信问题有：
（1）数据丢失：数据长度发送改变，丢失一位或者多位数据。
（2）数据位改变：受传输过程外界因素干扰，导致数据位值发生改变。
那么当接收端接收到数据后就需要对收到的数据进行校验，以保证数据的完整性和正确性。
3 奇偶校验
3.1 原理
为了解决数据传输过程中可能存在数据错误的问题，有人提出了一种比较简单的方式——奇偶校验法。奇偶校验主要原理如下：
在原始数据流的头部或者末尾添加一位bit，此bit用于校验此数据包的正确与否。例如：
| 原始码 | 奇校验(奇数个1) | 偶校验(偶数个1) |
|---|---|---|
| 1011000 | 10110000 | 10110001 |
| 1010000 | 10100001 | 10100000 |
3.2 优缺点
奇偶校验法优点：
（1）原理简单，实现方便。
奇偶校验法缺点：
（1）奇偶校验的检错率只有50%，因为只有奇数个数据位发生变化能检测到，如果偶数个数据位发生变化，奇偶校验方式不能检测出错误。
（2）奇偶校验每传输一个字节都需要加一位校验位，对传输效率影响很大。
（3）奇偶校验只能发现错误，但不能纠正错误，也就是说它只能告诉你出错了，但不能告诉你怎么出错了，一旦发现错误，只好重发。
4 循环冗余校验
4.1 生成多项式
生成多项式将一个任意的二进制数转换为多项式形式得到的一个特征多项式：
例如：二进制数 101011 ，对应的生成多项式为 ：
X6 + X4+X2 + X + 1。
二进制数101111，对应的生成多项式为：
X5+X3+X2+X+1。
4.2 模2运算
模2运算是一种二进制算法。与四则运算相同，模2运算也包括模2加、模2减、模2乘、模2除四种二进制运算。而且，模2运算也使用与四则运算相同的运算符，即“+”表示模2加，“－”表示模2减，“×”或“·”表示模2乘，“÷”或“/”表示模2除。
模2加减法运算其实就是异或运算，运算规则如下：
0 ± 0 = 0
1 ± 1 = 0
0 ± 1 = 1
1 ± 0 = 1
例如：1101 ± 1001 = 0100
计算过程如下:
1 1 0 1
± 1 0 0 1
-----------
0 1 0 0模2除法运算过程：
规则 : 设被除数为X，除数为P，余数为R。
（1）被除数X除以P(对X和P做模2加减法)，被除数首位为1时，商为1。当被除数首位为0时，商为0。
（2）所得余数去除首位(左移一位)。
R第一位为0，将其作为新的被除数，除以P，此时其首位为0，商即为0。
R第一位为1，将其作为新的被除数，除以P，此时其首位为1，商即为1。
（3）重复第2步直到R位数少于P位数。
例如：被除数为X = 1111000，除数P = 1101。运算过程如下：
1 0 1 1 //商
---------------
1 1 1 1 0 0 0 //被除数，注意首位为1
1 1 0 1 //被除数首位为1，除以除数
---------------
0 1 0 0 0 0 //余数去除首位，作为新的被除数
0 0 0 0 //被除数首位为0，除以0
---------------
1 0 0 0 0 //余数去除首位，作为新的被除数
1 1 0 1 //被除数首位为1，除以除数
---------------
1 0 1 0 //余数去除首位，作为新的被除数
1 1 0 1 //被除数首位为1，除以除数
---------------
0 1 1 1 //余数，此时余数位数少于除数，不能继续除了(忽略首位0)
--------------------- 详细过程
第1步：
1 //商
-------------
1 1 1 1 0 0 0 //被除数,注意首位为1
1 1 0 1 //除数
-------------
0 0 1 0 0 0 0 //余数,模2运算后结果第2步：余数去除首位(左移一位),当第一位为0时,除以0;为1时,除以除数。
1 0 //商
---------------
0 1 0 0 0 0 //余数去除首位,作为新的被除数
0 0 0 0 //被除数首位为0,除以0
---------------
0 1 0 0 0 0 //余数,模2运算后结果
--------------------- 第3步：
1 0 1 //商
----------------
1 0 0 0 0 //余数去除首位,作为新的被除数
1 1 0 1 //被除数首位为1,除以除数
----------------
0 1 0 1 0 //余数,模2运算后结果
--------------------- 第4步：
1 0 1 1 //商
----------------
1 0 1 0 //余数去除首位,作为新的被除数
1 1 0 1 //被除数首位为1,除以除数
----------------
0 1 1 1 //余数,此时余数位数少于除数,不能继续除了
--------------------- 得到最终结果：商为1011，余数为111。
4.3 CRC校验码
经过上述一系列基础知识的准备，终于到了CRC循环冗余校验部分。
CRC校验码求解过程：
（1）根据CRC校验标准选取适当生成多项式，并根据多项式计算出除数P。CRC生成特征多项式的标准有：
CRC-4 = X4 + X+ 1
CRC-8 = X8+X7+X6+X4+X2+1
CRC-12 = X12+X11+X3+X2+1
CRC-16 = X16+X15+X2+1
CRC-32 = X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1
（2）计算除数P的位数，若除数P共有n位，则需在原码后补充n-1位0，并将添加后的结果作为被除数X。
原因：因为余数的位数一定比除数少1位，也就是CRC校验码只比除数少1位。
（3）将除数X与被除数P按照模2除法进行运算，计算出余数R，得到R即为CRC校验码。
（4）将CRC校验码添加至原码末尾，构成新的数据帧进行发送。
实例：
第1步：
若数据传输过程中需要发送15位的二进制原码为S = 101001110100001。
第2步：
选择的CRC-8生成多项式为X8 + X7 + X6 + X4+ X2 + 1，则根据特征多项式得到的除数P = 111010101（共9位）。
第3步：
在源码S末尾添加8（9-1）位0，构成被除数X = 10100111010000100000000。
第4步：
将除数X与被除数P进行模2除法运算。
计算过程：
1 1 1 0 0 0 1 1 0 1 1 1 1 0 0
----------------------------------------------------
1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0(商添1)
1 1 1 0 1 0 1 0 1
----------------------------------------------------
0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0(去除0,首位为1,商添1)
1 1 1 0 1 0 1 0 1
----------------------------------------------------
0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0(去除0,首位为1,商添1)
1 1 1 0 1 0 1 0 1
----------------------------------------------------
0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0(去除4个0商添3个0)
1 1 1 0 1 0 1 0 1
----------------------------------------------------
0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0(去除0,首位为1,商添1)
1 1 1 0 1 0 1 0 1
----------------------------------------------------
0 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0(去除0,首位为0,商添0)
1 1 1 0 1 0 1 0 1
----------------------------------------------------
0 1 0 1 0 0 0 0 1 0 0 0 0 0(去除0,首位为1,商添1)
1 1 1 0 1 0 1 0 1
----------------------------------------------------
0 1 0 0 1 0 1 1 1 0 0 0 0(去除0,首位为1,商添1)
1 1 1 0 1 0 1 0 1
----------------------------------------------------
0 1 1 1 1 1 0 1 1 0 0 0(去除0,首位为1,商添1)
1 1 1 0 1 0 1 0 1
----------------------------------------------------
0 0 0 1 0 0 0 1 1 0 0(去除3个0,剩余8位,计算结束)通过上述计算得到CRC校验码R = 10001100。
将CRC校验码添加至原码S末尾得到发送的数据帧为：
10100111010000110001100（共23位）
5 结语
CRC校验码是基于数据计算一组效验码，是数据通信领域中最常用的一种查错校验码。希望读者通过本文的讲解可以深入理解CRC的校验过程。
6 CRC-16校验代码
public static int getCRC(byte[] bytes) {
int CRC = 0x0000ffff;
int POLYNOMIAL = 0x0000a001;
int i, j;
for (i = 0; i < bytes.length; i++) {
CRC ^= ((int) bytes[i] & 0x000000ff);
for (j = 0; j < 8; j++) {
if ((CRC & 0x00000001) != 0) {
CRC >>= 1;
CRC ^= POLYNOMIAL;
} else {
CRC >>= 1;
}
}
}
return (CRC);
}
