Scalable-chip-correct ECC scheme

• US 7,530,008 B2
• Filed: 08/08/2003
• Issued: 05/05/2009
• 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.
• Primary Examiner(s): Abraham; Esaw T
• Assistant Examiner(s): Ahmed; Enam
• Application Number:
  US10/637,469
• Publication Number:
  US 20050034050A1
• Time in Patent Office: 2,097 Days
• Field of Search: 714/784
• US Class Current: 714/784
• 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 encoder coupled to receive input data and configured to generate corresponding codewords; and

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

wherein each codeword comprises a plurality of b-bit portions including two or more b-bit portions that contain data, and further including a first set of b check bits and a second set of w check bits;

wherein b is an integer greater than one, and wherein the first set of b check bits is used to detect a magnitude of an error in a first b-bit portion of the plurality of b-bit portions, wherein the magnitude of the error indicates whether or not an error is detected and further indicates which bits within the first b-bit portion are in error, and wherein the second set of w check bits is 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;

wherein the encoder is configured to generate the first set of b check bits responsive to the plurality of b-bit portions of the codeword excluding the b-bit portion that stores the first set of b check bits, and wherein the encoder is configured to generate the second set of w check bits for a given codeword responsive to the data in the codeword; and

wherein the decoder is configured to decode the first set of b check bits and the codeword to detect and error and the magnitude of the error, and wherein the decoder is configured to decode the second set of w check bits and the data in the code word to locate the first b-bit portion containing the error.

2. The apparatus as recited in claim 1 wherein w is at least a ceiling function of log₂ [a number of the plurality of b-bit portions].

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 encoder 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 encoder 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 decoder 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 encoder coupled to receive input data and configured to generate corresponding codewords; and

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

wherein each codeword comprises a plurality of b-bit portions including two or more b-bit portions that contain data, and further including a first check symbol and a second check symbol;

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, and wherein the encoder is configured to generate the first check symbol as 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 the 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 encoder is configured to generate the second check symbol to satisfy an equation in which each of the symbols in the code word, excluding the first check 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, and wherein the first check symbol is used to detect a magnitude of an error in a first b-bit portion of the plurality of b-bit portions of the codeword, wherein the magnitude of the error indicates whether or not an error is detected and further indicates which bits within the first b-bit portion are in error, and wherein the second check symbol is used to locate which of the plurality of b-bit portions is the first b-bit portion that contains the error.

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

13. The apparatus as recited in claim 11 wherein w is at least a ceiling function of log₂ [a number of the plurality of b-bit portions].

14. 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.

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

16. A method comprising:

receiving input data in an integrated circuit, the integrated circuit comprising an encoder; and

the encoder generating a corresponding codeword for the input data, wherein the codeword comprises a plurality of b-bit portions including two or more b-bit portions that contain input data, and further including a first set of b check bits and a second set of w check bits; and

wherein b is an integer greater than one, and wherein the 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, wherein the magnitude of the error indicates whether or not an error is detected and further indicates which bits within the first b-bit portion are in error, and wherein the second set of w check bits is 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, and wherein generating the corresponding code word for the input data comprises;

the encoder generating the first set of b check bits responsive to the plurality of b-bit portions of the codeword excluding the b-bit portion that stores the first set of b check bits; and

the encoder generating the second set of w check bits for a given codeword responsive to the input data in the codeword.

17. The method as recited in claim 16 wherein w is at least a ceiling function of log₂ [a number of the plurality of b-bit portions].

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

19. The method as recited in claim 18 wherein generating the second set of check bits is performed 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.