Error correction decoder and operation method of the error correction decoder

• US 9,923,580 B2
• Filed: 10/07/2015
• Issued: 03/20/2018
• Est. Priority Date: 10/13/2014
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Kijun, Lee, Myungkyu, Lim, Sejin, Kong, Junjin
• Primary Examiner(s): Nguyen, Steve
• Application Number:
  US14/877,448
• Publication Number:
  US 20160103735A1
• Time in Patent Office: 895 Days
• CPC Class Codes: H03M 13/1525 Determination and particular use of error location 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/157 Polynomial evaluation, i.e. determination of a polynomial sum at a given value
• CPC Class Codes: H03M 13/3715 Adaptation to the number of estimated errors or to the channel state

Abstract

The inventive concepts relate to an operation method of an error correction decoder correcting an error of data read from a nonvolatile memory. The operation method may include receiving the data from the nonvolatile memory, performing a first error correction with respect to the received data in a simplified mode, and performing, when the first error correction fails in the simplified mode, a second error correction with respect to the received data in a full mode. When the first error correction of the simplified mode is performed, a part of operations of the second error correction of the full mode may be omitted.

Claims

1. An operation method of an error correction decoder correcting an error of data read from a nonvolatile memory, the operation method comprising:

receiving data from the nonvolatile memory;

performing an error correction with respect to the received data in a simplified mode, the simplified mode being a mode in which a portion of a process of the error correction is omitted;

storing information about the error correction in the simplified mode in a buffer;

performing the error correction with respect to the received data in a full mode based on the information stored in the buffer in response to the error correction failing in the simplified mode, the simplified mode being a subset of a full mode;

terminating early the error correction by skipping at least the error correction in the full mode in response to a first condition indicating successful error correction being satisfied during performing the error correction in the simplified mode; and

outputting results of the error correction as an error-corrected data.

2. The operation method of claim 1, wherein each of the performing an error correction in a simplified mode and the performing an error correction in a full mode includes calculating an error location polynomial, and

wherein in the simplified mode, the calculating an error location polynomial is terminated early in response to the first condition being satisfied, and is fully performed in response to a second condition being satisfied.

3. The operation method of claim 2, wherein the calculating an error location polynomial includes performing a plurality of calculation loops, and

the second condition includes that the error location polynomial is maintained without being renewed until a number of consecutive calculation loops reaches a threshold number.

4. The operation method of claim 3, wherein the first condition includes that the error location polynomial is calculated until a maximum loop of the plurality of calculation loops is performed.

5. The operation method of claim 2, wherein each of the performing an error correction in a simplified mode and the performing an error correction in a full mode further includes searching for errors in the received data using the error location polynomial, and

wherein it is determined that an error correction fails in response to an highest order of the error location polynomial not coinciding with a number of errors searched.

6. The operation method of claim 1, wherein, it is determined that the received data has errors beyond a correction range in response to a failure of the error correction in the full mode.

7. The operation method of claim 1, wherein the performing an error correction in a simplified mode comprises:

calculating syndromes based on the received data;

calculating a first error location polynomial using the calculated syndromes;

performing a chien search using the first error location polynomial; and

correcting an error of the received data according to a result of the chien search,

wherein the calculating a first error location polynomial comprises performing a plurality of calculation loops, and

wherein the calculating a first error location polynomial is terminated early before completion in response to the first error location polynomial being maintained without being renewed until as the performing a plurality of calculation loops reach a threshold number of times.

8. The operation method of claim 7, wherein the calculating a first error location polynomial performs the performing a plurality of calculation loops while selecting different syndromes, and

wherein each of the calculation loops comprises,

calculating discrepancy based on a selected one of the syndromes and a first error location polynomial calculated in a previous one of the calculation loops;

and

renewing or maintaining the first error location polynomial according to whether the calculated discrepancy has a first value.

9. The operation method of claim 7, wherein the performing the error correction in a full mode comprises:

calculating syndromes based on the received data;

calculating a second error location polynomial using the calculated syndromes;

performing a chien search using the second error location polynomial; and

correcting an error of the received data according to a result of the chien search,

wherein the calculating a second error location polynomial comprises performing a plurality of calculation loops, and

wherein the performing a plurality of calculation loops is performed with respect to each of the calculated syndromes.

10. The operation method of claim 7, wherein when the calculating a first error location polynomial is terminated, the calculated syndromes are stored in a buffer.

