Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!wuarchive!rex!uflorida!mailer.cc.fsu.edu!zeta!mayne
From: mayne@zeta.cs.fsu.edu (William Mayne)
Newsgroups: comp.theory
Subject: Re: Hamming codes 101
Message-ID: <1991Mar25.123457.24645@mailer.cc.fsu.edu>
Date: 25 Mar 91 17:34:57 GMT
References: <25MAR91.01330289@uc780.umd.edu>
Reply-To: mayne@nu.cs.fsu.edu
Organization: Florida State University Computer Science Department
Lines: 55

In article <25MAR91.01330289@uc780.umd.edu> cs450a03@uc780.umd.edu writes:

[Description and example of a Hamming code omitted.]

Here is an alternative description of a Hamming code which I think is
easier to understand and generalize.  The purpose of the code is to
detect and correct 1 bit errors in blocks of bits. Number the bits
1,2,3,...n, including both data and check bits. The trick is to devise
a check function which will be 0 if no bit errors have occurred and
will indicate the location of any single bit error. Any block containing
a one bit error can then be corrected by changing the indicated bit.

The required check function is based on the bit wise exclusive or of
the binary representation of the position of each bit which is 1.
The check bits are all those whose indexes are powers of 2. It is
convenient to number the bits of a block so that the check bits are
all collected together at the end, thus:

[data]  3,5,6,7,9,...n
[check] int(log2(n)),...,4,2,1

This assumes that n itself is not a power of 2. Otherwise it would
be a check bit. The method would still work, but is easier to explain
if n is not a power of 2 and is actually most efficient when n=2**m-1.

The values of the check bits can be computed by computing the check
value of the data bits. The binary representation of the result gives
the bit string for the check bits (right justified). It is easy to see
that this makes the check value of the whole block 0, and that if one
bit is changed the new check value will be the position of that bit,
regardless of whether it is a data bit or a check bit. This is the most
efficient possible coding which will detect and correct one bit errors.

Since only int(log2(n)) extra bits are required for n-int(log2(n)) data
bits the efficiency increases exponentially with the block size, but so
does the chance of a 2 bit error.

Implementation may be easier and reliability improved if several
checks are performed in parallel. For example, given a stream of
8 bit bytes to be encoded, compute 8 check values, so each byte
contributes just one bit to each of the check values. Besides
being arguably easier to program (less bit shifting), this will
correct errors in up to 8 consecutive bits, an advantage if noise
is likely to occur in short bursts.

>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?

Bill Mayne (mayne@cs.fsu.edu)