You can implement the cyclic redundancy check function in an embedded systems design with minimal impact on memory or performance by using linear feedback shift register instructions more intelligently.
In order to calculate the CRC code for a message, we look at the problem as an exercise in polynomial algebra over Galois Field GF(2). In short, GF(2) is a field consisting of the elements 0 and 1, with the + and * operators defined modulo-2; in other words, + is the Logical XOR and * is the Logical AND.
Method
For message string M of k bits in length and CRC field of length n bits, we define the following polynomials:
Mk-1(x) is a polynomial of degree k-1, of the form:
Mk-1(x) = mk-1xk-1 + mk-2xk-2 +...+ m0x0
Gn(x) is the CRC generator polynomial of degree n:
Gn(x) = xn + gn-1xn-1 +...+ g0x0
Cn-1(x) is the calculated CRC polynomial of degree n-1:
Cn-1(x) = cn-1xn-1 + cn-2xn-2 +...+ c0x0
The CRC is determined in this way:
Cn-1(x) = {Mk-1(x) • xn} mod Gn(x)
The mod division is performed modulo-2 over GF(2). The k bits of the message string are appended by n bits of zeros (this is the xn term in the equation). This kind of division is commonly implemented using LFSR circuits. There happen to be two canonical forms of LFSR implementation, which are interchangeable in that they will calculate the same result, given the same message and divisor polynomial.
One form, known as an External, Type I or Fibonacci LFSR has XOR gates in the feedback path, and the feedback terms are sampled from the relevant taps, added (modulo 2), and then fed back to the least significant bit (lsb).
Another form, known as an Internal, Type II or Galois LFSR takes the highest order bit (msb) as the feedback term that is fed back into the relevant taps through the XOR gates placed between the taps. This form is the more popular, as it seems to be faster when implemented with hardware logic gates. In fact, one can see the similarity between the algebraic process and this LFSR division. However, many implementers are unaware of the equivalence of the two forms.
An Internal CRC LFSR is implemented as shown in Figure 1. The equivalent External LFSR has the form shown in Figure 2.
View the full-size image
View the full-size image
