CRC algorithm and implementation BHW98 [original] Keyword CRC, FCS, generated polynomial, detection and wrong retaining, this article first discusses the algebraic algorithm of CRC, then use common CRC-ITU as an example, through the implementation of the hardware circuit, The bit type algorithm is taken out, and finally, the byte speed checklist is introduced, and the corresponding C language is given. Key words: CRC, FCS, generated polynomial, error detection Revitalization Introduction CRC's full name Cyclic Redundancy Check, Chinese name is a cyclic 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. The general algorithm of 1 generation mathematics is represented in an algebraic coding theory, and a code group is represented as a polynomial, and each symbol in the code group is 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). The formula is represented as a T (X) = XRP (X) R (X) receiver decoding method: divides T (X) divided by g (x), if the remainder is 0, then there is no error in the transmission, otherwise 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 process of CRC 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 class 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 of hardware circuitry polynomial division, can be implemented by dividing circuits. 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 CRC-ITU divider circuit, which 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 We 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. The 4-byte algorithm bit type algorithm is based on a bit by bit, and 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 Class C language program for computing and verify 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, 0x2010, 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, 0x0e70, 0x1ff9, 0xf78f, 0xe606, 0x229d, 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 = 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 can be used 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))
{
...
}
