Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ncar!gatech!purdue!haven!ni.umd.edu!uc780.umd.edu!cs450a03
From: cs450a03@uc780.umd.edu
Newsgroups: comp.arch
Subject: RE: Hamming code (or other) for 4-bit correction?
Message-ID: <24MAR91.12343947@uc780.umd.edu>
Date: 24 Mar 91 12:34:39 GMT
References: <16045.27ed2f20@levels.sait.edu.au>
Sender: usenet@ni.umd.edu (USENET News System)
Organization: The University of Maryland University College
Lines: 43

Ray (markw@levels.sait.edu.au) writes:
>Suppose one has 32-bit words and 8 more bits/word for error detection and
>correction.
> 
>(1) Can the hamming code for 32-bits (requiring 6 bits) be modified
>    to detect 2-bit errors (as well as correct 1-bit errors)?
> 
>(2) How about correcting 4-bit errors?

Ok, Hamming applications 101:

(1) you aren't going to get protection from errors occuring more
frequently than 1/word without adding a bunch of extra correction
bits.  This has severe diminishing return problems.

(2) Heuristically, errors can be grouped into three categories, Small,
Medium, and Large (yeah, you can add Extra-Large if you feel like it).

Small are practically instant, and generally show up as a flipped bit.
Hamming deals specifically with this case.

Medium usually means line noise, or something like that, that steps on
a bunch of words, but goes away quickly.  You can deal with this by
re-arranging your transmission so that, ferinstance, you send all the
bit-zeros of each word, and then all the bit-ones, then bit-twos, etc.
This spreads out your transmission so that a medium sized glitch shows
up as a bunch of small ones, which can be corrected.  Not practical
for memory-cpu transfers, unless you've got a really wierd setup (so
just say there is no 'medium' case there).

Large is something so bad it trashes everything (I suppose Extra-Large
would trash your machine too).  Best defense against this is
redundancy (backups, backtracking, or running several machines on the
same problem and comparing results).

As for detecting:  all error detection techniques guarantee that an
error will be detected under some set of circumstances, and that an
error will probably be detected under some other set of circumstances.
You just need to pick a technique tuned for your particular
circumstances.  (Significant questions:  What are you trying to do?
What are you afraid of?  What bad things have happened?)

Raul Rockwell