Cyclic Redundancy Check error - copy errors from CD DVD

Error detection is important whenever there is a non-zero chance of your data getting corrupted. Whether it's an Ethernet packet or a file under the control of your application, you can add a piece of redundant information to validate it.

The simplest example is a parity bit. Many computers use one parity bit per byte of memory. Every time the byte gets written, the computer counts the number of non-zero bits in it. If the number is even, it sets the ninth parity bit, otherwise it clears it. When reading the byte, the computer counts the number of non-zero bits in the byte, plus the parity bit. If any of the nine bits is flipped, the sum will be odd and the computer will halt with a memory error. (Of course, if two bits are flipped--a much rarer occurrence--this system will not detect it.)

For messages longer than one byte, you'd like to store more than one bit of redundant information. You might, for instance, calculate a checksum. Just add together all the bytes in the message and append (or store somewhere else) the sum. Usually the sum is truncated to, say, 32 bits. This system will detect many types of corruption with a reasonable probability. It will, however, fail badly when the message is modified by inverting or swapping groups of bytes. Also, it will fail when you add or remove null bytes.

Calculating a Cyclic Redundancy Check is a much more robust error checking algorithm. In this article I will sketch the mathematical foundations of the CRC calculation and describe two C++ implementations--first the slow but simple one, then the more optimized one.

Polynomials

Here's a simple polynomial, 2x² - 3x + 7. It is a function of some variable x, which depends only on powers of x. The degree of a polynomial is equal to the highest power of x in it; here it is 2 because of the x² term. A polynomial is fully specified by listing its coefficients, in this case (2, -3, 7). Notice that to define a degree-d polynomial you have to specify d + 1 coefficients.

It's easy to multiply polynomials. For instance,

(2x² - 3x + 7) * (x + 2)
= 2x³ + 4x² - 3x² - 6x + 7x + 14
= 2x³ + x² + x + 14

Conversely, it is also possible to divide polynomials. For instance, the above equation can be rewritten as a division:

(2x³ + x² + x + 14) / (x + 2) = 2x² - 3x + 7

Just like in integer arithmetic, one polynomial doesn't have to be divisible by another. But you can always divide out the "whole" part and be left with the remainder. For instance x² - 2x is not divisible by x + 1, but you can calculate the quotient to be x - 3 and the remainder to be 3:

(x² - 2x) = (x + 1) * (x - 3) + 3

In fact you can use a version of long division to perform such calculations

Arithmetic Modulo Two

Most of us are familiar with polynomials whose coefficients are real numbers. In general, however, you can define polynomials with coefficients taken from arbitrary sets. One such set (in fact a field) consists of the numbers 0 and 1 with arithmetic defined modulo 2. It means that you perform arithmetic as usual, but if you get something greater than 1 you keep only its remainder after division by 2. In particular, if you get 2, you keep 0. Here's the addition table:

0 + 0 = 0
0 + 1 = 1 + 0 = 1
1 + 1 = 0 (because 2 has remainder 0 after dividing by 2)

The multiplication table is equally simple:

0 * 0 = 0
0 * 1 = 1 * 0 = 0
1 * 1 = 1

What's more, subtraction is also well defined (in fact the subtraction table is identical to the addition table) and so is division (except for division by zero). What is nice, from the point of view of computer programming, is that both addition and subtraction modulo 2 are equivalent to bitwise exclusive or (XOR).

Now imagine a polynomial whose coefficients are zeros and ones, with the rule that all arithmetic on these coefficients is performed modulo 2. You can add, subtract, multiply and divide such polynomials (they form a ring). For instance, let's do some easy multiplication:

(1x² + 0x + 1) * (1x + 1)
= 1x³ + 1x² + 0x² + 0x + 1x + 1
= 1x³ + 1x² + 1x + 1

Let's now simplify our notation by representing a polynomial as a series of coefficients. For instance, 1x² + 0x + 1 has coefficients (1, 0, 1), 1x + 1 (1, 1), and 1x³ + 1x² + 1x + 1 (1, 1, 1, 1).

Do you see what I am driving at? A polynomial with coefficients modulo 2 can be represented as a series of bits. Conversely, any series of bits can be looked upon as a polynomial. In particular any binary message, which is nothing but a series of bits, is equivalent to a polynomial.

CRC

Take a binary message and convert it to a polynomial then divide it by another predefined polynomial called the key. The remainder from this division is the CRC. Now transmit both the message and the CRC. The recipient of the transmission does the same operation (divides the message by the same key) and compares his CRC with yours. If they differ, the message must have been mangled. If, on the other hand, they are equal, the odds are pretty good that the message went through uncorrupted. Most localized corruptions (burst of errors) will be caught using this scheme.

Not all keys are equally good. The longer the key, the better error checking. On the other hand, the calculations with long keys can get pretty involved. Ethernet packets use a 32-bit CRC corresponding to degree-31 remainder (remember, you need d + 1 coefficients for a degree-d polynomial). Since the degree of the remainder is always less than the degree of the divisor, the Ethernet key must be a polynomial of degree 32. A polynomial of degree 32 has 33 coefficients requiring a 33-bit number to store it. However, since we know that the highest coefficient (in front of x³²) is 1, we don't have to store it. The key used by the Ethernet is 0x04c11db7. It corresponds to the polynomial:

x³² + x²⁶ + ... + x² + x + 1

There is one more trick used in packaging CRCs. First calculate the CRC for a message to which you have appended 32 zero bits. Suppose that the message had N bits, thus corresponding to degree N-1 polynomial. After appending 32 bits, it will correspond to a degree N + 31 polynomial. The top-level bit that was multiplying x^N-1 will be now multiplying x^N+31 and so on. In all, this operation is equivalent to multiplying the message polynomial by x³². If we denote the original message polynomial by M (x), the key polynomial by K (x) and the CRC by R (x) (remainder) we have:

M * x³² = Q (x) * K (x) + R (x)

Now add the CRC to the augmented message and send it away. When the recipient calculates the CRC for this sum, and there was no transmission error, he will get zero. That's because:

M * x³² + R (x) = Q (x) * K (x) (no remainder!)

You might think I made a sign mistake--it should be -R (x) on the left. Remember, however, that in arithmetic modulo 2 addition and subtraction are the same!