Error detection/correction code which detects and corrects a first failing component and optionally a second failing component

• US 6,996,766 B2
• Filed: 06/28/2002
• Issued: 02/07/2006
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Cypher, Robert E.
• Primary Examiner(s): DILDINE JR, R STEPHEN
• Application Number:
  US10/185,959
• Publication Number:
  US 20040088636A1
• Time in Patent Office: 1,320 Days
• Field of Search: 714 5- 8, 714/711, 714/723, 714/763, 714766-767, 714/773
• US Class Current: 714/764
• CPC Class Codes: G06F 11/1048 using arrangements adapted for a specific error detection or correction feature
• CPC Class Codes: G06F 13/1668 Details of memory controller

Abstract

A memory controller includes a check/correct circuit and a data remap circuit. The check/correct circuit is coupled to receive an encoded data block from a memory comprising a plurality of memory devices. The encoded data block includes a plurality of check bits, and the check/correct circuit is configured to decode the encoded data block and to detect a failure of one of the plurality of memory devices responsive to decoding the encoded data block. The data remap control circuit is configured to cause a remap of each of a plurality of encoded data blocks to avoid storing bits in the failing memory device. A memory controller may also be configured to detect and correct a first failed memory device and a second failed memory device of the plurality of memory devices.

Claims

1. A memory controller comprising:

a check/correct circuit coupled to receive an encoded data block from a memory comprising a plurality of memory devices, the encoded data block including a plurality of check bits, wherein the check/correct circuit is configured to decode the encoded data block and to detect a failure of one of the plurality of memory devices responsive to decoding the encoded data block; and

a data remap control circuit coupled to receive an indication that the check/correct circuit has detected the failure of a failing memory device of the plurality of memory devices, wherein the data remap control circuit is configured to cause a remap of each of a plurality of encoded data blocks to avoid storing bits in the failing memory device, wherein each of the plurality of encoded data blocks has at least one bit stored in the failing memory device prior to remapping and has at least one other bit stored in a different memory device of the plurality of memory devices prior to the remapping.

2. The memory controller as recited in claim 1 further comprising a check bit encoder circuit configured to encode data blocks with the plurality of check bits, wherein the check bit encoder circuit is configured to perform the remap.

3. The memory controller as recited in claim 2 wherein the check bit encoder circuit is configured to assign binary zeros to bits that are stored in the failing memory device.

4. The memory controller as recited in claim 2 wherein the check/correct circuit is configured to reconstruct the data from the failed memory device using the remaining bits of the encoded data block.

5. The memory controller as recited in claim 4 wherein the encoded data block is logically arranged as an array of rows (0 to R-1) and columns (0 to C-1) of bits, wherein each column comprises the bits stored in a different one of the plurality of memory devices, and wherein the plurality of check bits include a plurality of auxiliary check bits and a plurality of inner check bits, wherein the plurality of auxiliary check bits are stored in a first column of the array, and wherein each of the plurality of auxiliary check bits is in a row of the array and covers bits in the other columns of the array, and wherein the check bit encoder circuit is configured to store the data from the failing memory device in the first column instead of the plurality of auxiliary check bits.

6. The memory controller as recited in claim 5 wherein the check bit encoder circuit is configured to include the first column in the generation of the plurality of inner check bits for the remap.

7. The memory controller as recited in claim 6 wherein each bit of the array has an associated assignment of one or more of the plurality of inner check bits that covers that bit, and wherein a same assignment is used before and after the remap of each of the plurality of encoded data blocks.

8. The memory controller as recited in claim 4 wherein the encoded data block is logically arranged as an array of rows (0 to R-1) and columns (0 to C-1) of bits, wherein each column comprises the bits stored in a different one of the plurality of memory devices, and wherein at least a first column of the array is logically not used, and wherein the check bit encoder circuit is configured to remap a second column storing data bits stored in the failed memory device to the first column.

