CRC Algorithm and Implementation

1234

CRC Algorithm and Implementation [Copy link]

CRC Algorithm and Implementation

Abstract: This paper first discusses the algebraic algorithm of CRC, then takes the common CRC-ITU as an example, introduces the bit-type algorithm through the implementation of hardware circuit, and finally focuses on the byte-type fast table lookup algorithm and gives the corresponding C language implementation.

Keywords: CRC, FCS, generator polynomial, error detection and retransmission

introduction

CRC stands for Cyclic Redundancy Check. It is an important type of linear block code with simple encoding and decoding methods and strong error detection and correction capabilities. It is widely used in the field of communication to achieve error control. In fact, in addition to data communication, CRC is also very useful in many other fields. For example, when we read files on a floppy disk or decompress a ZIP file, we occasionally encounter a "Bad CRC" error, which shows its application in data storage.

Error control theory is built on the basis of algebraic theory. Here we focus on introducing the algorithm and implementation of CRC, and can only briefly explain the principle. If you need to further understand the principles of linear codes, block codes, cyclic codes, error correction codes, etc., you can read relevant materials.

The process of using CRC for error detection can be simply described as follows: at the sending end, according to the k-bit binary code sequence to be transmitted, an r-bit supervision code (CRC code) is generated for verification according to certain rules, attached to the original information, forming a new binary code sequence of k+r bits, and then sent out. At the receiving end, according to the rules followed by the information code and the CRC code, a check is performed to determine whether there is an error in the transmission. This rule is called a "generating polynomial" in error control theory.

1 General Algorithms in Algebra

In algebraic coding theory, a code group is represented as a polynomial, and each code element in the code group is regarded as the coefficient of the polynomial. For example, 1100101 is represented as
1·x ⁶ +1· x ⁵ +0· x ⁴ +0·x ³ +1·x ² +0·x+1, that is, x ⁶ +x ⁵ +x ² +1.

Suppose the original information polynomial before encoding is P(x), the highest power of P(x) plus 1 is equal to k; the generating polynomial is G(x), the highest power of G(x) is equal to r; the CRC polynomial is R(x); the encoded information polynomial with CRC is T(x).

The encoding method of the sender is: multiply P(x) by xr (i.e. the corresponding binary code sequence is shifted left by r bits), and then divide it by G(x). The remainder is R(x). It can be expressed as
T(x)=x ^r P(x)+R(x)

The receiving party's decoding method is: divide T(x) by G(x). If the remainder is 0, it means that no error occurred in the transmission, otherwise it means that the transmission is erroneous.

For example, suppose the information code is 1100 and the generating polynomial is 1011, that is, P(x)=x ³ +x ² , G(x)=x ³ +x+1, the process of calculating CRC is

x r P(x) x 3 (x 3 +x 2 ) x 6 +x 5 x 
-------- = ---------- = -------- = (x 3 +x 2 +x) + -------- 
G(x) x 3 +x+1 x 3 +x+1 x 3 +x+1
 

That is, R(x)=x. Note that the highest power of G(x) is r=3, and the CRC is 010.

If we use vertical division, the calculation process is

1110 
------- 
1011 /1100000 (1100 shifted left 3 bits) 
1011 
---- 
1110 
1011 
----- 
1010 
1011 
----- 
0010 
0000 
---- 
010 
Therefore, T(x)=(x 6 +x 5 )+(x)=x 6 +x 5 +x, i.e. 1100000+010=1100010

If the transmission is correct,

T(x) x 6 +x 5 +x 
------ = --------- = x 3 +x 2 +x, 
G(x) x 3 +x+1
 

No remainder. Looking back at the vertical division above, if the dividend is 1100010, it is obviously divisible when the quotient is the third 1.

The above calculation process helps us understand the concept of CRC. However, directly implementing the above algorithm through programming is not only cumbersome but also inefficient. In fact, CRC is not directly calculated and verified in this way in engineering.

The following table lists some CRC information found in the standard:

name	Generating polynomials	Abbreviated *	Application Examples
CRC-4	x 4 +x+1		ITU G.704
CRC-12	x 12 +x 11 +x 3 +x+1
CRC-16	x16 + x12 + x2 + 1	1005	IBM SDLC
CRC-ITU **	x16 + x12 + x5 + 1	1021	ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS
CRC-32	x 32 +x 26 +x 23 +...+x 2 +x+1	04C11DB7	ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS
CRC-32c	x 32 +x 28 +x 27 +...+x 8 +x 6 +1	1EDC6F41	SCTP

* The highest power coefficient of the generator polynomial is fixed at 1, so in the shorthand, the highest 1 is removed, such as 04C11DB7 is actually 104C11DB7.

** Formerly known as CRC-CCITT. The predecessor of ITU is CCITT.

1234

2 Implementation method of hardware circuit Polynomial division can be realized by using a division circuit. The main body of the division circuit consists of a group of shift registers and modulo-2 adders (XOR units). Taking CRC-ITU as an example, it consists of 16-stage shift registers and 3 adders, as shown in the figure below (shared for encoding/decoding). Before encoding and decoding, each register is initialized to "1", and the information bit is shifted in with the clock. When all the information bits are input, the CRC result is output from the register group.

