Mathematics of CRC - Variations

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 and, and do not impact the properties of the algorithm.

• 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 is zero, the check passes. This works because the codeword is, which is always divisible by .

This simplifies many implementations by avoiding the need to treat the last few bytes of the message specially when checking CRCs.

• The shift register may be initialized with ones instead of zeroes. This is equivalent to inverting the first bits of the message feeding them into the algorithm. The CRC equation becomes, where is the length of the message in bits. The change this imposes on is a function of the generating polynomial and the message length, .

The reason this method is used is because an unmodified CRC does not distinguish between two messages which differ only in the number of leading zeroes, because leading zeroes do not affect the value of . When this inversion is done, the CRC does distinguish between such messages.

• The CRC may be inverted before being appended to the message stream. While an unmodified CRC distinguishes between messages with different numbers of trailing zeroes, it does not detect trailing zeroes appended after the CRC remainder itself. This is because all valid codewords are multiples of, so times that codeword is also a multiple. (In fact, this is precisely why the first variant described above works.)

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 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, called the check polynomial, residue or magic number. This may be computed as, or equivalently by computing the unmodified CRC of a message consisting of ones, .

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