Calm down, Wirt, you'll be ok!

I'd like to note that the original request, though mentioning CRC, was
actually for a hashing algorithm.  Gavin correctly pointed out that this
needs to be at least a bit slick, to avoid missing ANY change in the data.
But I've often used a cyclic (sorry) function to hash on the fly, which
saves having to keep another copy of the target record...
for 1 to len(record)
  hash += hash + I * byte(I)

or some such.  While I'm sure it would be easy to devise a data change that
would result in the same hash, that would, for my purposes, simply mean that
no changes would be saved.  I'm sure the algorithms to which Gavin referred
are smarter than the above.

Tracy

> -----Original Message-----
> From: Wirt Atmar [mailto:[log in to unmask]]
> Sent: Wednesday, October 10, 2001 11:38 AM
> To: [log in to unmask]
> Subject: Re: Checksum Logic
>
>
> Gavin wrongly writes (and it startles me that he does so. I
> am shocked,
> shocked!):
>
> > Keep in mind that "standard" checksum algorithms like CRC codes were
> >  designed to detect thermal noise in a transmission line, which has
> different
> >  characteristics than deliberate changes to binary data.
> The CRC codes rely
> >  to some degree on the fact that typical transmission line
> noise comes in
> >  bursts and never changes just one bit, whereas many operations on a
> database
> >  record might only change a single bit, which would
> increase the possibility
> >  that the CRC code would miss the "error".
>
> In contrast to the above paragraph, CRC codes are designed so
> that they will
> always be able to detect single-bit errors, and they are also
> able to detect
> double-bit and all odd numbers of errors. A quick & dirty
> more-than-any-sane-human-would-want-to-know application note
> on CRC codes is
> at:
>
>      http://www.cypress.com/pub/appnotes/crc.pdf
>
> In general, CRC's can't be used to correct errors once a packet of
> information is received, only that they're present. But if
> the packet of data
> has redundant bits for the transmitted word organized as a
> Hamming code,
> single-bit (and sometimes double-bit) errors can be recovered
> on the fly
> without having to request a retransmission of the original packet.
>
> Here's a similar 2001 note from Agilent that says much the same thing:
>
>
> http://www.ietf.org/internet-drafts/draft-cavanna-iscsi-crc-vs
-cksum-01.txt

Hamming code redundancies (which are different than CRC's) are also the
basis
of all error-correcting memory (ECC RAM) and have been a part of the HP3000
since its beginning.

Wirt Atmar

* To join/leave the list, search archives, change list settings, *
* etc., please visit http://raven.utc.edu/archives/hp3000-l.html *

* To join/leave the list, search archives, change list settings, *
* etc., please visit http://raven.utc.edu/archives/hp3000-l.html *