9. The memory controller as recited in claim 8 wherein the first column stores a constant set of data for any encoded data block.

10. The memory controller as recited in claim 9 wherein the first column comprises metadata bits which are logically not used.

11. The memory controller as recited in claim 8 wherein the plurality of check bits comprise a plurality of auxiliary check bits stored in a third column of the array, and wherein each of the plurality of auxiliary check bits covers bits stored in each other column of the array, and wherein the check/correct circuit is configured to detect a second failing memory device of the plurality of memory devices, and wherein a fourth column of the array corresponds to the second failing memory device, and wherein the check bit encoder circuit is configured to remap the fourth column to the third column.

12. A method comprising:

receiving an encoded data block from a memory comprising a plurality of memory devices, the encoded data block including a plurality of check bits;

decoding the encoded data block;

detecting a failure of one of the plurality of memory devices responsive to decoding the encoded data block; and

remapping each of a plurality of encoded data blocks to avoid storing bits in the failing memory device, wherein each of the plurality of encoded data blocks has at least one bit stored in the failing memory device prior to the remapping and has at least one other bit stored in a different memory device of the plurality of memory devices prior to the remapping.

13. The method as recited in claim 12 wherein the remapping includes assigning binary zeros to bits that are stored in the failing memory device.

14. The method as recited in claim 12 wherein the remapping comprises reconstructing the data from the failed memory device using the remaining bits of the encoded data block.

15. The method as recited in claim 14 wherein the encoded data block is logically arranged as an array of rows (0 to R-1) and columns (0 to C-1) of bits, wherein each column comprises the bits stored in a different one of the plurality of memory devices, and wherein the plurality of check bits include a plurality of auxiliary check bits and a plurality of inner check bits, wherein the plurality of auxiliary check bits are stored in a first column of the array, and wherein each of the plurality of auxiliary check bits is in a row of the array and covers bits in the other columns of the array, the method further comprising storing the data from the failing memory device in the first column instead of the plurality of auxiliary check bits.

16. The method as recited in claim 15 wherein the remapping further comprises including the first column in the generation of the plurality of inner check bits.

17. The method as recited in claim 16 wherein each bit of the array has an associated assignment of one or more of the plurality of inner check bits that covers that bit, and wherein a same assignment is used before and after the remapping of each of the plurality of encoded data blocks.

18. The method as recited in claim 14 wherein the encoded data block is logically arranged as an array of rows (0 to R-1) and columns (0 to C-1) of bits, wherein each column comprises the bits stored in a different one of the plurality of memory devices, and wherein at least a first column of the array is logically not used, and wherein the remapping comprises remapping a second column storing data bits stored in the failed memory device to the first column.

19. The method as recited in claim 18 wherein the first column stores a constant set of data for any encoded data block.

20. The method as recited in claim 19 wherein the first column comprises metadata bits which are logically not used.

21. The method as recited in claim 18 wherein the plurality of check bits comprise a plurality of auxiliary check bits stored in a third column of the array, and wherein each of the plurality of auxiliary check bits covers bits stored in each other column of the array, and wherein the check/correct circuit is configured to detect a second failing memory device of the plurality of memory devices, and wherein a fourth column of the array corresponds to the second failing memory device, the method further comprising remapping the fourth column to the third column.

22. An apparatus comprising:

means for decoding an encoded data block received from a memory comprising a plurality of memory devices, the encoded data block including a plurality of check bits;

means for detecting a failure of one of the plurality of memory devices responsive to decoding the encoded data block; and

means for remapping of each of a plurality of encoded data blocks to avoid storing bits in the failing memory device, wherein each of the plurality of encoded data blocks has at least one bit stored in the failing memory device prior to the remapping and has at least one other bit stored in a different memory device of the plurality of memory devices prior to the remapping.

23. A memory controller comprising:

