The principle and implementation method of CRC check-EEWORLD

Collect

1. Introduction to CRC Check

Cyclic Redundancy Check (CRC) is a commonly used checksum with error detection and correction capabilities. It is widely used in early communications. Cyclic Redundancy Check is often used for data verification of external storage and computer synchronous communication. Cyclic Redundancy Check establishes the agreed relationship between data bits and check bits through some mathematical operations.

Different from parity check, sum check, XOR check and other verification methods, the calculation process of CRC check is relatively complicated.

2. Introduction to Modulo 2 Division

Although the CRC check principle seems complicated, it is not difficult to understand. The basic idea is to first append a number to the frame to be sent, generate a new frame and send it to the receiving end. Of course, this additional number is not random. It must make the generated new frame divisible by a specific number selected by the sending and receiving ends. Here, binary division is not directly used, but a method called "modulo 2 division" is used. After reaching the receiving end, the received new frame is divided by the selected divisor (also using "modulo 2 division"). Because the sender has added a number before sending the data frame, the "remainder removal" process has been performed, so the result should have no remainder and the result can be divided by the divisor. If there is a remainder, it means that an error has occurred in the transmission process of the frame.

Here, in order to have a deeper understanding of CRC verification, let's introduce modulo 2 division. It is similar to "arithmetic division", but it does not borrow from the upper bit, nor does it compare the values of the same bits of the divisor and dividend. As long as the same number of bits is used for division, it will be fine. Modulo 2 subtraction is actually a bitwise XOR operation. That is, after comparison, if the corresponding bits of the two are the same, the result is "0", and if they are different, the result is "1". As shown in the figure below, the binary number 1010101 is divided by 1001, and the result is 1011, and the remainder is 110.

3. CRC verification principle

Above we have briefly introduced CRC verification. Now let’s take a look at how CRC verification is implemented.

First, in order to perform CRC check, the sender and receiver must agree on a divisor, which is usually expressed in a polynomial form, and this polynomial is also called a "generator polynomial". For example, the commonly used polynomial x4 + x + 1 represents a divisor of 10011, and the polynomial x16 + x15 + x2 + 1 represents a divisor of 110000000000000101. The following table lists the commonly used divisor polynomial formulas.

CRC algorithm name Polynomial formula Width Polynomial Initial value Result XOR value Input inversion Output inversion

CRC-4/ITU x4 + x + 1 4 03 00 00 true true

CRC-5/EPC x5 + x3 + 1 5 09 09 00 false false

CRC-5/ITU x5 + x4 + x2 + 1 5 15 00 00 true true

CRC-5/USB x5 + x2 + 1 5 05 1F 1F true true

CRC-6/ITU x6 + x + 1 6 03 00 00 true true

CRC-7/MMC x7 + x3 + 1 7 09 00 00 false false

CRC-8 x8 + x2 + x + 1 8 07 00 00 false false

CRC-8/ITU x8 + x2 + x + 1 8 07 00 55 false false

CRC-8/ROHC x8 + x2 + x + 1 8 07 FF 00 true true

CRC-8/MAXIM x8 + x5 + x4 + 1 8 31 00 00 true true

CRC-16/IBM x16 + x15 + x2 + 1 16 8005 0000 0000 true true

CRC-16/MAXIM x16 + x15 + x2 + 1 16 8005 0000 FFFF true true

CRC-16/USB x16 + x15 + x2 + 1 16 8005 FFFF FFFF true true

CRC-16/MODBUS x16 + x15 + x2 + 1 16 8005 FFFF 0000 true true

CRC-16/CCITT x16 + x12 + x5 + 1 16 1021 0000 0000 true true

CRC-16/CCITT-FALSE x16 + x12 + x5 + 1 16 1021 FFFF 0000 false false

CRC-16/X25 x16 + x12 + x5 + 1 16 1021 FFFF FFFF true true

CRC-16/XMODEM x16 + x12 + x5 + 1 16 1021 0000 0000 false false

CRC-16/DNP x16 + x13 + x12 + x11 + x10 + x8 + x6 + x5 + x2 + 1 16 3D65 0000 FFFF true true

CRC-32 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 32 04C11DB7 FFFFFFFF FFFFFFFF true true

CRC-32/MPEG-2 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 32 04C11DB7 FFFFFFFF 00000000 false false

After selecting the divisor, you need to add k-1 "0" bits after the data to be sent, where k is the number of digits of the divisor. Then divide the new number with k-1 "0" bits added (a total of m+k-1 bits) by the divisor in the "modulo 2 division" method, and the remainder is the CRC check code of the data. However, it should be noted that the number of digits of the remainder must be one less than the number of digits of the divisor, even if the first digit is 0, or even all 0 (when it is divisible), it cannot be omitted.

Finally, the check code is appended to the original data to construct a new frame and send it to the receiving end. Finally, the receiving end divides the new frame by the previously selected divisor using "modulo 2 division". If there is no remainder, it indicates that there was no error in the transmission of the frame, otherwise an error occurred.

Next, we use an example to illustrate the calculation process of CRC check.

Suppose we calculate the CRC checksum of the hexadecimal number 0xBB, and the generator polynomial we use is x4 + x + 1. The number to be calculated is represented by the binary bit 1011 1011, and the divisor is 10011. Since the number of bits of the generator polynomial is 5, according to the above introduction, the number of bits of the CRC checksum is 4 (the number of bits of the checksum is 1 less than the number of bits of the generator polynomial). Therefore, add 4 more zeros after the original data to get 1011 1011 0000, and then divide this number by the generator polynomial in the "modulo 2 division" method, and the remainder (i.e. CRC code) is 1111, as shown in the figure below.

Replace the four "0"s after the original frame 1011 1011 0000 with the CRC check 1111 calculated in the previous step to get the new frame 1011 1011 1111. Then send this new frame to the receiving end. When the above new frame arrives at the receiving end, the receiving end will divide the new frame with the divisor 10011 selected above in the "modulo 2 division" mode to verify whether the remainder is 0. If it is 0, it proves that there is no error in the transmission process of the frame data, otherwise there is an error.

4. CRC check c code implementation

The calculation process of CRC check is relatively complicated, and the general code implementation adopts the table lookup method. The following code is the code for CRC16 check implementation, the corresponding CRC algorithm is CRC-16/MODBUS, and the generated polynomial is x16 + x15 + x2 + 1.

#include

const unsigned char chCRCHTalbe[] = //CRC high byte value table

{