Posts

Explanation of CRC Operation: Polynomial Division, Shift Register, and Comparison (video)

Image
 Here is a video explaining the mechanics of Cyclic Redundancy Check computations, including: An example of the polynomial division approach An example of the XOR-feedback shift register approach A step-by-step comparison of how the polynomial division and shift register approaches are actually doing exactly the same computation. If you've ever wondered why it is that a shift register and polynomial division end up with the same result, this video explains it. Video links (27 minutes):    YouTube | Archive.org

Pending clean-up of papers

 I received the following comments with potential issues in some of my work.  I'm delighted to receive such feedback since a major point of my work is to try to get a complex topic straight. At the moment I'm fully engaged working on self-driving car safety so it will be a while before I can resolve these. However, in the spirit of transparency here are the points raised so you know to be careful on these points when reading my work. (This is posted with permission conditioned on anonymity. Thanks to the person who sent the comments.) ---------------------------------------------- 1) On page 5 of http://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf you say that SMBus uses CRC-8, polynomial 0xEA in your notation and say that 0x83 would be better. I am not familiar with SMBus but three sources say that the polynomial chosen for SMBus was 0x83. CRC Catalogue entry CRC-8/SMBUS lists poly=0x07 (they use what Wikipedia calls Normal form) SMBus Spec page 27 cl

CRC Information Quick Start

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

Effect of Initial Seed Values on CRCs and Checksums

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

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: https://youtu.be/WPoQfKQlOjg on computerphile.

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

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