Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!apple!amdcad!jetsun!weaver
From: weaver@jetsun.weitek.COM (Mike Weaver)
Newsgroups: comp.arch
Subject: Re: Hamming code (or other) for 4-bit correction?
Message-ID: <1991Mar25.183838.27404@jetsun.weitek.COM>
Date: 25 Mar 91 18:38:38 GMT
References: <16045.27ed2f20@levels.sait.edu.au>
Reply-To: weaver@jetsun.WEITEK.COM (Michael Weaver)
Organization: WEITEK, Sunnyvale CA
Lines: 22

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