Fault tolerant memory using bus bit aligned Reed-Solomon error correction code symbols

• US 5,313,464 A
• Filed: 05/05/1992
• Issued: 05/17/1994
• Est. Priority Date: 07/06/1989
• Status: Expired due to Term

• Current Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Reiff, Francis H.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Vales, Phillip
• Application Number:
  US07/878,749
• Time in Patent Office: 742 Days
• Field of Search: 371/2.1, 371/2.2, 371/38.1, 371/40.4, 371/40.1, 371/39.1
• US Class Current: 714/701
• CPC Class Codes: G06F 11/1028 Adjacent errors, e.g. error in n-bit (n>1) wide storage units, i.e. package error

Abstract

A symbol interleaving method for organizing data in a semiconductor memory such that fault tolerance of the memory is optimized when used in conjunction with a Reed-Solomon burst error correcting code. The Reed-Solomon symbols are aligned with respect to the bus bits of the memory such that the impact of a bus bit failure that affects all memory devices in the memory using the bus is constrained within the correction capability of the ECC. The symbols also are distributed among the memory devices in order to maximize fault tolerance. Up to two memory devices in the preferred embodiment may fail without exceeding the correction capability of the code.

Claims

1. In a memory having a plurality of random access memory devices and being adapted to receive over a multi-bit data bus multiple bit Reed-Solomon error correction code symbols corresponding to a block of data, a symbol level interleaving method for organizing said multiple bit Reed-Solomon error correction code symbols in said memory to maximize resistance to failure of bit paths of said data bus or failure of said memory devices, said method comprising the steps of:

conveying the bits of a predetermined number of said Reed-Solomon error correction code symbols to each one of said memory devices via the bit paths of said data bus; and

storing the bits of each of said Reed-Solomon error correction code symbols in like bit positions of a plurality of memory bytes in said memory devices, the number of memory bytes being equal to the number of bits in each of said symbols.

2. The method recited in claim 1 wherein said multiple bit Reed-Solomon error correction code corrects a predetermined maximum number of said symbols and wherein said step of storing includes storing no more than one-half of said predetermined maximum number of symbols correctable by said Reed-Solomon error correction code in each of said memory devices.

3. A memory system for storing a block of data arranged into multiple-bit Reed-Solomon error correction code symbols and having a plurality of random access memory devices arranged into at least two columns with said memory devices of one of said columns being connected to a first group of bit paths of a data bus for conveying said symbols to said memory devices and with said memory devices of another one of said columns being connected to a second group of bit paths of said data bus, said memory system comprising:

means for conveying the bits of a predetermined number of said symbols to each one of said memory devices via the bit paths of said data bus; and

means for storing the bits of each of said symbols in like bit positions of a plurality of memory bytes in said memory devices, the number of memory bytes being equal to the number of bits in each of said symbols.

4. A method for organizing a 640 byte block of data into 512 ten-bit Reed-Solomon error correction code symbols in a memory wherein said Reed-Solomon error correction code corrects up to thirty-two of said symbols in said data block and said memory has thirty-two random access memory devices arranged in two columns with the memory devices of one of the columns connected to a first group of eight bit paths of a data bus for conveying the symbols to the devices and the memory devices of the other of the columns connected to a second group of eight bit paths of the data bus, said method comprising the steps of:

distributing said 512 ten-bit Reed-Solomon error correction code symbols among said thirty-two random access memory devices by conveying the bits of sixteen of said symbols to each one of said memory devices via the bit paths of said data bus; and

data bus bit aligning each of said 512 ten-bit Reed-Solomon error correction code symbols in each of said thirty-two random access memory devices by storing the bits of each of said sixteen symbols in like bit positions of ten memory bytes of each of said memory devices.

5. A symbol level interleaving method of organizing a block of data in a memory having a plurality of random access memory devices, said method comprising the steps of:

encoding said block of data into multi-bit Reed-Solomon error correction code symbols;

converting said multi-bit Reed-Solomon error correction code symbols into a format transferable over a multi-bit data bus to said memory;

distributing said converted multi-bit Reed-Solomon error correction code among said plurality of memory devices by conveying the bits of a predetermined number of said Reed-Solomon error correction code symbols to each one of said memory devices via the bit paths of said data bus; and

data bus bit aligning said Reed-Solomon error correction code symbols in each of said memory devices by storing the bits of each of said Reed-Solomon error correction code symbols in like bit positions of a plurality of memory bytes in said memory devices, the number of memory bytes being equal to the number of bits in each of said symbols.