Re: Opinions on 16-bit checksums.

From: Grant Edwards (grante_at_visi.com)
Date: 08/26/04 

Date: 26 Aug 2004 03:58:09 GMT

On 2004-08-26, Neil Bradley <nb_no_spam@synthcom.com> wrote:

>> Any 16 bit sum (CRC or otherwise) maps every possible state of
>> the ROM into one of 65536 resulting "checksum" numbers. An
>> error is only detected when that mapping differs between the
>> correct state and the error state.
>
> It does map the values, but it does not take in to account
> position or anything else.

That depends on the algorithm you choose. It's true for some
and not true for others. There are tons of hashing algorithms
out there besides CRC and "add up the bytes".

> For example, your traditional 16 bit checksum
> (even/odd/additive approach) would not catch values that
> cancel themselves out, but a CRC would.

There are plenty of changes that "cancel themselves out" for a
CRC as well. For example: any time the current value of the
sum is 0, you can insert a block of zeros of any length into
the data without changing the sum. There are other checksum
algorithms that would detect such an error in the data stream.

>> However, I've never seen any information on failure modes and
>> statistics of ROMs. Without that information, how can one
>> claim that a CRC is better than, say, the IP checksum
>> algorithm?
>
> In 20 years of embedded systems development when 16 bit (or
> bigger) CRCs are used, I've witnessed no failures or oddities.
> During that period I've had about a dozen failures with
> checksums. Simple experience dictates it as such.

I've been doing embedded systems development for 20 years as
well, and have never seen either one fail. Therefore "simple
experience dictates they're equal". ;)

> Plus, I'm not a math whiz, but IIRC, CRC is significantly
> better than checksum because it also has data position order
> and sequence dependencies, and checksum doesn't.

But, a 16-bit CRC can still only generate 65536 different
output states. Therefore, there are billions of different
changes to a ROM that "cancel out" and generate the same CRC --
just as there are billions of changes that can occur and
generate the same IP checksum.

Unless you know what the characteristics of those changes are,
and can show that they're less likely for the CRC than the
types of changes that "cancel out" for other types of
checksums, you've got no real argument that CRCs are better
than others.

I'm not saying that for verifying a ROM, CRC's _aren't_ better
than the IP checksum, but I've never seen anybody who was able
to present any evidence that they are, either.

There _is_ plenty of evidence that the characteristics of a CRC
are well suited to the types of errors that occur in serial
data communications. I don't think it can be assumed that ROMs
have those same error characteristics. Perhaps I'm wrong and
ROMs do have the same error characteristics as a serial data
link. If so, just a few cites is all I ask. 

-- 
Grant Edwards                   grante             Yow!  Are you still an
                                  at               ALCOHOLIC?
                               visi.com

Relevant Pages

  • Re: CRC versus CheckSum
    ... I have a situation where I have a byte in which to place either a checksum ... Our packets cannot have bytes in a packet swapped in order (the transport ... jsut as good as the CRC. ... Neither detect all errors (there are after all the same number of states for the sum in either case). ...
    (comp.arch.embedded)
  • Re: Opinions on 16-bit checksums.
    ... >> possibly result in an unchanged CRC checksum. ... > There are two big reasons CRCs are used in serial communications: ... algorithms that consider the order of the data as well as the value - a ...
    (comp.arch.embedded)
  • Re: Crc16 on power failure
    ... a checksum is faster to calculate than a CRC by software. ... True, they are faster, but they are not nearly as good at detecting ... coonsider running an EEC on each parameter instead of a block check. ...
    (comp.arch.embedded)
  • Re: Opinions on 16-bit checksums.
    ... it's no longer a checksum, ... >> cancel themselves out, but a CRC would. ... I've witnessed no failures or oddities. ... I don't think it can be assumed that ROMs ...
    (comp.arch.embedded)