CRC(Cyclic Redundancy Check)校验应用较为广泛，以前为了处理简单，在程序中大多数采用LRC(Longitudinal Redundancy Check)校验，LRC校验很好理解，编程实现简单。用了一天时间研究了CRC的C语言实现，理解和掌握了基本原理和C语言编程。结合自己的理解简单写下来。
1、CRC简介
CRC检验的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个检验码r位(就是CRC码)，附在信息后面，构成一个新的二进制码序列数共(k+r)位，最后发送出去。接收端根据同样的规则校验，以确定传送中是否出错。接收端有两种处理方式：1、计算k位序列的CRC码，与接收到的CRC比较，一致则接收正确。2、计算整个k+r位的CRC码，若为0，则接收正确。
CRC码有多种检验位数，8位、16位、32位等，原理相同。16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（即乘以2的16次方后），除以一个多项式，最后所得到的余数就是CRC码。
求CRC码所采用的是模2运算法则，即多项式除法中采用不带借位的减法运算，运算等同于异或运算。这一点要仔细理解，是编程的基础。
CRC-16: (美国二进制同步系统中采用) G(X) = X16 + X15 + X2 + 1
CRC-CCITT: (由欧洲CCITT推荐) G(X) = X16 + X12 + X5 + 1
CRC-32: G(X) = X32 + X26 + X23 + X22 + X16 +X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1
2、按位计算CRC
采用CRC-CCITT多项式，多项式为0x11021，C语言编程时，参与计算为0x1021，这个地方得深入思考才能体会其中的奥妙，分享一下我的思路：当按位计算CRC时，例如计算二进制序列为1001 1010 1010 1111时，将二进制序列数左移16位，即为1001 1010 1010 1111 (0000 0000 0000 0000)，实际上该二进制序列可拆分为1000 0000 0000 0000 (0000 0000 0000 0000) + 000 0000 0000 0000 (0000 0000 0000 0000) + 00 0000 0000 0000 (0000 0000 0000 0000) + 1 0000 0000 0000 (0000 0000 0000 0000) + ……
现在开始分析运算：
<1>对第一个二进制分序列求余数，竖式除法即为0x10000 ^ 0x11021运算，后面的0位保留；
<2>接着对第二个二进制分序列求余数，将第一步运算的余数*2后再和第二个二进制分序列一起对0x11021求余，这一步理解应该没什么问题。如果该分序列为0，无需计算。
<3>对其余的二进制序列求余与上面两步相同。
<4>计算到最后一位时即为整个二进制序列的余数，即为CRC校验码。
该计算方法相当于对每一位计算，运算过程很容易理解，所占内存少，缺点是一位一位计算比较耗时。
下面给出C语言实现方法：
while( len-- ) {
for(i = 0x80; i != 0; i = i >> 1) {
temp = temp * 2;
if((temp & 0x10000) != 0)
temp = temp ^ 0x11021;
if((*ptr & i) != 0)
temp = temp ^ (0x10000 ^ 0x11021);
}
ptr++;
}
crc = temp;
printf("0x%x ",crc);
}
</div>
上面的程序根据运算分析而来，很容易理解。为了节约内存空间，我们对程序作进一步的简化。分析可知，当二进制序列中上一位计算的余数第15bit位为1时，即( 上一位计算的余数 & 0x8000) != 0，计算本位时，上一位余数 * 2后可对0x11021作求余运算,然后再加上本位计算所得余数。这个很好理解，也就是说，打个比方，把它看作简单的除法，计算上一位时的余数乘以2后，如果比较大可以当被除数，就再去除除数求余。有一点和普通除法不同的是，因为多项式除法中采用不带借位的减法运算，所以0x10000也可以被0x11021除，余数并非为0x10000,而是0x1021。这个自己动手算一下就知道了。余数之和也是不带进位的加法运算，即异或。最后还强调一点，因为二进制序列是左移16位后参与运算的，所以，一直算到序列的最后一位也是可以被除的，这点大家要明白。下面给出简化后的C语言实现。
while( len-- ) {
for(i = 0x80; i != 0; i = i >> 1) {
if((crc & 0x8000) != 0) {
crc = crc << 1;
crc = crc ^ 0x1021;
}
else {
crc = crc << 1;
}
if((*ptr & i) != 0) {
crc = crc ^ 0x1021;
}
}
ptr++;
}
printf("0x%x ",crc);
}
</div>
上面这段程序网上较为常见，但冇得详细的解释。通过我上面的详细分析，如果对此段程序理解还有困难，可以对比一下没简化之前的程序，细细品味一哈，还是比较容易理解的。要是还理解不了，还是从头再看下，我码这么多字容易吗。。。。。
按位计算CRC代码比较简单，所占内存少，但要一位一位去计算，下面再介绍一种按字节查表快速计算CRC的方法。
3、按字节计算CRC
有了上面按位计算的知识，理解这个就是小case了。还是举前面的例子：当字节计算CRC时，例如计算二进制序列为1001 1010 1010 1111时，即0x9a9f时，将二进制序列数左移16位，即为0x9a9f(0 0 0 0)，实际上该二进制序列可拆分为0x9a00(0 0 0 0) + 0x009f(0 0 0 0)，分析计算时和上面的步骤一样，唯一不同的是计算中上一步的余数CRC要乘以2的八次方参与下一步的运算，这个应该好理解撒。为了简化编程，将计算中的CRC拆成高八位和低八位的形式，高八位的值直接与本位值相加求余，低八位的值乘以2的八次方后作为余数和计算得的余数相加。为了提高计算速度，我们把8位二进制序列数的CRC全部计算出来，放在一个表中，采用查表法可大大提高计算速度。
表是怎么得到的呢？当然是计算出来的，下面的程序给出了多项式是0x11021的计算程序。
for(j = 0; j < 256; j++) {
crc = 0;
for(i = 0x80; i != 0; i = i >> 1) {
if((crc & 0x8000) != 0) {
crc = crc << 1;
crc = crc ^ 0x1021;
}
else {
crc = crc << 1;
}
if((j & i) != 0) {
crc = crc ^ 0x1021;
}
}
printf("0x");
if(crc < 0x10) {
printf("000");
&n