CN1633030A - A Fast Calculation Method of Cyclic Redundancy Check - Google Patents

Abstract

This invention discloses a quick computation method for circular redundant check. Based on the current logic structure corresponding to the multi-nominal generated by applying CRCN, the relation of the state renewed situation of each shift register used by CRCN and other register and input bit is got before hand, the corresponding loop-up list is generated based on said relation. When checking said loop-up list is used directly to obtain the output for every shift register at the present state, which can greatly increase the process speed of CRC check.

Description

A Fast Calculation Method of Cyclic Redundancy Check

technical field

The invention relates to a cyclic redundancy check technology, in particular to a fast calculation method of a cyclic redundancy check.

Background technique

With the continuous advancement of technology, various data communication applications are becoming more and more extensive. Due to the influence of transmission distance, site conditions, interference and many other factors, some unpredictable errors often occur in the communication data between devices. In order to reduce the impact of errors, a data verification method is generally used in communication, and a cyclic redundancy check (CRC) is one of the important verification methods commonly used.

The CRC check provides a simple and effective burst error detection method for data transmission, which can be applied to many aspects. The CRC check adopts a polynomial encoding method, and the processed data block can be regarded as an n-order binary polynomial. For example: assuming that the binary data segment to be sent is g(x), and the generator polynomial is m(x), the obtained CRC check code is c(x). Specifically, the encoding method of the CRC check code is to use The sent binary data g(x) is divided by the generator polynomial m(x), and the final remainder is used as a CRC check code. The CRC code can be implemented by software or hardware; it can be constructed by a serial method with a simple structure but a large processing delay; it can also be constructed by a parallel method with a complex structure but a small processing delay.

At present, the CRC coding technology is relatively mature, and there are three main implementation schemes as follows:

The first is the basic bit-level construction method, which can also be called the direct calculation method. This is the simplest CRC calculation method, which is realized by hardware. As shown in Figure 1, this method mainly uses linear feedback shift in hardware. bit register (LFSR) to achieve. The shift register is driven by the clock, and each clock input data shift register participates in the calculation, and also directly outputs; when all the input bits are processed, the rest of the shift register is the CRC bit, and the CRC bits are shifted out in turn To the data stream, the CRC encoding is completed. In practical applications, the following algorithms can be used to implement:

a1. Define a register R to store the cyclic redundancy check code. The length of the register is generally an integer multiple of the basic storage unit of the processor, such as 8 bits, 16 bits, 32 bits, etc., and set the value of the register R to is 0;

a2. If the leftmost bit of the register R is equal to 1, move the next message bit in, and XOR the register R and the generator polynomial; otherwise, just move the message bit in;

a3. Repeat step a2 until all message bits are shifted in for processing, and what remains in register R is the cyclic redundancy check code of the input sequence.

This method uses less module code, does not need to store a lookup table, is simple to calculate, flexible to modify, and has good portability. The complexity of hardware and software implementation is similar, and it is applicable to generator polynomials of any length m(x). However, if the data block to be sent is very long, this method is not suitable, because this method needs to be processed bit by bit, that is, only one bit of data can be processed at a time, the efficiency is too low, and the amount of calculation is large, which cannot meet the requirements of real-time processing. High-speed data communication is even less applicable.

The second is a standard look-up table algorithm. The CRC calculation of this method can be considered as the remainder of the polynomial pair generator polynomial composed of input bits and shift register status bits. This method needs to provide a CRC generation table in advance. Assuming that the width of the register is n and the number of input bits is m, in practical applications, when m<n, the following steps can be taken:

b1. Define a register R with a width of n bits to store the cyclic redundancy check code. The length of the register is generally an integer multiple of the basic storage unit of the processor, such as 8 bits, 16 bits, 32 bits, etc., and the The value of the register R is set to 0, that is, the bit sequence (r _n-1 ,...,r ₀ ) is set to 0;

b2. Shift register R to the right by nm bits to obtain (R _n-1 ,...,r _nkr ) sequence, and then XOR the obtained sequence with m input bits;

b3. Find the corresponding value in the look-up table, XOR with the sequence (r _m-1 , ..., r ₀ ) obtained by shifting m bits to the left of the register R, and obtain a new CRC value;

