Technique for partitioning data to correct memory part failures

• US 6,233,716 B1
• Filed: 09/24/1998
• Issued: 05/15/2001
• Est. Priority Date: 09/24/1998
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Cypher, Robert
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): LAMARRE, GUY J
• Application Number:
  US09/160,770
• Time in Patent Office: 964 Days
• Field of Search: 714/777, 714/763, 714/805, 714/5, 714/767
• US Class Current: 714/805
• CPC Class Codes: G06F 11/1028 Adjacent errors, e.g. error in n-bit (n>1) wide storage units, i.e. package error

Abstract

The bits of a data block are assigned to a plurality of logical groups such that at most one bit corresponding to a component is assigned to a logical group. This assignment ensures that a component failure may introduce at most one bit error to a logical group. A number of bits in a logical group is selected to reduce the number of check bits for a given number of data bits. Error correction may be performed within each logical group to correct single errors within the logical group. Because each logical group is assigned at most one bit corresponding to a component, component failures may be detected and corrected.

Claims

1. A memory system comprising:

a plurality of first components configured to store a data block, wherein said data block includes a plurality of data bits and a plurality of check bits, and wherein each bit of said data block is assigned to one of said plurality of first components;

a plurality of second components configured to transfer the bits of said data block, wherein each bit of said data block is assigned to one of said plurality of second components;

an error detection circuit coupled to said first components and said second components;

wherein said data bits and said check bits are grouped to form a plurality of logical groups, and wherein each logical group includes at most one bit assigned to a given one of said plurality of first components and at most one bit assigned to a given one of said plurality of second components;

wherein said error detection circuit is configured to;

generate one or more check bits of a given one of said logical groups from data bits of the given one of said logical groups;

verify the accuracy of the data bits of the given one of said logical groups using the check bits of the given one of said logical groups; and

wherein numbers of bits in each of said logical groups are selected to optimize a ratio of a number of said check bits to a number of said data bits.

2. The memory system as recited in claim 1 wherein said plurality of first components is a plurality of memory devices and said plurality of second components is a plurality of pins.

3. The memory system as recited in claim 1 wherein a number of said plurality of logical groups exceeds a number of said first components and a number of said second components.

4. The memory system as recited in claim 1 wherein said error detection circuit implements a Hamming Code, and wherein said error detection circuit is configured to correct errors detected in said data block.

5. A system comprising:

a processor;

a bus;

a memory coupled to said processor and said bus, comprising;

a plurality of first components configured to store a data block, wherein said data block includes a plurality of data bits and a plurality of check bits, and wherein each bit of said data block is assigned to one of said plurality of first components;

a plurality of second components configured to transfer bits of said data block, wherein each bit of said data block is assigned to one of said plurality of second components;

an error detection circuit coupled to said first components and said second components;

wherein said data bits and said check bits are grouped to form a plurality of logical groups, and wherein each of said logical groups includes at most one bit assigned to a given one of said plurality of first components and at most one bit assigned to a given one of said plurality of second components;

wherein said error detection circuit is configured to;

generate one or more check bits of a given one of said logical groups from data bits of the given one of said logical groups;

verify the accuracy of the data bits of the given one of said logical groups using the check bits of the given one of said logical groups; and

wherein numbers of bits in each of said logical groups are selected to optimize a ratio of a number of said check bits to a number of said data bits.

6. The system as recited in claim 5 wherein said plurality of first components is a plurality of memory devices and said plurality of second components is a plurality of pins.

7. The system as recited in claim 5 wherein a number of said plurality of logical groups exceeds a number of said first components and a number of said second components.

8. The system as recited in claim 5 wherein said error detection circuit implements a Hamming Code, and wherein said error detection circuit is configured to correct errors detected in said data block.

9. A method of detecting errors in a data block of a computer system that includes a plurality of components, comprising:

assigning a plurality of bits of said data block to a plurality of logical groups such that each of said logical groups includes at most one bit corresponding to a given one of said plurality of components, wherein said plurality of bits of said data block includes a plurality of data bits and a plurality of check bits; and

performing error correction on bits within each logical group of said plurality of logical groups, wherein said error correction is performed upon detection of at least one error in said bits;

wherein a number of bits in each of said logical groups is selected to decrease a number of check bits in said data block.

