Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!ukma!uunet!nbires!maa
From: maa@nbires.UUCP
Newsgroups: comp.arch
Subject: Re: Double-bit errors and ECC memory
Message-ID: <1215@nbires.UUCP>
Date: Sat, 12-Sep-87 13:37:53 EDT
Article-I.D.: nbires.1215
Posted: Sat Sep 12 13:37:53 1987
Date-Received: Sun, 13-Sep-87 10:19:05 EDT
References: <1184@itm.UUCP> <797@spar.SPAR.SLB.COM> <2891@phri.UUCP> <7319@steinmetz.steinmetz.UUCP>
Reply-To: maa@nbires.UUCP (Mark Armbrust)
Organization: NBI Inc, Boulder CO
Lines: 38

In article <7319@steinmetz.steinmetz.UUCP> oconnor@sunray.UUCP (Dennis Oconnor) writes:
>Sorry, this is incorrect. To perform just SINGLE bit error CORRECTION
>you need 1+log2(word-width) bits of ECC bits. That means you need
>6 bits for a 32-bit word, 5 for a 16-bit halfword, and 4 for a byte.
> <etc.>

Not strictly true!  I can remember reading (sorry, too long ago to remember
where) about a clever way to detect and correct all single bit errors, detect
all double bit errors, and correct most double bit errors USING ONE BIT PER
WORD.

The idea is that each parity bit is calculated as the mod 2 sum of all the bits
in the word plus one bit from each word at addresses +- n where n is the word
size:

n+8  p7654321*
n+7  p765432*0
...
n+2  p7*543210
n+1  p*6543210
n    X********		parity bit X calculated as mod 2 sum of *'s
n-1  p*6543210
n-2  p7*543210
...
n-7  p765432*0
n-8  p7654321*

God only knows how this could be implemented in a real memory system though;
to do a read/write you need to check/set the parity bits on all words +-n which
means reading all words +-2n.

Maybe some clever VLSI hack will do it for us.  8-)

Mark

P.S.  If anyone out there knows of any references to this type of coding, I'm
interested.  I was just a dumb (smartass?) college kid when I read (and mostly
forgot) this stuff!