Saturday, September 27, 2014

Data Integrity Techniques: Aviation Best Practices for CRC & Checksum Error Detection

I just presented a session at an FAA sponsored conference on "Data Integrity Techniques: Aviation Best Practices for CRC & Checksum Error Detection" on Sept. 25.  Here are the slides:


 (Acrobat download: http://users.ece.cmu.edu/~koopman/pubs/koopman14_crc_faa_conference_presentation.pdf)



A recording of an older variant of this presentation can be viewed below:



Webinar download:  https://cmu.box.com/s/nn5r9ogwpw100fqkp6g2
Accompanying slides for that older webinar can be found: here

Thursday, August 14, 2014

Significant update to on-line CRC performance data


I've managed to create a new set of pages with CRC performance data during my hobby time this summer.

"Best" CRC Polynomials:
    http://users.ece.cmu.edu/~koopman/crc/index.html
This contains an extensive list of of good CRC polynomials for different CRC sizes and dataword lengths.  I re-ran all the computations in light of some data that has become available since the initial publication a number of years back. The table is slightly different than the table I previously published.  The old table is OK, but this one is marginally better than the old one for the data that was previously provided, so there is no pressing need to change systems based on the old version so long as you were running at shorter than 2Kbit dataword sizes. More importantly, this new table consideres unlimited dataword lengths and larger CRC sizes.  (At this time the 32-bit computations are still running and they'll be updated as they are available.)

CRC Polynomial Zoo with Hamming Weight Data
Contains error detection performance data for a large variety of CRCs, including numerous "standard" and published CRCs. If you see one missing let me know with a citation and I'll add it.

Please be sure to scroll down past the data to see the notes on how to interpret the summary page and the data files.  The summary page is hand-created, and thus slightly prone to minor bugs, so please do double-check things there.  The data files are 100% machine created and therefore less prone to bugs (and have no bugs as far as I know).

I hope that this data is useful to others.  Some of the large polynomials have incomplete or shortened data files, and will be updating those over time as the computations complete.

Monday, August 4, 2014

CRC publication errata


Thanks to Prof. Berthold Gick at University of Applied Sciences in Koblenz Germany for finding a few bugs in my published CRC values.  (And also thanks for a very thorough second-check of results -- this is an essential part of scholarly publication that is not acknowledged as often as it should be!)

I have updated presentations and papers that I can find with the following corrections:

From my FAA presentation materials:
Polynomial      HD=2            HD=3      HD=4
0x80000d   |   16,777,212    |  5815     |  509               (length in bits at that HD)


From my 2002 paper:
Polynomial 0x992c1a4c has a maximal HD=6 payload of 32738 bits   (originally published as 32737)


From many publications the table of 16-bit and smaller CRCs:
11-bit polynomial 0x5d7  has a maximal HD=5 payload of 26 bits   (originally published as 25)


Some of the "best" polynomial recommendations have been updated. If you are unsure about a polynomial from a previous publication, you can look up its properties here:
   http://users.ece.cmu.edu/~koopman/crc/
and in the accompanying polynomial zoo (click on the polynomial size header in each column).

If anyone else spots an error please do let me know. This work happens time-available, but I do strive to eventually fix any bugs I know about.

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