1234

The CRC-ITU division circuit above can be completely simulated by software. Define a register group and initialize it to all "1". According to the circuit diagram, each input of an information bit is equivalent to the arrival of a clock pulse, which shifts from high to low. Before the shift, the information bit is added to bit0 to generate a temporary bit, of which bit15 is shifted into the temporary bit, and bit10 and bit3 are also added with temporary bits. When all the information bits are input, their values are taken out from the register group, which is the CRC code. typedef unsigned char bit; typedef unsigned char byte; typedef unsigned short u16; typedef union { u16 val; struct { u16 bit0 : 1; u16 bit1 : 1; u16 bit2 : 1; u16 bit3 : 1; u16 bit4 : 1; u16 bit5 : 1; u16 bit6 : 1; u16 bit7 : 1; u16 bit8 : 1; u16 bit9 : 1; u16 bit10 : 1; u16 bit11 : 1; u16 bit12 : 1; u16 bit13 : 1; u16 bit14 : 1; u16 bit15 : 1; } bits; } CRCREGS; // Register group CRCREGS regs; // Initialize the CRC register group: set the shift register to all "1" void crcInitRegisters() { regs.val = 0xffff; } // CRC input a bit void crcInputBit(bit in) { bit a; a = regs.bits.bit0 ^ in; regs.bits.bit0 = regs.bits.bit1; regs.bits.bit1 = regs.bits.bit2; regs.bits.bit2 = regs.bits.bit3; regs.bits.bit3 = regs.bits.bit4 ^ a; regs.bits.bit4 = regs.bits.bit5; regs.bits.bit5 = regs.bits.bit6; regs.bits.bit6 = regs.bits.bit7; regs.bits.bit7 = regs.bits.bit8; regs.bits.bit8 = regs.bits.bit9; regs.bits.bit9 = regs.bits.bit10; regs.bits.bit10 = regs.bits.bit11 ^ a; regs.bits.bit11 = regs.bits.bit12; regs.bits.bit12 = regs.bits.bit13; regs.bits.bit13 = regs.bits.bit14; regs.bits.bit14 = regs.bits.bit15; regs.bits.bit15 = a; } // Output CRC code (value of register group) u16 crcGetRegisters() { return regs.val; } The step-by-step shift/XOR operation in crcInputBit can be simplified: void crcInputBit(bit in) { bit a; a = regs.bits.bit0 ^ in; regs.val >>= 1; if(a) regs.val ^= 0x8408; } If you are careful, you can find the relationship between 0x8408 and 0x1021 (CRC-ITU shorthand). Since we output the bit stream from low to high, we can get 0x8408 by reversing 0x1021 left and right. Write the generating polynomial as G(x)=1+x5+x12+x16. Doesn't it look better? The following is a typical PPP frame. The last two bytes are called FCS (Frame Check Sequence), which is the CRC of the previous 11 bytes. FF 03 C0 21 04 03 00 07 0D 03 06 D0 3A Let's calculate the CRC of this PPP frame and verify it. byte ppp[13] = {0xFF, 0x03, 0xC0, 0x21, 0x04, 0x03, 0x00, 0x07, 0x0D, 0x03, 0x06, 0x00, 0x00}; int i,j; u16 result; /////////// Calculate FCS // Initialize crcInitRegisters(); // Input bit by bit, low bit first, excluding the two FCS bytesfor(i = 0; i < 11; i++) { for(j = 0; j < 8; j++) { crcInputBit((ppp >> j) & 1); } } // Get CRC: invert the value of the register groupresult = ~crcGetRegisters(); // Fill in FCS, low bit first then high bitpp[11] = result & 0xff; ppp[12] = (result >> 8) & 0xff; //////////// The following verifies FCS // Initialize crcInitRegisters(); // Input bit by bit, with the low bit of each byte first, including two FCS bytes for(i = 0; i < 13; i++) { for(j = 0; j < 8; j++) { crcInputBit((ppp >> j) & 1); } } // Get the verification result result = crcGetRegisters(); It can be seen that the calculated CRC is equal to 0x3AD0, which is the same as the original FCS. The verification result is equal to 0. Initializing to all "1" and negating the value of the register group to obtain the CRC are both requirements of CRC-ITU. In fact, whether it is initialized to all "1" or all "0", and whether the CRC is negated or not, the verification result is 0.

1234