b4. Repeat steps b2 and b3 until all message bits are shifted in for processing, and what remains in register R is the cyclic redundancy check code of the input sequence.

When n=m, step b2 and step b3 will be slightly changed:

b2'. XOR the input m bits with the register R, that is, XOR the input m bits with (r _nk-1 ,...,r ₀ );

b3'. Find the corresponding value in the lookup table to get the new CRC value.

When n<m, this algorithm cannot be adopted.

This algorithm needs to provide a lookup table with a size of 2 ^m × n bits, and it needs to perform a lookup table and two XOR operations for every m bits processed. The complexity and performance of the hardware and software implementation are similar. Contrary to the direct calculation method, this method has a small amount of calculation and fast speed, but its portability is poor, and its application is limited. It cannot handle the situation when m>n, that is, the number of bits m processed each time cannot be greater than The highest degree n of the generator polynomial, otherwise the algorithm cannot be applied.

In addition, the stored look-up table increases with the increase of m by an exponential of 2, for example: when 8 bits are processed each time, the size of the look-up table is 256 storage units; when 16 bits are processed each time, the size of the look-up table is It becomes 65536 storage units. It can be seen that the parallelism of this method cannot be too high.

The third is the parallel cyclic redundancy check coding method, as shown in Figure 2, which is a parallel structure based on linear feedback shift registers, in Figure 2, d ₀ ~ d _m-1 represent the m of the parallel input sequence bits, e _{r, c} are the rth row and cth column of the matrix F ^w , x ₀ ~ x _m-1 are the output system state column vectors, where w is the number of parallel input stages. This method actually constructs the relationship between the registers corresponding to the current CRCn generator polynomial through the hardware gate circuit, and finally obtains the CRC value.

It is not difficult to see that the speed of this method is w times that of the conventional method, and the cost is to store an F ¹⁶ matrix and increase the complexity of the hardware. This method has a high degree of parallelism and is suitable for hardware such as FPGA implementation, but this algorithm is not suitable for software such as DSP chip implementation. The reason is very simple. The parallelism of the parallel structure shown in Figure 2 is m, and the general processor cannot reach such a high degree of parallelism.

With the development of high-speed data services in the third-generation mobile communication, CRC check is also widely used in the data transmission of the third-generation mobile communication. However, due to the strict delay requirements of 3GPP baseband processing, the performance of the baseband processor is closely related to the service processing capability per unit time. In this way, the efficiency of CRC coding will directly affect the performance of the baseband processor. If there is no suitable fast CRC calculation method, the service processing capability in high-speed data communication will be greatly affected.

Contents of the invention

In view of this, the main purpose of the present invention is to provide a fast calculation method of cyclic redundancy check, which can greatly improve the processing speed of CRC check, reduce the processing delay of CRC check, and then improve the business processing capacity to a certain extent .

A further object of the present invention is a fast calculation method of cyclic redundancy check, so that it can achieve optimal storage capacity/time delay configuration while ensuring fast calculation speed.

In order to achieve the above object, technical solution of the present invention is achieved in that way:

A fast calculation method of cyclic redundancy check, the method comprises the following steps:

a. According to the logical structure of the CRCn generator currently used, obtain and store the state of each shift register in the generator when processing each input bit;

B. from all the states of all shift registers obtained in step a, extract the state of each shift register in the CRCn generator after processing each bit of the input sequence; and extract each shift register The initial state representation part and the input sequence representation part of the shift register in the state composition are stored separately;

c. Using the independent variable included in each storage part as an address index, generate a lookup table corresponding to the storage part;

d. When performing CRC check in CRCn mode, judge whether the current number of bits to be processed is greater than the number m of bits that can be processed each time, if not, process in a serial manner; if yes, read m bits, respectively The input bit and the shift register variable are the address index, look up the corresponding lookup table of the input sequence representation part and the corresponding lookup table of the shift register initial state representation part, and then XOR all the search results and save the XOR result; will correspond to each The XOR results of the shift registers are respectively used as the current state of the shift register, and return to step d.

Wherein, between step c and step d, it further includes: judging whether the respectively stored initial state representation part of the shift register or the input sequence representation part needs to be further subdivided, and if necessary, the current storage part is further divided into according to a given condition More than one storage part, and generate a corresponding lookup table for each divided storage part; otherwise, directly execute step d.