a check bit encoder circuit coupled to receive a data block to be written to a memory comprising a plurality of memory devices, wherein the check bit encoder circuit is configured to encode the data block with a plurality of check bits to generate an encoded data block for storage in the memory, and wherein the plurality of check bits are defined to provide at least;

(i) detection and correction of a first failed memory device of the plurality of memory devices, and (ii) detection and correction of a second failed memory device of the plurality of memory devices following (i); and

a check/correct circuit coupled to receive the encoded data block from the memory and configured to decode the encoded data block and perform at least the detection of (i) and (ii).

24. The memory controller as recited in claim 23 further comprising a data remap control circuit coupled to receive an indication of the first failed memory device from the check/correct circuit and configured to cause a remap of each of a plurality of encoded data blocks in response to the indication, the plurality of encoded data blocks each having at least one bit stored in the first failed memory device, the remap avoiding storing bits of the plurality of encoded data blocks in the first failed memory device.

25. The memory controller as recited in claim 24 wherein the encoded data block is logically arranged as an array of rows (0 to R-1) and columns (0 to C-1) of bits, wherein each column comprises the bits stored in a different one of the plurality of memory devices, and wherein at least a first column of the array is logically not used, and wherein the check bit encoder circuit is configured to remap a second column storing data bits stored in the first failed memory device to the first column.

26. The memory controller as recited in claim 25 wherein the first column stores constant data for any encoded block of data.

27. The memory controller as recited in claim 25 wherein the first column of data stores metadata that is not used.

28. The memory controller as recited in claim 25 wherein the plurality of check bits includes a plurality of auxiliary check bits and a plurality of inner check bits, and wherein the plurality of auxiliary check bits are stored in a third column of the array, and wherein the check bit encoder circuit is configured to remap a fourth column corresponding to the second failed memory device to the third column responsive to the check/correct circuit detecting the second failed memory device.

29. A method comprising:

receiving a data block to be written to a memory comprising a plurality of memory devices; and

encoding the data block with a plurality of check bits to generate an encoded data block for storage in the memory, wherein the plurality of check bits are defined to provide at least;

(i) detection and correction of a first failed memory device of the plurality of memory devices, and (ii) detection and correction of a second failed memory device of the plurality of memory devices following (i).

30. The method as recited in claim 29 further comprising:

receiving the encoded data block from the memory; and

decoding the encoded data block to perform the detection of (i) and (ii).

31. The method as recited in claim 30 further comprising remapping each of a plurality of encoded data blocks in response to detecting the first failed memory device, the plurality of encoded data blocks each having at least one bit stored in the first failed memory device, the remap avoiding storing bits of the plurality of encoded data blocks in the first failed memory device.

32. The method as recited in claim 31 wherein the encoded data block is logically arranged as an array of rows (0 to R-1) and columns (0 to C-1) of bits, wherein each column comprises the bits stored in a different one of the plurality of memory devices, and wherein at least a first column of the array is logically not used, and wherein the remapping comprises remapping a second column storing data bits stored in the first failed memory device to the first column.

33. The method as recited in claim 32 wherein the first column stores constant data for any encoded block of data.

34. The method as recited in claim 32 wherein the first column of data stores metadata that is not used.

35. The method as recited in claim 32 wherein the plurality of check bits includes a plurality of auxiliary check bits and a plurality of inner check bits, and wherein the plurality of auxiliary check bits are stored in a third column of the array, and wherein the check bit encoder circuit is configured to remap a fourth column corresponding to the second failed memory device to the third column responsive to the check/correct circuit detecting the second failed memory device.

36. An apparatus comprising:

means for encoding a data block to be written to a memory comprising a plurality of memory devices with a plurality of check bits to generate an encoded data block for storage in the memory, wherein the plurality of check bits are defined to provide at least;

(i) detection and correction of a first failed memory device of the plurality of memory devices, and (ii) detection and correction of a second failed memory device of the plurality of memory devices following (i); and

means for writing the encoded data block to the memory.

37. A communication system comprising:

a check/correct circuit coupled to receive an encoded data block from a transmission medium comprising a plurality of paths, the encoded data block including a plurality of check bits, wherein the check/correct circuit is configured to decode the encoded data block and to detect a failure of one of the plurality of paths responsive to decoding the encoded data block; and

a check bit encoder circuit coupled to receive an indication that the check/correct circuit has detected the failure of a failing path of the plurality of paths, wherein the check bit encoder circuit is configured to encode subsequent data blocks to avoid transmitting bits on the failing path.

39. The communication system as recited in claim 37 wherein the check bit encoder circuit is configured to assign binary zeros to bits that corresponding to the failing path.

40. The communication system as recited in claim 37 wherein the check/correct circuit is configured to reconstruct the data for the failed path using the remaining bits of the encoded data block.

41. The communication system as recited in claim 40 wherein the encoded data block is logically arranged as an array of rows (0 to R-1) and columns (0 to C-1) of bits, wherein each column comprises the bits transmitted on a different one of the plurality of paths, and wherein the plurality of check bits include a plurality of auxiliary check bits and a plurality of inner check bits, wherein the plurality of auxiliary check bits are stored in a first column of the array, and wherein each of the plurality of auxiliary check bits is in a row of the array and covers bits in the other columns of the array, and wherein the check bit encoder circuit is configured to remap the data from the failing path into the first column instead of the plurality of auxiliary check bits.

42. The communication system as recited in claim 41 wherein each bit of the array has an associated assignment of one or more of the plurality of inner check bits that covers that bit, and wherein a same assignment is used before and after the remap of each of the plurality of encoded data blocks.

43. The communication system as recited in claim 40 wherein the encoded data block is logically arranged as an array of rows (0 to R-1) and columns (0 to C-1) of bits, wherein each column comprises the bits transmitted on a different one of the plurality of paths, and wherein at least a first column of the array is logically not used, and wherein the check bit encoder circuit is configured to remap a second column storing data bits corresponding to the failed path to the first column.

44. The communication system as recited in claim 43 wherein the plurality of check bits comprise a plurality of auxiliary check bits stored in a third column of the array, and wherein each of the plurality of auxiliary check bits covers bits stored in each other column of the array, and wherein the check/correct circuit is configured to detect a second failing path of the plurality of paths, and wherein a fourth column of the array corresponds to the second failing path, and wherein the check bit encoder circuit is configured to remap the fourth column to the third column.

38. A communication system comprising:

a check bit encoder circuit coupled to receive a data block to be transmitted via a transmission medium comprising a plurality of paths, wherein the check bit encoder circuit is configured to encode the data block with a plurality of check bits to generate an encoded data block for transmission, and wherein the plurality of check bits are defined to provide at least;

(i) detection and correction of a first failed path of the plurality of paths, and (ii) detection and correction of a second failed path of the plurality of paths following (i); and

a check/correct circuit coupled to receive the encoded data block from the transmission medium and configured to decode the encoded data block and perform at least the detection of (i) and (ii).

45. The communication system as recited in claim 38 wherein the encoded data block is logically arranged as an array of rows (0 to R-1) and columns (0 to C-1) of bits, wherein each column comprises the bits transmitted on a different one of the plurality of paths, and wherein at least a first column of the array is logically not used, and wherein the check bit encoder circuit is configured to remap a second column storing data bits transmitted on the first failed path to the first column.

46. The communication system as recited in claim 45 wherein the first column stores constant data for any encoded block of data.

47. The communication system as recited in claim 45 wherein the first column of data stores metadata that is not used.

48. The communication system as recited in claim 45 wherein the plurality of check bits includes a plurality of auxiliary check bits and a plurality of inner check bits, and wherein the plurality of auxiliary check bits are stored in a third column of the array, and wherein the check bit encoder circuit is configured to remap a fourth column corresponding to the second failed path to the third column responsive to the check/correct circuit detecting the second failed path.