10. The method as recited in claim 9 wherein a size of a logical group of said plurality of logical groups is selected to optimize a ratio of the number of check bits to the number of data bits.

11. The method as recited in claim 10 wherein a number of said plurality of logical groups exceeds a number of said plurality of components to which said plurality of bits of said data block are assigned.

12. The method as recited in claim 11 wherein said plurality of components is a plurality of memory devices.

13. The method as recited in claim 12 wherein at most one bit stored in a given one of said plurality of memory devices is assigned to a any one of said logical groups such that a failure in the given one of said plurality of memory devices causes at most one bit error in any one of said plurality of logical groups.

14. The method as recited in claim 11 wherein said plurality of components is a plurality of pins for transferring a plurality of bits of said data block.

15. The method as recited in claim 14 wherein at most one bit transferred by a given one of said pins is assigned to any one of said logical groups such that a failure of the given one of said pins causes at most one bit error in any one of said plurality of logical groups.

16. The method as recited in claim 9 wherein said detection of said at least one error is performed using a Hamming Code and wherein said error correction is performed using error correcting Hamming Codes.

17. A method of detecting errors in a data block of a computer system that includes a plurality of first components and a plurality of second components wherein bits of said data block correspond to a first component and a second component, said method comprising:

assigning said bits of said data block to a plurality of logical groups such that at most one bit corresponding to a given one of said plurality of first components is assigned to a first logical group of said plurality of logical groups and at most one bit corresponding to a given one of said plurality of second components is assigned to said first logical group; and

performing error detection on bits within said first logical group, wherein said first logical group includes a plurality of data bits and a plurality of check bits;

wherein a number of bits in said first logical group is selected to decrease a number of check bits in said data block.

18. The method as recited in claim 17 wherein said number of bits in said first logical group is selected to optimize a ratio of said number of check bits to a number of said data bits.

19. The method as recited in claim 18 wherein a number of said plurality of logical groups exceeds a number of said plurality of first components or a number of said plurality of second components.

20. The method as recited in claim 19 wherein said plurality of first components are memory devices configured to store at least a portion of bits of said data block and said plurality of second components are pins configured to transfer said bits of said data block.

21. The method as recited in claim 20 wherein at most one bit stored in a given one of said memory devices is assigned to said first logical group and at most one bit transferred by a given one of said pins is assigned to said first logical group such that a failure of the given one of said memory devices causes at most one bit error in said first logical group and a failure of the given one of said pins causes at most one bit error in said first logical group.

22. The method as recited in claim 17 wherein said error detection is performed using a Hamming Code, and wherein said method further comprises performing error correction on a bit within said first logical group.

23. An apparatus for detecting errors in a data block of a computer system that includes a plurality of components, comprising:

means for assigning a plurality of bits of said data block to a plurality of logical groups such that at most one bit of said plurality of bits corresponding to a given one of said components is assigned to any given one of said logical groups, wherein said plurality of bits of said data block includes a plurality of data bits and a plurality of check bits; and

means for performing error correction on bits within each of said logical groups, wherein said error correction is performed upon detection of at least one error in said bits;

wherein a number of bits in each of said logical groups is selected to decrease a number of check bits in said data block.

24. The apparatus as recited in claim 23 wherein numbers of bits in said logical groups are selected to optimize a ratio of the number of check bits to the number of data bits.

25. The apparatus as recited in claim 24 wherein a number of said plurality of logical groups exceeds a number of said plurality of components to which said plurality of bits of said data block are assigned.

26. The apparatus as recited in claim 25 wherein said plurality of components is a plurality of memory devices.

27. The apparatus as recited in claim 26 wherein at most one bit stored in a given one of said memory devices is assigned to any one of said logical groups such that a failure in the given one of said memory devices causes at most one bit error in any one of said plurality of logical groups.

28. The apparatus as recited in claim 25 wherein said plurality of components is a plurality of pins for transferring a plurality of bits of said data block.

29. The apparatus as recited in claim 28 wherein at most one bit transferred by a given one of said pins is assigned to any one of said plurality of logical groups such that a failure of the given one of said pins causes at most one bit error in any one of said plurality of logical groups.

30. The apparatus as recited in claim 23 wherein said detection of said at least one error is performed using a Hamming Code and wherein said error correction is performed using error correcting Hamming Codes.