The scope of this article is to describe the basic concepts related to CRC (Cyclic Redundancy Check), an efficient and widely used way to protect data against accidental corruption.

CRC is the acronym for Cyclic Redundancy Check, and it is intended as a function which input is a collection of data bytes (also called as byte stream), and which output is a numeric value, usually an integer of 16 or 32 bits. The term CRC is used to refer both to the function and to the computed value. The data stream can be of several types: a file belonging to a certain file system, an array of bytes stored in memory (RAM, ROM, or NVRAM), a stream of bytes or a data packet flowing on a network, and so on. The main purpose of the CRC is to allow the detection of errors affecting the integrity of a data stream, thus acting as validity control associated to a specific group of data. Hereafter are presented some examples:

• If the CRC is associated to each file stored in a file system, the operating system will be able to check the integrity of the file prior to allow any access to it. There are many reasons which can cause a file corruption (I think that most of us have experienced it at least once in their lives): an error occurring during the transfer to/from an external devices, an error affecting the physical device which hosts the file, a sudden and unwanted shutdown of the system during a write operation, a software virus (unfortunately also that can happens), and so on
• Let’s now think to the binary image of an application running on an embedded system (nowadays it will probably reside on a flash memory, either external or integrated to a microcontroller, in the past it could have been burned on a eprom memory). If we compute the CRC of this image each time the firmware is upgraded and keep track of it, we have a way to check, anytime, whether the firmware itself corresponds to the version we are expecting. That provides a way both to check the integrity of the image, and to realize whether a tampering action has been performed by someone to alter the original code
• If the CRC is associated to a data packet exchanged between two or more nodes on a network or bus, by checking the CRC of each received packet it will be possible to detect a data corruption. As a result, the error could be recovered by re-transmitting the packet, or just signaling a transmission error to the alarm layer

The polynomial generator

The basic idea which is behind any CRC algorithm is quite simple: to treat the data stream as a huge binary number, to divide it by another constant (fixed) binary number, and to use the remainder from this division as the CRC value.

Actually, the divisor, dividend (the data stream), quotient, and remainder have not to be considered as positive integers, but rather as polynomials with binary coefficients. This is achieved by considering each number as a sequence of bits which are nothing else than the coefficients of a polynomial. Let’s show this with an example: the decimal number 35 is represented as 23H in hexadecimal, and 100011 in binary format. If the bits correspond to the polynomial coefficients, this number represents also the following polynomial:

1*x5+0*x4+0*x3+0*x2+1*x1+1*x0, that is x5 + x1 + 1.

In order to perform the CRC calculation, the first thing to do is to select the divisor, which is technically referred to as the “polynomial generator”. An important property of the polynomial generator is the width, which is defined as the position of its highest bit set to 1. Typical values for this width are 16 and 32, because they simplify the algorithm implementation on current computers. For example, the width of the polynomial generator considered in the previous example is 5 (not 6). It should be noticed that the high-order bit of the divisor polynomial is usually omitted when representing the divisor itself; that’s because the high-order bit should always be equal to 1.

Some commonly used polynomial generators are the following:

• CRC-8-ATM: it is used to compute the value of the HEC field of the ATM (Asynchronous Transfer Mode) cell. The polynomial is x8 + x2 + x + 1, and the corresponding representation is 0x07
• CRC-8-CCITT: it is used for 1-Wire bus devices (Maxim/Dallas has also introduced another type of CRC slightly different). The polynomial is x8 + x7 + x3 + x2 + 1, and the corresponding representation is 0x8D
• CRC-16 CCITT: it is used in many different applications such as Bluetooth, X.25, XMODEM, PPP, etc. The polynomial is x16 + x12 + x5 + 1, and the corresponding representation is 0x1021

The algorithm

Now we are going to see a very simple algorithm that is able to perform the CRC calculation for any chosen width value. The big thing to do is to implement the CRC division: once this step has been resolved, the algorithm is practically done.

The CRC calculation will refer to a data stream (i.e. a message or an array) consisting of a sequence of bytes with bit 7 of each byte being considered to be the most significant bit (MSB). As a result, we will actually have a bit stream composed by a sequence of bits.
First of all, a poly must be chosen. After that, the calculation consists in a CRC division between the bit stream and the poly. W zero bits have to be appended to the bit stream prior to execute the division, being W the poly width. Calculation is performed in binary with no carries, that is:

• 0+0=0
• 0+1=1
• 1+0=1
• 1+1=0 (no carry)

That means that in CRC mathematics addition and subtraction can be executed with the XOR function. All the operations are performed using a left shift register R with a number of bits equal to the polynomial width that is W.

The algorithm consists of the following steps:

1. augment the message by appending W bits to its end
2. load the register R with zero bits
3. if there are still message bits to be processed execute step 4, otherwise goto step 7
4. shift the register R left by one bit, loading the next message bit in register bit position 0
5. if a 1 is popped out of the register (i.e. if the most significant bit of the register prior to execute the left shift was 1) set: R = R XOR polynomial
6. goto step 3
7. the register R now contain the remainder, that is the CRC

Often, in applications related to communication protocols (such as Ethernet), the CRC is appended at the end of the message before the transmission. The receiver can then either recalculate the CRC and check it with the received one, or more easily just compute the CRC on the whole received message: if no error or corruption occurred, the result shall always be 0.

An example

Consider the following example:

• message composed of just two bytes: 0x32,0x24
• polynomial generator: 10011, that is W=4
• message in binary format, augmented with W 0 bits: 0011 0010 0010 0100 0000

Applying the algorithm, we obtain a CRC (the remainder) equal to 1101 (0x0D)

Conclusions

This simple algorithm has been presented because it can be easily implemented with hardware modules. From the software point of view, it is not very efficient, since many bit operations have to be performed (XOR and shifts). There is another algorithm which is faster and requires fewer resources, and is based on a precompiled lookup table. We are more interested in the version based on the shift register because in the second part of this article we will see that it is the exact followed to implement the CRC calculation, at hardware level, on the Freescale Flexis AC MCU Family.

Read the Italian version: Cyclic Redundancy Check (CRC) - Concetti basilari

CONTACT REQUEST
If you want to know more about this Freescale product, please submit your request to Arrow Italy using this form.

NOTE: this form is valid ONLY for Companies or Customers based in Italy and working in the Italian area.