The method further includes: pre-setting the conditions that need to be subdivided, and then judging whether subdivision is required is judging whether the subdivision condition is met, and if so, subdivision is required; otherwise, no subdivision is required. Here, the condition for subdividing is: the storage capacity of the respective storage parts divided in step b is greater than a given storage capacity.

If the current storage part is further divided into more than one storage part, then the lookup table corresponding to the input sequence representation part and the lookup table corresponding to the initial state representation part of the shift register described in step d are: respectively search for at least one input sequence representation part The corresponding look-up table and the initial state of one or more shift registers represent partially corresponding look-up tables.

In the above scheme, the content of each storage part can be stored in a table respectively. Additionally, the initial state of each shift register in the CRCn generator is stored in a register, or placed in a vector.

The fast calculation method of the cyclic redundancy check provided by the present invention can obtain in advance the current state of each register used by CRCn under the processing state of different input bits according to the logic structure corresponding to the CRCn generating polynomial currently used The relationship with other registers and input bits generates a corresponding lookup table, so that when performing CRC check, the output of each register in the current state can be directly calculated according to the pre-generated lookup table, thus greatly improving the CRC check The processing speed is reduced, that is, the processing delay of the CRC check is reduced.

The method of the present invention divides the obtained relationship according to the register value and the input bit value, and can further subdivide the divided register part or the input bit part according to the needs or according to the complexity of the algorithm, so that The amount of storage is reduced to varying degrees, and a large processing delay is exchanged for a small storage cost. Moreover, the method of the present invention has considerable flexibility. On the premise of ensuring fast calculation speed, the optimal storage capacity/calculation time configuration can be determined at any time according to specific conditions, and a high degree of parallelism can be realized.

Description of drawings

Fig. 1 is a schematic diagram of the composition structure of a LFSR;

Fig. 2 is a schematic diagram of the parallel CRC architecture;

Fig. 3 is the realization flowchart of the inventive method;

FIG. 4 is a schematic diagram of a logical structure of an embodiment of the present invention;

FIG. 5 is a schematic diagram of the CRC calculation process of the embodiment shown in FIG. 4 .

Detailed ways

The basic idea of the present invention is exactly: according to the logical structure corresponding to the CRCn generator polynomial that adopts at present, obtain in advance under the processing status of different input bits, the state update situation of each shift register used by CRCn is different from other shift registers and Input the relationship between bits, and generate a corresponding look-up table according to the relationship; when performing CRCn check, directly use the pre-generated look-up table to obtain the output of each shift register in the current state.

As shown in Figure 3, the concrete realization process of the inventive method comprises the following steps:

Step 301: Acquire and store the state of each shift register involved in the generator when processing each input bit according to the logic structure of the currently used CRCn generator.

Step 302: From all the states of all shift registers acquired in step 301, extract the state of each shift register of the CRCn generator after processing each bit of the input sequence.

Steps 303-304: Store the initial state representation part and the input sequence representation part of each shift register extracted in step 302 respectively; and use the independent variable contained in each storage part as the address index , to generate a lookup table corresponding to the storage part.

Steps 305-306: When performing CRC check in CRCn mode, first judge whether the current number of bits to be processed is greater than the number m of bits that can be processed each time, if not, then process according to the general serial method in the prior art; If yes, go to step 307.

Steps 307-310: read m-bit information, respectively use the input bit and the shift register variable as the address index, look up the look-up table corresponding to the input sequence representation part and the look-up table corresponding to the shift register initial state representation part, and set all Execute XOR on the search result, save the XOR result; and use the XOR result corresponding to each shift register as the current state of the shift register, and then return to step 305 .

A judgment can also be added between step 304 and step 305 to judge whether the initial state representation part or the input sequence representation part of the shift register respectively stored needs to be further subdivided, and if necessary, the current storage part will be divided according to a given condition It is further divided into more than one storage part, and a corresponding lookup table is generated for each divided storage part. Subdivision conditions can be set in advance, for example: if the storage capacity of the lookup table is greater than a certain value, it will be subdivided. Then, when subdividing, it will be determined how to subdivide according to the given value of the storage capacity. Specifically, the current storage part The storage capacity of the lookup table is 64K, and the given value is 32K, then the current storage part will be further divided into two storage parts. If subdivision is carried out, then step 308, or step 309, or step 308 and step 309 will use the independent variable contained in each storage part as the address index to search the corresponding lookup table, and then XOR all the search results .

