3 Gordon Drive, P.O.Box 1347 Rockland, Maine 04841 U.S.A.
Find Tools for Your Chip


 

© 2004 Avocet Systems, Inc.
Call Us Today at 207-596-7766 ("Picton Press")
Avocet Systems, Inc. : The Complete Solution for Embedded Systems Development Tools
Embedded Update
CRC Generation

By now most folks realize that simple checksums just don't cut it for finding errors in data transmission. (Also, for doing RAM and ROM tests - see the upcoming August issue of Embedded Systems Programming for an article about this subject).

Checksums are too easy to fool. Two errors can easily cancel each other out, creating a correct check word from garbled data.

The Cyclic Redundancy Check (CRC) has long been the standard approach to reducing the chances that incorrect data gets transmitted with a seemingly correct check word. It's operation, though, is a bit magical to most of us. Why is the CRC inherently better than a checksum?

Any data integrity monitoring system needs two different ingredients: a wide register that provides a low likelihood of generating a failure (that is, a 32 bit CRC or checksum is a lot better than 16), and the algorithm must exhibit chaotic behavior - where each input byte could conceivably change any number of bits in the check word.

Clearly, the second requirement isn't met by checksums. If you are accumulating a byte stream into a 32 bit doubleword, the summation process changes only the low order part of the doubleword (except in the case of propagating carries, which happens relatively infrequently). A CRC routine uses division instead of addition, saving only the remainder of the divide as the new checksum. Talk about chaotic! The receiver does the same operation, so it can compare results with the transmitted CRC doubleword.

Hardware implementations always use a polynomial instead of straightforward division to compute the CRC; it's easy to create shift registers with feedback terms. Many software incarnations simulate the hardware.

CRCs are simply to broad a subject to cover in a page or so. We have collected some references that give all the details needed to get working CRC code going.

The mother of all CRC documents is "A Painless Guide to CRC Error Detection Algorithms" by Ross Williams.