Algorithm analysis and program implementation of cyclic redundancy check CRC
School of Computer and Communication Engineering, Southwest Jiaotong University, Liu Dong
The purpose of the abstract communication is to transmit information and reliably to the other party, so that a communication system is required to transmit messages to be reliable and fast, and reliable and fast in digital communication systems is often a pair of contradictions. In order to solve reliability, communication systems use error control. This paper details the error control principle of cyclic redundancy check CRC (Cyclic Redundancy CHECK) and its algorithm implementation.
Keyword communication cycle redundancy check CRC-32 CRC-16 CRC-4
Overview
Reliable and fast in digital communication systems are often a pair of contradictions. If it is required to be fast, it will inevitably make each data symbol occupy the time, the waveform is narrowed, the energy is reduced, thereby increasing the possibility of incorrectly after being interfered, and the reliability of transmitting information is lowered. If reliable is required, the transmission message is slowed down. Therefore, how to reasonably resolve the reliability and speed this pair of contradictions, is one of the key issues that correctly design a communication system. In order to ensure the correctness of the transmission process, it is necessary to perform errors control over the communication process. The most common method of error control is to automatically request the retransmission mode (ARQ), forward error correction mode (FEC) and mixed error correction (HEC). When the transmission process is relatively low, it is ideal with FEC mode. When the transmission process is high, it is easy to "chaos" phenomenon using FEC. HEC mode The combination of ARQ and FEC. In many digital communication, ARQ mode is widely used, and the error control at this time only needs to detect the error. There are many error-controlled methods that implement the error detection function. Traditional: parity, checksum detection, repetition check, expansion code check, row redundancy check, etc., these methods are redundant The balance is sent to the receiving end together. The received data is the same verification, and then the resulting check code is compared to the received check code, if the two consistent, it is considered to be correct. But these methods have their own disadvantages, and the probability of misjudgment is relatively high.
The cycle redundancy check CRC (CYCLIC Redundancy Check) is a branch of the packet line, and its main application is a binary code group. The encoding is simple and the error probability is very low, and a wide range of applications are obtained in the communication system. The following focuses on the principle of CRC verification and its algorithm implementation.
First, the Circulatory Redundancy Rating Code (CRC) CRC check is made of polynomial coding method. The processed data block can be seen as a n-order binary polynomial, by. As an 8-bit binary number 10110101 can be represented as:. The polynomial multiplier operation process is the same as the normal algebraic polynomial. Multi-class add-oriented operations are not in 2 as 2 as the mold, and the addition or subtraction is not in, misplaced, and logical varying or calculation. When using a CRC check, the sender and the receiver use the same generated polynomial G (X), and the first bit of G (x) must be 1. The method of processing the CRC is that the sender removes T (X) by g (x) to obtain the remainder as a CRC check code. When the calibration is calculated as 0, it is determined whether the data frame is wrong. The CRC check can be detected by 100% of all odd random errors and lengths of less than or equal to K (k as g (x) steps). Therefore, the higher the class of the CRC generated polynomial, the smaller the probability of misjudgment. CCITT recommends: 2048 kbit / s PCM base group equipment uses a CRC-4 solution, and the CRC check code used is generated in polynomial G (X) =. With a 16-bit CRC check, it can be guaranteed that only one unspected error is only included in the Bit symbol. In the frame test sequence FCS of the IBM Synchronous Data Link Control Procedure SDLC, use CRC-16, which generates polynomial G (X) =; and the high-grade data link control procedure for ccitt HDLC frame check sequence FCS In, CCITT-16 is used, which generates polynomial g (x) =. CRC-32 generated polynomial g (x) =. The probability of the CRC-32 error is lower than that of CRC-16. Due to the reliability of CRC-32, the CRC-32 is used for important data transmission, so it is widely used in communication, computers. In some UART communication control chips (such as MC6582, Intel8273, and Z80-Si), CRC check code is used for error control; Ethernet card chips, MPEG decoding chips, also using CRC-32 in error control.
Second, the algorithm of CRC check code Analysis The encoding method of the CRC check code is to divide the binary data T (X) to be transmitted to generate a polynomial G (X), and the last remainder is used as the CRC check code. The present steps are as follows: (1) The data block that is sent is the m-bit binary polynomial T (X), (2) generates a poly-based G (x). The end of the data block is added at the end of the data block, and the length of the data block is increased to the M R bit, and (4) The corresponding binary polynomial is. (5) Remove with the generation of polynomial g (x), (6) The remainder is the binary polynomial y (x) of the order of the step of R-1. This binary polynomial y (x) is T (X) to generate a CRC check code encoded by polynomial G (X). (7) Lower Y (x), (8) to obtain binary polynomials with a mode 2. It is a string to be sent to the CRC check code. As can be seen from the CRC encoding rule, the CRC encoding is actually converted to the M-bit binary polynomial T (X) transmitted into a M R bit binary polynomial that can be removed by G (X), so it can be used when decoding The received data removal G (X), if the remaining number is zero, then the transmission process is not error; if the remainder is not zero, there is definitely an error during the transmission process. Many CRC hardware decoding circuits are detected in this way. It can also be seen as a combination of T (X) and CRC check code, so decoding the received binary data removes the R bit data of the tail, which is the original data. In order to understand the encoding process of the CRC check code, the encoding process of the CRC check code is described below with a simple example. Due to the basis of CRC-32, CRC-16, CCITT and CRC-4, only bit numbers and generated polynomial are different. In order to describe simple, an example of CRC encoding is used to illustrate the encoding process of the CRC. The data T (X) of the transmitted data T (X) is 12 bits of binary data 10010001100; the generation polynomial of the CRC-4 is g (x) =, the order R is 4, that is, 10011. First, 4 0 constitutions are added at the end of T (X), and the data block is 1001000111000000. Then use G (x), it is necessary to obtain the remainder y (x). The following table shows the division process. Summary / g (x) / Residual number 0 1 00100000000000000 1001100000000000000 1 1 001100000000000000 1 0011 0 000000000000 2 1 000000 1100 1 0011 0 001100
As can be seen from the table above, the CRC encoding is actually a circular shift model 2 operation. For CRC-4, we assume that there is a 5 bits register, by repeated displacement and CRC division, the value in the final register is the remainder of the value we require. So the above steps can be described below: // REG is a 5 bits register to set the value in the REG 0. Add R piece after the original data is added 0. while (data untreated) Begin IF (REG first 1) REG = REG XOR 0011. Move the value in the REG one bit left, read into a new data and placed in the position of the REGISTER's 0 bit. The last four of EndReg is the remainder we have requested. This algorithm is simple, easy to implement, and G (x) generated in any length is applicable. Under the case where the data is transmitted, it can be used. But if the data block sent is long, this method is not suitable. It can only handle one data at a time, the efficiency is too low. In order to improve the processing efficiency, 4 bits, 8 bits, 16 bits, 32 bits can be treated once. Since the structure of the processor basically supports processing of 8-bit data, the 8 bit is appropriate at a time. In order to have an intuitive understanding of the optimized algorithm, first change the above algorithm to an angle. In the above example, the encoding process can be regarded as the following process: Since it only requires the remainder, we only look at the last four digits. Constructs a four-bit register REG, the initial value is 0, and the data is moved into REG (0 bits), and the data of REG3 is removed from REG. There is a above algorithm that the REG is 0 when the data is 0 when the data is removed; when the transferred data is 0, the REG does not perform XOR operation with G (X), quite equal to 0000 Xor operation. That is to say, REG and what kind of data is determined by XOR removal. Since there is only one bit, there is a choice. The above algorithm can be described below, // reg is a 4 bits register initialization T [] = = {0011,0000} Place the value in the REG 0. Add R pieces after the original data (data is not processed) Begin shifted the value in the REG left, read into a new data and placed in the position of the REGISTER's 0 bit. REG = REG XOR T [The end] The end algorithm is processed in Bit, and the above algorithm can be extended to 8 bits, i.e., by BYTE, ie CRC-32. Constructs a four Byte's register REG, the initial value is 0x00000000, and the data is subjected to REG0 (0 bytes of REG, similar), and the data of REG3 moves out of REG. Push it in the above algorithm class to determine the REG and what data is made by the above algorithm class. Since there are 8 Bit, there is a choice. The above algorithm can be described as follows: // REG is a 4 Byte register initialization T [] = {...} // Total = 256 items set the value in REG 0. Add R / 8 0 bytes after the original data WHILE (Data Unexreed) Begin shifts the value of the REG left one byte to read a new byte and placed in the position of the 0th Byte of REG. REG = REG XOR T [The transferred byte] End algorithm is related to the polynomial division properties.
If a M-bit polynomial T (X) is divided by generating polynomial g (x), each bit (0 =
