ERROR CORRECTION MECHANISMS FOR FLASH MEMORIES

• US 20110239094A1
• Filed: 03/29/2010
• Published: 09/29/2011
• Est. Priority Date: 03/29/2010
• Status: Active Grant

• Current Assignee: SK Hynix NAND Product Solutions Corporation (SK Hynix Inc.)
• Original Assignee: Intel Corporation
• Inventors: Kwok, Zion S., Man, Chun Fung Kitter
• Granted Patent: US 8,433,985 B2
• Time in Patent Office: Days
• US Class Current: 714/782
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10
• CPC Class Codes: G11C 2029/0411 Online error correction
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey 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/158 Finite field arithmetic processing

Abstract

Methods and apparatuses for Bose-Chaudhuri-Hocquenghem (BCH) decoding utilizing Berlekamp-Massey Algorithm (BMA) and Chien Search. The BMA may utilize one or more of a scalable semi-parallel shared multiplier array, a conditional q-ary inversionaless BMA and/or a conditional binary Inversionless BMA. The Chien Search may be accomplished utilizing a non-rectangular multiplier array.

Claims

1. A method comprising:

receiving a syndrome corresponding to a codeword of data;

indicating that there is no error in the codeword if the syndrome is zero;

indicating an error in the codeword if the syndrome is non-zero;

generating an error location polynomial for the codeword based on the syndrome utilizing at least a conditional Berlekamp-Massey Algorithm (BMA);

analyzing the error location polynomial to determine bit error locations;

correcting bit errors in the codeword as indicated by the bit error locations; and

storing the codeword with the corrected bits.

2. The method of claim 1 wherein analyzing the error location polynomial to determine bit error locations comprises performing a Chien Search utilizing a non-rectangular multiplier array.

3. The method of claim 2 wherein the non-rectangular multiplier array comprises a rectangular multiplier array with functional flexibility.

4. The method of claim 2 wherein the non-rectangular multiplier array comprises a folding multiplier array.

5. The method of claim 1 wherein the BMA comprises at least computation of a conditional q-ary Inversionless BMA operation.

6. The method of claim 1 wherein the BMA comprises at least computation of a conditional binary Inversionless BMA operation.

7. The method of claim 1 wherein the BMA comprises at least use of a configurable semi-parallel shared multiplier architecture.

8. The method of claim 7 wherein the configurable semi-parallel shared multiplier architecture comprises a plurality of multiplier circuits receiving as a first input a selected one of a previous discrepancy, a current discrepancy value, and a partial syndrome value and receiving as a second input a selected one of an error locator polynomial coefficient value and an auxiliary polynomial coefficient value.

9. A system comprising:

a syndrome calculator coupled to receive a codeword from a memory device, the syndrome calculator to calculate a syndrome for the codeword, the syndrome to indicate whether the codeword includes an error;

Berlekamp-Massey Algorithm (BMA) circuitry coupled to receive the syndrome, the BMA circuitry to generate an error locator polynomial corresponding to the syndrome, wherein the BMA circuitry performs at least one conditional operation based, at least in part on a current discrepancy value;

Chien Search circuitry coupled to receive the error locator polynomial, the Chien Search circuitry to generate bit error locations based on the error locator polynomial; and

a codeword buffer to store the codeword, the codeword buffer coupled to receive the bit error locations and to correct errors in the codeword, if any, based at least on the bit error locations.

10. The system of claim 9 wherein the Chien Search circuitry utilizes a non-rectangular multiplier array.

11. The system of claim 10 wherein the non-rectangular multiplier array comprises a rectangular multiplier array with functional flexibility.

12. The system of claim 10 wherein the non-rectangular multiplier array comprises a folding multiplier array.

13. The system of claim 9 wherein the BMA circuitry performs at least computation of a conditional q-ary Inversionless BMA operation.

14. The system of claim 9 wherein the BMA circuitry performs at least computation of a conditional binary Inversionless BMA operation.

15. The system of claim 9 wherein the BMA circuitry utilizes at least a configurable semi-parallel shared multiplier architecture.

16. An apparatus comprising:

an encoder coupled to receive data to be stored, the encoder to generate a codeword based on the received data;

a storage device coupled with the encoder, the storage device to store the codeword;

a codeword buffer coupled to receive the codeword in response to the codeword being read from the storage device, the codeword buffer to store the codeword after it is read from the storage device;

a syndrome calculator coupled to the storage device to receive the codeword from the storage c device, the syndrome calculator to calculate a syndrome for the codeword, the syndrome to indicate whether the codeword includes an error;

Berlekamp-Massey Algorithm (BMA) circuitry coupled to the syndrome calculator, the BMA circuitry to generate an error locator polynomial corresponding to the syndrome, wherein the BMA circuitry performs at least one conditional operation based, at least in part on a current discrepancy value; and

Chien Search circuitry coupled to the BMA circuitry to receive the error locator polynomial, the Chien Search circuitry to generate bit error locations based on the error locator polynomial, the Chien Search circuitry also coupled with the codeword buffer to provide the bit error locations to the codeword buffer;

wherein the codeword buffer receives the bit error locations to correct errors in the codeword, if any, based at least on the bit error locations.

17. The apparatus of claim 16 wherein the Chien Search circuitry utilizes a non-rectangular multiplier array.

18. The apparatus of claim 17 wherein the non-rectangular multiplier array comprises a rectangular multiplier array with functional flexibility.

19. The apparatus of claim 17 wherein the non-rectangular multiplier array comprises a folding multiplier array.

20. The apparatus of claim 16 wherein the BMA circuitry performs at least computation of a conditional q-ary Inversionless BMA operation.

21. The apparatus of claim 16 wherein the BMA circuitry performs at least computation of a conditional binary Inversionless BMA operation.

22. The apparatus of claim 16 wherein the BMA circuitry utilizes at least a configurable semi-parallel shared multiplier architecture.

23. A system comprising:

a syndrome calculator coupled to receive a codeword from a memory device, the syndrome calculator to calculate a syndrome for the codeword, the syndrome to indicate whether the codeword includes an error;

Berlekamp-Massey Algorithm (BMA) circuitry coupled to receive the syndrome, the BMA circuitry to generate an error locator polynomial corresponding to the syndrome;

Chien Search circuitry coupled to receive the error locator polynomial, the Chien Search circuitry to generate bit error locations based on the error locator polynomial wherein the Chien Search circuitry utilizes a non-rectangular multiplier array; and

a codeword buffer to store the codeword, the codeword buffer coupled to receive the bit error locations and to correct errors in the codeword, if any, based at least on the bit error locations.

24. The system of claim 23 wherein the non-rectangular multiplier array comprises a rectangular multiplier array with functional flexibility.

25. The system of claim 23 wherein the non-rectangular multiplier array comprises a folding multiplier array.

26. The system of claim 23 wherein the BMA circuitry performs at least computation of a conditional q-ary Inversionless BMA operation.

27. The system of claim 23 wherein the BMA circuitry performs at least computation of a conditional binary Inversionless BMA operation.

28. The system of claim 23 wherein the BMA circuitry utilizes at least a configurable semi-parallel shared multiplier architecture.