Method Of Correcting Adjacent Errors By Using BCH-Based Error Correction Coding

• US 20130262957A1
• Filed: 03/30/2012
• Published: 10/03/2013
• Est. Priority Date: 03/30/2012
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Wu, Wei, Lu, Shih-Lien L., Khellah, Muhammad M.
• Granted Patent: US 8,762,821 B2
• Time in Patent Office: Days
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• 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 is provided that comprises a processor. The processor comprises a cache to store data, a decoder, an error classification module, and an error correction module. The cache stores data, the data encoded as a codeword. The decoder reads the codeword from cache and calculates a syndrome of the codeword using an H-matrix. The error classification module determines an error type of the syndrome. The H-matrix is redesigned such that the columns form a geometrical sequence, and as a result not only the t-bit random errors but also (t+1) bit adjacent errors can be corrected. The error correction module, triggered by the enhanced error classification module, takes one of two sets of inputs depends on the error type (either random or adjacent error) and produces corrected data from the syndrome when the syndrome comprises a detectable and correctable error.

Claims

1. A processor comprising:

a cache to store data, the data encoded as a codeword to cache;

a decoder to read the code word from the cache, the decoder to calculate a syndrome of the codeword using an H-matrix;

an error classification module to determine an error type of the syndrome; and

an error correction module, triggered by the error classification module, the error correction module to produce corrected data from the syndrome when the syndrome comprises a detectable and correctable error.

2. The processor of claim 1, the error correction module comprising an error bit locating module, the error bit locating correcting module to determine when adjacent errors exist that can be corrected as adjacent errors.

3. The processor of claim 2, the error bit locating module coupled to the error classification module with a pair of multiplexors coupled to the input and output of the error bit locating module, the error bit locating module activated by an indication of a multiple bit error.

4. The processor of claim 2, the error correction module to produce a detectable but uncorrectable error (DUE) flag when a determination by the error classification module finds the syndrome to comprise a double error, multiple error, or when the error correction module does not determine an error bit position.

5. The processor of claim 1, the error correction module comprising:

a bit correcting module to evaluate a normalized syndrome* against each column of the H-matrix to determine a first error bit position;

an input multiplexor coupled to the input of the bit correcting module;

an output multiplexor coupled to the output of the bit correcting module, the input multiplexor and the output multiplexor triggered by a double error flag from the error classification module; and

the error bit correcting module to produce an uncorrectable error flag when the normalized syndrome* evaluated against each column of the H-matrix does not determine the first error bit position.

6. The processor of claim 5, the error correction module comprising:

a error bit locating logic circuitry to evaluate a locator polynomial constructed based on the normalized syndrome* against each column of the H-matrix to determine the first error bit position;

an input multiplexor coupled to the input of the error bit locating logic circuitry;

an output multiplexor coupled to the output of the error bit locating logic circuitry, the input multiplexor and the output multiplexor triggered by a triple adjacent error flag from the error classification module; and

the error bit locating logic circuitry to produce an uncorrectable error flag when the error bit locating logic circuitry does not determine the first error bit position.

7. The processor of claim 6, the error correction module to produce a detectable but uncorrectable error (DUE) flag when the error classification module determines the syndrome comprises a multiple error, or when the error bit locating logic circuitry produces an uncorrectable flag.

8. A system comprising:

a multi-core processor including;

a cache to store data, the data encoded as a codeword to cache;

a decoder to read the code word from the cache, the decoder to calculate a syndrome of the codeword using an H-matrix;

an error classification module to determine an error type of the syndrome;

an error correction module, triggered by the error classification module, the error correction module to produce corrected data from the syndrome when the syndrome comprises a detectable and correctable error; and

a dynamic random access memory (DRAM) coupled to the multi-core processor.

9. The system of claim 8, the error correction module comprises a bit correcting module, the bit correcting module to evaluate the syndrome against each column of the H-matrix to determine a single error bit position.

10. The system of claim 9, the error correction module to produce a detectable but uncorrectable error (DUE) flag when evaluation of the syndrome against each column of the H-matrix does not determine the single error bit position

11. The system of claim 9, the error correction module to produce a detectable but uncorrectable error (DUE) flag when the error classification module determines the syndrome comprises a double error, multiple errors, or when the error correction module evaluation of the syndrome against each column of the H-matrix does not determine the first error bit position.

12. The system of claim 8, the error correction module comprises:

a bit correcting module to evaluate the normalized syndrome* against each column of the H-matrix to determine a first error bit position;

an input multiplexor coupled to the input of the bit correcting module;

an output multiplexor coupled to the output of the bit correcting module, the input multiplexor and the output multiplexor triggered by a double error flag from the error classification module; and

the bit correcting module to produce an uncorrectable error flag when the normalized syndrome* evaluated against each column of the H-matrix does not determine the first error bit position.

13. The system of claim 8, the error correction module comprises:

a double error bit locating logic circuitry to evaluate a locator polynomial based on the syndrome against each column of the H-matrix to determine the first error bit position;

an input multiplexor coupled to the input of the double error bit locating logic circuitry;

an output multiplexor coupled to the output of the double error bit locating logic circuitry, the input multiplexor and the output multiplexor triggered by a triple adjacent error flag from the error classification module;

the error correction module to;

produce an uncorrectable error flag when double error bit locating logic circuitry cannot determine the first error bit position; and

produce corrected data when the first error bit position is located.

14. The system of claim 13, the error correction module to produce a detectable but uncorrectable error (DUE) flag when the error classification module determines the syndrome comprises a multiple error, or when the double error bit locating logic circuitry produces an uncorrectable flag.

15. A method comprising:

retrieving an encoded codeword from a cache;

reading the encoded code word from the cache;

calculating a syndrome of the encoded codeword using an H-matrix;

determining an error type of the syndrome; and

error correcting the encoded codeword to produce corrected data, the error correcting triggered by the error type of the syndrome, the error correcting triggered when the syndrome comprises a detectable and correctable error.

16. The method of claim 15, where the error correcting further comprising evaluating the syndrome against each column of the H-matrix.

17. The method of claim 16, further comprising producing a detectable but uncorrectable error (DUE) flag when evaluation of the syndrome against each column of the H-matrix does not determine an error bit position.

18. The method of claim 16, where the error correcting further comprises:

producing a detectable but uncorrectable error (DUE) flag when the syndrome comprises a double error, multiple error, or when evaluation of the syndrome against each column of the H-matrix does not determine an error bit position.

19. The method of claim 15, where the error correcting further comprises:

evaluating the syndrome against each column of the H-matrix to determine a single error bit position;

evaluating a normalized Syndrome* against each column of the H-matrix to determine a the first error bit position in an adjacent double-bit error pair; and

producing the corrected data when the first error bit position is located, and a second error bit position is adjacent to the first error bit position.

20. The method of claim 15, where the error correcting further comprises:

evaluating a locator polynomial constructed based on the syndrome, against each column of the H-matrix to determine a triple adjacent error bit position;

producing an uncorrectable error flag when a first error bit position cannot be determined; and

producing corrected data when the first error bit position of the triple adjacent error is located and a second error bit position and a third error bit position are adjacent to the first error bit position