Embedded Systems Design - March 2008 - (Page 36)

0308esd.p33to37 2/13/08 7:59 PM Page 36 feature Internal CRC LFSR. g0 g1 g2 gn-1 [Mk-1,0..0] Figure 1 S0 S1 S2 Sn-1 Cn-1(X) = [ Sn-1 S1 S0 ], after k + n clocks External CRC LFSR. gn-1 i k Figure 2 Cn-1(X) from clock k + 1 to k + n gn-2 g1 g0 [Mk-1,0..0] S0 S1 S2 Sn-1 form to an External form is: 1. While keeping the LFSR ﬂow direction the same, reverse the order of the feedback taps; 2. After the ﬁrst k clocks, feed the ﬁrst 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. 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 deﬁnition 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 deﬁne 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 ﬁrst 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 deﬁned 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: [00000]➝[10000]➝[01000]➝ [10100]➝[11010]➝[01101] 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]. IMPLEMENTING CRC When implementing CRC in software, a common way of accelerating the calculations is through the use of lookup tables. This requires allocation of memory space that grows exponentially with increasing performance (generally, we need 2p rows of n bits each for p look ahead acceleration). However, if you are building a system based on the Blackﬁn processor, you can take advantage of some instructions included in the basic Instruction Set Architecture (ISA) speciﬁcally deﬁned for efﬁcient LFSR implementation. These instructions—BXOR and BXORSHIFT— offer excellent performance, without a requirement for lookup tables. This fact makes it ideal for use when available memory is in shortage. Using these instructions, one can calculate an External CRC at a rate of two cycles per input bit. The example program in Listing 1 shows how to use these instructions. This program consists of three functional parts. The ﬁrst part is the initializa- Internal representation of G5(x) = x5 + x4 + x2 +1. [Mk-1,0..0] Figure 3 S0 S1 S2 S3 S4 External representation of G5(x) = x5 + x4 + x2 +1. [Mk-1,0..0] Figure 4 i>k i <= k S0 S1 S2 S3 S4 36 MARCH 2008 | embedded systems design | www.embedded.com http://www.embedded.com

Table of Contents Feed for the Digital Edition of Embedded Systems Design - March 2008

Embedded Systems Design - March 2008 Contents #Include Programming Pointers Designing DSP-based Motor Control Using Fuzzy Logic Hardware/Software Verification Enters the Atomic Age Efficient CRC Calculation with Minimal Memory Footprint Programming Your Own Microcontroller Advertising Index Break Points Marketplace

Embedded Systems Design - March 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.