Atmega128 MCU CRC check code table lookup and direct generation

introduction

With the continuous advancement of technology, various data communications are being used more and more widely. Due to the influence of many factors such as transmission distance, field conditions, interference, etc., some unpredictable errors often occur in the communication data between devices. In order to reduce the impact of errors, data verification is generally used during communication, and cyclic redundancy check is one of the commonly used important verification methods.

AVR high-speed embedded microcontroller is an 8-bit RISC MCU. It only takes one clock cycle to execute most instructions. It is fast (the running speed of 8MHz AVR is approximately equal to that of 200MHz 80C51). The 32 general registers are directly connected to the ALU, eliminating the calculation bottleneck. It has embedded Flash and EPPROM that can be serially downloaded or self-programmed, with many functions and multiple operating modes.

This paper adopts Atmega128 high-speed embedded microcontroller from Atmel Company, and in accordance with the 802.11 wireless LAN protocol standard announced by IEEE in 1999, adopts 32-bit cyclic redundancy check code (Cyclic Redundancy Check) to realize error checking when wirelessly transmitting data.

1 CRC Cyclic Redundancy Check Code Principle

1.1 Frame format for data transmission

According to the 802.11 wireless local area network protocol developed by IEEE, data transmission should be based on frames. Here, we use the information processing system - data communication - high-level data link control protocol - frame structure, and each frame consists of the following fields (transmission order from left to right):

Address – Data station address field;

Control – Control fields.

Info – information field;

CRC checksum - CRC checksum generated based on the previous three fields.

The total field consisting of the three fields of address, control, and information is collectively called the data segment.

1.2 Theoretical Generation Method of CRC Check Code

CRC checksum adopts polynomial coding method, and the processed data block can be regarded as an n-order binary polynomial. Here, it is assumed that the binary data segment to be sent is g(x), the generating polynomial is m(x), and the obtained CRC checksum is c(x).

The encoding method of the CRC check code is to divide the binary data g(x) to be sent by the generating polynomial m(x), and use the final remainder as the CRC check code. The implementation steps are as follows.

① Assume that the data block to be sent is an m-bit binary polynomial g(x), and the generating polynomial is m(x) of order r. Add r zeros at the end of the data block, and the length of the data block increases to m+r bits. The corresponding binary polynomial is G(x).

② Divide G(x) by the generating polynomial m(x) and obtain the remainder, which is a binary polynomial c(x) of order r-1. This binary polynomial c(x) is the CRC checksum of g(x) encoded by the generating polynomial m(x).

③ Subtract c(x) modulo 2, and the resulting binary polynomial is the string to be sent that contains the CRC check code.

CRC check can detect 100% of all odd random errors and burst errors with length less than or equal to r (r is the order of m(x)). Therefore, the higher the order of the CRC generator polynomial, the smaller the probability of misjudgment. CCITT recommends: 2048 Kb/s PCM basic group equipment uses the CRC-4 scheme, and the CRC check code generator polynomial m(x)=x4+x+1 is used. Using 16-bit CRC check can ensure that there is only 1 undetected error in the 1014-bit code element. In the frame check sequence FCS of IBM's synchronous data link control protocol SDLC, CRC-16 is used, and its generator polynomial m(x)=x16+x15+x2+1; in the frame check sequence FCS of the high-level data link control protocol HDLC recommended by CCITT, CCITT-16 is used, and its generator polynomial m(x)=x16+x15+x5+1. The generating polynomial of CRC-32 is m(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1. The probability of CRC-32 error is 10-5 of that of CRC-16. Due to the reliability of CRC-32, it is very suitable to use CRC-32 for important data transmission, so it is widely used in the fields of communication and computer. In some UART communication control chips (such as MC6582, Intel8273 and Z80-SIO), CRC check code is used for error control; Ethernet card chips and MPEG decoding chips also use CRC-32 for error control.

