Computation of CRC - Implementation

Implementation

Writing out the full message at each step, as done in the example above, is very tedious. Efficient implementations use an -bit shift register to hold only the interesting bits. Multiplying the polynomial by is equivalent to shifting the register by one place, as the coefficients do not change in value but only move up to the next term of the polynomial.

Here is a first draft of some pseudocode for computing an n-bit CRC. It uses a contrived composite data type for polynomials, where x is not an integer variable, but a constructor generating a Polynomial object that can be added, multiplied and exponentiated. To xor two polynomials is to add them, modulo two; that is, to exclusive OR the coefficients of each matching term from both polynomials.

function crc(bit array bitString, int len) { remainderPolynomial := polynomialForm(bitString) // First n bits of the message // A popular variant complements remainderPolynomial here for i from 1 to len { remainderPolynomial := remainderPolynomial * x + bitString * x0 // Define bitString=0 for k>len if coefficient of xn of remainderPolynomial = 1 { remainderPolynomial := remainderPolynomial xor generatorPolynomial } } // A popular variant complements remainderPolynomial here return remainderPolynomial }

Code fragment 1: Simple polynomial division

Note that this example code avoids the need to specify a bit-ordering convention by not using bytes; the input bitString is already in the form of a bit array, and the remainderPolynomial is manipulated in terms of polynomial operations; the multiplication by could be a left or right shift, and the addition of bitString is done to the coefficient, which could be the right or left end of the register.

This code has two disadvantages. First, it actually requires an n+1-bit register to hold the remainderPolynomial so that the coefficient can be tested. More significantly, it requires the bitString to be padded with n zero bits.

The first problem can be solved by testing the coefficient of the remainderPolynomial before it is multiplied by .

The second problem could be solved by doing the last n iterations differently, but there is a more subtle optimization which is used universally, in both hardware and software implementations.

Because the XOR operation used to subtract the generator polynomial from the message is commutative and associative, it does not matter in what order the various inputs are combined into the remainderPolynomial. And specifically, a given bit of the bitString does not need to be added to the remainderPolynomial until the very last instant when it is tested to determine whether to xor with the generatorPolynomial.

This eliminates the need to preload the remainderPolynomial with the first n bits of the message, as well:

function crc(bit array bitString, int len) { remainderPolynomial := 0 // A popular variant complements remainderPolynomial here for i from 1 to len { remainderPolynomial := remainderPolynomial xor (bitstring * xn-1) if (coefficient of xn-1 of remainderPolynomial) = 1 { remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial } else { remainderPolynomial := (remainderPolynomial * x) } } // A popular variant complements remainderPolynomial here return remainderPolynomial }

Code fragment 2: Polynomial division with deferred message XORing

This is the standard bit-at-a-time hardware CRC implementation, and is well worthy of study; once you understand why this computes exactly the same result as the first version, the remaining optimizations are quite straightforward. If remainderPolynomial is only n bits long, then the coefficients of it and of generatorPolynomial are simply discarded. This is the reason that you will usually see CRC polynomials written in binary with the leading coefficient omitted.

In software, it is convenient to note that while one may delay the xor of each bit until the very last moment, it is also possible to do it earlier. It is usually convenient to perform the xor a byte at a time, even in a bit-at-a-time implementation like this:

function crc(byte array string, int len) { remainderPolynomial := 0 // A popular variant complements remainderPolynomial here for i from 1 to len { remainderPolynomial := remainderPolynomial xor polynomialForm(string) * xn-8 for j from 1 to 8 { // Assuming 8 bits per byte if coefficient of xn-1 of remainderPolynomial = 1 { remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial } else { remainderPolynomial := (remainderPolynomial * x) } } } // A popular variant complements remainderPolynomial here return remainderPolynomial }

Code fragment 3: Polynomial division with bytewise message XORing

This is usually the most compact software implementation, used in microcontrollers when space is at a premium over speed.