Partitioning data for error correction

• US 7,237,176 B2
• Filed: 01/12/2004
• Issued: 06/26/2007
• Est. Priority Date: 01/12/2004
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Tsao, Jay, Briggs, Theodore Carter, Brueggen, Chris Michael
• Primary Examiner(s): CHASE, SHELLY A
• Application Number:
  US10/756,447
• Publication Number:
  US 20050160329A1
• Time in Patent Office: 1,261 Days
• Field of Search: 714/767
• US Class Current: 714/767
• CPC Class Codes: G06F 11/1028 Adjacent errors, e.g. error in n-bit (n>1) wide storage units, i.e. package error

Abstract

Reading and writing data from a plurality of memory devices. A code word having a plurality of bits is partitioned into nibbles. Adjacent nibbles are stored on a common physical medium. The failure of the common physical medium results in errors in adjacent nibbles of a reconstructed code word.

Claims

1. A method of writing to a plurality of memory devices of the same width of a memory system, the method comprising:

receiving a code word for storage in the memory system;

partitioning the code word into a plurality of nibbles, each nibble having a width equal to the width of each of the plurality of memory devices; and

storing the code word into the plurality of memory devices by storing a plurality of successive nibbles of the code word into a plurality of corresponding address lines in each of the plurality of memory devices.

2. The method according to claim 1 further comprising:

receiving a data block;

generating error detection and correction bits for the data block; and

combining the error detection and correction bits and the data block to form the code word.

3. The method according to claim 1 wherein the memory system comprises K memory devices each having a width W, the code word has a width CW that is a multiple of (K*W), and the method comprises:

partitioning the code word into N=(CW/W) nibbles of W bits each, sequentially numbered from 0 to N−

1;

partitioning the code word into M chunks where M=(CW/(K*W)) and each chunk includes K nibbles defined as;

Chunk[C]={nibble[C+(K−

1)*M], nibble[C+(K−

2)*M], . . . ,

nibble[C+(1)M], nibble[C+(0)*M]}

for C=0, 1, . . . M−

1; and

writing each chunk into a corresponding address line in the memory devices.

4. The method according to claim 1 wherein the memory system comprises 36 memory devices, each having a width of 4 bits, the code word comprises 288 bits, and the method comprises:

partitioning the code word into 72 sequentially numbered nibbles of 4 bits each;

forming a first chunk including the odd nibbles;

forming a second chunk including the even nibbles; and

storing the first and second chunks in respective address lines of the plurality of memory devices so each pair of adjacent nibbles from the code word is stored in a different one of the plurality of memory devices.

5. A method of reading from a plurality of memory devices of the same width of a memory system, the method comprising:

a. reading a plurality of chunks of data from a plurality of corresponding address lines in each of the plurality of memory devices, each chunk comprising a nibble from each of the plurality of memory devices having a width equal to the width of the corresponding memory device; and

b combining the nibbles from the plurality of chunks to generate a code word where the nibbles from each of the plurality of memory devices are adjacent in the code word.

6. The method according to claim 5 wherein the code word comprises data bits and error detection and correction bits and the method further comprises extracting the data bits and the error detection and correction bits from the code word.

7. The method according to claim 5 wherein the memory system comprises K memory devices each having a width W and the code word has a width CW that is a multiple of (K*W), the method comprising:

reading M=CW/(K*W) chunks from the K memory devices where each chunk comprises one nibble having a width W from each of the memory devices; and

arranging the nibbles to form a code word where the nibbles from each memory device are adjacent as follows

Code Word=[nibble(M−

1,K−

1), nibble (M−

2,K−

1), . . . , nibble(0,K−

1),

nibble(M−

1,K−

2), nibble (M−

2,K−

2), . . . , nibble(0,K−

2),

nibble(M−

1,0), nibble (M−

2,0), . . . , nibble(0,0)]

where each nibble is designated as nibble(x,y) where x is its chunk identifier and y is its sequential position within the chunk.

8. The method according to claim 5 wherein the memory system comprises 36 memory devices, each having a width of 4 bits, the code word comprises two chunks of 144 bits each, and the method comprises:

reading a first chunk having 36 4-bit first nibbles from the memory devices, each nibble from one of the memory devices;

reading a second chunk having 36 4-bit second nibbles from the memory devices, each nibble from one of the memory devices;

combining the first and second chunks to generate a code word having the first and second nibbles from each memory device adjacent to each other.

9. A memory system comprising:

a. a plurality of memory devices having a width of MD bits;

b. a data buffer for reading chunks of MD bits from and writing chunks of MD bits to an address line in the memory devices;

c. a data separator for receiving a code word of CW bits, separating the code word into a plurality of chunks each comprising a plurality of sequential nibbles having widths corresponding to the width of at least one of the plurality of memory devices, partitioning the nibbles into groups of M adjacent nibbles where M is a value equaling CW divided by MD, and generating M chunks of bits, each chunk having only one nibble from each group of M nibbles where nibbles of each group are in the same relative position in their respective chunks; and

d. a data combiner for generating a code word from M chunks received from the data buffer by separating the M chunks into a plurality of nibbles having widths corresponding to at least one of the memory devices and arranging M nibbles having the same relative position in their respective chunks adjacent to each other in the code word.

10. The system according to claim 9 wherein the code word comprises data bits and error detection and correction bits and the system comprises an error detection and correction component that receives code words from the data combiner, detects and corrects errors in code word, and extracts the data from the code word.

11. The system according to claim 10 wherein the error detection and correction component corrects errors from a failure of any one of the plurality of memory devices.

12. The system according to claim 9 comprising 36 memory devices each having a width of 4 bits and a code word comprises 288.

13. The system according to claim 9 wherein the data combiner and the data separator are implemented in a single module.

14. The system according to claim 9 wherein the memory devices are dynamic random access memory devices.

15. The system according to claim 9 wherein the nibbles having widths corresponding to the width of only one of the plurality of memory devices.

16. A computer readable media comprising computer readable code for instructing a computer to write data into a plurality of memory devices of the same width of a memory system comprising:

receiving a code word for storage in the memory system;

partitioning the code word into a plurality of nibbles, each nibble having a width equal to the width of each of the plurality of memory devices; and

storing the code word into the plurality of memory devices by storing a plurality of successive nibbles of the code word into a plurality of corresponding address lines in each of the plurality of memory devices.

17. A computer readable media comprising computer readable code for instructing a computer to read data from a plurality of memory devices of the same width of a memory system comprising:

reading a plurality of chunks of data from a plurality of corresponding address lines in each of the plurality of memory devices, each chunk comprising a nibble from each of the plurality of memory devices having a width equal to the width of the corresponding memory device; and

combining the nibbles from the plurality of chunks to generate a code word where the nibbles from each of the plurality of memory devices are adjacent in the code word.

18. A system for writing data to a plurality of memory devices of the same width in a memory system comprising:

a module for receiving a code word for storage in the memory system;

a data separator for partitioning the code word into a plurality of nibbles, each nibble having a width equal to the width of each of the plurality of memory devices; and

a buffer for storing the code word into the plurality of memory devices by storing a plurality of successive nibbles of the code word into a plurality of corresponding address lines in each of the plurality of memory devices.

19. A system for reading data from a plurality of memory devices of the same width of a memory system comprising:

a buffer for reading a plurality of chunks of data from a plurality of corresponding address lines in each of the plurality of memory devices, each chunk comprising a nibble from each of the plurality of memory devices having a width equal to the width of the corresponding memory device; and

a data combiner for combining the nibbles from the plurality of chunks to generate a code word where the nibbles from each of the plurality of memory devices are adjacent in the code word.