Friday, May 31, 2013

CRC and Checksum Study Results -- Slides


(Updated Sept 29 2013 with revised version.)

I can now make public the study results from an FAA-sponsored look at CRC and Checksum performance for aviation systems. While some of the material is aircraft-specific, it is all relevant to safety critical systems and contains quite a bit of information about CRC vs. checksum performance.

Click here to access the full set of slides (Adobe Acrobat, 1.6 MB)

The general flow of the presentation is with starting slide numbers is:

  • 6 - Terminology and background of CRCs and checksums
  • 10 - Why picking the right CRC matters
  • 22 - Project results overview
  • 25 - Checksum results (Checksum, Fletcher Checksum, ATN-32)
  • 31 - It's all about the Hamming Distance
  • 34 - CRC results
  • 38 - Aviation industry results (might be enlightening for everyone)
  • 43 - Multiple CRC & memory-specific CRC results
  • 46 - System level effects and cross-layer interactions (e.g., unprotected length field, bit encoding)
  • 48 - ARINC-825 issues
  • 52 - Gbit Ethernet issue
  • 54 - Mapping to criticality levels (how do you know your CRC/checksum is good enough?)
  • 64 - Determining Bit Error Ratio (BER)
  • 74 - A simple recipe for how to determine how big and capable a CRC/checksum you need
  • 76 - CRC/Checksum seven deadline sins (bad ideas)
  • 80 - Review of the study project subtasks (most readers can skip this part)
I owe significant thanks to my Co-Investigators Kevin Driscoll and Brendan Hall at Honeywell labs, without whom this work could not have been done. And also a warm and sincere thanks to our FAA contact Chuck Kilgore for his good spirits, kind words, and unfailing support.

"This work was supported by the Federal Aviation Administration, Aircraft Certification Service, and Assistant Administration for NextGen, William J. Hughes Technical Center, Aviation Research

Division, Atlantic City International Airport, New Jersey 08405. The findings and conclusions in this presentation are those of the author(s) and do not necessarily represent the views of the funding agency. This presentation does not constitute FAA policy."  FAA Contract DTFACT-11-C-00005


Saturday, May 12, 2012

CRC and Checksum Tutorial Slides

I recently presented an invitation-only 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.) 


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.
 Related pages:
It is important to realize that Wikipedia is not necessarily an authoritative source. For this area it seems there is enough critical mass of authors, editors and reviewers to get the pages into reasonable shape.

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 extra-sure 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 8-bit data word:
8-bit CRC:  HD=5;  0x9C = x^8 + x^5 + x^4 + x^3 + 1  
16-bit CRC: HD=8; 0xE92F = x^16 + x^15 + x^14 + x^12 + x^9 + x^6 + x^4 + x^3 + x^2 + x + 1
32-bit 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 16-bit data word:
8-bit CRC:  HD=4;  0x93 = x^8 + x^5 + x^2 + x + 1  
16-bit CRC: HD=7; 0x978A = x^16 + x^13 + x^11 + x^10 + x^9 + x^8 + x^4 +  x^2 + 1
32-bit 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 32-bit data word:
8-bit CRC:  HD=4;  0x92 = x^8 + x^5 + x^2 + 1  
16-bit 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
32-bit 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.

Wednesday, December 28, 2011

Pointers to other CRC discussions

Over time I'll add links to postings on CRCs that I find interesting or entertaining:

Nigel Jones has an essay on how we don't always stop to think about whether what we're doing is actually good enough, even if it is what we've always done. In this case he's talking about CRC selection.
(link: Thoughts on BCC's, LRC's, CRC's and being experienced)

 Lammert Bies has a Q&A forum about practical implementations of standard CRC functions.
(link: Error Correction and Detection Forum )