Facilitating probabilistic error detection and correction after a memory component failure

1. A method for providing error detection and correction after a failure of a memory component in a memory system, comprising:

accessing a block of data from the memory system, wherein the memory system is previously determined to have a specific failed memory component, wherein each block of data in the memory system includes an array of bits logically organized into R rows and C columns, including a row checkbit column including row-checkbits for each of the R rows, an inner checkbit column including X<R inner checkbits and R−X data bits, and C−2 data-bit columns containing data bits, wherein each column is stored in a different memory component, and wherein the checkbits, which comprise the row-checkbits and the inner checkbits, are generated from the data bits to provide block-level detection and correction for a failed memory component;

attempting to correct a column of the block from the failed memory component by using the checkbits and the data bits to produce a corrected column;

regenerating row-parity bits and the inner checkbits for the block of data, wherein the block includes the corrected column;

comparing the regenerated row-parity bits and inner checkbits with existing row-parity bits and inner checkbits; and

if comparison indicates that there remains a double-bit error wherein both erroneous bits are in the same row and one is in the column associated with the failed component, flipping the erroneous bits to correct the double-bit error.

2. The method of claim 1 ,

wherein the row checkbit column contains the row-parity bits for each of the R rows in the block; and

wherein the inner checkbit column contains X<R inner checkbits which are defined to cover bits in the array in accordance with a set of check vectors, wherein each check vector is associated with a different bit in the array and is an element of a Galois Field (GF(2 X )), wherein the check vectors are derived from a set of keys which are unique elements of GF(2 X ), wherein each key is associated with a different column of the array, and wherein the check vector for a row r of a column c is the product in GF(2 X ) of the key for the column c and α r , wherein α is a primitive element of GF(2 X ).

3. The method of claim 2 , wherein the set of keys are elements of a subfield of G(2 X ), wherein the subfield does not contain any α i , where 1≦i≦R.

4. The method of claim 3 , wherein attempting to correct the column from the failed memory component involves:

regenerating the row-parity bits and the inner checkbits for the block of data from the data bits in the block of data;

computing a row syndrome by exclusive-ORing the regenerated row-parity bits with the existing row-parity bits;

computing an inner syndrome by exclusive-ORing the regenerated inner checkbits with the existing inner checkbits;

using the row syndrome to identify erroneous bits in the data-bit column associated with the failed memory component; and

flipping the identified erroneous bits to produce the corrected data-bit column.

5. The method of claim 3 , wherein for the case where the corrected column was produced and the row-parity bits and the inner checkbits were regenerated using the corrected column, comparing the regenerated row-parity bits and inner checkbits with the existing row-parity bits and inner checkbits involves:

computing a row syndrome by exclusive-ORing the regenerated row-parity bits with the existing row-parity bits;

computing an inner syndrome by exclusive-ORing the regenerated inner checkbits with the existing inner checkbits; and

determining from the row syndrome and the inner syndrome whether there remains a double-bit error wherein both erroneous bits are in the same row and one is in the column associated with the failed component.

6. The method of claim 3 , wherein CV(x, y) is the check vector associated with the bit at row x and column y of the array, and wherein the set of keys are selected so that for any two distinct rows r 1 and r 2 and any three distinct columns c 1 , c 2 , and c 3 , CV(r 1 , c 1 ) XOR CV(r 2 , c 2 ) XOR CV(r 1 , c 3 ) XOR CV(r 2 , c 3 ) is not equal to zero.

7. The method of claim 3 , wherein a key associated with a column c y is denoted as key(c y ), and wherein the set of keys are selected so that for any row r, and for any three distinct columns c 1 , c 2 and c 3 , key(c 1 ) XOR key(c 2 ) is not equal to the product in GF(2 X ) of key(c 1 ) XOR key(c 3 ) and α r .

8. The method of claim 3 , wherein prior to accessing the block of data, the method further comprises generating the set of keys associated with the columns so that key 0 =0, and for each i, 1≦i≦C−1, key i =α^((2 (X/2) +1)j), wherein j is a unique integer for each value of i and X is an even integer.

9. The method of claim 1 , wherein previously determining that the memory component failed involves:

accessing a block of data from the memory system, wherein the block of data includes an array of bits logically organized into R rows and C columns, including two checkbit columns and C−2 data-bit columns;

re-generating the checkbits for the two checkbit columns from the data bits in the data-bit columns;

comparing the re-regenerated checkbits with the existing checkbits in the two checkbit columns; and

determining that the memory component has failed based on the comparison.

10. The method of claim 9 , wherein comparing the regenerated row-parity bits and inner checkbits with the existing row-parity bits and inner checkbits involves:

computing a row syndrome by exclusive-ORing the regenerated row-parity bits with the existing row-parity bits;

computing an inner syndrome by exclusive-ORing the regenerated inner checkbits with the existing inner checkbits; and

if the row syndrome viewed as an element of GF(2 X ) is non-zero, using the row syndrome and the inner syndrome to determine a key for a column associated with the failed memory component, and then comparing the determined key against the set of keys to identify the failed memory component.

