Abstract: This article first discusses the algorithm algorithm of CRC, and then takes the hardware circuit as an example, through the implementation of the hardware circuit, leads to the bit type algorithm, and finally introduces the byte quick check table algorithm, give the corresponding C language implementation.
Key words: CRC, FCS, generate polynomial, error detection
introduction
The total name of CRC is Cyclic Redundancy Check, the Chinese name is a loop redundancy check. It is an important linear packet code, encoding, and decoding method simple, error detection, and error correction ability, and is widely used in communication fields to implement errors control. In fact, in addition to data communication, CRC is also used in many other fields in other fields. For example, when we read the file on the floppy disk, and when you decompress a zip file, occasionally touch the "Bad CRC" error, whereby it can be slightly spoiled in data storage applications.
The error control theory is based on algebra theory. Here we look at the algorithm and implementation of the CRC, and only the principle can only be described. If you need to further understand the principles of linear code, packet code, cycle code, error correction coding, etc., you can read the relevant information.
The process of detecting the error using the CRC can be simply described as: generates a check-check R bit supervisory code (CRC code) with a certain rule based on the K-bit binary code sequence to be transmitted, and attached to the original information. A new binary code sequence is constituted a total of K R bit, and then send it out. At the receiving end, the verification followed between the information code and the CRC code to determine if the transfer is wrong. This rule is called "generated polynomial" in the error control theory.
General algorithm for 1 generation mathematics
In the algebraic encoding theory, a code group is represented as a polynomial, and each symbols in the code group are as a coefficient of polynomial. For example, 1100101 is represented as 1 · x6 1 · x5 0 · x4 0 · x3 1 · x2 0 · x 1, X6 X5 X2 1.
The original information polynomial before the encoding is set to p (x), the maximum power of 1 equal to K; the generation polynomial is G (x), G (x), the highest power is equal to R; CRC polynomial is R ( x); the encoded information polynomial with CRC is T (X).
Sending party encoding method: P (x) multiplied by XR (ie, the corresponding binary code sequence left shift R bit), then the resulting remaining is R (x). Expressed as T (X) = XRP (X) R (X) by formula
Receiver decoding method: divides t (x) by g (x), if the remainder is 0, then there is no error in the transmission, otherwise the transmission is incorrect.
For example, the information code is 1100, and the polynomial is 1011, which is p (x) = x3 x2, g (x) = x3 x 1, calculating the CRC process is
XRP (x) x3 (x3 x2) x6 x5 x
-------- = ---------- = -------- = (x3 x2 x) --------
G (x) x3 x 1 x3 x 1 x3 x 1
That is, R (x) = x. Note that G (x) maximum power R = 3 is obtained, and the CRC is 010.
If the vertical division is used, the calculation process is
1110
-------
1011/1100000 (1100 left shift 3)
1011
----
1110
1011
-----
1010
1011
-----
0010
0000
----
010
Therefore, T (x) = (x6 x5) (x) = x6 x5 x, that is, 1100000 010 = 1100010 If the transmission is correct,
T (x) x6 x5 x
------ = --------- = x3 x2 x,
G (x) x3 x 1
No blessing. Looking back, look at the above vertical division, if the divided is 1100010, it is obvious that the merchants can be except for the third 1st.
The above estimation process helps us understand the concept of CRC. But directly programmed to achieve the above algorithm, not only cumbersome, efficient is not high. In fact, the CRC will not be calculated and verified directly in the project.
The following table lists some CRC information seeing:
Name Generated Polytelet News * Application Example CRC-4 X4 X 1 ITU G.704 CRC-12 X12 X11 X3 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 X32 X26 X23 ... X2 X 1 04C11DB7 ZIP, RAR, IEEE 802 LAN / FDDI, IEEE 1394, PPP-FCS CRC-32C X32 X28 X27 ... X8 X6 1 1EDC6F41 SCTP
* Generate the maximum power secondary coefficient of polynomial is fixed 1, so in a short release, the highest 1 is unified, such as 04C11DB7 is actually 104C11DB7.
** called CRC-CCITT. The predecessor of ITU is CCITT.
2 implementation method for hardware circuit
A polynomial division, a divided circuit can be achieved. The main body of the divider circuit consists of a set of shift registers and modes 2 adders (alone or units). Taking CRC-ITU as an example, it consists of a 16-level shift register and 3 plus enactment, see the figure below (encoding / decoding sharing). Encoding, the register is initialized to "1" before decoding, and the information bit moves as the clock. When the information bit is all entered, the CRC result is output from the register group.
3 bit type algorithm
The above CRC-ITU division circuit can be simulated using software. Define a register group and initialize all "1". According to the circuit diagram, each input is entered, which is equivalent to a clock pulse from high to low. The pre-shift information bit adds a temporary bit to Bit0, where bit15 is moved into temporary bits, Bit10, and Bit3 also add to a temporary bit. When all the information bits are completed, remove their values 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: The shift register is set to all "1"
Void crcinitregisters ()
{
Regs.val = 0xfffff;
}
// CRC Enter 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;
}
Step by step by step in CRCINPUTBIT, you can simplify:
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 short). Since we are from low to high output bitstream, the 0x1021 is reversed to get 0x8408. Write a polynomial write to g (x) = 1 x5 x12 x16, is it better?
Here is a typical PPP frame. The last two bytes are called FCS (FRME CHECK Sequence), which is the front 11 bytes of CRC.
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;
/// below calculation FCS
// Initialization
CRCINITREGISTERS ();
// By playing, each byte is lower, does not include two FCS bytes
For (i = 0; i <11; i )
{
For (j = 0; j <8; j )
{
CRCINPUTBIT ((PPP [I] >> J) & 1);
}
}
// Get CRC: Reverse the value of the register group
Result = ~ crcgetRegisters ();
// Fill in the FCS, first low
PPP [11] = Result & 0xFF;
PPP [12] = (Result >> 8) & 0xFF;
/// The following verification FCS
// Initialization
CRCINITREGISTERS ();
// By playing, each byte is lower, including two FCS bytes
For (i = 0; i <13; i )
{
For (j = 0; j <8; j )
{
CRCINPUTBIT ((PPP [I] >> 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. Initialization is all "1", and the value of the register group is the requirements of the CRC-ITU. In fact, regardless of the initialization of "1" or "0", calculate the CRC reflective or not, the resulting verification result is 0.
4-byte algorithm
The bit type algorithm is inclined by bit, the efficiency is relatively low, and it is not suitable for high-speed communication. Digital communication system (various communication standards) is typically a CRC check for one frame data, and byte is the basic unit of the frame. The most commonly used is a fast algorithm for byte check. This algorithm is based on the fact that the CRC code after this byte is calculated, equal to the low 8 bit left shift 8 bits of the previous one-by-case CRC code, plus the previous byte CRC to move 8 bits and this byte. The CRC code obtained later. If we calculate all the 8-bit binary CRC (a total of 256), placed in a table, when encoding, as long as you find the corresponding value from the table, you can process it.
The calculation algorithm of CRC-ITU is as follows:
a. Register group initializes "1" (0xfffff).
b. The register group moves one byte to the right.
c. The byte that is just removed is different or the data byte, and the index of a pointing value table is obtained.
d. Table values referred to indexes are different or the register groups.
f. Data pointer plus 1, if the data is not completely processed, then repeat step b.
g. Register assembly retrore, get the CRC, which is attached to the data.
The CRC-ITU's verification algorithm is as follows:
a. Register group initializes "1" (0xfffff).
b. The register group moves one byte to the right.
c. The byte that is just removed is different or the data byte, and the index of a pointing value table is obtained.
d. Table values referred to indexes are different or the register groups.
e. Data pointer 1, if the data is not completely processed, then step B (the data includes two bytes of the CRC).
f. Whether the value of the register group is equal to "magic value" (0xf0b8), if the phase is equal, otherwise it will fail.
Below is a universal CRC-ITU lookup table and the C language program for calculating and verifying 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, 0x555bd, 0xad4a, 0xbcc3, 0x8e58, 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, 0xcc5c, 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, 0x38cb, 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, 0x2B1Ab, 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 = 0xfffff; // Initialization
While (NLENGTH> 0)
{
FCS = (FCS >> 8) ^ CRCTAB16 [(FCS ^ * PDATA) & 0xFF];
NLENGTH -;
PDATA ;
}
Return ~ fcs; //
}
// Check that the 16-bit CRC of the given length data is correct.
Bool Iscrc16Good (const byte * pdata, int NLENGTH)
{
U16 FCS = 0xfffff; // Initialization
While (NLENGTH> 0)
{
FCS = (FCS >> 8) ^ CRCTAB16 [(FCS ^ * PDATA) & 0xFF];
NLENGTH -;
PDATA ;
}
Return (FCS == 0xf0b8); // 0xf0b8 is "Magic Value" of CRC-ITU
}
Use the byte type algorithm, the PPP frame FCS calculation and verification process, which appears in front, can be implemented with the following program segment:
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 the FCS, first low
PPP [11] = Result & 0xFF;
PPP [12] = (Result >> 8) & 0xFF;
// Verify FCS
IF (ISCRC16GOOD (PPP, 13))
{
...
}
The data length in this example is 11, indicating that the CRC calculation does not require data 2 bytes or 4 bytes aligned.
As for the generation algorithm of the lookup table, and the algorithm of other CRCs such as CRC-32, 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 different protocols, the initialization, shift order, verification methods, and the like may be different.
Conclusion
CRC is one of the important technologies in the field of modern communications. Master the algorithm and implementation method of CRC, play a large role in the design of the communication system, the analysis of the communication protocol, and software protection. For example, in a multi-gate data transmission system designed by the author, each serial port rate is 460kbps, the error rate is greater than 10-6 without the calibration, and the performance improvement in the simple parity is not obvious, using the CRC The error retransmission, the bit error rate is reduced to 10-15 or less, meet the requirements of practical applications.
references
1. Simpson, W., Editor, "The Point-to-Point Protocol (PPP)", STD 51, RFC 1661, 19942. J. Stone, "Stream Control Transmission Protocol (SCTP) Checksum Change, RFC 3309, 20023 . J. Satran, "Internet Protocol Small Computer System Interface (iSCSI) Cyclic Redundancy Check (CRC) / Checksum Considerations", RFC 3385, 20024. International Standardization, "High-level data link control (HDLC) procedures", ISO / IEC 3309, 19925. ITU-T v.41, "Code-Independent Error-Control System", 19896. Guo Yuyun, "Data Transmission (Revised)", People's Posts Publishing House, 1998 [Related Resources] ◆ RFC / STD Document : Internet FAQ Archives ◆ ITU Official Website: http://www.itu.int/HOME/index.html ◆ BHW98 column: http://www.9cbs.net/develop/author/netauthor/bhw98/
First release: 2003-04-10 Last revision: 2003-04-10
