Data error detection and correction in non-volatile memory devices

• US 7,865,809 B1
• Filed: 07/01/2008
• Issued: 01/04/2011
• Est. Priority Date: 03/11/2004
• Status: Expired due to Fees

• Current Assignee: Super Talent Technology, Corporation
• Original Assignee: Super Talent Electronics, Inc.
• Inventors: Shen, Ming-Shiang, Lee, Charles C., Ma, Abraham Chih-Kang, Yu, I-Kang
• Primary Examiner(s): RIZK, SAMIR WADIE
• Application Number:
  US12/166,191
• Time in Patent Office: 917 Days
• Field of Search: 714/781, 714/782, 714/784
• US Class Current: 714/782
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey algorithm
• CPC Class Codes: H03M 13/1535 using the Euclid algorithm
• CPC Class Codes: H03M 13/1545 Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial
• CPC Class Codes: H03M 13/6561 Parallelized implementations

Abstract

Data error detection and correction in non-volatile memory devices are disclosed. Data error detection and correction can be performed with software, hardware or a combination of both. Generally an error corrector is referred to as an ECC (error correction code). One of the most relevant codes using in non-volatile memory devices is based on BCH (Bose, Ray-Chaudhuri, Hocquenghem) code. In order to correct reasonable number (e.g., up to 8-bit (eight-bit)) of random errors in a chunk of data (e.g., a codeword of 4200-bit with 4096-bit information data), a BCH(4200,4096,8) is used in GF(2¹³). ECC comprises encoder and decoder. The decoder further comprises a plurality of error detectors and one error corrector. The plurality of error decoders is configured for calculating odd terms of syndrome polynomial for multiple channels in parallel, while the error corrector is configured for sequentially calculating even terms of syndrome polynomial, key solver and error location.

Claims

1. A system for performing data error correction in a non-volatile memory device comprising:

a plurality of data error detectors each containing an odd-syndrome calculator, wherein the odd-syndrome calculator is configured for calculating odd terms of syndrome polynomial of a codeword;

at least one data encoder configured for encoding a chunk of data based on a predetermined coding scheme of (Bose, Ray-Chaudhuri, Hocquenghem) BCH (4200, 4096,

     8) code including a 4200-bit codeword with 4096-bit information data and up to eight (8) random correctible data errors;

a multiplexer coupling to the plurality of data error detectors; and

a data error corrector, coupling to the multiplexer, comprising an even-syndrome calculator, a key-solver and an error locator, wherein the even-syndrome calculator is configured for calculating even terms of the syndrome polynomial, wherein the key solver is configured for determining coefficients of error polynomial based on the odd and even terms of the syndrome polynomial, and wherein the error locator is configured for finding one or more locations of random data error using the coefficients of error location polynomial.

2. The system of claim 1, wherein the at least one data encoder encodes the chunk of data using a generator polynomial in Galois Field GF(2¹³).

3. The system of claim 2, wherein the chunk of data comprises a data sector of 512-byte.

4. The system of claim 3, wherein the codeword includes the data sector plus parity checks of 13-byte.

5. The system of claim 4, wherein the generator polynomial is created based on maximum eight random data errors.

6. The system of claim 1, wherein the odd and even terms of the syndrome polynomial are calculated based on maximum number of random data errors configured in the BCH code.

7. The system of claim 1, wherein the plurality of data error detectors is configured to perform calculations in parallel, and the data error corrector in serial.

8. The system of claim 1, wherein the key solver is based on inversion-less Berlekamp-Massey with half loop count iterative process.

9. The system of claim 1, wherein the error locator is based on ‘

p’

-way parallel Chien search, where ‘

p’

is a positive integer.

10. The system of claim 1, wherein a plurality of data error detectors comprises four symmetrical data error detectors.

11. A method of performing data error correction in a non-volatile memory device comprising:

receiving a plurality of codewords each encoded with a predetermined coding scheme of (Bose, Ray-Chaudhuri, Hocquenghem) BCH (4200, 4096,

     8) code including a 4200-bit codeword with 4096-bit information data and up to eight (8) random correctible data errors;

calculating odd terms of syndrome polynomial of each of the codewords in parallel;

determining whether said each of the codewords contains any data error;

when said data error is found,

sequentially calculating even terms of the syndrome polynomial corresponding to the odd terms of those of the codewords containing said data error;

iteratively obtaining coefficients of error polynomial using the odd and even terms of the syndrome polynomial;

locating at least one random error location in each of said those of the codewords containing said data error using Chien search logic; and

correcting data error at the at least one random error location accordingly.

12. The method of claim 11, wherein the BCH (4200,4096,8) is created in a Galois Field GF(2¹³) with a generator polynomial.

13. The method of claim 12, wherein the generator polynomial comprises 49 terms represented as follows:

1+x+x⁵+x⁸+x⁹+x¹¹+x¹²+x¹³+x¹⁴+x¹⁵+x¹⁸+x²²+x²³+x²⁴+x²⁶+x³⁰+x³¹+x³²+x³⁸+x⁴⁰+x⁴¹+x⁴²+x⁴⁷+x⁴⁸+x⁴⁹+x⁵²+x⁵⁸+x⁵⁹+x⁶⁴+x⁶⁵+x⁶⁷+x⁶⁸+x⁶⁹+x⁷⁰+x⁷⁷+x⁷⁸+x⁷⁹+x⁸²+x⁸⁴+x⁸⁸+x⁹¹+x⁹²+x⁹³+x⁹⁴+x⁹⁵+x⁹⁶+x⁹⁸+x¹⁰⁰+x¹⁰⁴.

14. The method of claim 13, wherein both the odd and even terms of the syndrome polynomial are calculated using the generator polynomial.

15. The method of claim 11, wherein the key solver is based on inversion-less Berlekamp-Massey iterative procedure with half loop count.

16. The method of claim 11, wherein the Chien search logic comprises a ‘

p’

-way parallel logic, where ‘

p’

is a positive interger.