The cyclic redundancy check (CRC) is based on division in the ring of polynomials over the finite field GF(2) (the integers modulo 2), that is, the set of polynomials where each coefficient is either zero or one, and arithmetic operations wrap around.
Contents
- Math
- Polynomial arithmetic modulo 2
- Variations
- Reciprocal polynomials
- Error detection strength
- Bitfilters
- References
Any string of bits can be interpreted as the coefficients of a message polynomial of this sort, and to find the CRC, we multiply the message polynomial by
Math
In general, computation of CRC corresponds to Euclidean division of polynomials over GF(2):
Here
In communication, the sender attaches the
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.
Polynomial arithmetic modulo 2
Since the coefficients are constrained to a single bit, any math operation on CRC polynomials must map the coefficients of the result to either zero or one. For example in addition:
Note that
Multiplication is similar:
We can also divide polynomials mod 2 and find the quotient and remainder. For example, suppose we're dividing
In other words,
The division yields a quotient of x2 + 1 with a remainder of −1, which, since it is odd, has a last bit of 1.
In the above equations,
111
,
Variations
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
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
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
These inversions are extremely common but not universally performed, even in the case of the CRC-32 or CRC-16-CCITT polynomials.
All the well-known CRC generator polynomials of degree
The msbit-first form is often referred to in the literature as the normal representation, while the lsbit-first is called the reversed representation. It is essential to use the correct form when implementing a CRC. If the coefficient of
To further confuse the matter, the paper by P. Koopman and T. Chakravarty converts CRC generator polynomials to hexadecimal numbers in yet another way: msbit-first, but including the
Reciprocal polynomials
A reciprocal polynomial is created by assigning the
The most interesting property of reciprocal polynomials, when used in CRCs, is that they have exactly the same error-detecting strength as the polynomials they are reciprocals of. The reciprocal of a polynomial generates the same codewords, only bit reversed — that is, if all but the first
Error detection strength
The error-detection ability of a CRC depends on the degree of its key polynomial and on the specific key polynomial used. The "error polynomial"
(As an aside, there is never reason to use a polynomial with a zero
That is, the CRC of any message with the
The combination of these factors means that good CRC polynomials are often primitive polynomials (which have the best 2-bit error detection) or primitive polynomials of degree
Bitfilters
Analysis Technique using bitfilters allows one to very efficiently determine the properties of a given generator polynomial. The results are the following:
- All burst errors (but one) with length no longer than the generator polynomial can be detected by any generator polynomial
1 + ⋯ + X n n + 1 , whenn is the degree of the generator polynomial (which itself has a length ofn + 1 ). The exception to this result is a bit pattern the same as that of the generator polynomial. - All uneven bit errors are detected by generator polynomials with even number of terms.
- 2-bit errors in a (multiple) distance of the longest bitfilter of even parity to a generator polynomial are not detected; all others are detected. For degrees up to 32 there is an optimal generator polynomial with that degree and even number of terms; in this case the period mentioned above is
2 n − 1 − 1 . Forn = 16 this means that blocks of 32767 bits length do not contain undiscovered 2-bit errors. For uneven number of terms in the generator polynomial there can be a period of2 n − 1 ; however, these generator polynomials (with odd number of terms) do not discover all odd number of errors, so they should be avoided. A list of the corresponding generators with even number of terms can be found in the link mentioned at the beginning of this section. - All single bit errors within the bitfilter period mentioned above (for even terms in the generator polynomial) can be identified uniquely by their residual. So CRC method can be used to correct single-bit errors as well (within those limits, e.g. 32767 bits with optimal generator polynomials of degree 16). Since all odd errors leave an odd residual, all even an even residual, 1-bit errors and 2-bit errors can be distinguished. However, like other SECDED techniques, CRCs cannot always distinguish between 1-bit errors and 3-bit errors. When 3 or more bit errors occur in a block, CRC bit error correction will be erroneous itself and produce more errors.