Embedded Systems Design - March 2008 - (Page 34)

0308esd.p33to37 2/13/08 7:59 PM Page 34 are Logical XOR and Logical AND. Since the operation of an LFSR circuit is deterministic, and the CRC is shorter than the message, typically few messages are mapped to each CRC value. A well-chosen polynomial ensures an evenly distributed mapping of messages to CRC values (for example, if all messages were mapped to the same CRC, detection of an error in a message bit would be impossible). The trick in an embedded systems design is to implement this technique in the most efﬁcient way possible and in the smallest possible footprint. In this article, we discuss aspects of the theory and implementation of LFSRs and CRCs, illustrated using a family of instructions on Analog Devices’ Blackﬁn processor speciﬁcally deﬁned for addressing the task of efﬁcient LFSR implementation. We also provide a method for converting an implementation from an Internal LFSR form to an External LFSR form. DOWN TO BASICS The CRC was developed to answer the requirement for an error detection mechanism. The code consists of a bit ﬁeld (of some set length) that is transmitted with the message (usually appended to the message) over the communication medium. On the receiver side, a second CRC is calculated from the received message and then compared with the received CRC. If both ﬁelds are not the same, an error in the transmission has occurred (it is not known, though, if the message is bad, the CRC is bad, or both are bad). 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 ﬁeld consisting of the elements 0 and 1, with the + and * operators deﬁned modulo-2; in other words, + is the Logical XOR and * is the Logical AND. Mk-1(x) is a polynomial of degree k-1, of the form: Mk-1(x) = mk-1xk-1 + mk-2xk-2 +…+ m0 x0 Gn(x) is the CRC generator polynomial of degree n: Gn(x) = xn + gn-1x n-1 +…+ g0 x0 Cn-1(x) is the calculated CRC polynomial of degree n-1: Cn-1(x) = cn-1x n-1 + cn-2 x n-2 +…+ c0 x 0 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 x n 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 signiﬁcant 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. As mentioned previously, the two circuits are equivalent, and the simple rule for conversion from an Internal Technologic SYSTEMS We use our stuff. visit our TS-7200 powered website at METHOD For message string M of k bits in length and CRC ﬁeld of length n bits, we deﬁne the following polynomials: www.embeddedARM.com (480) 837-5200 http://www.embeddedARM.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.