To check the CRC, instead of calculating the CRC on the message and comparing it to the CRC, a CRC calculation may be run on the entire codeword. If the result (called the residual) is zero, the check passes. This works because the codeword is $M(x)\cdot x^{n}-R(x)=Q(x)\cdot G(x)$ , which is always divisible by $G(x)$ .

There are several standard variations on CRCs, any or all of which may be used with any CRC polynomial. Implementation variations such as endianness and CRC presentation only affect the mapping of bit strings to the coefficients of $M(x)$ and $R(x)$ , and do not impact the properties of the algorithm.

In practice, the last two variations are invariably used together. They change the transmitted CRC, so must be implemented at both the transmitter and the receiver. While presetting the shift register to ones is straightforward to do at both ends, inverting affects receivers implementing the first variation, because the CRC of a full codeword that already includes a CRC is no longer zero. Instead, it is a fixed non-zero pattern, the CRC of the inversion pattern of $n$ ones.

The CRC thus may be checked either by the obvious method of computing the CRC on the message, inverting it, and comparing with the CRC in the message stream, or by calculating the CRC on the entire codeword and comparing it with an expected fixed value $C(x)$ , called the check polynomial, residue or magic number. This may be computed as $C(x)=\left(\sum _{i=n}^{2n-1}x^{i}\right)\,{\bmod {\,}}G(x)$ , or equivalently by computing the unmodified CRC of a message consisting of $n$ ones, $M(x)=\sum _{i=0}^{n-1}x^{i}$ .

These inversions are extremely common but not universally performed, even in the case of the CRC-32 or CRC-16-CCITT polynomials.

Reversed representations and reciprocal polynomials[edit]

Polynomial representations[edit]

Example of CCITT 16-bit Polynomial in the forms described (bits inside square brackets are included in the word representation; bits outside are implied 1 bits; vertical bars designate nibble boundaries):

Because a CRC is based on division, no polynomial can detect errors consisting of a string of zeroes prepended to the data, or of missing leading zeroes. However, see .

Variations

All single bit errors will be detected by any polynomial with at least two terms with non-zero coefficients. The error polynomial is $x^{k}$ , and $x^{k}$ is divisible only by polynomials $x^{i}$ where $i\leq k$ .

All two bit errors separated by a distance less than the of the primitive polynomial which is a factor of the generator polynomial will be detected. The error polynomial in the two bit case is $E(x)=x^{i}+x^{k}=x^{k}\cdot (x^{i-k}+1),\;i>k$ . As noted above, the $x^{k}$ term will not be divisible by the CRC polynomial, which leaves the $x^{i-k}+1$ term. By definition, the smallest value of ${i-k}$ such that a polynomial divides $x^{i-k}+1$ is the polynomial's order or exponent. The polynomials with the largest order are called primitive polynomials, and for polynomials of degree $n$ with binary coefficients, have order $2^{n}-1$ .

order

All errors in an odd number of bits will be detected by a polynomial which is a multiple of $x+1$ . This is equivalent to the polynomial having an even number of terms with non-zero coefficients. This capacity assumes that the generator polynomial is the product of $x+1$ and a primitive polynomial of degree $n-i$ since all primitive polynomials except $x+1$ have an odd number of non-zero coefficients.

All of length $n$ will be detected by any polynomial of degree $n$ or greater which has a non-zero $x^{0}$ term.

Reversed representations and reciprocal polynomials[edit]

Polynomial representations[edit]

Variations

order

burst errors

Barrett reduction

Error correcting code

List of checksum algorithms

Parity (telecommunication)

Polynomial representations of cyclic redundancy checks