11. The operation method of claim 10, wherein the performing the error correction in a full mode comprises:

reading the syndromes from the buffer;

calculating a second error location polynomial using the read syndromes;

performing a chien search using the second error location polynomial; and

correcting an error of the received data according to a result of the chien search,

wherein the calculating the second error location polynomial comprises performing a plurality of calculation loops, and

wherein the performing a plurality of calculation loops is performed with respect to each of the calculated syndromes.

12. The operation method of claim 7, further comprising:

storing in the buffer at least one of the syndromes that is not used in the performing a plurality of calculation loops and the first error location polynomial in response to the calculating a first error location polynomial being terminated.

13. The an operation method of claim 12, wherein the performing the error correction in the full mode comprises:

reading the at least one of the syndromes that is not used and the first error location polynomial from the buffer;

calculating a second error location polynomial using the at least one of the syndromes unused and the first error location polynomial;

performing a chien search using the second error location polynomial; and

correcting an error of the received data according to a result of the chien search,

wherein the calculating the second error location polynomial comprises performing a plurality of calculation loops, and

wherein the performing a plurality of calculation loops are terminated after performing the plurality of calculation loops with respect to each of the at least one of the syndromes that is not used.

14. An error correction decoder configured to correct an error of data read from a nonvolatile memory comprising:

a syndrome calculation unit configured to receive data and calculate syndromes based on the received data;

a key equation solving unit configured to receive the syndromes and calculate an error location polynomial based on the received syndromes by selecting different ones of the syndromes and repeating an error location polynomial calculation loop until either one of (1) that the error location polynomial calculation loop is performed with respect to a last one of the syndromes or that a stop condition of the error location polynomial calculation loop for an early termination is satisfied in a simplified mode, and store information about the error location polynomial calculation loop, or (2) that the error location polynomial calculation loop is performed with respect to a last one of the syndromes in a full mode based on the information, the simplified mode being a mode in which a portion of a process of an error correction is omitted and being a subset of the full mode;

a chien search unit configured to receive the error location polynomial and generate error location information by performing a chien search based on the received error location polynomial;

an error correction unit configured to receive the error location information and correct an error of the received data based on the received error location information; and

a control unit configured to select one of the simplified mode and the full mode.

15. The error correction decoder of claim 14, wherein the control unit is configured to initially select the simplified mode, and select the full mode in response to the error correction unit failing to correct the error of the received data in the simplified mode.

16. An error correction method, comprising:

receiving data;

performing an error correction with respect to the received data in a simplified mode, the simplified mode being a mode in which a portion of a process of the error correction is omitted, the performing an error correction in a simplified mode including,

calculating syndromes based on the received data,

performing a calculation loop of calculating a first error location polynomial with respect to a selected one of the syndromes,

repeating the performing a calculation loop until a number of times that a selected one of the syndromes belongs to the first error location polynomial of a previous calculation loop reaches a threshold number to estimate a first error count,

performing a chien search based on the first error location polynomial to detect a second error count, and

storing information about the error correction in the simplified mode in a buffer;

performing the error correction of the received data in a full mode in response to a determination that the error correction fails in the simplified mode based on the first and second error counts, the simplified mode being a subset of the full mode; and

terminating early the error correction by skipping at least the error correction in the full mode based on the information stored in the buffer in response to a condition indicating successful error correction being satisfied during performing the error correction in the simplified mode.

17. The error correction method of claim 16, wherein the performing an error correction in a full mode includes,

calculating syndromes based on the received data,

performing a calculation loop, the calculation loop including,

calculating a second error location polynomial with respect to a selected one of the syndromes,

calculating a discrepancy based on the selected one of the syndromes and the second error location polynomial of a previous calculation loop, and

renewing the second error location polynomial when the discrepancy has a value other than zero, and

repeating the performing a calculation loop with respect to respective ones of the syndromes.

18. The error correction method of claim 17, further comprising:

storing the syndromes calculated in the error correction in the simplified mode,

wherein the calculating a second error location polynomial calculates the second error location polynomial with respect to each of the stored syndromes by performing the calculation loop included in the performing an error correction in a full mode.

19. The error correction method of claim 17, further comprising:

storing the first error location polynomial and at least one of the syndromes that is not used during the performing an error correction in a simplified mode,

wherein the calculating a second error location polynomial calculates the second error location polynomial of the error correction in the full mode using the first error location polynomial and at least one of the syndromes unused during the performing an error correction in a simplified mode.