Computation of cyclic redundancy checks

Computation of a cyclic redundancy check is derived from the mathematics of polynomial division, modulo two. In practice, it resembles long division of the binary message string, with a fixed number of zeroes appended, by the 'generator polynomial' string except that exclusive or operations replace subtractions. Division of this type is efficiently realised in hardware by a modified shift register, and in software by a series of equivalent algorithms, starting with simple code close to the mathematics and becoming faster (and arguably more obfuscated) through byte-wise parallelism and space–time tradeoffs. Computation of a cyclic redundancy check is derived from the mathematics of polynomial division, modulo two. In practice, it resembles long division of the binary message string, with a fixed number of zeroes appended, by the 'generator polynomial' string except that exclusive or operations replace subtractions. Division of this type is efficiently realised in hardware by a modified shift register, and in software by a series of equivalent algorithms, starting with simple code close to the mathematics and becoming faster (and arguably more obfuscated) through byte-wise parallelism and space–time tradeoffs. Various CRC standards extend the polynomial division algorithm by specifying an initial shift register value, a final exclusive OR step and, most critically, a bit ordering (endianness). As a result, the code seen in practice deviates confusingly from 'pure' division, and the register may shift left or right. As an example of implementing polynomial division in hardware, suppose that we are trying to compute an 8-bit CRC of an 8-bit message made of the ASCII character 'W', which is binary 010101112, decimal 8710, or hexadecimal 5716. For illustration, we will use the CRC-8-ATM (HEC) polynomial x 8 + x 2 + x + 1 {displaystyle x^{8}+x^{2}+x+1} . Writing the first bit transmitted (the coefficient of the highest power of x {displaystyle x} ) on the left, this corresponds to the 9-bit string '100000111'. The byte value 5716 can be transmitted in two different orders, depending on the bit ordering convention used. Each one generates a different message polynomial M ( x ) {displaystyle M(x)} . Msbit-first, this is x 6 + x 4 + x 2 + x + 1 {displaystyle x^{6}+x^{4}+x^{2}+x+1} = 01010111, while lsbit-first, it is x 7 + x 6 + x 5 + x 3 + x {displaystyle x^{7}+x^{6}+x^{5}+x^{3}+x} = 11101010. These can then be multiplied by x 8 {displaystyle x^{8}} to produce two 16-bit message polynomials x 8 M ( x ) {displaystyle x^{8}M(x)} . Computing the remainder then consists of subtracting multiples of the generator polynomial G ( x ) {displaystyle G(x)} . This is just like decimal long division, but even simpler because the only possible multiples at each step are 0 and 1, and the subtractions borrow 'from infinity' instead of reducing the upper digits. Because we do not care about the quotient, there is no need to record it.