Checksum and CRC Central

I'm not able to spend much if any time on this lately due to my work in self driving car safety. Here is a quick start for those looking for info. A tutorial on using CRCs and Checksums (how to apply them, pitfalls, system considerations; not a deep crawl through the math): https://betterembsw.blogspot.com/2013/11/crc-webinar.html A report written for the FAA on CRCs and Checksums (goes with the tutorial) https://betterembsw.blogspot.com/2015/04/faa-crc-and-checksum-report.html A web site of "best" CRCs, including: Description: https://betterembsw.blogspot.com/2010/05/whats-best-crc-polynomial-to-use.html Table of "best" CRCs for each size and length https://users.ece.cmu.edu/~koopman/crc/index.html A zoo that has performance of most published CRCs (there is a page for each polynomial size): https://users.ece.cmu.edu/~koopman/crc/crc32.html Software you can run yourself to confirm performance as a double-check on the tables (which were generated wi

Checksums and CRCs involve a repeated computation over the length of a dataword that accumulates a result to form an FCS value. The accumulation value must be initialized to some known value for this process to produce a predictable result for any given codeword. When the initial value is unstated, it is typically assumed to be zero. In some cases, a non-zero value is used instead, such as 0xFFFF for a 16-bit checksum or CRC. This has the advantage of making an all zero codeword impossible. Perhaps more importantly for Fletcher checksum, ATN-32, and CRCs, this has the additional advantage of causing leading zeros of a message to affect the FCS value. To better understand, consider a CRC initialized with an all zero seed value. Any number of all zero dataword chunks can be fed into the CRC and it will stay at a zero value, throwing away information about how many zero chunks have been processed. However, if the CRC computation is initialized to any non-zero value, processing

Nice video that talks about Hamming Codes and gives a hypercube explanation that helps understand Hamming Distance Perfect Codes: https://youtu.be/WPoQfKQlOjg on computerphile.

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

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:     http://users.ece.cmu.edu/~koopman/crc/ 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 e

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. Note that any "perfect" pseudo-random number generator will produce HD=1, including cryptographically