Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!ames!haven!ni.umd.edu!uc780.umd.edu!cs450a03
From: cs450a03@uc780.umd.edu
Newsgroups: comp.theory
Subject: Hamming codes 101
Message-ID: <25MAR91.01330289@uc780.umd.edu>
Date: 25 Mar 91 01:33:02 GMT
Sender: usenet@ni.umd.edu (USENET News System)
Organization: The University of Maryland University College
Lines: 38
Nntp-Posting-Host: uc780.umd.edu

This is to follow up to another posting by Ray something-or-other (in
another newsgroup).  Last time I dealt with this stuff was in '89, so
feel free to jump on me where I screw up.

Hamming codes, in their basic form, are a specialized application of
parity.  Essentially, bits can be grouped together, and parity can be
computed for each grouping, so that if some error flips one of the
bits (either data or parities) it leaves a signature which can spot
the impact point.

Example, take an 8 bit word: bit 1, bit 2, bit 3, bit 4, ... bit 8
assign 4 parity bits, call them bit 9, bit 10, bit 11, and bit 12

call bits 1 3 5 7 and 9 a grouping, and set bit 9 for odd parity
call bits 2 3 6 7 and 10 a grouping, and set bit 10 for odd parity
call bits 4 5 6 7 and 11 a grouping, and set bit 11 for odd parity
call bits 8 thru 12 a grouping, and set bit 12 for odd parity

That feels a bit lumpy, but nevermind...

Now, an error flips a bit, and wango, you get the bit's address in the
parity bits (bit 9, 11 go off, that's 12 11 10 9 : 0 1 0 1 : error in
bit 5.

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.  

Somebody want to bail me out here, before I reveal myself as a total
idiot?

Thanks,

Raul Rockwell

P.S. remember: underlying assumption is we're just considering
bit-flipping, no framing errors.