CRC Basics - Microcontroller

Created by Jeremy Purcell, last modified on Jun 22, 2012

Features

• Basic explanation of CRC (appending zeros method)
• Short discussion on brute force calculation of CRC
• Examples of calculating a CRC sum
• C code for simple implementation of CRC

Introduction

A Cyclic Redundancy Check (CRC) is a verification method used to ensure that data being sent is not corrupted during transfer. The use of CRCs is common in communication mediums that transmit digital data, such as WiFi and Ethernet. There is a need to check for communication errors in embedded systems, as technology drives them to be capable of creating and sending larger data packets in a faster and more complex manner. This application note discusses a method for computing and verifying a CRC.

Background

The CRC algorithm computes a checksum for each specific data set that is sent through it. This algorithm utilizes a polynomial key and the transferred data.

The sending system calculates the check or verification code and appends it to the outgoing message. On the receiving end, the data is put through the same process. If the CRC produced at the receiving end does not match the sent CRC, then the data is possibly corrupt. The receiver can request that the data be retransmitted or simply ignore the data. When the CRC matches the received version, the user can be fairly confident that the transmission is not corrupted.

Implementing CRCs is accomplished using two different methods. The brute force method requires more computational resources and can be more time consuming. The lookup table method requires more memory resources and is useful for defined and/or repetitive data sets.

Application

This application discusses the brute force method of computing CRCs. CRC math can be accomplished in software by shifting the data or shifting the polynomial key, then performing the computations. There are several implementations that compute the CRC checksum.

CRC Polynomial

The polynomial key is an important part of the CRC. Keys are not just random polynomials; they are generated using a set of mathematical formulas and are intended to increase the number of mistakes that the CRC process identifies. The polynomial is typically defined by the network protocol or external device. Since there is a well-established set of keys available, the processes for defining keys is not discussed here.

The polynomial key is translated into a binary expression. This is done by expanding the polynomial, and then taking the coefficients. An example polynomial to binary translation is shown below.

Polynomial key:

Expanded polynomial key:

Polynomial coefficients: 100110001

The highest power of the polynomial shown is eight, which makes this polynomial an 8-bit CRC, commonly referred to as CRC-8. Four, eight, sixteen, and thirty-two bit are very common polynomial sizes used in CRCs.

Computing a CRC Checksum

The sending device calculates the CRC by appending the data with the correct number of zeros. The data is then processed using binary math before sending it over the communication channel. This method is the “appended zeros” implementation show in Figure 1. Example 1 in the Appendix demonstrates this technique.

First, zeros are appended to the full packet of data. Align the polynomial with the leftmost 1 in the data. The data is XORed with the polynomial. The result is the new data. Again align the polynomial with the leftmost 1 in the data. The process continues until the data is smaller then the polynomial. This CRC is added to the data stream before transmission.

image310×516 58.2 KB Figure 1. Appending Zeros Algorithm

CRC Verification

On the receiving side of the system, there are two methods explained here for verifying the CRC: the “appended zeros” implementation or the “zero result” implementation.

In the “appended zeros” implementation, the CRC is removed, and the data is appended with n zeros, where n is the highest power of the polynomial. With CRC-8, eight zeros are appended to the end of the data. The CRC is then calculated as show in Figure 1 and compared with the CRC value received.

In the “zero result” implementation, a similar process to that shown in Figure 1 is followed, except zeros are not appended, and data includes the received CRC. Once the process is complete, the result equals zero if the data matches the CRC. Example 2 in the Appendix demonstrates this technique.

Many applications use a lookup table, since they require fewer computational resources. These lookup tables contain CRC values that correspond to specific data sets. This method is effective for applications with defined and/or repetitive data transmissions.

Considerations

Endianness is the term used to describe the byte order of the data. Big-endian means that data is being sent with the most significant bit (MSB) first. Conversely, little-endian is sent with the least significant bit (LSB) first. Endianness matters, because the CRC changes when the byte is flipped from MSB first to LSB first. Typically, the endianess is determined by the type of data being transferred.

Conclusion

A CRC is a simple but effective way to check for errors in data being sent over a noisy medium. This application note discussed how CRCs work and presented methods for calculating and verifying them. A CRC can be easily incorporated into most embedded systems.

Appendix: Examples

Example 1: Appended Zeros Method

The incoming data MSB first is 01101010 10101111 (two bytes). This example uses the polynomial key: x8 + x2 + x1 + 1 or 100000111. For the CRC-8, which is 8-bit, the key is actually 9 bits.

011010101010111100000000 Data appended with 8 zeros 100000111 Right shift polynomial key 011010101010111100000000 100000111 XOR data with key and right shift 01010110110111100000000 100000111 XOR and right shift 0010111000111100000000 100000111 Right shift 010111000111100000000 100000111 XOR and right shift 00111011011100000000 100000111 Right shift 0111011011100000000 100000111 XOR and right shift 011011100100000000 100000111 XOR and right shift 0101111100000000 100000111 XOR and right shift 0011110110000000 100000111 Right shift 011110110000000 100000111 XOR and right shift 01110101100000 100000111 XOR and right shift 0110100010000 100000111 XOR and right shift 010100101000 100000111 XOR and right shift 00100110100 100000111 Right shift 0100110100 100000111 XOR 000110011 Result < Polynomial Key

The resulting check for the data 0x6AAF is 0x33. In this example, the data stream out of the transmitter (in HEX) is 34 (xx) 6A AF 33. The first byte(s) are protocols for transmission, the next two bytes are the data, and the last byte is the CRC.

Example 2: Zero Result Method

The incoming data MSB first is 01101010 10101111 (two bytes). This example uses the polynomial key: x8 + x2 + x1 + 1 or 100000111. For the CRC-8, which is 8-bit, the key is actually 9 bits.

011010101010111100110011 Data and CRC received 100000111 Right shift polynomial key 011010101010111100110011 100000111 XOR data with key and right shift 01010110110111100110011 100000111 XOR and right shift 0010111000111100110011 100000111 Right shift 010111000111100110011 100000111 XOR and right shift 00111011011100110011 100000111 Right shift 0111011011100110011 100000111 XOR and right shift 011011100100110011 100000111 XOR and right shift 01011111000110011 100000111 XOR and right shift 0011110110110011 100000111 Right shift 011110110110011 100000111 XOR and right shift 01110101010011 100000111 XOR and right shift 0110100100011 100000111 XOR and right shift 010100011011 100000111 XOR and right shift 00100000111 100000111 Right shift 0100000111 100000111 XOR 000000000 Result < polynomial Key

The check for 0x6AAF is 0x00 using the “zero result method,” which confirms that the proper data was received.

Questions/Comments

Any questions or comments please go to Digi-Key’s TechForum