FAA CRC and Checksum Report

I've been working for several years on an FAA document covering good practices for CRC and Checksum use.  At long last this joint effort with Honeywell researchers has been issued by the FAA as an official report.  Those of you who have seen my previous tutorial slides will recognize much of the material. But this is the official FAA-released version.

Selection of Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity
DOT/FAA/TC-14/49
Philip Koopman, Kevin Driscoll, Brendan Hall

http://users.ece.cmu.edu/~koopman/pubs/faa15_tc-14-49.pdf

(Don't miss the webinar tutorial on this other Blog post.)

Abstract:

This report explores the characteristics of checksums and cyclic redundancy codes (CRCs) in an aviation context. It includes a literature review, a discussion of error detection performance metrics, a comparison of various checksum and CRC approaches, and a proposed methodology for mapping CRC and checksum design parameters to aviation integrity requirements. Specific examples studied are Institute of Electrical and Electronics Engineers (IEEE) 802.3 CRC-32; Aeronautical Radio, Incorporated (ARINC)-629 error detection; ARINC-825 Controller Area Network (CAN) error detection; Fletcher checksum; and the Aeronautical Telecommunication Network (ATN)-32 checksum. Also considered are multiple error codes used together, specific effects relevant to communication networks, memory storage, and transferring data from nonvolatile to volatile memory.

Key findings include:

• (1) significant differences exist in effectiveness between error-code approaches, with CRCs being generally superior to checksums in a wide variety of contexts; 
• (2) common practices and published standards may provide suboptimal (or sometimes even incorrect) information, requiring diligence in selecting practices to adopt in new standards and new systems; 
• (3) error detection effectiveness depends on many factors, with the Hamming distance of the error code being of primary importance in many practical situations; 
• (4) no one-size-fits-all error-coding approach exists, although this report does propose a procedure that can be followed to make a methodical decision as to which coding approach to adopt; and 
• (5) a number of secondary considerations must be taken into account that can substantially influence the achieved error-detection effectiveness of a particular error-coding approach.

You can see my other CRC and checksum posts via the CRC/Checksum label on this blog.

Be sure to see the webinar version of this report.

Official FAA site for the report is here: http://www.tc.faa.gov/its/worldpac/techrpt/tc14-49.pdf

CRC and Checksum Tutorial Webinar

I've completed my 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.

I'm pleased to be able to share a two-hour Webinar recording describing all the work, as well as the slides and draft report. There is a guide to the material below that you may find useful if you are looking for a specific topic.

• Video: Vimeo (streaming and download)
• Video:  Youtube (streaming)
• Slides (Acrobat)
• Final report (Acrobat)
• My other blog posts on CRCs and checksums

The general flow of the presentation is as follows, by slide number:

• 6 - CRC and checksum background and terminology

• 10 - Why picking the right CRC isn't as easy as you might think

• 20 - Summary of project technical approach

• 21 - Project results overview

• 24 - Checksum results (Checksum, Fletcher Checksum, ATN-32)

• 30 - CRC-32 compared to checksums

• 31 - It's all about the Hamming Distance

• 33 - Table of checksum compared to CRC-32

• 35 - Good CRC choices (8 & 16 bits)

• 36 - Good CRC choices (24 & 32 bits)

• 37 - 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 / CAN issues

• 52 - 8b10b encoding Gbit Ethernet issue

• 53 - Mapping to criticality levels (how do you know your CRC/checksum is good enough?)

• 64 - Determining Bit Error Ratio (BER)

• 71 - Error detection mechanism failure and scrubbing

• 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)

• 79 - 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 contacts, and especially to Chuck Kilgore for his good spirits, kind words, and unfailing support.

NOTES:

"The provided links will give you the option of downloading the video file or view it through your web browser.   Some people have reported problems viewing the video with their web browser due to the 2 hour length.  Others have been able to view the video in a browser without any problems.   If you encounter problems, we recommend that you download the file for offline viewing if possible to avoid any streaming issues."

"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."

The Webinar was scheduled Oct 1, 2013, but was delayed due to the government shutdown. The webinar was actually held on Oct 29, 2013.

Seven Deadly Sins of CRCs and Checksums

We're wrapping up the final report for an FAA-sponsored study of CRC and Checksum performance for aviation applications, although the results in general apply to all uses of those error detection codes.

As part of our results we came up with an informal list of "Seven Deadly Sins" (bad ideas):

1. Picking a CRC based on a popularity contest instead of analysis
• This includes using “standard” polynomials such as IEEE 802.3
2. Saying that a good checksum is as good as a bad CRC
• Many “standard” polynomials have poor HD at long lengths
3. Evaluating with randomly corrupted data instead of BER fault model
• Any useful error code looks good on random error patterns vs. BER random bit flips
4. Blindly using polynomial factorization to choose a CRC
• It works for long dataword special cases, but not beyond that
• Divisibility by (x+1) doubles undetected fraction on even # bit errors
5. Failing to protect message length field
• Results in pointing to data as FCS, giving HD=1
6. Failing to pick an accurate fault model and apply it
• “We added a checksum, so ‘all’ errors will be caught” (untrue!)
• Assuming a particular standard BER without checking the actual system
7. Ignoring interaction with bit encoding
• E.g., bit stuffing compromises HD to give HD=2
• E.g., 8b10b encoding – seems to be OK, but depends on specific CRC polynomial

(I haven't tried to map it onto the more traditional sin list... if someone comes up with a clever mapping I'll post it!)

