The cyclic redundancy check (CRC) is a check of the remainder after division in the ring of polynomials over GF(2) (the finite field of integers modulo 2).
That is, the set of polynomials where each coefficient is either zero or one, and arithmetic operations wrap around.
Any string of bits can be interpreted as the coefficients of a polynomial of this sort, and a message has a valid CRC if it divisible by (i.e. is a multiple of) an agreed-on generator polynomial.
CRCs are convenient and popular because they have good error-detection properties and such a multiple may be easily constructed from any message polynomial
is convenient for use of CRCs, the error-detection properties do not make a distinction; errors are detected equally anywhere within
In general, computation of CRC corresponds to Euclidean division of polynomials over GF(2): Here
Using modulo operation, it can be stated that In communication, the sender attaches the
Software implementations sometimes separate the message into its parts and compare the received
to a value reconstructed from the received message, but hardware implementations invariably find the full-length division described above to be simpler.
In practice CRC calculations most closely resemble long division in binary, except that the subtractions involved do not borrow from more significant digits, and thus become exclusive or operations.
A CRC is a checksum in a strict mathematical sense, as it can be expressed as the weighted modulo-2 sum of per-bit syndromes, but that word is generally reserved more specifically for sums computed using larger moduli, such as 10, 256, or 65535.
CRCs can also be used as part of error-correcting codes, which allow not only the detection of transmission errors, but the reconstruction of the correct message.
These codes are based on closely related mathematical principles.
Multiplication is similar (a carry-less product): We can also divide polynomials mod 2 and find the quotient and remainder.
Implementation variations such as endianness and CRC presentation only affect the mapping of bit strings to the coefficients of
These two variations serve the purpose of detecting zero bits added to the message.
Likewise, using a non-zero remainder detects trailing zero bits added to a message.
, appending a zero bit will result in the different remainder
They change the transmitted CRC, so must be implemented at both the transmitter and the receiver.
Both ends must preset their division circuitry to all-ones, the transmitter must add the trailing inversion pattern to the result, and the receiver must expect this pattern when checking the CRC.
These inversions are extremely common but not universally performed, even in the case of the CRC-32 or CRC-16-CCITT polynomials.
This bit string may then be converted to a binary number using one of two conventions: The msbit-first form is often referred to in the literature as the normal representation, while the lsbit-first is called the reversed representation.
happens to be zero, the forms can be distinguished at a glance by seeing which end has the bit set.
For example, the degree-16 CCITT 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): All the well-known CRC generator polynomials of degree
happens to be zero, the forms can be distinguished at a glance by seeing which end has the bit set.
To further confuse the matter, the paper by P. Koopman and T. Chakravarty [1][2] converts CRC generator polynomials to hexadecimal numbers in yet another way: msbit-first, but including the
This "Koopman" representation has the advantage that the degree can be determined from the hexadecimal form and the coefficients are easy to read off in left-to-right order.
The reciprocal of a polynomial generates the same codewords, only bit reversed — that is, if all but the first
Recall that a CRC is the remainder of the message polynomial times
[1] Analysis using bitfilters[1] allows one to very efficiently determine the properties of a given generator polynomial.