[94B99] (72,64,4) codes over F_2: can you name a good one?
Henry Baker
[This message has been forwarded from sci.math. --hbaker]
In article <1996Oct1520...@koobera.math.uic.edu>,
d...@koobera.math.uic.edu (D. J. Bernstein) wrote:
> Short version: Apparently there's a size-2^64 binary code of length 72
> and distance 4 suitable for hardware implementation. Can you name it?
>
> Long version: If you're purchasing a PC today you can spend about 15%
> extra on memory to get parity RAM. Parity RAM stores each 8-bit byte in
> 9 bits, normally using ``odd parity,'' the complement of the obvious
> (9,8,2) code. Odd parity will detect any single-bit error and halt the
> computer.
>
> It's possible to spend substantially more for ECC RAM, which uses extra
> bits (I don't know how many) for a higher-distance code (I don't know
> which one) so that it can correct single-bit errors, letting the
> computer continue while it informs you that your memory is going bad.
>
> Enter the Intel 430HX chipset. Here's where the story gets interesting.
> According to Intel, a 430HX-based motherboard will do single-bit error
> correction and double-bit error detection---with parity RAM!
>
> Pentium-class machines access memory in 8-byte chunks. Supposedly the
> 430HX uses the relevant 8 bits of parity for an error-correcting code.
>
> So now I'm curious what code Intel is using. Is there an obvious
> (72,64,4) code that's easy to implement?
>
> ---Dan
Kai Harrekilde-Petersen
hba...@netcom.com (Henry Baker) writes:
>
> [This message has been forwarded from sci.math. --hbaker]
>
> In article <1996Oct1520...@koobera.math.uic.edu>,
> d...@koobera.math.uic.edu (D. J. Bernstein) wrote:
>
> > Short version: Apparently there's a size-2^64 binary code of length 72
> > and distance 4 suitable for hardware implementation. Can you name it?
> >
[snip]
> > Enter the Intel 430HX chipset. Here's where the story gets interesting.
> > According to Intel, a 430HX-based motherboard will do single-bit error
> > correction and double-bit error detection---with parity RAM!
From the 430HX data sheet I've looked at, it seems that the HX uses
that same ECC code as the P6 processor. It's a SECDED (Single Error
Correction - Double Error Detection) code, which is also able to
detect 3 and 4bit errors that are confined to nibbles. The algorithm
is discussed in 'the litterature' (Intel just refers to the article
and then proceeds to discuss the thigns you need to know to implement
the ECC).
So how can you do this with parity RAM? Well, as long as the chipset
does RMW cycles when sub-8 bytes writes occur, you're home free.
Kai
--
Kai Harrekilde-Petersen <k...@dolphinics.no> #include <std/disclaimer.h>
http://www.dolphinics.no/~khp/ Linux: the choice of a GNU generation
Route 287 - Where Men are Men and sheep are nervous ...
Del Cecchi
In article <kk3sp7f...@scimitar.dolphinics.no>, Kai Harrekilde-Petersen <k...@dolphinics.no> writes:
|> hba...@netcom.com (Henry Baker) writes:
|>
|> >
|> > [This message has been forwarded from sci.math. --hbaker]
|> >
|>
|> From the 430HX data sheet I've looked at, it seems that the HX uses
|> that same ECC code as the P6 processor. It's a SECDED (Single Error
|> Correction - Double Error Detection) code, which is also able to
|> detect 3 and 4bit errors that are confined to nibbles. The algorithm
|> is discussed in 'the litterature' (Intel just refers to the article
|> and then proceeds to discuss the thigns you need to know to implement
|> the ECC).
|>
|> So how can you do this with parity RAM? Well, as long as the chipset
|> does RMW cycles when sub-8 bytes writes occur, you're home free.
|>
|>
type simms use DRAM with multiple bits per chip, so SECDED codes will not correct
errors resulting from a total chip kill. I don't have the figures handy as to
what percentage of chip failures are single bit, vrs word line or chip kills.
But a significant percentage of hard errors are multiple bit. Soft errors caused
by alpha particles are single bit.
Crashes due to bad memory are of course dwarfed in number by those caused by bad
programs or bad electricity. :-)
|> Kai
|> --
|> Kai Harrekilde-Petersen <k...@dolphinics.no> #include <std/disclaimer.h>
|> http://www.dolphinics.no/~khp/ Linux: the choice of a GNU generation
|> Route 287 - Where Men are Men and sheep are nervous ...
--
Del Cecchi
Personal Opinions Only.
Kevin Normoyle
I'm flummoxed about what the game is.
8 check bits for 64 data bits? Sure, there's lots of codes.
Maybe the mistake is in saying "detects double-bit errors"
Generally the codes detect "2 or more errors". I don't know of
any that can say "exactly 2 errors", with (72,64)
With 8 check bits you can get codes to detect any error within groups of 4 bits.
Some of the codes are optimized for sharing xor terms, or balancing the number
of loads on the data bits.
Some codes are optimized so that byte parity is easily produced at the same
time. (useful if you're writing to parity sram, from ecc dram!)
-kevin
Jan Vorbrueggen
cec...@signa.rchland.ibm.com (Del Cecchi) writes:
> Just so people don't have a false sense of security, a reminder. Most (all?)
> PC type simms use DRAM with multiple bits per chip, so SECDED codes will not
> correct errors resulting from a total chip kill.
IIRC, you can design a 72,64 code that will:
- detect and correct all 1 bit errors
- detect all 2 bit errors and some of the 3 and 4 bit errors
- detect (and correct?) all aligned nibble (4 bit) stuck-at errors, which are
typical of failed chips.
Jan