Discussion on CRC Check Programming and Hardware Fast Check

Introduction

Cyclic Redundancy Check (CRC) is the most commonly used verification method for data communication between computers and instruments. CRC code is a linear block code with simple coding but strong error detection and correction capabilities. In addition to various embedded instruments, inverters and other devices, the output data of some digital sensors also provide CRC codes, such as digital temperature sensor DS18B20, integrated temperature and humidity acquisition chip SHT11, etc. However, the CRC check polynomials (used for modulus division of the same communication code) provided by various manufacturers are different, and there are CRC8 and CRC16. In addition, it is stipulated that all bits of the initial value of the modulus remainder are either all cleared to 0 or all set to 1 (the CRC hardware generation circuit is different), so the calculation process of the modulus remainder is also different. It is often difficult for beginners to understand that omitting CRC check reduces the reliability of communication. However, many C language programs require more RAM units when calculating, which is difficult to run on low-end microcontrollers such as 80C51 and PIC16.

Therefore, for CRC check in embedded systems, it is a very common practice to calculate the 256 remainders corresponding to the 1-byte data range in advance according to a specific check polynomial, and use it as a table, and write it into the program memory for query to avoid online calculation. In view of this, some manufacturers directly provide this list in the manual. However, if it is a CRC16 check, the storage table will take up 512 bytes (CRC32 requires 1 KB), which is a large proportion for the limited MCU ROM resources. Often, just because this table is installed, the model of the MCU has to be upgraded.

This article analyzes and explains the generation characteristics of the actual CRC check code, and based on this, gives a general CRC check programming idea and program structure that saves RAM and ROM and has fast calculation, and explores the method of using a small amount of hardware to achieve fast and reliable CRC check.

1 CRC principle and actual check code reverse generation characteristics machine

When a k-bit binary data is transmitted, some redundant bits are added according to a certain rule to increase its code distance, which can detect and correct errors. The standard CRC code is to shift the original data left by r bits, and then divide it modulo with a special r+1-bit polynomial function to obtain a remainder of at most r (8, 16, 32) bits, and generate a k+r-bit code to send after the original data. The receiver then uses the same agreed polynomial to divide the received data modulo. If the remainder is 0, the transmission is correct, and if it is other values, it corresponds to errors in each bit. .

However, for practical applications, in order to speed up communication, the r-bit remainder is not transmitted every time, but the cumulative modulo addition (XOR) method is used to continuously XOR with the next k-bit data to form a new intermediate remainder (still r bits, because r ≥ k is generally selected), and then divided modulo with the agreed polynomial to obtain a new remainder value, and so on, until all communication data are XORed with the intermediate remainder and then divided modulo. In this way, the final r-bit remainder is obtained, which is sent after the group of data as the CRC code for the whole group of data verification. The receiver uses the same process to calculate the final remainder of the received array, and then compares it with the last received CRC code (or uses the CRC code as data to see if the final remainder is 0). Of course, this can only detect whether the transmission of the group of data is wrong, but cannot correct the error.

The remainder of the first data is unique, and after XORing with any subsequent specific data, the result is still unique. Therefore, as long as r is selected with enough bits, it can be guaranteed that once there is a transmission error in a single bit of multiple data, the possibility that its final CRC remainder is equal to the correct remainder of the transmission is extremely low, so the transmission error can be detected.

For components and many devices, their final remainder, that is, the CRC code of the group check, is quickly generated by hardware. In order to simplify the hardware circuit and make it easier for the receiver to check and program, the deformed generated CRC code and the corresponding check processing method are often used.

For the initial value of the modulus remainder, the ISO/IEC 13239 standard stipulates that each bit (8, 16, 32) is set to 1, while the communication CRC code of the DS18B20 device and some control instruments is cleared to 0. Different initial values ​​should be assigned according to different devices during software programming.

The polynomial g(x) is specially agreed to be r+1 bits, such as CRC8 in ISO/IEC 13239 standard, g(x)=x8+x2+x+1. Its highest bit is always 1, and implicitly making it can simplify the modulus operation, but in this way, the following bits are 0, which makes it difficult to locate the calculation and storage in the multi-byte (such as 16 bits need 2 bytes) CRC check. Therefore, most CRC code generation and verification processes use the method of reversing the agreed polynomial, that is, putting the lowest bit 1 in the highest bit and discarding the highest power coefficient 1, so that both the operation and storage are reduced to r bits.

For CRC8, g(x)=x8+x2+x+1, the modulus after removing the high bit inversion is 11100000 (0E0H), r=8.
For CRC16, g(x)=x16+x15+x2+1, the modulus after removing the high bit inversion is 0A001H, r=16. 
For CRCCCITT, g(x)=x16+x12+x5+1, the modulus after the same processing is 8408H, but the positive sequence value 1021H is also commonly used. For
CRC32, g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1, the modulus after the processing is 0EDB88320H, r=32. 

After the above processing, it stands to reason that the modulus dividend and the remainder should also be reversed. But in this case, when the r-bit remainder is modulo-added with the next k-bit data, not only the k-bit data should be reversed, but also the left end (highest bit) must be aligned for XOR, which is not only troublesome but also prone to errors. Therefore, the actual generation and verification of CRC codes generally still arranges the remainder, that is, the (modulus) dividend, in positive order, and the new data is still right-aligned XORed into the remainder. However, the original left shift of the modulus dividend r bits and right addition of 0 is changed to right shift of r bits and left addition of (r) 0. This is equivalent to only r bits in the k+r bit modulus dividend being reversed (placed on the left end), while the first k bits (now placed on the right end) are still in the positive order. It can be seen that according to the reverse order principle, in fact, each time the reversed value of the communication data is XORed, such as 11001000B (0C8H) becomes 00010011 (13H), and then XORed with the modulus dividend to obtain the CRC check code. However, since the reversed values ​​of all binary numbers are uniquely corresponding, it does not affect the unique certainty of the generated CRC code, but the receiver needs to process it according to the same reverse order rule.

