Error correcting code with chip kill capability and power saving enhancement

• US 8,010,875 B2
• Filed: 06/26/2007
• Issued: 08/30/2011
• Est. Priority Date: 06/26/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Flynn, William T., Chen, Dong, Trager, Barry M., Marcella, James A., Winograd, Shmuel, Gara, Alan G., Takken, Todd, Coteus, Paul W.
• Primary Examiner(s): Baker; Stephen M
• Application Number:
  US11/768,559
• Publication Number:
  US 20090006899A1
• Time in Patent Office: 1,526 Days
• Field of Search: 714/773
• US Class Current: 714/773
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence

Abstract

A method and system are disclosed for detecting memory chip failure in a computer memory system. The method comprises the steps of accessing user data from a set of user data chips, and testing the user data for errors using data from a set of system data chips. This testing is done by generating a sequence of check symbols from the user data, grouping the user data into a sequence of data symbols, and computing a specified sequence of syndromes. If all the syndromes are zero, the user data has no errors. If one of the syndromes is non-zero, then a set of discriminator expressions are computed, and used to determine whether a single or double symbol error has occurred. In the preferred embodiment, less than two full system data chips are used for testing and correcting the user data.

Claims

1. A method of detecting memory chip failure in a computer memory system, the memory system including a first set of user data memory chips and a second set of system data memory chips, the method comprising the steps of:

accessing user data from the user data chips,

testing the user data for errors using error detection data from the system data chips, including the steps of

i) generating a sequence of check symbols from the user data,

ii) grouping the user data into a sequence of data symbols,

iii) computing a sequence of syndromes using said sequence of data symbols and said sequence of check symbols,

iv) if all the syndromes are zero, identifying the user data as having no error, and

v) if one of the syndromes is non-zero, then (1) computing a set of discriminator expressions, and (2) using said discriminator expressions to determine whether a single symbol error has occurred or a double symbol error has occurred.

2. A method according to claim 1, comprising the further step of using said syndromes to determine if an entire one of the memory chips has failed.

3. A method according to claim 1, comprising the further step of:

if an error is detected, then correcting said error; and

wherein less than two full system data chips are used for testing the user data and correcting the error.

4. A method according to claim 3, comprising the further step of using extra bits on said two full system data chips for constraining the number of switching data bits in the memory system.

5. A method according to claim 1, wherein the step of using said syndromes to determine if an entire one of the memory chips has failed includes the steps of:

identifying the number, N1, of syndromes in the sequence of syndromes;

identifying the number, N2, of the data symbols in error when an entire one of the memory chips has failed;

determining a third number N3 by the equation;

N1−

N2=N3;

modifying N3 of the syndromes to produce N3modified syndromes; and

using said N3 modified syndromes to determine if an entire one of the memory chips has failed.

6. A method according to claim 5, wherein the step of using said syndromes includes the further step of using said N3 modified syndromes to identify the locations of said entire one of the memory chips that has failed.

7. A method according to claim 5, wherein the step of using said N3 modified syndromes includes the step of determining if all of said N3 modified syndromes are equal to zero.

8. A method according to claim 1, wherein:

the step of computing the set of discriminator expressions includes the step of computing a set of discriminator expressions D0, D1 and D using the syndromes.

9. A method according to claim 8, wherein:

the sequence of syndromes includes first and second syndromes S0 and S1 respectively; and

the step of using the discriminator expressions to determine whether a single symbol error or a double symbol error has occurred includes the step of testing to determine whether;

i) D0=D1=D2=0, and

ii) both S0 and S1 are non-zero.

10. A method according to claim 9, wherein:

if D0=D1=D2=0 and both S0 and S1 are non-zero, then a single symbol error has occurred.

11. A method according to claim 10, comprising the further step of using S1 and S0 to identify the location of the error.

12. A method according to claim 9, wherein if each of D0, D1 and D2 is non-zero, then a double syndrome error has occurred.

13. A method according to claim 12, wherein:

the step of computing the set of discriminator expressions includes the step of computing another set of discriminator expressions E_j using the syndromes; and