For the storage mentioned in each of the above steps, a table can be set for storage. If two tables are divided from a certain table, these two tables can be called sub-tables of the original table.

For the convenience of further describing the fast calculation principle of CRC in the present invention, CRC16 is taken as an example below, and the generator polynomial and logic structure diagram of CRC16 are used as reference.

The generation process of the lookup table adopted by CRC16 includes the following steps:

In the first step , the state of each shift register when processing each input bit is obtained according to the logic structure of the CRC16 generator.

The generator polynomial of CRC16 is shown in formula (1):

g _crc16 (D)＝D ¹⁶ +D ¹² +D ⁵ +1 (1)

The logical structure of CRC16 is shown in Figure 4. The generator of CRC16 includes 16 shift registers R1~R16.  in Figure 4 means modulo 2 addition, that is, XOR. Assume that R1-R16 respectively represent the initial states of the 16 shift registers, and the current input sequence is M, and Mi represents the i-th bit of the input sequence. In this embodiment, the input sequence M consists of 8 bits. That is M1 ~ M8. Then, the state update of each shift register can be obtained according to FIG. 4 each time an input bit is processed, wherein all states of the shift register are represented by the initial states R1-R16 and the input sequence M. The state of each shift register at each moment is specifically shown in Table 1: M1 M2 M3 M4 M5 M6 M7 M8 R16 R15 R14 R13 R12+M1+R16 R11+M2+R15 R10+M3+R14 R9+M4+R13 R8+M5+R12+M1+R16 R15 R14 R13 R12+M1+R16 R11+M2+R15 R10+M3+R14 R9+M4+R13 R8+M5+R12+M1+R16 R7+M6+R11+M2+R15 R14 R13 R12+M1+R16 R11+M2+R15 R10+M3+R14 R9+M4+R13 R8+M5+R12+M1+R16 R7+M6+R11+M2+R15 R6+M7+R10+M3+R14 R13 R12+M1+R16 R11+M2+R15 R10+M3+R14 R9+M4+R13 R8+M5+R12+M1+R16 R7+M6+R11+M2+R15 R6+M7+R10+M3+R14 R5+M1+R16+M8+R9+M4+R13 R12 R11 R10 R9 R8 R7 R6 R5+M1+R16 R4+M2+R15 R11 R10 R9 R8 R7 R6 R5+M1+R16 R4+M2+R15 R3+M3+R14 R10 R9 R8 R7 R6 R5+M1+R16 R4+M2+R15 R3+M3+R14 R2+M4+R13 R9 R8 R7 R6 R5+M1+R16 R4+M2+R15 R3+M3+R14 R2+M4+R13 R1+M5+R12+M1+R16 R8 R7 R6 R5+M1+R16 R4+M2+R15 R3+M3+R14 R2+M4+R13 R1+M5+R12+M1+R16 M1+R16+M6+R11+M2+R15 R7 R6 R5+M1+R16 R4+M2+R15 R3+M3+R14 R2+M4+R13 R1+M5+R12+M1+R16 M1+R16+M6+R11+M2+R15 R15+M2+M7+R10+M3+R14 R6 R5+M1+R16 R4+M2+R15 R3+M3+R14 R2+M4+R13 R1+M5+R12+M1+R16 M1+R16+M6+R11+M2+R15 R15+M2+M7+R10+M3+R14 R14+M3+M8+R9+M4+R13 R5 R4 R3 R2 R1 M1+R16 R15+M2 R14+M3 R13+M4 R4 R3 R2 R1 M1+R16 R15+M R14+M3 R13+M4 R12+M1 2 +R16+M5 R3 R2 R1 M1+R16 R15+M2 R14+M3 R13+M4 R12+M1+R16+M5 R11+M2+R15+M6 R2 R1 M1+R16 R15+M2 R14+M3 R13+M4 R12+M1+R16+M5 R11+M2+R15+M6 R10+M3+R14+M7 R1 R16+M1 R15+M2 R14+M3 R13+M4 R12+M1+R16+M5 R11+M2+R15+M6 R10+M3+R14+M7 R9+M4+R13+M8

