Saturday, March 11, 2017

Video on Hamming Codes & Hamming Distance

Nice video that talks about Hamming Codes and gives a hypercube explanation that helps understand Hamming Distance

Perfect Codes:
on computerphile.

Sunday, January 22, 2017

On sabbatical

I noticed that my e-mail has some CRC queries. I'm on sabbatical through summer 2017, so there might be significant delays before I'm able to respond to e-mails.  If you notice something that seems to be a problem please do let me know, but please bear with me until I have time to respond.

(Contrary to what some might think "sabbatical" is usually the opposite of "vacation" for engineering faculty.  It is a chance for us to concentrate on a large difficult problem that we can't do during normal semesters because of all the many demands made upon our time.)

Tuesday, July 28, 2015

Significantly updated CRC data

Over the course of the summer I was able to get a little time to revise and update my CRC data web site.  It is still work-in-progress, but you'll find a lot more data than was there previously.

New summary tables:

Recommendations for "good" polynomials with various HD values are completed through 25 bit CRCs, and I'll let the scripts compute away for a few months until eventually the tables are completed through 32 bits.  Past 32 bits my search algorithm starts taking a long time to execute so probably will only have samples above that, but we'll see how it goes.

When you look at the data, yellow and blank mean things I'm working on (the color coding helps me keep straight what the scripts are currently working on).  Green boxes and "under construction" mean preliminary results that should be OK but aren't double-checked yet.  A significant addition is that I've added automatically generated examples of violations of the HD so you can confirm results for yourself. There is also some do-it-yourself HD computation help here.

If you see a polynomial missing that is published somewhere let me know and I'll add it.

I should mention that Prof. Berthold Gick from University of Applied Sciences, Koblenz, Germany has been independently working in this area and verified many of my results.  More importantly, he's pointed out a few typos and other issues that I'm working to correct.  I'd like to take this chance to thank him for his efforts.  If anyone else notices problems please let me know.

Thursday, June 11, 2015

Is HD=1 Useful?

I received an e-mail with a question as to why a HD=1 checksum would ever be useful (referred to on slide 89 of my Sept 2014 slide set on CRCs).  The point is that HD=1 means you are not guaranteeing detection of any error, not even 1-bit errors.  Here's my answer, which I am posting since it might have general interest:.

HD=1 (zero errors guaranteed to be detected) means that there is still a residual capability to randomly detect most errors (all errors except 1 in 2**k for k bits).
If you only need an error detection ratio of a few orders of magnitude this is fine if you have a large CRC.

If you are using a 256 bit cryptographic checksum (which must be assumed to have HD=1) then undetected error probability is 1 in 2**256, which is pretty good.  However, a high-HD CRC will usually get you better non-malicious error detection for less computational cost.

Saturday, April 11, 2015

FAA CRC Report

After an extensive editing and approval process, the FAA has released the report that I did with Kevin Driscoll & Brendan Hall from Honeywell.  You can see it here:

Selection of Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity

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:

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

Webinar download:
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:
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.