### Should you use a CRC or Checksum?

Please use this link to see this blog posting:

http://betterembsw.blogspot.com/2010/05/which-error-detection-code-should-you.html

- Get link
- Other Apps

Please use this link to see this blog posting:

http://betterembsw.blogspot.com/2010/05/which-error-detection-code-should-you.html

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

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

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

What do you mean: "use 1's complement addition"?

ReplyDeleteLike this? a = b + (~c)

No, that won't quite do it.

ReplyDeletehttp://en.wikipedia.org/wiki/Ones'_complement

has a discussion. The net result has to be addition in which both positive and negative zero values are taken into account.

In assembly language you wrap the carry-out back and increment if the carry-out has been set. In C it gets messy, but the usual technique is to use extra precision for the addition and catch the carry-out bits there, then add them back in later.

Ok, thank you. Can you explain why 1's complement is required. You only say it kills performance, but give no explanation. Thank you for your blog BTW, I took your advice and implemented the fletcher checksum in order to verify the ROM content of an ASIC.

ReplyDeleteOne's complement addition catches the carry-out bit of the addition and "wraps it around" back into a carry in to the lowest bit position. (That's not the mathematical definition; it's how you implement it on a two's complement computer.) It catches the case where the the highest two bits of a word are changed from 0/0 to 1/1 or the reverse because that change generates the opposite carry-out bit value. Two's complement throws that change away. One's complement wraps that changed carry-out back to the sum, detecting the change.

ReplyDeleteThe performance hit is modest or almost zero if you use a clever algorithm; high if you do it the hard way. The clever algorithms are a post for another day.