CRC from principle to achieve =============== Author: Spark Huang (hcpp@263.net) Date: 2004/12/8
Abstract: CYCLIC Redundancy Check is widely used in errors detection during data communication, with strong error detection capabilities. This paper details the basic principles of CRC, and various specific implementation methods are introduced in accordance with the origin of the interpreted check-up algorithm.
1. Error detection -------------------------------------------------------------------------------------------------------------------------------- CYCLIC Redundancy Check. They all calculate the check code on the sender to calculate the check code according to some algorithm, and then send the check code and message to the receiving end. The receiving end paid the message to the same algorithm, and compared to the received check code to determine whether the message received is correct.
Parity values only need one check code, which is also very simple. As an example, the transmitting end only needs to be different or calculated for all message bits. If it is 0, the calibration code is 1, otherwise 0. The receiving end can calculate the message, then compare the check code. You can also calculate the message along with the check code. If the value is 0, there is an error, otherwise the verification is passed. Typically, parity can detect 1 bit error, in fact it can detect any odd bit error.
The idea of checksum is also very simple, regarding the message of the transmission as an 8-bit (or 16/32-bit) integer, adding these integers to governing the check code, the check code is also called checksum. The checksum is used in the IP protocol, followed by 16-bit integer, and its MSB (MOST SIGNITIANT BIT) is added to the results.
Obviously, parity checksum has a significant shortcomings. The parity cannot detect an even bit error. For checksum, if there are two integers in the integer sequence, an additional value is added, and the other reduces the same value, this error does not detect.
2. Basic principle of CRC algorithm ------------------ CRC algorithm is based on GF (2) (2) (2) (2) (2 element gapevo domain) multi-class arithmetic basis, It sounds terrible, but in fact it is very understandable and computational rules.
Only one variable x in the polynomial, the factor is only 0 and 1, such as: 1 * x ^ 7 0 * x ^ 6 1 * x ^ 5 0 * x ^ 4 0 * x ^ 3 1 * x ^ 2 1 * x ^ 1 1 * x ^ 0 is: x ^ 7 x ^ 5 x ^ 2 x 1 (x ^ n represents x N power)
GF (2) Adjuground Dimensample 2 Mode 2 Arithmetic Execution Correction Coefficient Dimensional, Mode 2 does not consider carry and borrow when the addition is subtracted, namely: 0 0 = 0 0 - 0 = 0 0 1 = 1 0 - 1 = 1 1 0 = 1 1 - 0 = 1 1 1 = 0 1 - 1 = 0 Obviously, the addition is the same effect (so in the GF (2) polynomial, " "Number) is equivalent to different or operations. For example, P1 = X ^ 3 x ^ 2 1, p2 = x ^ 3 x ^ 1 1, P1 P2 is:
X ^ 3 x ^ 2 1 x ^ 3 x 1 ---------------- x ^ 2 XGF (2) Polynomial multiplication and general polynomial multiplication basics Like, only mode 2 arithmetic is performed at each addition, for example, P1 * P2 is:
(x ^ 3 x ^ 2 1) (x ^ 3 x ^ 1 1) = (x ^ 6 x ^ 4 x ^ 3 x ^ 5 x ^ 3 x ^ 2 x ^ 3 x 1) = x ^ 6 x ^ 5 x ^ 4 x ^ 3 x ^ 2 x 1
GF (2) polynomial division is also basically the same as general polynomial division, but only mode 2 arithmetic occurs when each subtraction is reduced, such as P3 = x ^ 7 x ^ 6 x ^ 5 x ^ 2 x, p3 / P2 is:
X ^ 4 X ^ 3 1 ------------------------------------------------------------------------------------- - x ^ 3 x 1) x ^ 7 x ^ 6 x ^ 5 x ^ 2 x ^ 7 x ^ 5 x ^ 4 ------------- -------- x ^ 6 x ^ 4 x ^ 6 x ^ 4 x ^ 3 -------------------- x ^ 3 x ^ 2 x ^ 3 X 1 ---------------- x ^ 2 1 CRC algorithm to correspond to a message of M bits, a GF (2) Polynomial M, such as 8-bit messages 11100110, if the MSB is transmitted first, it corresponds to X ^ 7 x ^ 6 x ^ 5 x ^ 2 X. The transmitting end and the receiving end contemplated a GF (2) polynomial g of a number of R, called generated polynomial, such as X ^ 3 X 1, R = 3. The polynomial of the R 0 corresponding to the R 0 is added to M ', obviously M' = MX ^ R. The use of M 'is divided by G will obtain a number of remaining numbers R-1 R, and the corresponding R bits are the check code. As follows:
11001100 ------------- 1011) 11100110000 1011 ....... ----....... 1010 ... 1011 ... ----...... 1110 ... 1011 ... ------ 100 <--- check code sending the M bit message along with the M bit message The R bit check code (that is, M ' R), together, the receiving end calculates the check code of the received M bit message, and compares the received check code. The receiving end can also be divided by all M R bits received to generate a polynomial, and then determine if the remainder is 0. This is because M ' R = (Qg R) R = QG, here Q is commercial. Obviously, it can also increase R 0, re-removed to generate a polynomial, if there is no error occurs, if there is no error occurs, and the remainder is still 0.
3. Generate a polynomial selection ------------------ It is obvious, different generated polynomial, its error-in error is different. How to choose a good generated polynomial requires a certain mathematical theory, which is only analyzed from some side. Obviously, to use the R bit check code, the number of times the polynomial should be R. Generating a polynomial should include an item "1", otherwise the LSB (Least Significant Bit) of the check code will always be 0. If the message (including the check code) T generates an error during the transfer, the message received by the receiving end can be represented as T E. If e cannot be generated in the polynomial G, the error can be detected. Consider the following cases:
1) 1 bit error, ie E = x ^ n = 100 ... 00, n> = 0. As long as G is at least 2 bits 1, E cannot be removed by G. This is because GX ^ K is equivalent to shifting the G left to the K bit, and the QG is equivalent to the left movement of multiple different g from any polynomial Q. If g is at least two bits 1, there are at least two digits of a plurality of different left shift addresses. 2) The odd bit error, as long as the G contains factor f = x 1, E cannot be removed by G. This is because QG = Q'F, from 1) analysis, and a plurality of different left shift results 1 of F is inevitably even.
3) Explosive error, 即 E = (x ^ n ... 1) x ^ m = 1 ... 100 ... 00, n> = 1, m> = 0, obviously only g contains items 1 ", and the number of times is greater than n, you can't remove E. 4) 2-bit error, ie E = (x ^ n 1) x ^ m = 100 ... 00100 ... 00, n> = 0. Set x ^ n 1 = qg r, then e = qgx ^ m rx ^ m, from 3) can be known that E can be removed by G and is only 0. Therefore, it is only necessary to analyze X ^ n 1, according to [3], for the number R, there is always one generated polynomial G such that N 1 is required to except X ^ n 1. The generated polynomial is original (Primitive), which provides the highest power of 2-bit error on this time, because when n = 2 ^ r - 1, X ^ n 1 can be removed by any R times polynomial . [3] At the same time, it is pointed out that the original generated polynomial is unpublished, but the unpublished polynomial is not necessarily original, so the original generation polynomial is not detected for some odd bit errors. Here are some standards of some standard CRC algorithms: standard polynomial 16 credit representation ----------------------------------------------------------------------------------------------- ------------------------------------------ CRC12 x ^ 12 x ^ 11 x ^ 3 x ^ 2 X 1 80F CRC16 x ^ 16 X ^ 15 X ^ 2 1 8005 CRC16-CCITT X ^ 16 X ^ 12 X ^ 5 1 1021 CRC32 x ^ 32 X ^ 26 x ^ 23 x ^ 22 x ^ 16 x ^ 12 x ^ 11 04C11DB7 X ^ 10 x ^ 8 x ^ 7 x ^ 5 x ^ 4 x ^ 2 X 1 16 The principal indicates the highest number, and CCITT is renamed ITU-T in 1993. CRC12 is used for 6-bit bytes, and other uses for 8-bit bytes. CRC16 is in IBM's Bisynch communication standard. CRC16-CCITT is widely used in communication protocols such as XMODEM, X.25 and SDLC. Ethernet and FDDI use CRC32, which are also used in files such as ZIP, RAR. In these generated polynomials, CRC32 is original, while three of the three contain factors X 1.
4. CRC algorithm implementation --------------- To implement the CRC algorithm with the program, consider the conversion to the long-scale method of Section 2, still M = 11100110, g = 1011, Its coefficient R is 3. 11001100 11100110000 ------------- 1011 1011) 11100110000 ----------- 1011 ....... 1010110000 ----....... 1010110000 1010 ... 1011 1011 ... ===> ----------- ----.... 001110000 1110 ... 1110000 1011 .. 1011 --------------- 1010 .. 101000 1011 .. 101000 ---- 1011 100 <--- Cat Code --------- - 00100 100 <--- check code The program can be implemented as follows: 1) Put the front R bit of MX ^ R into a register of a length of R; 2) If the first bit of the register is 1, the left shift the register left 1 bit (MSB to move the MSB of MX ^ R) The LSB of the register is different from the rear R of g or, otherwise only the register left shifts 1 bits (LSB moves the MSB of MX ^ R); 3) Repeat step 2 until Mf all MX ^ r moves into the register; 4) The value in the register is the check code. The generated polynomial 0x1021, which uses CRC16-CCITT, its C code (all code assumes that the system is 32 digits, and all in VC6 is compiled) as follows:
Unsigned short do_crc (unsigned int LEN) {INT I, J; Unsigned short crc_reg; crc_reg = (Message [0] << 8) Message [1]; for (i = 0; i
UNSIGNED DO_CRC (unsigned int LEN) {INT I, J; unsigned short crc_reg = 0; unsigned short current; for (i = 0; i In the above discussion, each byte of the message is first transmitting the MSB, but the CRC16-CCITT standard is calculated according to the first transfer LSB, the message right shift register is calculated. Simply change the code to the LSB of the determination register, the 0x1021 bit is bred down (0x8408) and the register is different or, as shown below: Unsigned short do_crc (unsigned char * message, unsigned int LEN) {Int i, j; Unsigned short crc_reg = 0; unsigned short current; for (i = 0; i This algorithm uses two layers of cycles, processes the message, which is very low. In order to improve time efficiency, the usual idea is to change time in space. Considering that the internal cycle is only related to the current message byte and the low byte of the CRC_REG, the algorithm does the following equivalent conversion: unsigned short do_crc (unsigned char * message, unsigned int len) {int i, j; unsigned short crc_reg = 0; unsigned char index; unsigned short to_xor; for (i = 0; i Now the internal cycle is only related to index, you can generate a table CRC16_ccitt_table in advance, so that to_xor = crc16_ccitt_table [index] can simplify: unsigned short do_crc (unsigned char * message, unsigned int len) {unsigned short crc_reg = 0; while (len--) crc_reg = (crc_reg >> 8) ^ crc16_ccitt_table [(crc_reg ^ * message ) & 0xff]; return crc_reg; } CRC16_CCITT_TABLE is generated by code: INT main () {unsigned char index = 0; unsigned short to_xor; int i; Printf ("Unsigned short crc16_ccitt_table [256] = / n {"); While (1) {if (! (index% 8)) Printf ("/ n"); to_xor = index; for (i = 0; i < 8; i ) {if (to_xor & 0x0001) TO_XOR = (TO_XOR >> 1) ^ 0x8408; Else TO_XOR >> = 1;} Printf ("0x% 04x", TO_XOR); if (INDEX == 255) {Printf ("/ n"); Break;} else {printf (","); index ;}} printf ("};"); return 0;} The generated table is as follows: Unsigned short crc16_ccitt_table [256] = {0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf, 0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e, 0x9cc9 , 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd, 0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,0x3183, 0x200a , 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c, 0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb, 0xce4c, 0xdfc5, 0xed5e , 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a, 0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,0x6306, 0x728f, 0x4014, 0x519d , 0x2522, 0x34ab, 0x0630, 0x17b9,0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb , 0xA862, 0x9AF9 , 0x8b70,0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff, 0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036 , 0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e, 0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd, 0xb58b , 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c, 0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,0x4a44, 0x5bcd , 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb, 0x2f, 0xc704, 0x0a9f, 0x8120, 0x90a9, 0x8120, 0x90a9, 0x8120, 0x90a9, 0x8120, 0x, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a, 0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330, 0x7bc7, 0x6a4e, 0x3de3, 0x2c6a, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78}; this is the message unsigned char message [len], the check code is: unsigned short code = do_crc (message, len); and send it as follows Going out: Message [len] = code & 0x00ff; Message [LEN 1] = (CODE >> 8) & 0x00FF; the receiving end performs DO_CRC to the received Len 2 byte, if there is no error, the result should be 0 . In some transport protocols, the sender does not point out the length of the message, but uses the end flag, considering the following errors: 1) Add 1 or more 0 bytes before the message; 2) Messages in 1 or more A continuous 0 byte begins, throwing 1 or more 0; 3) After the message (including the check code), add 1 or more 0 bytes; 4) Messages (including the check code) in 1 Or a plurality of consecutive 0 bytes, throwing 1 or more 0; constant. In order to solve the first two problems, only the initial value of the register is not 0, the following improvements are made to DO_CRC: unsigned short do_inc (unsigned short reg_init, unsigned char * message, unsigned int LEN) {unsigned short crc_reg = reg_init; while (WHILE) LEN - CRC_REG = (CRC_REG >> 8) ^ crc16_ccitt_table [(CRC_REG ^ * Message ) & 0xFF]; Return CRC_REG;} REG_INIT = 0xfff in crc16-ccitt standard, in order to solve the two problems, the calculated check code is different from 0xffff in the CRC16-CCITT standard, namely: unsigned short code = do_crc (0xfff, message, len) ; Code ^ = 0xfff; message [len] = code & 0x00ff; Message [LEN 1] = (CODE >> 8) & 0x00FF; Obviously, now the receiving end performs DO_CRC to receive all bytes received, if there is no error occurrence The result should be a normal value good_crc. It satisfies the following relationship: unsigned char p [] = {0xFF, 0xFF}; good_crc = do_crc (0, p, 2); its result is good_crc = 0xF0b8.
