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

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

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.