16-bit CRC check principle and algorithm analysis

Aguilera

16-bit CRC check principle and algorithm analysis [Copy link]

Here, we will not discuss the error correction principle of CRC and why we should choose the generating polynomial mentioned below. We will only give a more detailed explanation on how to obtain the CRC check code based on the following generating polynomial. The standard CRC generator polynomials are as follows: Name Generator Polynomial Abbreviation* Standard Reference CRC-4 x4+x+1 3 ITU G.704 CRC-8 x8+x5+x4+1 0x31 CRC-8 x8+x2+x1+1 0x07 CRC-8 x8+x6+x4+x3+x2+x1 0x5E CRC-12 x12+x11+x3+x+1 80F CRC-16 x16+x15+x2+1 8005 IBM SDLC CRC16-CCITT x16+x12+x5+1 1021 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS CRC-32 x32+x26+x23+...+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS CRC-32c x32+x28+x27+...+x8+x6+1 1EDC6F41 SCTP The highest bit of the generator polynomial is fixed to 1, so the highest bit 1 is ignored in the shorthand expression, such as 0x1021 is actually 0x11021. I. Basic algorithm (manual calculation): Take CRC16-CCITT as an example. The CRC checksum is 16 bits and the generator polynomial is 17 bits. If the data stream is 4 bytes: BYTE[3], BYTE[2], BYTE[1], BYTE[0]; Shift the data stream left by 16 bits, which is equivalent to expanding it by 256×256 times, and then divide it by the generator polynomial 0x11021, and perform a division operation without borrowing (equivalent to bitwise XOR). The remainder is the CRC checksum. The data stream when sending is 6 bytes: BYTE[3], BYTE[2], BYTE[1], BYTE[0], CRC[1], CRC[0]; II. Computer algorithm 1 (bit-type algorithm): 1) Put the high 16 bits (BYTE[3], BYTE[2]) of the expanded data stream (6 bytes) into a register with a length of 16; 2) If the first bit of the register is 1, shift the register left by 1 bit (the lowest bit of the register is obtained from the next byte), and then XOR it with the abbreviated form of the generating polynomial; otherwise, only shift the register left by 1 bit (the lowest bit of the register is obtained from the next byte); 3) Repeat step 2 until the data stream (6 bytes) is fully moved into the register; 4) The value in the register is the CRC check code CRC[1], CRC[0]. III. Computer Algorithm 2 (Byte Algorithm): 256^n represents 256 to the power of n. The byte-arranged data stream is represented as a mathematical polynomial. Let the data stream be BYTE[n]BYTE[n-1]BYTE[n-2], BYTE[1]BYTE[0], and the mathematical expression is BYTE[n]×256^n+BYTE[n-1]×256^(n-1) +...+BYTE[1]*256+BYTE[0], where + represents an exclusive-or operation. Let the generating polynomial be G17 (17 bits) and the CRC code be CRC16. Then, CRC16 = (BYTE[n]×256^n+BYTE[n-1]×256^(n-1)+...+BYTE[1]×256+BYTE[0])×256^2/G17, that is, the data stream is shifted left by 16 bits and then divided by the generating polynomial G17. First, convert BYTE[n-1] and BYTE[n-1] to the expanded form, CRC16 = BYTE[n]×256^n×256^2/G17+BYTE[n-1]×256^(n-1)×256^2/G17+...+BYTE[1]×256×256^2/G17+BYTE[0]×256^2/G17 =(Z[n]+Y[n]/G17)×256^n+BYTE[n-1]×256^(n-1)×256^2/G17+...+BYTE[1]×256×256^2/G17+BYTE[0]×256^2/G17 ＝Z[n]×256^n+{Y[n]×256/G17+BYTE[n-1]×256^2/G17}×256^(n-1)+...+BYTE[1]×256×256^2/G17+BYTE[0]×256^2/G17 ＝Z[n]×256^n+{(YH8[n]×256+YHL[n ])×256/G17+BYTE[n-1]×256^2/G17}×256^(n-1)+...+BYTE[1]×256×256^2/G17+BYTE[0]×256^2/G17 =Z[n]×256^n+{YHL[n]×256/G17+(YH8[n]+BYTE[n-1])×256^2/G17}×256^(n-1)+...+BYTE[1]×256×256^2/G17+BYTE[0]×256^2/G17 It can be deduced that the CRC check code of BYTE[n-1] byte is {YHL[n]×256/G17+(YH8[n]+BYTE[n-1])×256^2/G17}, that is, the high 8 bits (YH8[n]) of the CRC check code Y[n] of the previous byte are XORed with the current byte BYTE[n-1]. The result is used to calculate the CRC checksum separately (i.e., the 16-bit CRC checksum of a single byte. For a single byte, a table can be established to generate the corresponding 16-bit CRC checksum in advance). The obtained CRC checksum is XORed with the lower 8 bits (YL8[n]) of the previous byte CRC checksum Y[n] multiplied by 256 (i.e., shifted left by 8 bits). Then, the CRC is calculated byte by byte until BYTE[0]. The general description of the byte-based algorithm is: the CRC code of this byte is equal to the lower 8 bits of the previous byte CRC code shifted left by 8 bits, and XORed with the CRC code obtained by XORing the previous byte CRC code with the current byte after shifting right by 8 bits. The byte-based algorithm is as follows: 1) The CRC register group is initialized to all "0" (0x0000). (Note: When the CRC register group is initialized to all 1, the final CRC should be inverted.) 2) The CRC register group is shifted left by 8 bits and saved to the CRC register group. 3) The upper 8 bits of the original CRC register group (shifted right by 8 bits) are XORed with the data byte to obtain an index to the value table. 4) XOR the table value pointed to by the index with the CRC register group. 5) Add 1 to the data pointer. If the data has not been processed completely, repeat step 2). 6) Obtain CRC. unsigned short GetCrc_16(unsigned char * pData,int nLength) //Function: Calculate the 16-bit CRC check code of data stream * pData, the data stream length is nLength { unsigned short cRc_16 = 0x0000; // Initialization while(nLength>0) { cRc_16 = (cRc_16 << 8) ^ cRctable_16[((cRc_16>>8) ^ *pData) & 0xff]; //cRctable_16 table is generated by function mK_cRctable nLength--; pData++; } return cRc_16; } void mK_cRctable(unsigned short gEnpoly) //Function: Generate 16CRC check codes corresponding to 0-255, which is actually computer algorithm 1 (bit type algorithm) //gEnpoly is the generating polynomial//Note that when the low bit is transmitted first, the generating polynomial should be reversed (the low bit and the high bit are swapped). If CRC16-CCITT is 0x1021, it will be 0x8408 after inversion { unsigned short cRc_16=0; unsigned short i,j,k; for(i=0,k=0;i<256;i++,k++) { cRc_16 = i<<8; for(j=8;j>0;j--) { if(cRc_16&0x8000) //cRc_16&0x0001 when inverted cRc_16=(cRc_16<<=1)^gEnpoly; //cRc_16=(cRc_16>>=1)^gEnpoly else cRc_16<<=1; //cRc_16>>=1 when inverted } cRctable_16[k] = cRc_16; } }