Scalable-chip-correct ECC scheme

• US 20050034050A1
• Filed: 08/08/2003
• Published: 02/10/2005
• Est. Priority Date: 08/08/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Das, Debaleena, Mandel, Alan H.
• Granted Patent: US 7,530,008 B2
• Time in Patent Office: Days
• US Class Current: 714/758
• CPC Class Codes: H03M 13/1575 Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance

Abstract

An apparatus comprises an encode circuit coupled to receive input data and configured to generate corresponding codewords and a decode circuit coupled to receive codewords and detect an error in the codewords (and may, in some cases, correct the error). Each codeword comprises a plurality of b-bit portions (b is an integer greater than one). Additionally, each codeword comprises a first set of b check bits used to detect a magnitude of an error in a b-bit portion of the plurality of b-bit portions. Each codeword further comprises a second set of w check bits used to locate which one of the plurality of b-bit portions is the b-bit portion containing the error (w is an integer greater than zero and less than b).

Claims

1. An apparatus comprising:

an encode circuit coupled to receive input data and configured to generate corresponding codewords; and

a decode circuit coupled to receive codewords and detect an error in the codewords;

wherein each codeword comprises a plurality of b-bit portions, wherein b is an integer greater than one, and wherein each codeword comprises a first set of b check bits used to detect a magnitude of an error in a first b-bit portion of the plurality of b-bit portions, and wherein each codeword comprises a second set of w check bits used to locate which one of the plurality of b-bit portions is the first b-bit portion containing the error, wherein w is an integer greater than zero and less than b.

2. The apparatus as recited in claim 1 wherein w is at least a ceiling function of log₂.

3. The apparatus as recited in claim 1 wherein the codewords are stored in and retrieved from a plurality of memories, wherein each memory stores a different one of the plurality of b-bit portions of a given code word.

4. The apparatus as recited in claim 3 wherein each memory has a b-bit input/output width.

5. The apparatus as recited in claim 1 wherein the codewords are transmitted on a transmission medium comprising a plurality of slices.

6. The apparatus as recited in claim 5 wherein each of the plurality of slices comprises b conductors that carry the b-bit portions during use.

7. The apparatus as recited in claim 1 wherein a second b-bit portion of the plurality of b-bit portions comprises the first set of check bits, and wherein the encode circuit is configured to generate the first set of check bits as a sum, in GF(2^b), of the other ones of the plurality of b-bit portions excluding the second b-bit portion.

8. The apparatus as recited in claim 7 wherein the encode circuit is configured to generate the second set of check bits according to an equation in which each of the plurality of b-bit portions except the second b-bit portion is multiplied by a different matrix having b columns and w rows, each column of the matrix being an element of GF(2^w), wherein the results of the multiplications are summed to equal zero.

9. The apparatus as recited in claim 1 wherein a second b-bit portion of the plurality of b-bit portions comprises the second set of check bits, and wherein the second b-bit portion of the codeword further comprises at least one data bit.

10. The apparatus as recited in claim 1 wherein the decode circuit is further configured to correct the error if the error is located by the second set of check bits, wherein at least one possible error is not locatable using the second set of check bits.

11. An apparatus comprising:

an encode circuit coupled to receive input data and configured to generate corresponding codewords; and

a decode circuit coupled to receive codewords and detect an error in the codewords;

wherein each codeword comprises a plurality of b-bit portions, wherein b is an integer greater than one, each b-bit portion comprising a symbol that is an element of GF(2^b), and wherein a first b-bit portion of the plurality of b-bit portions is a first check symbol comprising a sum in GF(2^b) of the remaining plurality of b-bit portions, and wherein a second b-bit portion of the plurality of b-bit portions comprises a second check symbol that is an element of GF(2^w), wherein w is an integer greater than zero and less than b, and wherein the second check symbol is generated to satisfy an equation in which each of the symbols in the code word, excluding the first symbol, is multiplied by a different matrix having b columns and w rows, each of the columns comprising a symbol in GF(2^w), and the sum of the multiplication results equaling zero.

12. The apparatus as recited in claim 11 wherein the first check symbol is used to detect a magnitude of an error in a second symbol of the codeword, and wherein the second check symbol is used to detect which symbol of the codeword is in error.

13. The apparatus as recited in claim 12 wherein the decode circuit is further configured to correct the error in the symbol if the error is locatable, wherein at least one possible error is not locatable.

14. The apparatus as recited in claim 11 wherein w is at least a ceiling function of log₂.

15. The apparatus as recited in claim 11 wherein the codewords are stored in and retrieved from a plurality of memories, wherein each memory stores a different one of the plurality of b-bit portions of a given code word.

16. The apparatus as recited in claim 11 wherein the codewords are transmitted on a transmission medium comprising a plurality of b-bit slices.

17. A method comprising:

receiving input data; and

generating a corresponding codeword for the input data, wherein the codeword comprises a plurality of b-bit portions, wherein b is an integer greater than one, and wherein the codeword comprises a first set of b check bits used to detect a magnitude of an error in a first b-bit portion of the plurality of b-bit portions, and wherein the codeword comprises a second set of w check bits used to locate which one of the plurality of b-bit portions is the first b-bit portion containing the error, wherein w is an integer greater than zero and less than b.

18. The method as recited in claim 17 wherein w is at least a ceiling function of log₂.

19. The method as recited in claim 17 wherein a second b-bit portion of the plurality of b-bit portions comprises the first set of check bits, and wherein generating the corresponding codeword comprises generating the first set of check bits as a sum, in GF(2^b), of the other ones of the plurality of b-bit portions excluding the second b-bit portion.

20. The method as recited in claim 19 wherein generating the corresponding codeword further comprises generating the second set of check bits according to an equation in which each of the plurality of b-bit portions except the second b-bit portion is multiplied by a different matrix having b columns and w rows, each column of the matrix being an element of GF(2^w), wherein the results of the multiplications are summed to equal zero.

21. An apparatus comprising:

a means for encoding input data to generate corresponding codewords; and

a means for decoding codewords and detecting an error in the codewords;

wherein each codeword comprises a plurality of b-bit portions, wherein b is an integer greater than one, and wherein each codeword comprises a first set of b check bits used to detect a magnitude of an error in a first b-bit portion of the plurality of b-bit portions, and wherein each codeword comprises a second set of w check bits used to locate which one of the plurality of b-bit portions is the first b-bit portion containing the error, wherein w is an integer greater than zero and less than b.

22. An apparatus comprising:

an encode circuit coupled to receive input data and configured to generate corresponding codewords; and

a decode circuit coupled to receive codewords and detect an error in the codewords;

wherein each codeword comprises a plurality of b-bit portions, wherein b is an integer greater than one, and wherein each codeword comprises a first set of b check bits used to detect a magnitude of an error in a first b-bit portion of the plurality of b-bit portions, and wherein each codeword comprises a second set of b check bits used to locate which one of the plurality of b-bit portions is the first b-bit portion containing the error, and wherein the second set of check bits is generated to ensure that a sum of the results of a matrix multiplication of each of the plurality of b-bit portions except the first b-bit portion by a different one of a plurality of b×

b matrices is zero, and wherein a first matrix of the plurality of b×

b matrices has columns that are elements of GF(2^b), and wherein the columns are linearly independent, and wherein the first matrix differs from the matrix corresponding to multiplication by e⁰ in GF(2^b), and wherein each of the other ones of the plurality of b×

b matrices are derived from the first matrix by multiplying the columns of the first matrix by e^k in GF(2^b), wherein k is an integer ranging between 1 and N−

1, wherein N is an integer equal to a number of the plurality of b-bit portions in the codeword.