MEMORY SYSTEM AND METHOD FOR PROVIDING ERROR CORRECTION

• US 20090217140A1
• Filed: 02/23/2009
• Published: 08/27/2009
• Est. Priority Date: 02/27/2008
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: JO, Nam-Phil, YOUN, Dae-Han
• Granted Patent: US 8,301,986 B2
• Time in Patent Office: Days
• US Class Current: 714/785
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• 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/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
• CPC Class Codes: H03M 13/3715 Adaptation to the number of estimated errors or to the channel state

Abstract

An error correction decoder includes a syndrome computation circuit, an error correction and computation circuit and an error correction circuit. The syndrome computation circuit calculates a syndrome of read data. The error correction and computation circuit calculates a location of a single-bit error using a division operation between elements of the syndrome when the single-bit error exists in the read data. The error correction circuit corrects the single-bit error of the read data based on the location of the single-bit error.

Claims

1. An error correction decoder comprising:

a syndrome computation circuit for calculating a syndrome of read data;

an error correction and computation circuit for calculating a location of a single-bit error using a division operation between elements of the syndrome when the single-bit error exists in the read data; and

an error correction circuit for correcting the single-bit error of the read data based on the location of the single-bit error.

2. The error correction decoder of claim 1, wherein the error correction and computation circuit comprises:

a single-bit error correction circuit for performing the division operation between the elements of the syndrome to compute the location of the single-bit error; and

a multi-bit error correction circuit for performing a forward Chien search operation to compute error location and pattern from the syndrome.

3. The error correction decoder of claim 2, further comprising:

a controller for detecting from the syndrome whether to activate the single-bit error correction circuit.

4. The error correction decoder of claim 2, wherein the single-bit error correction circuit comprises:

an inverse Galois-Field module for providing a reciprocal (1/S_i) of a first element (S_i) of the syndrome; and

a Galois-Field multiplier for performing Galois-Field multiplication of the reciprocal (1/S_i) and a second element (S_i+1) of the syndrome to output a result as an error location function (S_i+1/S_i).

5. The error correction decoder of claim 4, wherein the single-bit error correction circuit further comprises:

a converter for converting the error location function (S_i+1/S_i) into a format of error correction data for correcting the error of the read data.

6. The error correction decoder of claim 5, wherein the error correction data comprises error location and error pattern values.

7. The error correction decoder of claim 4, wherein the inverse Galois-Field module comprises a table stored in a read-only memory (ROM) having a plurality of reciprocals corresponding to a plurality of elements of the syndrome, the ROM table being driven in a look-up table manner where the reciprocal (1/S_i) is provided in response to the first element (S_i).

8. The error correction decoder of claim 4, wherein the inverse Galois-Field module comprises a software module configured to compute the reciprocal (1/S_i) of the first element (S_i).

9. The error correction decoder of claim 2, wherein the single-bit error correction circuit comprises:

a divider for performing a Galois-Field division operation using a first element (S_i) of the syndrome as a divisor and a second element (S_i+1) of the syndrome as a dividend; and

a converter for converting an output of the divider as an error location function (S_i+1/S_i) into a format of error correction data for correcting the error of the read data.

10. The error correction decoder of claim 2, wherein the multi-bit error correction circuit comprises:

a key equation solver (KES) circuit for generating an error location polynomial and an error pattern polynomial from the syndrome;

a seed generator for generating a seed value for a Chien search operation with reference to code length information (n, k) of the read data; and

a Chien search circuit for computing zeros of the error location polynomial and the error pattern polynomial with reference to the seed value.

11. The error correction decoder of claim 1, further comprising:

a buffer for storing the read data to provide the read data to the error correction circuit.

12. The error correction decoder of claim 1, wherein the read data includes an error correction code of a circuit code manner.

13. The error correction decoder of claim 1, wherein the read data comprises an error correction code of a Bose Chaudhuri Hocquenghem (BCH) or a Read-Solomon (RS) code type.

14. A method of correcting an error of circuit code data comprising:

computing a syndrome of read data;

determining when the read data includes an error and whether the error of the read data is a one-bit error, based on the syndrome;

when the error of the read data is a one-bit error, obtaining an error location using a division operation of consecutive elements of the syndrome; and

correcting the error of the read data based upon the error location.

15. The method of claim 14, wherein the division operation comprises obtaining a reciprocal (1/S_i) of a first element (S_i) of the syndrome;

and multiplying the reciprocal and a second element (S_i+1) of the syndrome.

16. The method of claim 15, wherein the reciprocal (1/S_i) is obtained from a table.

17. The method of claim 15, wherein the reciprocal (1/S_i) is obtained via a reciprocal computation algorithm provided by a Galois-Field.

18. The method of claim 14, further comprising:

performing a forward Chien search operation for computing an error location from the syndrome when the error is a multi-bit error.

19. The method of claim 18, further comprising:

computing a seed value used to perform the forward Chien search operation.

20. A memory system comprising:

a non-volatile memory device; and

a memory controller comprising an error correction code (ECC) circuit for eliminating an error from read data of the non-volatile memory device, wherein the ECC circuit comprises;

a syndrome computation circuit for computing a syndrome from the read data;

an error correction and computation circuit for computing a location of the error of the read data using a division operation between elements of the syndrome, when the error is a single-bit error; and

an error correction circuit for correcting the error of the read data with reference to the error location.