Thanks to Kevin Driscoll and Brendan Hall at Honeywell for their work as co-investigators. You can read more about the research on my CRC and Checksum Blog.  That blog has more detailed postings, slide sets, and will have the final research report when it is made publicly available.

What's the best CRC polynomial to use?

(If you want to know more, see my Webinar on CRCs and checksums based on work sponsored by the FAA.)

If you are looking for a lightweight error detection code, a CRC is usually your best bet. There are plenty of tutorials on CRCs and a web search will turn them up. If you're looking at this post probably you've found them already.

The tricky part is the "polynomial" or "feedback" term that determines how the bits are mixed in the shift-and-XOR process. If you are following a standard of some sort then you're stuck with whatever feedback term the standard requires. But many times embedded system designers don't need to follow a standard -- they just need a "good" polynomial. For a long time folk wisdom was to use the same polynomial other people were using on the presumption that it must be good. Unfortunately, that presumption is often wrong!

Some polynomials in widespread use are OK, but many are mediocre, some are terrible if used the wrong way, and some are just plain wrong due factors such as a typographical error.

Fortunately, after spending a many CPU-years of computer time doing searches, a handful of researchers have come up with optimal CRC polynomials. You can find my results below. They've been cross-checked against other known results and published in a reviewed academic paper. (This doesn't guarantee they are perfect!  But they are probably right.)

(click for larger version)
(**** NOTE: this data is now a bit out of date. See this page for the latest ****)

Here is as thumbnail description of using the table. HD is the Hamming Distance, which is minimum number of bit errors undetected. For example, HD=4 means all 1, 2, and 3 bit errors are detected, but some 4-bit errors are undetected, as are some errors with more than 4 bits corrupted.

The CRC Size is how big the CRC result value is. For a 14-bit CRC, you add 14 bits of error detection to your message or data packet.

The bottom number in each box within the table is the CRC polynomial in implicit "+1" hex format, meaning the trailing "+1" is omitted from the polynomial number. For example, hex 0x583 = binary 101 1000 0011 = x^11 + x^9 + x^8 + x^2 + x + 1. (This is "Koopman" notation in the wikipedia page.  No, I didn't write the wikipedia entry, and I wasn't trying to be gratuitously different. A lot of the comparison stuff happened after I'd already done too much work to have any hope of changing my notation without introducing mistakes.) 

The top number in each box is the maximum data word length you can protect at that HD. For example, the polynomial 0x583 is an 11-bit CRC that can provide HD=4 protection for all data words up to 1012 bits in length.  (1012+11 gives a 1023 bit long combined data word + CRC value.)

You can find the long version in this paper:  Koopman, P. & Chakravarty, T., "Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks," DSN04, June 2004. Table 4 lists many common polynomials, their factorizations, and their relative performance. It covers up to 16-bit CRCs. Longer CRCs are a more difficult search and the results aren't quite published yet.

You can find more discussion about CRCs and Checksums at my blog on that topic: http://checksumcrc.blogspot.com/

(Note: updated 8/3/2014 to correct the entry for 0x5D7, which provides HD=5 up to 26 bits. The previous graphic incorrectly gave this value as 25 bits. Thanks to Berthold Gick for pointing out the error.)

Which Error Detection Code Should You Use?

Any time you send a message or save some data that might be corrupted in storage, you should think about using some sort of error detection code so you can tell if the data has been corrupted. If you do a web search you will find a lot of information about error detection codes. Some of it is great stuff. But much of it is incorrect, or on a good day merely suboptimal. It turns out that the usual rule of thumb of "do what the other guys do and you can't go far wrong" works terribly for error detection. There is lots of folk wisdom that just isn't right.


So, here is a guide to simple error correction in embedded systems. There is a journal paper with all the details (see this link), but this is the short version.

If you want the fastest possible computation with basic error detection:

• Parity is fine if you have only one bit to spend, but takes about as much work to compute as a checksum.
• Stay away from XOR checksums (often called LRCs or Longitudinal Redundancy Checks). Use an additive checksum instead to get better error detection at the same cost.
• Use an additive checksum if you want something basic and fast. If possible, use a one's complement additive checksum instead of normal addition. This involves adding up all the bytes or words of your data using one's complement addition and saving the final sum as the checksum. One's complement addition cuts vulnerability to undetected errors in the top bit of the checksum in half. In a pinch normal integer addition will work, but gives up some error detection capability.

If you want intermediate computation speed and intermediate error detection:

• Use a Fletcher checksum. Make sure that you use one's complement addition in computing the parts of that checksum, not normal integer addition. Normal integer addition just kills error detection performance for this approach.
• Don't use an Adler checksum. In most cases it isn't as good as a Fletcher checksum and it is a bit slower to compute. The Adler checksum seems like a cool idea but it doesn't really pay off compared to a Fletcher checksum of the same size.

If you can afford to spend a little more computation speed to get a lot better error detection:

• Use a CRC (cyclic redundancy check)
• If you are worried about speed there are a variety of table lookup methods that trade memory for speed. CRCs aren't really as slow as people think they will be. Probably you can use a CRC, and you should if you can.  Mike Barr has a posting on CRC implementations.
• Use an optimal CRC polynomial if you don't have to conform to a standard. If you use a commonly used polynomial because other people use it, probably you are missing out on a lot of error detection capability. (More on this topic in a later post.)

You can find more discussion about CRCs and Checksums at my blog on that topic: http://checksumcrc.blogspot.com/