(Transfer from http://www.equn.com/forum/viewthread.php?tid=5470&sid=3rrqvomr)
The basic idea of CRC check code is to utilize linear encoding theory, generate a check-in monitoring code (both CRC code) R bit according to a certain rule based on the K bit binary code sequence to be transmitted, and attached to information Rear, constitute a new binary code sequence number (k r) bit, and finally send it. At the receiving end, the verification is performed based on the rules followed between the information code and the CRC code to determine if there is an error in the transfer. In the field of data storage and data communication, the CRC is ubiquitous: the FCS (frame error sequence) of the famous communication protocol X.25 is CRC. CCITT, ARJ, LHA and other compression tool software adopted CRC32, disk drive The read and write uses CRC16, universal image storage formats GIF, TIFF, etc. also use CRC as an error mean. The essence of the CRC is the remainder of the mold-2 division, and the divisor is divided, and the type of CRC is different. Typically, the divisor of the CRC is represented by a generated polynomial. The most commonly used CRC code generation polynomial has CRC16, CRC32. Take CRC16 as an example, the rule generated by the 16-bit CRC code is to move the number of binary sequences to be transmitted to 16 bits (two by 2 ^ 16), then except With a polynomial, the remainder obtained is both a CRC code, as shown in the following formula, wherein K (x) represents the N-bit number, g (x) is a polynomial, Q (X) is an integer, R (X) is The remainder (both CRC code). K (x) >> 16 = g (x) q (x) r (x) Searching the CRC code to use the model 2 decreasement algorithm, which is both bits and subtraction, subtraction, subtraction, subtraction, such plus In practice, the reduction is actually logical, the equivalent, multiplication and subtraction equivalence, multiplication and division operations are the same as the general algebraic multi-process method, which is in line with the same law. The polynomial of the generated CRC code is as follows, where CRC-16 and CRC-CCIT are generated by 16-bit CRC code, and the CRC-32 generates a 32-bit CRC code receiver will receive the binary sequence (including information code and CRC). Code) divided by polynomial, if the remainder is 0, then there is no error in the transmission, otherwise the transmission is incorrect, and the principle is no longer described here. When calculating the CRC code with the software, the recipient can ask the received information code code code, the comparison result, and whether the received CRC code is the same. CCITT recommended advanced data link control procedure HDLC frame test sequence FCS, using CCITT-16, CRC16, generated polynomial for g (x) = x16 x12 x5 1, CRC-32 generated polynomial for g (x) = x32 x26 x23 x22 x16 x11 x10 x16 x8 x7 x5 x4 x2 x 1
