Re: Opinions on 16-bit checksums.

From: Neil Bradley (nb_nospam_at_synthcom.com)
Date: 08/26/04 

Date: Wed, 25 Aug 2004 22:48:39 -0700

"Grant Edwards" <grante@visi.com> wrote in message
news:412d5fd1$0$8088$a1866201@newsreader.visi.com...
> On 2004-08-26, Neil Bradley <nb_no_spam@synthcom.com> wrote:
>>> 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".

Agreed - MD2/MD5 come to mind, as they're also well suited for the job, but
significantly more expensive to implement. Our last project had a 40Mhz
cacheless ARM fetching code from an external flash using MD2 and it
significantly slowed things down.

However, I'd contend if you are doing more than "Adding up the bytes", then
it's no longer a checksum, but a check code. Note the operative word "sum"
in checksum...

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

But not as many as checksum. You can reverse two bytes in a file and a
traditional checksum won't catch it, but a CRC most likely will. If you
don't believe me, try it yourself.

>> 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". ;)

Consider yourself lucky, then. You yourself have already proven that
checksums aren't the best things. Not to say that CRCs are the ultimate, but
I'd bank $$ on it that CRCs are better than traditional checksums.

> But, a 16-bit CRC can still only generate 65536 different
> output states.

Same deal with a 16 bit checksum. ;-)

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

The question becomes one of the nature of "naturally occuring" failures and

> 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 think you're really talking about "check codes" rather than traditional
checksums. Surely you don't think that a traditional 16 bit checksum is as
good as a CRC...

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

CRC Is good at catching occasional byte errors, or small bursts. It's not
the type of data errors that occur on a serial link, but rather the nature
of when they occur.

I own an arcade, and I've had several video games over the course of the
last 1.3 years (Galaga 88, Marble Madness, and Battlezone to be specific) -
all use checksums - reported no failures in their ROM sets, yet when read in
their 16 bit CRCs were different. They were using 8 bit or 16 bit checksums
(G88/MM Were 16 bit traditional and Battlezone is an 8 bit).

Compared to a traditional 16 bit checksum, a CRC 16 is better. Compared to
other "checksums", well, obviously their merits will have to stand on their
own, and I'm sure even better algorithms could be made.

-->Neil

-->Neil

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.
    ... out there besides CRC and "add up the bytes". ... There are other checksum ... I don't think it can be assumed that ROMs ... ROMs do have the same error characteristics as a serial data ...
    (comp.arch.embedded)
  • Re: TECH: Asteroids Version Verification?
    ... ROMs other than doing checksum or the invincible spaceship thing in the high score area? ... Have Atari-marked -02 roms in a newly acquired asteroids; checksums read same as the -01 version rom images on the gamearchive.com. ... Either the PO re-burned the roms with the -01 version, or the version vs. checksum values at the game archive site is backwards. ...
    (rec.games.video.arcade.collecting)