Embedded Systems Design Europe - April 2008 - (Page 26)

crc calculation rule for conversion from an Internal 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 (S ) with n zeros and read the n output bits (which are the required CRC) as the sum of the feedback and the input. 0 In both cases, M is fed in starting with the highest order bit m . For example, consider two equivalent implementations of the generator polynomial G (x) = x +x +x +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. k-1 5 4 2 5 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 I . 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 I (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 I 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 n n n string for a given I . 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 G (x) = x +x +x +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], n 5 4 2 5 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]. Listing 1 Example program showing use of BXOR and BXORSHIFT instructions. // _CRC_BXOR - calculate the CRC of a message polynomial // for a given generator polynomial. #deﬁne MSG_LEN 32 // bits #deﬁne CRC_LEN 16 // bits _CRC_BXOR: a1 = a0 = 0; r1 = 0x8408 (z); a1.w = r1; r2.h = 0xd065; r2.l = 0x86c9; // // // // initialize LFSR state LFSR polynomial, reversed: x^16 + x^12 + x^5 + 1 initialize LFSR mask // r2 = message p1 = MSG_LEN (z); loop _MSG_loop lc0 = p1; loop_begin _MSG_loop; r2 = rot r2 by 1; a0 = bxorshift(a0, a1, cc); loop_end _MSG_loop; r0 = 0; // CRC r2.l = cc = bxor(a0, r1); r0 = rot r0 by 1; p1 = CRC_LEN-1 (z); loop _CRC_loop lc0 = p1; loop_begin _CRC_loop; r2.l = cc = bxorshift(a0, r1); r0 = rot r0 by 1; loop_end _CRC_loop; // r0 now contains the CRC _CRC_BXOR.end: 26 APRIL 2008 | embedded systems design europe | www.embedded.com/europe 024-025-026-027_ESDE.indd 26 8/04/08 12:47:11 http://www.embedded.com/europe

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

Embedded Systems Design Europe - April 2008 Contents Chip Industry Confronts 'Software' Gap Wind River's VxWorks OS Part of the nEUROn UCAV Demonstrator iSuppli Cuts Electronic Equipment Forecast Study Says GigE Vision Not Mature Chip Aids Wireless Health Monitoring Kontron Reports Strong Financial Growth Xilinx Completes Virtex-5 Line-Up French Project Builds Open Platform Home Automation Group Uses Enocean Radio Layer MIPs Adds Multi-Core Option to Portfolio Cover Feature: Next Gen Programmable Chips: Why Can't Hardware Be More Like Software? Improving Productivity & Quality With Domain-Specific Modeling Efficient CRC Calculation With Minimal Memory Footprint Do-It-Yourself Linux Embedded Development Tools Hardware/Software Verification Enters the Atomic Age New Products Advertising Contacts

Embedded Systems Design Europe - April 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.