CRC Basics

TechForum · April 7, 2021, 9:29pm

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.

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