Felix

技术源于积累,成功始于执着!

16bit CRC校检原理与C源码

0
阅读(69) 评论(0)

CRC(Cyclic Redundancy Check)循环冗余校验是常用的数据校验方法。先说说什么是数据校验。数据在传输过程(比如通过网线在两台计算机间传文件)中,由于传输信道的原因,可能会有误码现象(比如说发送数字5但接收方收到的却是6),如何发现误码呢?方法是发送额外的数据让接收方校验是否正确,这就是数据校验。最容易想到的校验方法是和校验,就是将传送的数据(按字节方式)加起来计算出数据的总和,并将总和传给接收方,接收方收到数据后也计算总和,并与收到的总和比较看是否相同。如果传输中出现误码,那么总和一般不会相同,从而知道有误码产生,可以让发送方再发送一遍数据。

CRC校验也是添加额外数据做为校验码,这就是CRC校验码,那么CRC校验码是如何得到的呢?非常简单,CRC校验码就是将数据除以某个固定的数(比如ANSI-CRC16中,这个数是0x18005),所得到的余数就是CRC校验码。

那这里就有一个问题,我们传送的是一串字节数据,而不是一个数据,怎么将一串数字变成一个数据呢?这也很简单,比如说2个字节B1,B2,那么对应的数就是(B1<<8)+B2;如果是3个字节B1,B2,B3,那么对应的数就是((B1<<16)+(B2<<8)+B3),比如数字是0x01,0x02,0x03,那么对应的数字就是0x10203;依次类推。如果字节数很多,那么对应的数就非常非常大,不过幸好CRC只需要得到余数,而不需要得到商

从上面介绍的原理我们可以大致知道CRC校验的准确率,在CRC8中出现了误码但没发现的概率是1/256,CRC16的概率是1/65536,而CRC32的概率则是1/2^32,那已经是非常小了,所以一般在数据不多的情况下用CRC16校验就可以了,而在整个文件的校验中一般用CRC32校验。

这里还有个问题,如果被除数比除数小,那么余数就是被除数本身,比如说只要传一个字节,那么它的CRC就是它自己,为避免这种情况,在做除法之前先将它移位,使它大于除数,那么移多少位呢?这就与所选的固定除数有关了,左移位数比除数的位数少1,下面是常用标准中的除数:

  • CRC8:多项式是X8+X5+X4+1,对应的数字是0x131,左移8位

  • CRC12:多项式是X12+X11+X3+X2+1,对应的数字是0x180D,左移12位

  • CCITT CRC16:多项式是X16+X12+X5+1,对应的数字是0x11021,左移16位

  • ANSI CRC16:多项式是X16+X15+X2+1,对应的数字是0x18005,左移16位

  • CRC32:多项式是X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1,对应数字是0x104C11DB7,左移32位。

因此,在得到字节串对应的数字后,再将数字左移M位(比如ANSI-CRC16是左移16位),就得到了被除数。

好了,现在被除数和除数都有了,那么就要开始做除法求CRC校验码了。CRC除法的计算过程与我们笔算除法类似,首先是被除数与除数高位对齐后,被除数减去除数,得到了差,除数再与差的最高位对齐,进行减法,然后再对齐再减,直到差比除数小,这个差就是余数。不过和普通减法有差别的是,CRC的加(减)法是不进(借)位的,比如10减01,它的结果是11,而不是借位减法得到的01,因此,实际上CRC的加法和减法所得的结果是一样的,比如10加01的结果是11,10减01的结果也是11,这其实就是异或操作。虽然说了这么多也不一定能说清楚,我们还是看一段CRC除法求余程序吧:

/* ************************* DECLARATIONS ************************ */
#include <stdio.h>
/* Start of Test Data */
static unsigned char gpcTestData0[] = { 0x00 };
static unsigned char gpcTestData1[] = { 0x01 };
static unsigned char gpcTestData2[] = { 0xFF, 0x00, 0x00, 0x00, 0x1E,
        0xF0, 0x1E, 0xC7, 0x4F, 0x82, 0x78, 0xC5, 0x82, 0xE0, 0x8C, 0x70,
        0xD2, 0x3C, 0x78, 0xE9, 0xFF, 0x00, 0x00, 0x01 };
static unsigned char gpcTestData3[] = { 0xFF, 0x00, 0x00, 0x02, 0xB9,
        0xDC, 0xF3, 0x72, 0xBB, 0xD4, 0xB8, 0x5A, 0xC8, 0x75, 0xC2, 0x7C,
        0x81, 0xF8, 0x05, 0xDF, 0xFF, 0x00, 0x00, 0x01 };
#define NUMBER_OF_TEST_DATA0_BYTES 1
#define NUMBER_OF_TEST_DATA1_BYTES 1
#define NUMBER_OF_TEST_DATA2_BYTES 24
#define NUMBER_OF_TEST_DATA3_BYTES 24
/* End of Test Data */
unsigned short CalculateCRC16( unsigned char *pcDataStream, unsigned short sNumberOfDataBytes );
/* ************************** MAIN ROUTINE ************************* */
void main( void )
{
    unsigned short sCRC16Result;
    sCRC16Result = CalculateCRC16( gpcTestData2,
    NUMBER_OF_TEST_DATA2_BYTES );
    printf( "Checksum CS[15:0] = 0x%04X\n", sCRC16Result );
}
/* ********** END OF MAIN ****** START OF CRC CALCULATION ********** */

/* CRC16 Polynomial, logically inverted 0x1021 for x^16+x^15+x^5+x^0 */
static unsigned short gsCRC16GenerationCode = 0x8408;
/*
sCRC16Result: the return of this function,
sByteCounter: address pointer to count the number of the
calculated data bytes
cBitCounter: counter for bit shift (0 to 7)
cCurrentData: byte size buffer to duplicate the calculated data
byte for a bit shift operation
*/
unsigned short CalculateCRC16( unsigned char *pcDataStream, unsigned short sNumberOfDataBytes )
{
    unsigned short sByteCounter;
    unsigned char cBitCounter;
    unsigned char cCurrentData;
    unsigned short sCRC16Result = 0xFFFF;
    if ( sNumberOfDataBytes > 0 )
    {
        for ( sByteCounter = 0; sByteCounter < sNumberOfDataBytes; sByteCounter++ )
        {
            cCurrentData = *( pcDataStream + sByteCounter );
            for ( cBitCounter = 0; cBitCounter < 8; cBitCounter++ )
            {
                if ( ( ( sCRC16Result & 0x0001 ) ^ ( ( 0x0001 * cCurrentData) & 0x0001 ) ) > 0 ) 
                    sCRC16Result = ( ( sCRC16Result >> 1 )  & 0x7FFF ) ^ gsCRC16GenerationCode;
                else
                    sCRC16Result = ( sCRC16Result >> 1 ) & 0x7FFF;
                cCurrentData = (cCurrentData >> 1 ) & 0x7F;
            }
        }
    }
    return sCRC16Result;
}
/* *************** END OF SUBROUTINE TO CALCULATE CRC ************** */


Outputs from the various input streams are as follows:

Data (gpcTestData0): 00

Checksum CS[15:0] = 0x0F87

Data (gpcTestData1): 01

Checksum CS[15:0] = 0x1E0E

Data (gpcTestData2): FF 00 00 00 1E F0 1E C7 4F 82 78 C5 82 E0 8C 70 D2 3C 78 E9 FF 00 00 01

Checksum CS[15:0] = 0xE569

Data (gpcTestData3): FF 00 00 02 B9 DC F3 72 BB D4 B8 5A C8 75 C2 7C 81 F8 05 DF FF 00 00 01

Checksum CS[15:0] = 0x00F0