The coefficients of the m(x) generating polynomial are either 0 or 1, but the first coefficient of m(x) is 1, and the last coefficient must also be 1. The higher the degree of m(x), the stronger its error detection capability.

2 Generate 32-bit CRC check code using Atmega128

2.1 Direct calculation method to generate 32-bit CRC check code

The direct calculation method is to design the program based on the principle of CRC checksum generation. Its advantages are less module code, flexible modification and good portability. This algorithm is simple and easy to implement, and is applicable to any length of generating polynomial m(x). It can be used when the data to be sent is not long, but if the data block to be sent is very long, this method is not suitable. Because it can only process 1 bit of data at a time, the efficiency is too low and the amount of calculation is large.

The process of generating a 32-bit CRC check code by calculation is shown in Figure 1.

The CRC-32 source code implemented in AVR microcontroller assembly language can be found in the online supplementary version of this journal (http://www.dpj.com.cn).

2.2 Generate 32-bit CRC check code by table lookup method

In contrast to the direct calculation method, the advantages of the table lookup method for generating 32-bit CRC check codes are small amount of calculation and high speed; the disadvantage is poor portability. This algorithm first requires a 32-bit CRC generation table. Since 1 byte has 8 bits, this table has a total of 256 items. However, since the registers in the AVR high-speed embedded microcontroller are in units of 1 byte, in the programming implementation, this CRC generation table has a total of 1024 items, from 0 to 1023; every 4 bits correspond to an item in the 32-bit CRC generation table, and each item is arranged in descending order from high to low. For details on the program for the 32-bit CRC generation table, please refer to the online supplementary version of this journal (http://www.dpj.com.cn).

The process of generating a 32-bit CRC check code using the table lookup method is shown in Figure 2.

In the flowchart shown in Figure 2, when the index of the CRC generation table is obtained through XOR operation, since the register in the AVR high-speed embedded microcontroller is based on 1 byte, the corresponding coefficient should be multiplied according to the number of bits of the CRC check code required to be generated in the programming implementation. For example: when a 32-bit CRC check code is required during data transmission, the obtained index number should be multiplied by the coefficient 4, and then the contents of the 32-bit CRC generation table unit should be obtained from high to low.

For the source code of using the table lookup method to obtain the 32-bit CRC check code, please refer to the online supplementary version of this journal (http://www.dpj.com.cn).

3 Experimental Results

In order to compare the characteristics of the two 32-bit CRC check code generation methods, data segments with different byte numbers are selected respectively, and the effects of the two methods under different conditions are compared, as shown in Table 1.

Table 1 Comparison of experimental results of the two algorithms

All the above experimental results were obtained by simulating at a running speed of 12MHz using Atmel's Atmega128 high-speed embedded microcontroller as the experimental equipment platform on the AVR Studio4 simulation software.

When calling the 32-bit CRC generation table program to obtain the 32-bit CRC generation table, it takes 3968.33 μs and executes 47620 clock cycles. The following conclusions can be drawn from the above experimental results.

① If the time to generate the 32-bit CRC table is not taken into consideration, for example, the 32-bit CRC table is directly burned into the programmable flash memory Flash of Atmega128, it can be clearly seen from Table 1 that the table lookup method runs much faster than the direct calculation method. Therefore, in similar cases, when generating a 32-bit CRC check code for data transmission, the table lookup method should be selected.

② In some applications, if the hardware memory space requirements are very high and there are no particularly high requirements for time to a certain extent, the direct calculation method can be used to avoid the memory space occupied by the CRC generation table in the table lookup method.

③ Although the experimental results compare the two algorithms for 32-bit CRC check codes, the conclusions obtained are also applicable to 8-bit, 16-bit, and 24-bit CRC check codes.

Conclusion

CRC cyclic redundancy check code is a convenient, effective and fast verification method, which is widely used in many practical projects. The two algorithms listed in this article - table lookup method and direct calculation method, can both obtain CRC check code; but they have their own characteristics. In engineering applications, the most suitable method should be selected according to actual needs to obtain the best effect.