Table I

In Table 1, the first column represents 16 shift registers, the first row represents the processed input bit Mi, and correspondingly, the second column is the current state of the 16 shift registers when processing the first input bit M1; the second column To process the current state of the 16 shift registers when processing the second input bit M2, and so on, "+" in the table represents modulo 2 addition.

The specific generation method of the above-mentioned Table 1 includes the following process: First, store the initial states of the 16 shift registers in Figure 4 in the first column of Table 1; then, execute for each input bit: according to the current input bit, use the previous The state of the shift register at a moment and the current input indicate the state of the shift register at the moment until all 8 bits are processed. For example: the current state of the shift register R1 should be equal to the exclusive OR of the current state of the shift register R16 and the input sequence M, and the current state of the shift register R2 is equal to the current state of the shift register R1; another example: according to Figure 4 The current state of the shift register R6 is equal to the current state of the shift register R5 and the current state of the shift register R16 and the XOR result of the input sequence M, and the state of the shift register in the CRC16 generator can be deduced by analogy.

In the second step , the state of each shift register of the CRC16 generator after processing each bit of the input sequence is extracted.

After Table 1 is generated, the state of each shift register after processing 8 input bits can be obtained according to the last column of Table 1, which are represented by R'1~R'16 respectively, and Table 2 is obtained. List of states of the shift register after each bit of the input sequence: R'16 R8+R12+R16+M5+M1 R'15 R7+R11+R15+M2+M6 R'14 R6+R10+R14+M7+M3 R'13 R5+R9+R13+R16+M1+M4+M8 R'12 R4+R15+M2 R'11 R3+R14+M3 R'10 R2+R13+M4 R'9 R1+R12+R16+M1+M5 R'8 R16+R11+R15+M1+M2+M6 R'7 R15+R10+R14+M2+M3+M7 R'6 R14+R9+R13+M3+M8+M4 R'5 R13+M4 R'4 R12+R16+M1+M5 R'3 R11+R15+M2+M6 R'2 R10+R14+M3+M7 R'1 R9+R13+M4+M8

Table II

The third step is to divide the obtained states of each shift register after processing all the bits of the input sequence, and construct a corresponding look-up table.

In order to reduce the amount of storage and simplify the complexity of constructing the lookup table, Table 2 is divided into two sub-tables according to the initial state R1~R16 of the shift register and the input bit sequence M1~M8. Table 3 shows each shift register after processing the input sequence. The state is related to the initial state of other shift registers. Table 4 shows the part of each shift register state related to the input bit sequence after processing the input sequence. R'16 R8+R12+R16 R'15 R7+R11+R15 R'14 R6+R10+R14 R'13 R5+R9+R13+R16 R'12 R4+R15 R'11 R3+R14 R'10 R2+R13 R'9 R1+R12+R16 R'8 R16+R11+R15 R'7 R15+R10+R14 R'6 R14+R9+R13 R'5 R13 R'4 R12+R16 R'3 R11+R15 R'2 R10+R14 R'1 R9+R13

Table three R'16 M5+M1 R'15 M2+M6 R'14 M7+M3 R'13 M1+M4+M8 R'12 M2 R'11 M3 R'10 M4 R'9 M1+M5 R'8 M1+M2+M6 R'7 M2+M3+M7 R'6 M3+M8+M4 R'5 M4 R'4 M1+M5 R'3 M2+M6 R'2 M3+M7 R'1 M4+M8

Table 4

