Simple and practical single chip microcomputer CRC fast algorithm

rain

Simple and practical single chip microcomputer CRC fast algorithm [Copy link]

Abstract: Two practical CRC fast algorithms that can be implemented by software on a single-chip microcomputer are provided. One of them is suitable for single-chip microcomputers such as the 51 series, and the other is suitable for PIC single-chip microcomputers. These two algorithms are very simple and fast. Keywords: CRC algorithm, single chip microcomputer Author: Han Ju Electronics Teaching and Research Section, Taiyuan Branch, China Coal Research Institute (710032) Jiao Chun, Chen Martin, Li Hongyi 1 Introduction CRC (Cyclic Redundancy Code) verification technology is widely used in the field of measurement, control and communication. In many cases, CRC calculation is implemented by dedicated hardware, but for small and low-cost single-chip microcomputer systems, if CRC verification is to be implemented without the support of these hardware, the first thing to be solved is how to complete the CRC calculation efficiently and quickly through software , that is, the problem of CRC algorithm. Two slightly different algorithms are provided here. One is suitable for 51 series microcontrollers with larger program space , and the other is suitable for PIC microcontrollers with very strict program space usage conditions. These algorithms calculate byte by byte, using only table lookup and simple XOR operations, so the calculation process is quite simple and the calculation speed is very fast. The following briefly describes the CRC principle, and then uses the CRC-CCITT standard generating polynomial as an example to illustrate the algorithm, and gives a 51 series microcontroller subroutine and a PIC microcontroller subroutine. 2 　CRC Principle The CRC check principle is actually to add an r -bit binary check code ( sequence ) after a p -bit binary data sequence , thus forming a binary sequence with a total length of n = p + r bits. For example , the p - bit binary data sequence D = [ dp - 1dp - 2 ...... d1d0 ] , the r- bit binary check code R = [ rr - 1rr - 2 .... r1r0 ] , the resulting n- bit binary sequence is M = [ dp - 1dp - 2 ...... d1d0rr - 1rr - 2 .... r1r0 ] ; there is a certain relationship between the check code attached to the data sequence and the content of the data sequence. If one or some bits in the data sequence are wrong due to interference or other reasons, this specific relationship will be destroyed . Therefore , by checking this relationship , the correctness of the data can be verified. The check code R is obtained by performing a binary remainder division operation on the data sequence D. It is divided by a ( r + 1 )-bit binary sequence G = [ g r g r -1 .... g 1 g 0 ] called a generating polynomial , which can be expressed in polynomial form as ( 1 ) Here, x r D ( x ) means shifting the data sequence D left by r bits (i.e. adding r 0 bits at the end of D ), Q ( x ) represents the quotient obtained by this division, and R ( x ) is the required remainder. This operation relationship can also be expressed by formula ( 2 ) ( 2 ) Where Re[ ] means to perform remainder operation on the expression in the brackets. The coding calculation of the check code is as described above, and the check process is to directly perform a division remainder operation on the M sequence, that is, ( 3 ) Or expressed as ( 4 ) If the obtained remainder R ( x ) is zero, it means that the data is correct, otherwise it is considered that an error has occurred. 3 Basic ideas of fast algorithm Here we only take the CRC-CCITT standard generator polynomial as an example. CRC-CCITT is a 17- bit generator polynomial G = [1 0001 0000 0010 0001] , which is expressed in polynomial form as G ( x ) = x16 + x12 + x5 + 1. The binary number of the check code R generated by it is 16 bits ( 2 bytes). The operation of the microcontroller is performed in the form of bytes, so the algorithm should be operated in bytes. Here, the binary sequence composed of bytes is called a "byte sequence". Obviously, the data sequence, check code and the sequence M composed of the two of the microcontroller are all byte sequences, or "multi-byte sequences". In fact, the problem that this algorithm is trying to solve is how to perform division remainder operations on multi-byte sequences. 3.1 Multi-byte sequence operation rules First, suppose there is an 8× i-bit binary sequence consisting of i bytes m1 , m2, ..., mi - 1 , mi , and express it in byte form as Mi = [ m1m2 ... mi - 1mi ] , then extract the first ( i - 1 ) bytes of Mi to form a Mi - 1 sequence , Mi -1 = [ m1m2 ... mi - 1 ] . The relationship between these two sequences can be expressed by a polynomial as Mi ( x ) = x8Mi - 1 ( x ) + mi ( x ) , where mi ( x ) is the binary polynomial representation of the byte mi , and x8Mi - 1 ( x ) means shifting the Mi - 1 sequence left by one byte . For the sequence Mi - 1 , (5) Among them, the two-byte sequence remainder R i -1 = [ h i -1 l i -1 ] . For the Mi sequence, we can get (6) The first term of this result is an integer, so it is independent of the remainder. Thus, the remainder can only appear in the second term. Therefore, the remainder operation on x 8 R i- 1 (x) + mi (x) is equivalent to the remainder operation on Mi ( x ) , which can be expressed in the form of formula ( 4 ): (7) x 8 R i- 1 (x)+m i (x) represents a three-byte sequence [ h i-1 l i-1 m i ] consisting of R i- 1 and m i , and the remainder operation on this three-byte sequence is equal to the remainder operation on the M i sequence, and the result isthe remainder of the M i sequence R i = [ h i l i ] . Similarly, for a M i + 1 sequence (which hasone more byte m i + 1 than the M i sequence ), the operation on the three-byte sequence [ h i l i m i + 1 ] is equivalent to the operation on the M i + 1 sequence, and the result is the remainder of the M i + 1 sequence R i + 1 = [ h i + 1 l i + 1 ] . Obviously, this reflects a law of recursive operation as shown in Figure 1. It can be seen that each recursive operation is a calculation of a three-byte sequence, so how to calculate the three-byte sequence simply and quickly is another key to this algorithm. 3.2 Three-byte sequence calculation When it comes to simplicity and speed, people naturally think of using a table lookup method, such as calculating all the remainders of the three-byte sequence in advance and placing them in a table called a "remainder table" for easy access at any time. However, such a table is too large and requires 2 24 units, which means it takes up 2 25 bytes of storage space, which is absolutely unacceptable for a single-chip microcomputer. Therefore, it is necessary to find a way to reduce the storage space occupied. 　Figure 1 Recursive calculation steps Suppose there is a three-byte sequence T abc = [ abc ] , a T a00 = [ a 0 0 ] and a two-byte sequence T bc = [ bc ] . The relationship between them can be expressed in polynomial form as T abc ( x ) = T a 00 ( x ) + T bc ( x ) . Therefore, for T a 00 , ( 8 ) For Tabc , Among them, Q a 00 is an integer and has nothing to do with the remainder; while Ra 00 and T bc are both two-byte sequences, so their sum (modulo 2 addition, that is, XOR operation) is still a two-byte sequence ( 16 bits in binary, less than the 17 bits of the generating polynomial ), so it is the remainder Rabc of T abc , that is , ( 9 ) This shows that the operation of the three-byte sequence T abc = [ abc ] can be decomposed into two steps, as shown in FIG2 . 1. By looking up the remainder table (Table 1 ), read the remainder R a 00 = [ ha 00 l a 00 ] of T a 00 = [ a 0 0 ] ; 2. Perform an XOR operation on Ra00 and [ bc ] to obtain the remainder of [ abc ] Rabc = [ habc labc ] , that is , habc = ha00 ? b , labc = la00 ? c . Since only one byte in [ a 0 0] is not zero, the remainder table of [ a 0 0] requires only 256 cells, which occupies 512 bytes. Figure 2 Calculation method of three-byte sequence [ abc ] 4 Algorithms 　applicable to 51 series microcontrollers The method described above can be directly applied to 51 series microcontrollers, because the 512- byte remainder table is not a problem at all for their program storage capacity. The calculation is performed directly through the above recursive process. Each recursion is a calculation of a three-byte sequence: the first is [ m 1 m 2 m 3 ] , and the result is [ h 3 l 3 ] ; the second is [ h 3 l 3 m 4 ] , and the result is [h 4 l 4]; ..., the i-th time is [hi +1 l i +1 m i +2], and the result is [hi +2 l i +2 ] ; ... ; the last is [ h k + 1 l k + 1 m k + 2 ] , and the final result is [ h l ] . If there are k data bytes , the recursion is k times . The following is a three-byte sequence calculation subroutine for each recursive operation. Note that before the first call, m 1 , m 2 and m 3 are stored in R0 , R1 and R2 respectively (when the subroutine returns, the calculation results will be stored in R0 and R1 ). Starting from the second call, each time before calling, just store the bytes involved in the operation into R2 (the second time is m 4 , the third time is m 5 , ... , the i- th time is mi + 2 , ... ). When the last call returns, R0 and R1 store the final results h and l respectively . CRC MOV DPH, #table ; Points to the lower half of the remainder table MOV DPL, R0 ; Point to the corresponding unit CLR A ; MOVC A, @A+DPTR ; Read the high byte of the remainder XRL A, R1 ; Calculate the high byte of the remainder MOV R0, A ; Store in R0 INC DPH ; Point to the upper half of the remainder table CLR A ; MOVC A, @A+DPTR ; Read the lower byte of the remainder XRL A, R2 ; Calculate the low byte of the remainder MOV R1, A ; Deposit into R1 RET This subroutine has only 12 instructions, so it is very simple and only takes up 16 machine cycles. In other words, it only takes 16 machine cycles to calculate each byte, which is more than ten times faster than traditional software algorithms.

Table 1 [ a 0 0 ] remainder table a 0 1 2 3 4 5 6 7 8 9 A B C D E F 0× 0000 1021 2042 3063 4084 50A5 60C6 70E7 8108 9129 A14A B16B C18C D1D E1CE F1EF 1× 1231 0210 3273 2252 52B5 4294 72F7 62D6 9339 8318 B37B A35A D3BD C39C F3FF E3DE 2× 2462 3443 0420 1401 64E6 74C7

2004-5-10

InstanceEndEditable