[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Disk II Checksum
Alex Freed wrote:
"Michael J. Mahon" <mjmahon@aol.com> wrote in message
UomdnRsI-69uulDYnZ2dnUVZ_tKjnZ2d@comcast.com">news:UomdnRsI-69uulDYnZ2dnUVZ_tKjnZ2d@comcast.com...
Assuming all errors are equaly probable.
Which is a reasonable assumption, since the only
categories of errors in the Disk ][ serial channel are
random bit flips (extra pulse or missing pulse) or
burst errors (media blemish).
Michael, I'm not claiming that's not true but I'm not sure
that it is true either.
For example the recorded bytes are far from random: high
bit is always set and only some values are legal.
We know that more than 2 zeros back to back make reading
not reliable. Consider a byte like 100100xx.
If the "1" in bit 4 reads as "0" this can be messy.
Again I'm not claiming this changes the odds in any particular way,
but the odds may not be exactly 1/256.
I get your point, Alex.
I'll have to take a look at exactly what is being EORed to make
the checksum. I think that it's the 6-bit value prior to conversion
to a nibble, so perhaps the "strength" of the checksum is only 6 bits,
not 8 (again, under the assumption of uncorrelated errors).
Of course, the values of these 6 bits may not be equidistributed
(probably aren't), which would lower the strength a little more.
I recall many years ago doing a quick "pop count" on 1's in Apple II
programs, and found that only about a third of the bits were 1's, which
certainly reduces the entropy, and so the effectiveness of a simple
checksum technique.
As you pointed out (in the case of a CRC), the closer the checksum
routine is to an encryption-strength hash, the more closely its
error detection effectiveness approaches the maximum value of 1:2^n.
Simple checksum techniques fall short of this ideal, but fortunately
can still be "good enough", based on experience.
-michael
NadaNet networking for Apple II computers!
Home page: http://members.aol.com/MJMahon/
"The wastebasket is our most important design
tool--and it's seriously underused."