the step of using the set of discriminator expressions includes the further step of using the discriminator expressions E_j to confirm that a double syndrome error has occurred.

14. A method according to claim 12, comprising the further step of using D0, D1 and D to identify the locations of the errors.

15. A method according to claim 14, comprising the further step of using D0, D1 and D to correct the double errors.

16. A memory error detection system for detecting memory chip failure in a computer memory system, the memory system including a first set of user data memory chips and a second set of system data memory chips, the memory error detection system comprising:

a memory controller for accessing user data from the user data chips and for testing the user data for errors using error detection data from the system data chips by;

i) generating a sequence of check symbols from the user data,

ii) grouping the user data into a sequence of data symbols,

iii) computing a sequence of syndromes using said sequence of data symbols and said sequence of check symbols,

iv) if all the syndromes are zero, identifying the user data as having no error, and

v) if one of the syndromes is non-zero, then (1) computing a set of discriminator expressions, and (2) using said discriminator expressions to determine whether a single symbol error has occurred or a double symbol error has occurred.

17. A memory error detection system according to claim 16, the memory controller includes code for correcting an error in the user data, and wherein less than two full system data chips are used for testing the user data and correcting the error.

18. A memory error detection system according to claim 17, wherein extra bits on said two full system data chips are used for constraining the number of switching data bits in the memory system.

19. A memory error detection system according to claim 16, wherein:

the set of discriminator expressions are computed by computing a set of discriminator expressions D0, D1 and D using the syndromes;

the sequence of syndromes includes first and second syndromes S0 and S1 respectively; and

the discriminator expressions are used to determine whether a single symbol error or a double symbol error has occurred by testing to determine whether;

i) D0=D1=D=0, and

ii) both S0 and S1 are non-zero;

if D0=D1=D=0 and both S0 and S1 are non-zero, then a single symbol error has occurred, and S1 and S0 are used to identify the location of the error; and

if each of D0, D1 and D is non-zero, then a double syndrome error has occurred, and D0, D1 and D are used to identify the locations of the errors.

20. A memory error detection system according to claim 19, wherein said D0, D1 and D are used to correct the double errors.

21. A memory error detection system according to claim 19, wherein another set of discriminator expressions E_j are computed using the syndromes, and said another set of discriminator expressions E_j are used to confirm that a double syndrome error has occurred.

22. A program storage device tangibly embodying a program of instructions readable by machine for instructing the machine to perform method steps for detecting memory chip failure in a computer memory system, the memory system including a first set of user data memory chips and a second set of system data memory chips, said method steps comprising:

accessing user data from the user data chips, testing the user data for errors using error detection data from the system data chips, including the steps of;

i) generating a sequence of check symbols from the user data,

ii) grouping the user data into a sequence of data symbols,

iii) computing a sequence of syndromes using said sequence of data symbols and said sequence of check symbols,

iv) if all the syndromes are zero, identifying the user data as having no error, and

v) if one of the syndromes is non-zero, then (1) computing a set of discriminator expressions, and (2) using said discriminator expressions to determine whether a single symbol error has occurred or a double symbol error has occurred.

23. A program storage device according to claim 22, wherein said method steps comprise the further step of:

if an error is detected, then correcting said error; and

wherein less than two full system data chips are used for testing the user data and correcting the error.

24. A program storage device according to claim 22, wherein:

the step of computing the set of discriminator expressions includes the step of computing a set of discriminator expressions D0, D1 and D using the syndromes;

the sequence of syndromes includes first and second syndromes S0 and S1 respectively, and the step of using the discriminator expressions to determine whether a single symbol error or a double symbol error has occurred includes the step of testing to determine whether;

i) D0=D1=D2=0, and

ii) both S0 and S1 are non-zero;

if D0=D1=D2=0 and both S0 and S1 are non-zero, then a single symbol error has occurred, and said method steps comprise the further step of using S1 and S0 to identify the location of the error; and

if each of D0, D1and D2is non-zero, then a double syndrome error has occurred, and said method steps comprise the further step of using D0, D1 and D to identify the locations of the errors.

25. A method of detecting failure of an entire memory chip in a computer memory system, the memory system including a first set of user data memory chips and a second set of system data memory chips, the method comprising the steps of:

accessing user data from the user data chips;

testing the user data for errors using error detection data from the system data chips, including the steps of;

i) generating a sequence of check symbols from the user data,

ii) grouping the user data into a sequence of data symbols,

iii) computing a sequence of syndromes using said sequence of data symbols and said sequence of check symbols, and

iv) using said syndromes to determine whether an entire one of the data memory chips has entirely failed, and if so, to identify which one of said data memory chips has entirely failed, including computing a respective one set of modified syndromes for each of the user data memory chips, and using the sets of modified syndromes to determine the one of the data memory chips that has entirely failed.

26. A method according to claim 25, comprising the further step of, after using the modified syndromes to locate a failing chip, then using the original syndromes to correct the content of the failing chip.

27. A method according to claim 25, comprising the further steps of:

once the same memory chip has failed repeatedly, declaring said failed memory chip a hard chip kill whose location is known; and

then locating and correcting one additional symbol error besides correcting the contents of the known failed chip.

28. A method of detecting failure of an entire memory chip in a computer memory system, the memory system including a first set of user data memory chips and a second set of system data memory chips, the method comprising the steps of:

accessing user data from the user data chips;

testing the user data for errors using error detection data from the system data chips, including the steps of;

i) generating a sequence of check symbols from the user data,

ii) grouping the user data into a sequence of data symbols,

iii) computing a sequence of syndromes using said sequence of data symbols and said sequence of check symbols, and

iv) using said syndromes to determine whether an entire one of the data memory chips has entirely failed, and if so, to identify which one of said data memory chips has entirely failed; and

wherein the step of using said syndromes to determine if an entire one of the memory chips has failed includes the steps of;

identifying the number, N1, of syndromes in the sequence of syndromes;

identifying the number, N2, of the data symbols in error when an entire one of the memory chips has failed;

determining a third number N3 by the equation;

N1−

N2=N3;

modifying N3 of the syndromes to produce N3 modified syndromes; and

using said N3 modified syndromes to determine if an entire one of the memory chips has failed.

29. A method according to claim 28, wherein the step of using said syndromes includes the further step of using said N3 modified syndromes to identify the locations of said entire one of the memory chips that has failed, including the step of determining if all of said N3 modified syndromes are equal to zero.

30. A memory error detection system for detecting failure of an entire memory chip in a computer memory system, the memory system including a first set of user data memory chips and a second set of system data memory chips, the memory error detection system comprising:

a memory controller for accessing user data from the user data chips and for testing the user data for errors using error detection data from the system data chips by;

i) generating a sequence of check symbols from the user data,

ii) grouping the user data into a sequence of data symbols,

iii) computing a sequence of syndromes using said sequence of data symbols and said sequence of check symbols, and

iv) using said syndromes to determine whether an entire one of the data memory chips has failed, and if so, to identify which one of said data memory chips has failed, including computing a respective one set of modified syndromes for each of the user data memory chips, and using the sets of modified syndromes to determine the one of the data memory chips that has entirely failed.

31. A memory error detection system according to claim 30, wherein less than two full system data chips are used for testing the user data and correcting the failed memory chip.

32. A memory error detection system according to claim 31, wherein extra bits on said two full system data chips are used for constraining the number of switching data bits in the memory system.

33. A memory error detection system according to claim 30, wherein said syndromes are used to determine if an entire one of the memory chips has failed by:

identifying the number, N1, of syndromes in the sequence of syndromes;

identifying the number, N2, of the data symbols in error when an entire one of the memory chips has failed;

determining a third number N3 by the equation;

N1−

N2=N3;

modifying N3 of the syndromes to produce N3 modified syndromes; and

using said N3 modified syndromes to determine if an entire one of the memory chips has failed.

34. A memory error detection system according to claim 33, wherein said N3 modified syndromes are used to identify the locations of said entire one of the memory chips that has failed.

35. A memory error detection system according to claim 33, wherein said N3 modified syndromes are used to identify the location of said entire one of the memory chips that has failed by determining if all of said N3 modified syndromes are equal to zero.