2 Programming of CRC Check in Embedded Systems

As mentioned above, the k+r bit modulus dividend is continuously divided by the reversed agreed polynomial using the right shift method, which also complies with the division rule of continuously reducing the remainder from high to low. However, since there is no need to find the quotient of the modular division, we only need to continuously shift the divisor to the right and subtract it from the reversed agreed polynomial with the highest bit removed to find the remainder. 

However, if the bit shifted out of the lowest bit of the divisor to the right is 0, no matter how many 0s are added from the left, it is not enough to divide the agreed polynomial (whose implicit highest bit is 1). In this case, the quotient of this bit is 0, and the remainder does not change. We should not perform the modular subtraction with the agreed polynomial, but continue to add 0s to the left and shift right until the value of the bit shifted out of the current remainder (divisor) to the right is 1, which is enough for the modular division (quotient 1), and then the remainder can be subtracted from the polynomial again. From this, we can see that removing the highest bit of the agreed polynomial can reduce the number of bits r calculated for modular subtraction (XOR) (generally r is exactly an integer multiple of the number of bits in a byte).

Since the divisor is k+r bits, it is necessary to shift right k bits in total, that is, add k 0s to the left, to end the modular division to the lowest bit. The remainder obtained is at most r bits (the polynomial is agreed to be r+1 bits), and then it is XORed into a new data as the new modulus dividend. 

Each time a data is XORed and a new round of CRC code is calculated, only k (byte data k=8) right shifts and generally less than k modular subtraction (XOR) operations are performed, and the intermediate difference of modular subtraction does not need to be retained (the latter value covers the former value). Therefore, the operation process of CRC code generation is a k-cycle process of right shifting, judging that the shifted-out bit is 1, then the same polynomial modular subtraction (C language cannot detect the shifted-out bit, and the remainder needs to be backed up and "ANDed" with 0x01), and the difference is stored back and then right shifted again, as shown in Figure 1. After that, XOR the next data (this step is consistent with the table lookup method). If the programming is proper, the amount of calculation is very small. .

 

The author used 51 assembly language to write a CRC8 check program. It only takes 64 to 80 machine cycles to calculate the CRC code of 1 byte of data, and only uses 1 more byte of RAM unit (CRC16 check uses 2 more bytes, which doubles the time) to store the remainder, that is, the next modulus divisor (continuously overwriting the previous useless one). Therefore, it is completely possible to directly calculate without having to store a large number of data tables. When programming in C language, it is necessary to consider the optimization of statement code and only define and use int and char type local variables to avoid wasting time and occupying too many R.AM units. [page]

For the last received r-bit CRC check code, the receiver does not need to include it in the modulus division to make the final remainder 0. It only needs to compare it with the modulus division remainder of the information data. If they are equal, it is determined that the communication is correct. This can reduce the number of modulus division cycles and save time. 

3 Discussion on hardware CRC check

In the manual of a device or equipment, the generation circuit of its hardware CRC code is often given. Taking the bus digital temperature sensor DS18B20 as an example, its 8-bit CRC code generation circuit is shown in Figure 2. .

For this hardware circuit, the equivalent modulus division polynomial is: 

 

After the modulus polynomial is reversed, the highest bit is implied, and the value of the polynomial is 8CH.

The initial value of the 8-bit shift register is cleared to 0 (00H), and each byte of the communication array data is input in sequence with the low bit first. When all the data is input, the storage (output) value of each bit of the shift register is the required CRC check code. 

In actual applications, it is found that the communication CRC check code of control instruments of brands such as Autonics is exactly the same as that of DS18B20.

 

The hardware generation circuit corresponding to FIG2 can be formed by connecting one 8D flip-flop (such as 74HC373) and one 4-package XOR gate (such as 74HC136), as shown in FIG3.

 

For the operation of assigning the initial value of CRC to 00H (74HC373 cleared to 0), the random values ​​of D0 to D7 can be read out first, and then the read data can be serially input. Because the same data is different or always 0, it is still 0 when divided by any polynomial.

If the MCU has enough remaining I/O ports, the D0 to D7 bits of the CRC code can be read in parallel. Otherwise, a 74HC165 is required to convert D0 to D7 into serial data for reading.

Implementing fast CRC with a small amount of hardware can save the computing time and storage resources of the microcontroller. When used at the sending end, the CRC check code can be obtained quickly, which can enhance the real-time performance when other tasks in the system are very heavy. When used at the receiving end, in addition to the above advantages, it can also significantly enhance the reliability of the system receiving and confirming information, and is suitable for some remote control execution devices (such as variable frequency drives, valve positioning controllers, important monitoring and alarm devices, etc.). Once these devices cannot correctly judge the execution of the received data or command information due to mischecking, the consequences are relatively serious. Therefore, to improve the reliability and real-time performance of embedded systems, hardware CRC check is an option.

Conclusion

Based on the analysis of the reverse generation principle of the commonly used CRC code, this paper gives the unified steps of its programming operation, and proposes a circuit and method for quickly generating CRC code by hardware or performing CRC check on received data, which can provide a reference for the reliability and real-time design of embedded systems.

References

   1. Wang Xinmei Xiao Guozhen Error Correction Code--Principle and Method 2001
   2. Luo Weixiong Han Liyuan Dongchang Communication Principle and Circuit 1999
   3. Li Anfu Fast CRC Operation in Compliance with ISO/IEC Standards [Journal Article] - Single Chip Microcomputer and Embedded System Application 2008(10)
   4. Williams Ross A Painless Guide to CRC Error Detection Algorithms 2008