Channels ▼

Al Williams

Dr. Dobb's Bloggers

Cyclic Cycles

October 14, 2011

If that title seems strange to you, keep in mind that the last few posts I've been writing about error detection. One of the most common ways to handle error detection is the cyclic redundancy check or CRC. (And what could be more redundant than a cyclic cycle?)

I sometimes hear people who aren't well-acquainted with CRCs say, "We can use a CRC." That's like saying "I'm going to use paint." That tells you a class of items, but it isn't specific enough that you can actually get to work. There isn't just a single way to compute a CRC any more than there is just one kind of paint.

Parity, checksums, and many other error-detection schemes suffer from varying degrees of the same problem: Errors can accumulate in such a way that the error detection doesn't work. In a simplistic byte-wide checksum, for example, if two bytes of 0s turns into two bytes each equal to 80 hex, you won't detect any error. You can make a smarter checksum (I talked about that two weeks ago) but there's always a limit.

The CRC seeks to make more bits significant so that any change in the number or order of bits will change the CRC. It isn't perfect, of course. But the chances of changing some bits in a block of data and not changing the CRC are very small.

The CRC is based on polynomials. That sound computationally scary, but it really isn't. In general, a polynomial is something like this:

11x3-4x2+3x+9

In this case, the coefficients of the polynomial are 11, 4, 3, and 9. However, for a CRC, we use polynomials in GF(2). That's just fancy math speak for a polynomial that only has coefficients of 1 or 0. All addition is done in single bit math (modulo 2), so the exclusive or operator works to both add and subtract any two coefficients.

So adding:

x4+x2

and

x4+x+1

results in:

x2+x+1

The exclusive or operator wipes out the power of 4 term. For the CRC, you need to divide two polynomials. You can think of this as long division.

But how do you make a block of data a polynomial? For the purposes of the CRC, each bit is a coefficient. So the byte 10000011 (in binary, of course) represents the polynomial:

x7+x1+1

To compute the CRC of a block of data you take the polynomial it represents and divide it by a generator polynomial. The remainder from division is the CRC. For example, one of the standard 16-bit CRC generators is x16+x12+x5+1.

That's why saying "use a CRC" doesn't mean a lot. You need to know how many bits the CRC will be and what generator polynomial it will use. As you might expect, there are lots of very efficient ways to compute the remainder of such a division.

There are many "common" CRC generators. However, many of these were not selected very scientifically. In 2004, Koopman and Chakravarty at Carnegie Mellon did very interesting work on evaluating existing CRC generators and finding new, better ones. You can read their results here. The key take away, though, is that different generators will have a different Hamming distance for a given block size of data. The Hamming distance is the smallest number of bit errors that can go undetected. A table in the paper will show you that for a 16-bit CRC, for example, the best CRC generator can detect all 3-bit errors in a 2048 byte block of data. The paper examines several "classic" and new generators, and has some surprising results. Koopman also has a paper on 32-bit CRCs that exhaustively evaluates 32-bit CRC generators.

My point to all this is that there isn't a single way to compute a CRC, and picking the right generator can make a big difference in your system's performance in the face of errors. You could probably write the CRC code yourself, but there's so much highly optimized code (and code generators) that it really doesn't make sense. There's plenty of places to grab it already made:

Next time someone casually says, "We'll use a CRC," you can smile knowingly and ask which one.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video