11. The method of claim 10 , wherein determining the key for the column associated with the failed memory component involves performing a division operation in GF(2 X ) of the inner syndrome by the row syndrome to determine the key for the column associated with the failed memory component.

12. The method of claim 10 , wherein determining the key for the column associated with the failed memory component involves:

performing multiplication operations in GF(2 X ) between the row syndrome and each key in the set of keys;

comparing the inner syndrome against results of the multiplication operations; and

if the inner syndrome matches a result, determining that the key associated with the result is the key for the column associated with the failed memory component.

13. The method of claim 1 , wherein each data block contains a cache line or a portion of a cache line.

14. A memory system that provides error detection and correction after a failure of a memory component in a memory system, comprising:

an access mechanism configured to access a block of data from the memory system, wherein the memory system is previously determined to have a specific failed memory component, wherein each block of data in the memory system includes an array of bits logically organized into R rows and C columns, including a row checkbit column including row-checkbits for each of the R rows, an inner checkbit column including X<R inner checkbits and R−X data bits, and C−2 data-bit columns containing data bits, wherein each column is stored in a different memory component, and wherein the checkbits, which comprise the row-checkbits and the inner checkbits, are generated from the data bits to provide block-level detection and correction for a failed memory component; and

an error-handling circuit configured to,

attempt to correct a column of the block from the failed memory component by using the checkbits and the data bits to produce a corrected column,

regenerate row-parity bits and the inner checkbits for the block of data, wherein the block includes the corrected column,

compare the regenerated row-parity bits and inner checkbits with existing row-parity bits and inner checkbits, and

if comparison indicates that there remains a double-bit error wherein both erroneous bits are in the same row and one is in the column associated with the failed component, flip the erroneous bits to correct the double-bit error.

15. The memory system of claim 14 ,

wherein the row checkbit column contains the row-parity bits for each of the R rows in the block; and

wherein the inner checkbit column contains X<R inner checkbits which are defined to cover bits in the array in accordance with a set of check vectors, wherein each check vector is associated with a different bit in the array and is an element of a Galois Field (GF(2 X )), wherein the check vectors are derived from a set of keys which are unique elements of GF(2 X ), wherein each key is associated with a different column of the array, and wherein the check vector for a row r of a column c is the product in GF(2 X ) of the key for the column c and α r , wherein α is a primitive element of GF(2 X ).

16. The memory system of claim 15 , wherein the set of keys are elements of a subfield of G(2 X ), wherein the subfield does not contain any α i , where 1≦i<R.

17. The memory system of claim 16 , wherein while attempting to correct the column from the failed memory component, the error-handling circuit is configured to:

regenerate the row-parity bits and the inner checkbits for the block of data from the data bits in the block of data;

compute a row syndrome by exclusive-ORing the regenerated row-parity bits with the existing row-parity bits;

compute an inner syndrome by exclusive-ORing the regenerated inner checkbits with the existing inner checkbits;

use the row syndrome to identify erroneous bits in the data-bit column associated with the failed memory component; and

flip the identified erroneous bits to produce the corrected data-bit column.

18. The memory system of claim 16 , wherein for the case where the corrected column was produced and the row-parity bits and the inner checkbits were regenerated using the corrected column, while comparing the regenerated row-parity bits and inner checkbits with the existing row-parity bits and inner checkbits, the error-handling circuit is configured to:

compute a row syndrome by exclusive-ORing the regenerated row-parity bits with the existing row-parity bits;

compute an inner syndrome by exclusive-ORing the regenerated inner checkbits with the existing inner checkbits; and

determine from the row syndrome and the inner syndrome whether there remains a double-bit error wherein both erroneous bits are in the same row and one is in the column associated with the failed component.

19. The memory system of claim 16 , further comprising a key-generation mechanism, wherein prior to accessing the block of data, the key-generation mechanism is configured to generate the set of keys associated with the columns so that key 0 =0, and for each i, 1≦i≦C−1, key i =α^((2 (X/2) +1)j), wherein j is a unique integer for each value of i and X is an even integer.

20. A computer system that provides error detection and correction after a failure of a memory component in a memory system, comprising:

a processor;

a memory system;

an access mechanism within the memory system configured to access a block of data from the memory system, wherein the memory system is previously determined to have a specific failed memory component, wherein each block of data in the memory system includes an array of bits logically organized into R rows and C columns, including a row checkbit column including row-checkbits for each of the R rows, an inner checkbit column including X<R inner checkbits and R−X data bits, and C−2 data-bit columns containing data bits, wherein each column is stored in a different memory component, and wherein the checkbits, which comprise the row-checkbits and the inner checkbits, are generated from the data bits to provide block-level detection and correction for a failed memory component; and

an error-handling circuit within the memory system configured to,

attempt to correct a column of the block from the failed memory component by using the checkbits and the data bits to produce a corrected column,

regenerate row-parity bits and the inner checkbits for the block of data, wherein the block includes the corrected column,

compare the regenerated row-parity bits and inner checkbits with existing row-parity bits and inner checkbits, and

if comparison indicates that there remains a double-bit error wherein both erroneous bits are in the same row and one is in the column associated with the failed component, flip the erroneous bits to correct the double-bit error.