cs450a03@uc780.umd.edu (03/24/91)
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
marwk@levels.sait.edu.au (03/24/91)
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?
It is ok to put 2 or more words together and correct on the lot (eg 512 bytes).
In fact this would be necessary as 2 bits more is not enough for (2), but of
course only 1 more hamming bit is required for every extra power of 2 in the
number of bits the code is produced for.
If the Hamming code cannot be modified then what is another code for this.
I cannot find anything in the literature and I cannot work it out with
a pencil. Maybe I am looking in the wrong place?
Thank you.
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!cs450a03@uc780.umd.edu (03/25/91)
Ray something-or-another writes: >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. Oh, you wanted to know how hamming codes are devised? Why didn't you say so in the first place? And why wasn't the first place comp.theory? I'll post a real follow-up there. Raul Rockwell
marwk@levels.sait.edu.au (03/25/91)
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!
davidsen@crdos1.crd.ge.COM (Wm E Davidsen Jr) (03/25/91)
In article <16045.27ed2f20@levels.sait.edu.au> marwk@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)? Yes, but I'm not sure it's called Hamming, I just can't remember what it should be called. | (2) How about correcting 4-bit errors? You are getting into the area of Fire codes, and I think people are still writing theses about it. I used to understand it, mostly, while reading the papers. I don't now. Please enter theorist, stage left... -- bill davidsen (davidsen@crdos1.crd.GE.COM -or- uunet!crdgw1!crdos1!davidsen) "Most of the VAX instructions are in microcode, but halt and no-op are in hardware for efficiency"
weaver@jetsun.weitek.COM (Mike Weaver) (03/26/91)
In article <16045.27ed2f20@levels.sait.edu.au> marwk@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? Hamming code is a single error correcting code (actually, any single bit correcting code is called 'Hamming' by courtesy). To make it also detect two bit errors, you add a parity bit. If the parity bit is correct, but the other ECC bits indicate error, you know that you have two (or more) bits in error. In this case, you would end up with 7 bits to add to the original 32. See Richard W. Hamming, 'Coding and Information Theory', Prentice, 1980. Multiple error correction codes exist, of course (e.g. Fire Code, Reed-Solomon, BCH). Most of them are geared towards bursts of errors in 'long' blocks because this is the most common requirement for multiple error correction. The book I have on the subject (don't have it here) is by Blaauw, and the title is approximately 'Error Correction Codes'.
davidsen@crdos1.crd.ge.COM (Wm E Davidsen Jr) (03/26/91)
In article <16047.27edd518@levels.sait.edu.au> marwk@levels.sait.edu.au writes: | 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. I think a check of the literature will show some better approaches than hamming, and you don't even have to invent them. And if you want to roll your own it would be nice if it wasn't identical to something already known. -- bill davidsen (davidsen@crdos1.crd.GE.COM -or- uunet!crdgw1!crdos1!davidsen) "Most of the VAX instructions are in microcode, but halt and no-op are in hardware for efficiency"