Re: Disk II Checksum

[russotto@grace.speakeasy.net (Matthew T. Russotto)]

In article <UomdnRsI-69uulDYnZ2dnUVZ_tKjnZ2d@comcast.com>,
Michael J. Mahon <mjmahon@aol.com> wrote:
>Alex Freed wrote:
>> "Michael J. Mahon" <mjmahon@aol.com> wrote in message 
>> SLydnXx975xZfVHYnZ2dnUVZ_uPinZ2d@comcast.com">news:SLydnXx975xZfVHYnZ2dnUVZ_uPinZ2d@comcast.com...
>> 
>>>There is one chance in 256 of an incorrect read producing
>>>a correct checksum, but this level of integrity checking
>>>seems to be sufficient.
>> 
>> 
>> 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).

That's not an "all errors are equally probable".  "All errors are
equally probable" means that every pattern of bits other than the
correct one is equally probable.  It's not a bad model in some cases
(e.g. sampling RF when the transmitter is normally off the air.  Or
reading a degaussed disk, so all you're really reading is noise), but
it's not the proper model for the Disk II under normal circumstances. 

>We already know that checksum errors are rare.  Therefore
>the ones that happen are essentially random in their effect
>on the checksum.
>
>> I'm not an expert at all, but as I recall it CRC was invented
>> because the odds of finding an error are much better than
>> using a simple 16 bit checksum.
>
>There is still a 1-in-2^16 chance of accidental match.
>
>The CRC was chosen to maximize robustness under the assumption
>of certain kinds of channel errors.

Precisely those which occur in a Disk II, in fact.  But in practice
the checksum works well enough.  And even an a 8-bit CRC is much more
compute-intensive, dozens of instructions per byte compared to one.


-- 
  There's no such thing as a free lunch, but certain accounting practices can
  result in a fully-depreciated one.