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.
As mentioned previously, the two circuits are equivalent, and the simple rule for conversion from an Internal form to an External form is:
1. While keeping the LFSR flow direction the same, reverse the order of the feedback taps;
2. After the first k clocks, feed the first tap (S0) with n zeros and read the n output bits (which are the required CRC) as the sum of the feedback and the input.
In both cases, M is fed in starting with the highest order bit mk-1. For example, consider two equivalent implementations of the generator polynomial G5(x)=x5+x4+x2+1, shown in Figures 3 and 4.
View the full-size image
View the full-size image
Given the same bit sequence at the input, the resultant CRC from the two circuits will be the same.
Initialization of the LFSR
In practice, there are a few variations on the subject of CRC definition and implementation. These variations regard bit ordering, bit inversion and LFSR initialization. Several standards state that the LFSR taps are initialized to zero. For some good reasons, other standards define the taps to be initialized to ones. In general, any initialization string may be valid. Given an initialization string for an internal LFSR, we need a method for conversion of that string to the equivalent external LFSR. The following method is applied:
Consider an internal LFSR initialized with an initialization string In. The resulting CRC after k+n clocks will be just the same as if we have a LFSR initialized with zeros, and the message prepended by In (advancing n+k+n clocks in total). This is true because the first n bits just propagate through the LFSR without being fed back. So, after n clocks we are at the point where the LFSR contains In and the message is about to be fed in.
Since we know the two LFSR types are equivalent when initialized with zeros, we can repeat the same practice with the external LFSR. This time, after n clocks the taps are populated with some string that is determined by the generator polynomial--but is a well defined string for a given In. So, we can precalculate this equivalent initialization string and use it to initialize our LFSR.
For example consider the generator polynomial from the previous section G5(x)=x5+x4+x2+1. If we need to initialize the internal LFSR state with [11111], what will be the initialization string of the external form? Initializing it to [00000] and feeding with [11111], the following LFSR states are calculated with each clock:
If we use this string to initialize our external LFSR, we can calculate a CRC of the message as if it was done with an internal LFSR initialized with [11111].
