I recently presented an invitationonly webinar on the topic of CRC and Checksum good practices and error detection effectiveness. The talk was for an aviation audience, but it applies almost entirely to other applications as is. The recording didn't work out, but if there is enough demand I'll find time this summer to see if I can do an audio narration recording to go with the slides.
Meanwhile, you can find the slides here:
http://www.ece.cmu.edu/~koopman/pubs/KoopmanCRCWebinar9May2012.pdf
Contents:
 Introduction
 Motivation  why isn't this a solved problem?
 Parity computations as an example
 Error code construction and evaluation (without scary math)
 Example using parity codes
 Checksums
 What's a checksum?
 Commonly used checksums and their performance
 Cyclic redundancy codes (CRCs)
 What's a CRC
 Commonly used CRC approaches and their performance
 Don't blindly trust what you hear on this topic
 A good CRC is almost always much better than a good checksum
 Many published (and popular) approaches are suboptimal or just plain wrong
 There are some topics to be careful of for which we don't know the answers yet
We are also collecting information about how CRCs and checksums are used in real applications (which is not necessarily the same as what researchers study!) If you have anecdotes, examples, or other information about what you do or what you'd like to do, we'd love to hear about it. If you are in the aviation community the FAA is running a much more
specific survey just for you; let me know and I'll get you in touch with the
appropriate FAA contact.
(We can't necessarily provide immediate answers to specific questions such as "which polynomial should I use for this specific situation." But popular topics and questions that we think are broadly applicable will be put into the research bin and published here or in a report when results are available.)
Cyclic Redundancy Codes, Checksums, and related issues for computer system data integrity.
Saturday, May 12, 2012
Sunday, January 15, 2012
Consolidated Wikipedia Pointers for Checksums and CRCs
Here are some starting points within Wikipedia if you are interested in checksum and CRC background. (These articles also point to other places of interest.) Over time I hope to distill the practical application of all this in my blog, but for now these are reasonable starting points.
 List of checksum and CRC algorithms: http://en.wikipedia.org/wiki/List_of_checksum_algorithms
 Longitudinal Redundancy Check (XOR checksum): http://en.wikipedia.org/wiki/Longitudinal_redundancy_check
 Overview of Checksums: http://en.wikipedia.org/wiki/Checksum
 Fletcher Checksum: http://en.wikipedia.org/wiki/Fletcher%27s_checksum
 Adler Checksum: http://en.wikipedia.org/wiki/Adler32
 Overview of CRC: http://en.wikipedia.org/wiki/Cyclic_redundancy_check
 More detailed example of CRC computation: http://en.wikipedia.org/wiki/Computation_of_CRC
 Mathematics of CRCs: http://en.wikipedia.org/wiki/Mathematics_of_CRC
 Overview of error detection and correction codes: http://en.wikipedia.org/wiki/Redundancy_check
 Discussion of parity: http://en.wikipedia.org/wiki/Parity_bit
 Check digits (it's like parity for numbers handled by people): http://en.wikipedia.org/wiki/Check_digit
Sunday, January 1, 2012
CRC for Protecting A Single Value
Some critical applications need to protect a single byte or word of data in memory against corruption. (For example, if you want to be extrasure about protecting EEPROM values against corruption.) A previous post gives good CRC polynomials for a wide range of circumstances, but it is always nice to know if you can do better for a special case. Below are optimal CRC polynomials for a few special cases involving small data words that might be stored in memory (RAM, EEPROM, or otherwise).
Protecting an 8bit data word:
8bit CRC: HD=5; 0x9C = x^8 + x^5 + x^4 + x^3 + 1
16bit CRC: HD=8; 0xE92F = x^16 + x^15 + x^14 + x^12 + x^9 + x^6 + x^4 + x^3 + x^2 + x + 1
32bit CRC: HD=16; 0xC563942F = x^32 +x^31 +x^27 +x^25 +x^23 +x^22 +x^18 +x^17 +x^16 +x^13 +x^11 +x^6 +x^4 +x^3 +x^2 +x +1
Protecting a 16bit data word:
8bit CRC: HD=4; 0x93 = x^8 + x^5 + x^2 + x + 1
16bit CRC: HD=7; 0x978A = x^16 + x^13 + x^11 + x^10 + x^9 + x^8 + x^4 + x^2 + 1
32bit CRC: HD=14; 0xB396786D = x^32 +x^30 +x^29 +x^26 +x^25 +x^24 +x^21 +x^19 +x^18 +x^15 +x^14 +x^13 +x^12 +x^7 +x^6 +x^4 +x^3 +x +1
Protecting a 32bit data word:
8bit CRC: HD=4; 0x92 = x^8 + x^5 + x^2 + 1
16bit CRC: HD=6; 0x8BFC = x^16 + x^12 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
32bit CRC: HD=12; 0xB527A43B = x^32 +x^30 +x^29 +x^27 +x^25 +x^22 +x^19 +x^18 +x^17 +x^16 +x^14 +x^11 +x^6 +x^5 +x^4 +x^2 +x +1
The hex number has an implicit +1. "HD" means Hamming Distance. Other information about this topic can be found at my previous post on good CRCs.
Note that for this sort of use it is a good idea to "seed" the CRC computation with a value of that is not zero. That avoids a data word value of zero giving a CRC computed value of zero  which will result in an undetected error if memory is wiped to all zeros for some reason.
Protecting an 8bit data word:
8bit CRC: HD=5; 0x9C = x^8 + x^5 + x^4 + x^3 + 1
16bit CRC: HD=8; 0xE92F = x^16 + x^15 + x^14 + x^12 + x^9 + x^6 + x^4 + x^3 + x^2 + x + 1
32bit CRC: HD=16; 0xC563942F = x^32 +x^31 +x^27 +x^25 +x^23 +x^22 +x^18 +x^17 +x^16 +x^13 +x^11 +x^6 +x^4 +x^3 +x^2 +x +1
Protecting a 16bit data word:
8bit CRC: HD=4; 0x93 = x^8 + x^5 + x^2 + x + 1
16bit CRC: HD=7; 0x978A = x^16 + x^13 + x^11 + x^10 + x^9 + x^8 + x^4 + x^2 + 1
32bit CRC: HD=14; 0xB396786D = x^32 +x^30 +x^29 +x^26 +x^25 +x^24 +x^21 +x^19 +x^18 +x^15 +x^14 +x^13 +x^12 +x^7 +x^6 +x^4 +x^3 +x +1
Protecting a 32bit data word:
8bit CRC: HD=4; 0x92 = x^8 + x^5 + x^2 + 1
16bit CRC: HD=6; 0x8BFC = x^16 + x^12 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
32bit CRC: HD=12; 0xB527A43B = x^32 +x^30 +x^29 +x^27 +x^25 +x^22 +x^19 +x^18 +x^17 +x^16 +x^14 +x^11 +x^6 +x^5 +x^4 +x^2 +x +1
The hex number has an implicit +1. "HD" means Hamming Distance. Other information about this topic can be found at my previous post on good CRCs.
Note that for this sort of use it is a good idea to "seed" the CRC computation with a value of that is not zero. That avoids a data word value of zero giving a CRC computed value of zero  which will result in an undetected error if memory is wiped to all zeros for some reason.
Subscribe to:
Posts (Atom)
Why To Avoid Hash Algorithms If What You Really Need Is A Checksum
Sometimes we hear that someone plans to use a hash function for fault detection instead of a checksum. This is probably not the best idea, b...

Checksums and CRCs involve a repeated computation over the length of a dataword that accumulates a result to form an FCS value. The accumul...

An Improved Modular Addition Checksum Algorithm Philip Koopman This paper introduces a checksum algorithm that provides a new point in the p...

Here is a video explaining the mechanics of Cyclic Redundancy Check computations, including: An example of the polynomial division approach...