4 Byte-based algorithms Bit-based algorithms perform operations bit by bit, which is inefficient and not suitable for high-speed communication. Digital communication systems (various communication standards) generally perform CRC checks on a frame of data, and bytes are the basic units of frames. The most commonly used is a fast algorithm that looks up a table by byte. This algorithm is based on the fact that the CRC code after calculating this byte is equal to the CRC code obtained by shifting the lower 8 bits of the remainder CRC code of the previous byte left by 8 bits, plus the CRC code obtained by shifting the previous byte right by 8 bits and the sum of this byte. If we calculate all the CRCs of 8-bit binary serial numbers (a total of 256) and put them in a table, when encoding, we only need to look up the corresponding value from the table for processing. The calculation algorithm of CRC-ITU is as follows: a. The register group is initialized to all "1" (0xFFFF). b. The register group is shifted right by one byte. c. The byte just shifted out is XORed with the data byte to obtain an index pointing to the value table. d. The table value pointed to by the index is XORed with the register group. f. The data pointer is incremented by 1. If the data has not been processed completely, repeat step b. g. The register group is inverted to obtain the CRC, which is appended to the data. The verification algorithm of CRC-ITU is as follows: a. The register group is initialized to all "1" (0xFFFF). b. The register group is shifted one byte to the right. c. The byte just shifted out is XORed with the data byte to obtain an index pointing to the value table. d. The table value pointed to by the index is XORed with the register group. e. The data pointer is incremented by 1. If the data has not been processed completely, repeat step b (the data includes two bytes of CRC). f. Is the value of the register group equal to the "Magic Value" (0xF0B8)? If so, it passes, otherwise it fails. Below is a generic CRC-ITU lookup table and a C program to calculate and verify the CRC: // CRC-ITU lookup table const u16 crctab16[] = { 0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf, 0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7, 0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e, 0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876, 0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd, 0xad4a, 0xbcc3, 0 x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5, 0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c, 0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974, 0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb, 0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3, 0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a, 0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72, 0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9, 0xef4e, 0xfec7, 0 xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1, 0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738, 0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70, 0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7, 0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff, 0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036, 0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e, 0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5, 0x2942, 0x38 cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd, 0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134, 0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c, 0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3, 0x4a44 , 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb, 0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232, 0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a, 0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1 , 0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9, 0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330, 0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78, }; // Calculate the 16-bit CRC of the given length data. u16 GetCrc16(const byte* pData,int nLength) { u16 fcs = 0xffff; // Initialize while(nLength>0) { fcs = (fcs >> 8) ^ crctab16[(fcs ^ *pData) & 0xff]; nLength--; pData++; } return ~fcs; // Negate } // Check if the 16-bit CRC of the given length data is correct. bool IsCrc16Good(const byte* pData, int nLength) { u16 fcs = 0xffff; // Initialize while(nLength>0) { fcs = (fcs >> 8) ^ crctab16[(fcs ^ *pData) & 0xff]; nLength--; pData++; } return (fcs == 0xf0b8); // 0xf0b8 is the "Magic Value" of CRC-ITU } Using the byte algorithm, the PPP frame FCS calculation and verification process mentioned above can be implemented with the following program fragment: byte ppp[13] = {0xFF, 0x03, 0xC0, 0x21, 0x04, 0x03, 0x00, 0x07, 0x0D, 0x03, 0x06, 0x00, 0x00}; u16 result; // Calculate CRC result = GetCrc16(ppp, 11); // Fill in FCS, low first then high ppp[11] = result & 0xff; ppp[12] = (result >> 8) & 0xff; // Verify FCS if(IsCrc16Good(ppp, 13)) { ... ... } In this example, the data length is 11, which means that CRC calculation does not require 2-byte or 4-byte alignment of data. As for the generation algorithm of the lookup table, as well as the algorithms of other CRCs such as CRC-32, please refer to RFC 1661, RFC 3309 and other documents. It should be noted that although the essence of the CRC algorithm is the same, the initialization, shift order, verification method, etc. specified by different protocols and standards may be different. Conclusion CRC is one of the important technologies in the field of modern communications. Mastering the algorithm and implementation method of CRC can play a great role in many aspects such as the design of communication systems, analysis of communication protocols and software protection. For example, in a multi-serial port data transmission system designed by the author, the rate of each serial port is 460kbps. The bit error rate is greater than 10-6 without verification. After adding a simple parity check, the performance improvement is not obvious. By using CRC for error detection and retransmission, the bit error rate is reduced to below 10-15, which meets the requirements of practical applications. References 1. Simpson, W., Editor, "The Point-to-Point Protocol (PPP)", STD 51, RFC 1661, 1994 2. J. Stone, "Stream Control Transmission Protocol (SCTP) Checksum Change", RFC 3309, 2002 3. J. Satran, "Internet Protocol Small Computer System Interface (iSCSI) Cyclic Redundancy Check (CRC)/Checksum Considerations", RFC 3385, 2002 4. International Standardization,"High-level data link control (HDLC) procedures", ISO/IEC 3309, 1992 5. ITU-T V.41, "Code-independent error-control system", 1989 6. Guo Tiyun et al., "Data Transmission (Revised Edition)", Posts and Telecommunications Press, 1998"High-level data link control (HDLC) procedures", ISO/IEC 3309, 1992 5. ITU-T V.41, "Code-independent error-control system", 1989 6. Guo Tiyun et al., "Data Transmission (Revised Edition)", Posts and Telecommunications Press, 1998"High-level data link control (HDLC) procedures", ISO/IEC 3309, 1992 5. ITU-T V.41, "Code-independent error-control system", 1989 6. Guo Tiyun et al., "Data Transmission (Revised Edition)", Posts and Telecommunications Press, 1998