Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!samsung!munnari.oz.au!yoyo.aarnet.edu.au!sirius.ucs.adelaide.edu.au!levels!marwk
From: marwk@levels.sait.edu.au
Newsgroups: comp.arch
Subject: Re: RE: Hamming code (or other) for 4-bit correction?
Message-ID: <16047.27edd518@levels.sait.edu.au>
Date: 25 Mar 91 01:16:48 GMT
References: <16045.27ed2f20@levels.sait.edu.au> <24MAR91.12343947@uc780.umd.edu>
Organization: University of South Australia
Lines: 57

In article <24MAR91.12343947@uc780.umd.edu>, cs450a03@uc780.umd.edu writes:
> 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

I am trying to understand how to create error detection and correction codes
so that I can devise my own given a variety of circumstances.
If I have have methods of solution to the above questions then I think I could
devise my own for, say, detection of 3-bit and correction of 2-bit errors.

Ray

--
University of South Australia   | Plus ca change, plus c'est la meme chose.
P.O. Box 1                      | Ghing thien me how, ming thien gung me how.
Ingle Farm                      | Knobs, knobs everywhere,
South Australia                 |              just vary a knob to think!