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