Please use this link to see this blog posting:
http://betterembsw.blogspot.com/2010/05/which-error-detection-code-should-you.html
Subscribe to:
Post Comments (Atom)
-
Sometimes we hear that someone plans to use a hash function for fault detection instead of a checksum. This is probably not the best idea, b... -
Comparative speeds for different Checksum & CRC implementations. For more information see my new book: Understanding Checksums and Cy... -
I'm thinking about why a Hamming Distance of 6 for network checksums/CRCs is so often found. Certainly that is designed into many networ...
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.