Re: Opinions on 16-bit checksums.
From: Grant Edwards (grante_at_visi.com)
Date: 08/26/04
- Next message: jah: "9S12DP256 board"
- Previous message: Anthony Simpson: "Ethernet based programable sensors"
- In reply to: Neil Bradley: "Re: Opinions on 16-bit checksums."
- Next in thread: CBFalconer: "Re: Opinions on 16-bit checksums."
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 26 Aug 2004 14:38:48 GMT
On 2004-08-26, Neil Bradley <nb_nospam@synthcom.com> wrote:
>> There are plenty of changes that "cancel themselves out" for a
>> CRC as well.
>
> But not as many as checksum.
People keep _saying_ things like that, but nobody ever has any
real evidence that it's true.
Let's say you've got a 1024 byte block you're summing. There
are 2^8192 possible combinations of bits. For _any_
well-behaved[1] 16-bit checksum (CRC or otherwise), There are
2^8176 - 1 bit patterns that are wrong but generate the correct
sum.
[1] By "well behaved" I mean that all output values are equally
likely for a random input stream.
> 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.
Possibly, but what makes you think there aren't just as many
other types of errors that a CRC will miss and a different
algorithm will catch?
> 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.
I'm sure if it was settled by majority vote CRC would win, but
in math, things aren't settled by majority vote.
>> 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
That's my point. CRCs are well suited to the errors than
naturally occur in serial communictions. Nobody seems to care
that ROMs probably do not not have the same naturally occuring
failure modes.
> I think you're really talking about "check codes" rather than
> traditional checksums.
OK, whatever. Such "check codes" are traditionally called
checksums. CRC results are often called checksums, even though
they're remainders of polynomial division or something like
that. What happens when you run the md5sum program? Hint: it
doesn't just add up all the byte values.
> Surely you don't think that a traditional 16 bit checksum is
> as good as a CRC...
It probably isn't, but I'd like some real, statistical evidence
rather than a bunch of hand-waving and anecdotes.
> 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.
Huh? I don't get the difference between the "type of error"
and "the nature of when they occur". In binary data the
"nature of when they occur" is the only thing that matters
unless you want to differentiate between errors based on the
actual value of the original bit.
Burst errors are one type of error, lots of randomly
distributed single-bit errors are another type.
> I own an arcade, and I've had several video games...
> [anecdotes elided]
> Compared to a traditional 16 bit checksum, a CRC 16 is better.
A lot of people believe that (myself included), but that belief
does not constitute evidence. We're supposed to be engineers
here...
> 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.
Maybe not. It could be that CRCs are the best you can get. I
just want somebody to point to to a source with a real
argument.
--
Grant Edwards grante Yow! You should all JUMP
at UP AND DOWN for TWO HOURS
visi.com while I decide on a NEW
CAREER!!
- Next message: jah: "9S12DP256 board"
- Previous message: Anthony Simpson: "Ethernet based programable sensors"
- In reply to: Neil Bradley: "Re: Opinions on 16-bit checksums."
- Next in thread: CBFalconer: "Re: Opinions on 16-bit checksums."
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