Here, the construction of the corresponding lookup table is to calculate the corresponding values of R'1-R'16 according to the different values of all the independent variables in Table 3 or Table 4. Taking Table 4 as an example, the independent variables in Table 4 are M1-M8. Since each bit of M1-M8 can be 0 or 1, there are 256 different combinations of the values of M1-M8. Then, the specific process of constructing the lookup table is: first list 256 values of M1~M8; The value of R'1~R'16 corresponding to the value; with M1~M8 as the address index, all R'1~R'16 values are stored in the register, and the address of each byte addresses a word; The finally formed 256 values of R'1 to R'16 are the required lookup table. For example: when the value of M1～M8 is 01111010, since R'1 is M4+M8, here M4=1, M8=0, then the calculated value of R'1 is 1; similarly, R'2 is M3+M7 , where M3=1, M7=1, then the value of R'2 is calculated to be 0; the calculation methods of other R'i (i=3, 4...16) are similar and will not be repeated here. If the DSP chip used for processing uses words as the storage unit, no special processing is required; if it uses bytes as the storage unit, it is necessary to expand the 8-bit M address index by 2 times.

The independent variables in Table 3 are R1~R16, and there are ²¹⁶ combinations in total. If directly using R1-R16 as the address index, and storing the corresponding R'1-R'16 in the memory, the storage capacity is 64K words. As for the storage capacity of 64K words, it can be used directly; Table 3 can also be further divided to reduce the storage capacity. If you need to continue to divide Table 3, go to Step 4.

The fourth step is to further refine the part of each shift register state related to the initial state of other shift registers after the input sequence is processed, that is, to further divide Table 3 into two sub-tables, and construct a corresponding lookup table for each sub-table .

Divide the independent variables R1~R16 in Table 3 into two groups R1~R8 and R9~R16. Correspondingly, divide Table 3 into two sub-tables corresponding to the two groups of independent variables: Table 5 and Table 6. Usually, Table 5 uses the independent variables R1~R8 as address indexes, and stores the corresponding R'1~R'16 values in the memory to form a lookup table; Table 6 uses the independent variables R9~R16 as address indexes, and stores the corresponding The values of R'1~R16 are stored in the memory to form a look-up table. R'16 R8 R'15 R7 R'14 R6 R'13 R5 R'12 R4 R'11 R3 R'10 R2 R'9 R1 R'8 0 R'7 0 R'6 0 R'5 0 R'4 0 R'3 0 R'2 0 R'1 0

Table five R'16 R12+R16 R'15 R11+R15 R'14 R10+R14 R'13 R9+R13+R16 R'12 R15 R'11 R14 R'10 R13 R'9 R12+R16 R'8 R16+R11+R15 R'7 R15+R10++R14 R'6 R14+R9+R13 R'5 R13 R'4 R12+R16 R'3 R11+R15 R'2 R10+R14 R'1 R9+R13

  Table 6

In actual operation, if the number of bits of the input sequence M is 16, 32, etc., it is also possible to divide the part of each shift register state related to the input bit sequence after processing the input sequence according to the above-mentioned similar method, and the table Four is further divided into two sub-tables, and a corresponding lookup table is constructed for each sub-table. Here, the process of forming the lookup table is the same as the process of constructing the lookup table described in the third step.

After the above four steps, the required lookup table in this embodiment is constructed. In fact, in this embodiment, Table 5 does not need to construct a lookup table, as long as the address indexes R1-R8 are arithmetically shifted, the corresponding R'1-R'16 can be obtained.

Based on the lookup table constructed above, when checking with CRC16, the calculation process of CRC includes the following steps as shown in Figure 5:

Step 501: Determine whether the number of bits currently to be processed is less than the number m of bits that can be processed each time. In this embodiment, the value of m is 8. If the remaining bits are greater than 8, then perform step 504; otherwise, perform step 502.

Steps 502-503: Perform CRC calculation processing on the remaining bits according to the general serial input method, and read out the value in the shift register, ending the current CRC calculation process.

Step 504: Store the initial state of the shift register shown in FIG. 4 into a 16-bit storage unit R. Here, if implemented by DSP, it can be stored in a register; if implemented by FPGA, it can be stored in a 16-bit vector.

Steps 505-506: Take m bits from the bit stream to be processed and store them in the storage unit M, where m often takes values such as 8 and 16, and takes m=8 in this embodiment. Using M1-M8 as the address index look-up table generated by the look-up table 4, the corresponding R'1-R'16 are obtained and stored in the i-th 16-bit storage unit Ti respectively. If the M table is divided into multiple sub-tables, for example, when M takes values such as 16 and 32, look up the lookup table corresponding to each sub-table, and add the obtained R'1 to R'16 modulo 2 and store them in the storage unit respectively In Ti.

