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

crc calculation The receiver performs a CRC function on the message and compares the result with the received CRC code to verify the integrity of the message. CRC is commonly used in a number of applications such as digital communications and computer data storage systems. The CRC is performed through binary polynomial division between the transmitted message and a polynomial divisor and is usually implemented using a linear feedback shift register (LFSR). An LFSR is a shift register where its next state is a linear combination of its previous state and input bits. In our context, the linear operators 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. For message string M of k bits in length and CRC ﬁeld of length n bits, we deﬁne the following polynomials: M (x) is a polynomial of degree k-1, of the form: k-1 M (x) = m x + m x +…+ m x k-1 k-2 k-1 k-1 k-2 0 n 0 G (x) is the CRC generator polynomial of degree n: G (x) = x + g x +…+ g x n n-1 n n-1 0 n-1 0 C (x) is the calculated CRC polynomial of degree n-1: C (x) = c x + c x +…+ c x n-1 n-2 n-1 n-1 n-2 0 0 The CRC is determined in this way: C (x) = {M (x) • x } mod G (x) n n-1 k-1 n 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 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 n www.embedded.com/europe | embedded systems design europe | APRIL 2008 25 024-025-026-027_ESDE.indd 25 8/04/08 12:46:56 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.