GENERAL PROGRAMMING

CRCs (Cyclic Redundancy Checks)

Article by:
Date Published:
Last Modified:

Overview

“Everything you wanted to know about CRC algorithms, but were afraid to ask for fear that errors in your understanding might be detected.” - Ross N. Williams.

Generator Polynomial

The hexadecimal representation of the polynomial is what you end up exclusively-ORing the data with when writing the CRC software algorithm.

Start Value

A value of all 0’s or all 1’s are common start values for CRC calculations (e.g. 0x0000 and 0xFFFF for a 16-bit CRC calculations).

Start values that are not 0 are better at detecting errors if the message begins with one or more bits that are 0.

MSB-first vs. LSB-first

The least-significant-bit first CRC algorithm is slightly simpler to implement in software/firmware, however the most-significant-bit first algorithm is easier to conceptualize.

Properties Of CRCs

When checking a CRC, rather than recalculating the CRC for the message and comparing with the sent CRC, the CRC calculation can be run on the all the data bits received (including the sent CRC). If the result is 0, the CRC check is O.K.

CRC Calculators

NinjaCalc has a CRC calculator which allows you to calculate the CRC value for ASCII or hex data, using either common pre-loaded CRC algorithms or your own custom algorithm.

Example usage of the CRC Calculator within NinjaCalc (http://gbmhunter.github.io/NinjaCalc/).
Example usage of the CRC Calculator within NinjaCalc (http://gbmhunter.github.io/NinjaCalc/).

Some Common CRC Algorithms

Note that this does in no way try and be an exhaustive list. Sites like CRC RevEng - Catalogue of parameterized CRC algorithms and Prof. Koopman’s CRC Polynomial Zoo have great detailed lists of CRC algorithms.

CRC-8-ATM

It uses the generator polynomial:

$$ x^{8} + x^{2} + x + 1 $$

It can be represented by the following hexadecimal numbers:

Normal: 0x

CRC-16 (CCITT-FALSE)

Aliases
  • CRC-16
  • CCITT-FALSE
Width16 bits
Polynomial0x1021
Initial Value0x0000

CRC-16-CCITT was first used by IBM in it’s SDLC data link protocol. It is also known as just CRC-CCITT (it always uses a 16-bit CRC checksum).

However, CRC-16-CCITT are not all the same. There are a few common variants of the CRC-16-CCITT in use:

  • XModem
  • 0xFFFF. This is an adaptation of the CRC-CCITT algorithm but with a starting CRC value of 0xFFFF rather than 0x0000.
  • 0x1D0F
  • Kermit. This is in fact the “true” CRC-CCITT CRC algorithm.

All of the CRC-CCITT variants use the following generator polynomial:

$$ x^{16} + x^{12} + x^{5} + 1 $$

It can be represented by the following hexadecimal numbers:

Normal: 0x1021  
Reverse: 0x8408  
Koopman: 0x8810

External Resources

http://reveng.sourceforge.net/crc-catalogue/16.htm is a great webpage catalogue of many 16-bit CRC algorithms.

A Painless Guide To CRC Error Detection Algorithms is an old (1993), sore-on-the eyes (pure text article) but great in-depth introduction to CRC algorithms.


Authors

Geoffrey Hunter

Dude making stuff.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License .

Related Content:

Tags

comments powered by Disqus