Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!mcnc!uvaarpa!haven!ni.umd.edu!uc780.umd.edu!cs450a03
From: cs450a03@uc780.umd.edu
Newsgroups: comp.theory
Subject: RE: Hamming codes 101
Message-ID: <26MAR91.00093317@uc780.umd.edu>
Date: 26 Mar 91 00:09:33 GMT
References: <25MAR91.01330289@uc780.umd.edu> <1991Mar25.123457.24645@mailer.cc.fsu.edu>
Sender: usenet@ni.umd.edu (USENET News System)
Organization: The University of Maryland University College
Lines: 47
Nntp-Posting-Host: uc780.umd.edu

William Mayne writes        >
Me                          >>
  [... careful explanation of Hamming codes elided ...]
>>Now what if you want to correct two-bit errors?  I think you can just
>>repeat the process (make a hamming code for a 12-bit word), and go
>>through two iterations of correction and make out all right most of
>>the time (all of the time?).  But that's not even close to rigorous.
>
>I'm not sure about this. I don't think error correcting for two bit
>errors is that simple, but I haven't pursued it. Any other ideas or
>better yet informed answers?

First off, it's occurred to me that unless you permute the bits, a
second iteration of Hamming coding would be pretty silly.  If you do
permute them (say reverse order), well... I still need to think about
that. 

Second off, it should be noted that some extra corrective redundancy
can be had by applying Hamming to a smaller word.  But as the word
gets smaller you approach pure redundancy.  Here permuting might be
used to get you away from errors which hit several adjacent bits.

And, I suppose the most general way of correcting N bit errors is with
redundancy greater than 1+2N.  

Still, I think the original question that Ray (or whoever it was) was
posing was how do you get a hamming distance greater than 2 between
the encodings of a word of data.  I'm inclined to say take a Grey
code, and choose every n-th number (where n is a number that depends
on the number of bits distance you want).  

0 0 0 0 0 0    start: 0 bits distance 
0 0 0 0 0 1    n=1    1 bit distance  (straight encoding)
0 0 0 0 1 1    n=2    2 bit distance  (analogous to hamming code)
0 0 0 0 1 0
0 0 0 1 1 0
0 0 0 1 1 1    n=5    3 bit distance ????? (won't wrap around properly)
0 0 0 1 0 1

and I think n=10 is 4 bits distance.

I dunno, I still feel like I'm missing something pretty basic.

(Thanks for posting Bill, I think you did capture the exact definition
of Hamming code.)

Raul Rockwell