Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!ncar!gatech!prism!mailer.cc.fsu.edu!delta!mayne
From: mayne@delta.cs.fsu.edu (William Mayne)
Newsgroups: comp.theory
Subject: Re: Hamming codes 101
Message-ID: <1991Mar26.100044.16609@mailer.cc.fsu.edu>
Date: 26 Mar 91 15:26:53 GMT
References: <25MAR91.01330289@uc780.umd.edu> <1991Mar25.123457.24645@mailer.cc.fsu.edu> <26MAR91.00093317@uc780.umd.edu>
Reply-To: mayne@cs.fsu.edu
Organization: Florida State Universiy Computer Science Department
Lines: 90

In article <26MAR91.00093317@uc780.umd.edu> cs450a03@uc780.umd.edu writes:
>  [... careful explanation of Hamming codes elided ...]

Thanks, but as I think back on it it wasn't so careful.
When I gave the indexes of the check bits it should obviously have been:

2**(log2(n)),...,4,2,1

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

You are right, at least about the first part. Also I can't think of
any way to permute the bits for a second application of a Hamming code
to correct 2 bit errors. But surprisingly (to me) the number of
redundant bits needed to correct errors in up to 2 bits is only about
twice that required for 1 bit correction. I would have expected more
than 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.

The method I described of slicing words of a message into bits and
applying Hamming coding to corresponding bits from consecutive words
will work to correct errors in n consecutive bits, where n is the
word size, whether or not the n or fewer consecutive corrupted bits
cross a word boundary.

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

The exact amount of redundancy needed for a word size of n (where n
counts both bits of useful data and check bits) is:

n=1 -> log2(n+1)  [This proves the Hamming code is the most efficient
                  possible to correct 1 bit errors.]

n=2 -> log2(n**2+1) [Only twice as many check bits.]

n=3 -> log2(n**3-2*n**2+2*n+1) [Unless I've made an algebraic mistake,
                               which is not unlikely.]

The general rule for this is derived as follows:

For n bits there are 2**n distinct configurations.
If there are up to m bits which may be corrupted there are f(m,n)
different ways that one intended message can be code, where f(m,n)
is as defined below. So n bits with up to m errors can contain
(2**n)/f(m,n) different messages, or log2 of that many bits of
data. Thus the number of bits devoted to error correction is
log2(f(m,n)).

To construct f(m,n) we have to ask how many configurations there
are for a given message with Hamming distance less than or equal
to m. For m=1 this is n+1 (the correct version plus one for each
possible error position). For m=2 is is n(n-1)+n+1=n**2+1,
i.e. n(n-1) with 2 bad bits, n with 1 bad bit, and 1 with no bad bits.
For m=3 it is n(n-1)(n-2)+n(n-1)+n+1. It is hard to represent the
general form in ascii, but you just keep adding terms on the left
as n(n-1)(n-2)...(n-m-1). Obviously the result with be O(n**m).

This establishes the lower limit on redundancy. The Hamming code for
m=1 is optimal and the specific coding used is elegant since it is
so easy to understand and compute. Unfortunately I don't any elegant
codes for m>1, or if there is a general rule to construct them in
an elegant way.

CAVEAT: This isn't really my specialty. I've had only minimal
formal instruction in error correcting codes and derived the
formula and proof that Hamming codes are optimal myself. If
I've made some gross error either in my thinking or in typing
it in I expect I'll hear about it. Asbestos suit on.

>[Suggestion based on Grey code omitted.]

I believe the idea is correct, if I understand you correctly.
But this doesn't answer the question of how to actually map
data to and from the redundant representation needed. It would be
nice if there is a simple algorithm such as the one for the Hamming
code which could be applied for any number of errors. Unfortunately
I don't have time to pursue that.

Bill Mayne (mayne@cs.fsu.edu)