Step 507: Carry out arithmetic shift operation with R1~R8 as the address index, add the word or vector obtained by R'1~R'16 to the value in the corresponding storage unit Ti modulo 2, and then store the result in the corresponding In the storage unit Ti; then use R9-R16 as the address index, look up the look-up table corresponding to Table 6, and perform modulo 2 on the obtained word or vector formed by R'1-R'16 and the value in the corresponding storage unit Ti Add, and the result is stored in the corresponding storage unit Ti.

If there are more sub-tables, such as CRC24 and CRC32, the initial state has a width of 24 and 32 bits. In these cases, look up the lookup tables corresponding to all sub-tables, and compare the currently obtained table entries with the corresponding storage units each time. The value in Ti is added modulo 2, and then stored in the corresponding Ti.

Step 508: Store the values of storage units T1-T16 into R1-R16 as the state of the shift register Ri after m bits are processed, and as the initial state of the shift register Ri in the next stage of CRC calculation, and return to step 501 .

According to the method of the present invention to perform CRC calculation, in terms of performance, if there are T sub-tables, T table lookup operations and T-1 XOR operations need to be performed, and the CRC calculation speed can be accelerated without increasing the complexity. In terms of storage overhead, the storage overhead can be significantly reduced while maintaining the same or even improved performance. Taking 8-bit, 12-bit, 16-bit and 24-bit CRC modes commonly used in 3GPP as an example, when m=8, that is, when 8 input bits are processed each time, the size of each subtable is 256, and the unit is determined by the CRC length. The specific storage overhead is shown in Table 7: CRC mode 8 12 16 twenty four Number of subtables 2 3 3 4 Total table length (bits) 2×2 ⁸ ×8 3×2 ⁸ ×12 3×2 ⁸ ×16 4×2 ⁸ ×24

Table 7

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the protection scope of the present invention.

Claims (7)

1, a kind of fast calculation method of cyclic redundancy check, it is characterized in that, the method comprises the following steps: a. According to the logical structure of the CRCn generator currently used, obtain and store the state of each shift register in the generator when processing each input bit; B. from all the states of all shift registers obtained in step a, extract the state of each shift register in the CRCn generator after processing each bit of the input sequence; and extract each shift register The initial state representation part and the input sequence representation part of the shift register in the state composition are stored separately; c. Using the independent variable included in each storage part as an address index, generate a lookup table corresponding to the storage part; d. When performing CRC check in CRCn mode, judge whether the current number of bits to be processed is greater than the number m of bits that can be processed each time, if not, process in a serial manner; if yes, read m bits, respectively The input bit and the shift register variable are the address index, look up the corresponding lookup table of the input sequence representation part and the corresponding lookup table of the shift register initial state representation part, and then XOR all the search results and save the XOR result; will correspond to each The XOR results of the shift registers are respectively used as the current state of the shift register, and return to step d. 2. The method according to claim 1, characterized in that between step c and step d further includes: judging whether the respectively stored initial state representation part of the shift register or the input sequence representation part needs to be further subdivided, if necessary, Then divide the current storage part into more than one storage part according to a given condition, and generate a corresponding lookup table for each divided storage part; otherwise, directly execute step d. 3. The method according to claim 2, characterized in that the method further comprises: pre-setting the conditions that need to be subdivided, then said judging whether subdivision is required is judging whether the subdivision conditions are met, and if so, needing to subdivision; otherwise no subdivision is required. 4. The method according to claim 3, wherein the condition for performing subdivision is: the storage capacity of the respective storage parts divided in step b is greater than a given storage capacity. 5. The method according to claim 2, wherein if the current storage part is further divided into more than one storage part, the lookup table corresponding to the input sequence representation part in step d and the initial state representation of the shift register Partially corresponding lookup tables are: respectively look up at least one corresponding lookup table for the input sequence representation part and at least one corresponding lookup table for the initial state representation part of the shift register. 6. The method according to claim 1, characterized in that the content of each storage part is stored in a table respectively. 7. The method of claim 1, wherein the initial state of each shift register in the CRCn generator is stored in a register, or placed in a vector.

Images