Explanation of the CRC calculation steps
- Line the input bits in a row, a0 at the left-most position and aA-1 at the right most position.
- Pad the input bits by L zeros to the right side. L + 1 is the length of the polynomial.
- Divide the padded bits with the coefficients of the polynomial. The remainder are the CRC bits. The division steps are listed in table below:
|Polynomial coefficients||Input data||Padding|
Denote the input bits to the CRC computation by a0, a1, a2, a3, ..., aA-1, and the parity bits by p0, p1, p2, p3, ..., pL-1, where A is the size of the input sequence and L is the number of parity bits. The parity bits are generated by one of the following cyclic generator polynomials:
- - gCRC24A(D)=[D24+D23+D18+D17+D14+D11+D10+D7+D6+D5+D4+D3+D1+1] for a CRC length L=24;
- - gCRC24B(D)=[D24+D23+D6+D5+D1+1] for a CRC length L=24;
- - gCRC24C(D)=[D24+D23+D21+D20+D17+D15+D13+D12+D8+D4+D2+D+1] for a CRC length L=24;
- - gCRC16(D)=[D16+D12+D5+1] for a CRC length L=16;
- - gCRC11(D)=[D11+D10+D9+D5+1] for a CRC length L=11;
- - gCRC6(D)=[D6+D5+1] for a CRC length L=6.
The encoding is performed in a systematic form, which means that in GF(2), the polynomial: a0DA+L-1+a1DA+L-2+...+aA-1DL+p0DL-1+p1DL-2+...+pL-2D1+pL-1 yields a remainder equal to 0 when divided by the corresponding CRC generator polynomial.
The bits after CRC attachment are denoted by b0, b1, b2, b3,..., bB-1 where B = A + L. The relation between ak and bk is:
bk = ak for k = 0,1,2,...,A-1
bk-A = ak for k = A, A+1, A+2, ..., A+L-1
CRC is an error detecting code to detect accidental changes to raw data. Blocks of input data get a short check value attached, based on the remainder of a polynomial division of their contents. Receiver performs the same CRC calculation to detect data corruption. Specification of a CRC code requires definition of a generator polynomial. This polynomial becomes the divisor in a polynomial long division, which takes the input data as the dividend and in which the quotient is discarded and the remainder becomes the result.
Commonly used CRCs employ the Galois field of two elements, GF(2). The two elements are usually called 0 and 1, matching computer architecture.
A CRC is called an n-bit CRC when its check value is n bits long. For a given n, multiple CRCs are possible, each with a different polynomial. Such a polynomial has highest degree n, which means it has n + 1 terms. In other words, the polynomial has a length of n + 1.