Cyclic Cycles

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:

11×3-4×2+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.

Leave a Reply

Your email address will not be published. Required fields are marked *

*