Systems and methods for decoding data for solid-state memory

• US 9,081,701 B1
• Filed: 03/15/2013
• Issued: 07/14/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Ip Gem Group, LLC
• Original Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Inventors: Northcott, Philip Lyon, Graumann, Peter, Bates, Stephen
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US13/844,474
• Time in Patent Office: 851 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD

Abstract

Apparatus and methods provide relatively low uncorrectable bit error rates, low write amplification, long life, fast and efficient retrieval, and efficient storage density such that a solid-state drive (SSD) can be reliably implemented using various types of memory cells, including relatively inexpensive multi-level cell flash. One embodiment intelligently coordinates remapping of bad blocks with error correction code control, which eliminates the tables used to avoid bad blocks.

Claims

1. An electronically-implemented method of retrieving user data, the method comprising:

receiving a logical address and a read request for the user data;

determining a journaling cell slot, a first page stripe, and a page grid corresponding to the logical address, wherein the page grid comprises a plurality of related page stripes including the first page stripe, wherein the page stripes of the page grid are related by having a grid error correction code having codewords spanning the page grid, wherein a page stripe of the plurality of related page stripes comprises a plurality of pages or integer fractions thereof, wherein the journaling cell slot is allocated to the first page stripe;

retrieving information indicative of a capacity of journaling cell slots per page stripe of the page grid, wherein the capacity is zero for at least a second page stripe of the page grid;

identifying data corresponding to the at least second page stripe as identically zero for a decoder of the grid error correction code;

retrieving data from a set of page stripes of the page grid having non-zero journaling cell slot capacity, wherein page stripes having non-zero journaling cell slot capacity each have a primary error correction code within the page stripe;

performing error correction within the page stripes of the page grid having non-zero journaling cell slot capacity;

decoding the grid error correction code to correct errors throughout the page grid to generate a first corrected first page stripe;

performing primary error correction on the first corrected first page stripe to generate a second corrected first page stripe; and

providing the user data from the journaling cell slot of the second corrected first page stripe.

2. The method of claim 1, further comprising iterating the following until at least the first corrected page stripe decodes successfully or until a stopping criterion is reached:

performing error correction within page stripes of the page grid having non-zero journaling cell slot capacity; and

decoding the grid error correction code to correct errors throughout the page grid to generate corrected or partially corrected page stripes.

3. The method of claim 1, further comprising arranging primary corrected data from the page stripes of the page grid into grid ECC codewords for decoding of the grid error correction code.

4. The method of claim 1, further comprising marking as erasures, the data of primary codewords that were not successfully decoded, for performance of grid error correction.

5. The method of claim 1, wherein if a page stripe of the page grid is determined to have failed, grid codeword symbols corresponding to locations in the failed page stripe are marked as erasures for the purpose of grid error correction.

6. The method of claim 1, further comprising:

at least prior to retrieving data from the set of page stripes of the page grid having non-zero journaling cell slot capacity;

reading data stored in the journaling cell slot and a corresponding primary error correction code, wherein the primary error correction code is protective of errors within the first page stripe; and

attempting to perform a first error correction decoding on at least a user data portion of the read data using only the primary error correction code, wherein the attempt results in a failure to error correction decode the user data portion correctly.

7. The method of claim 1, further comprising:

associating the logical address with a page grid address and a grid journaling cell slot number, the page grid address identifying a page grid, the page grid comprising a plurality of page stripes, wherein each page stripe of the page grid is associated with a page stripe number, wherein page stripes of the page grid are programmed in a predetermined order;

computing which page stripe number for the page grid corresponds to the grid journaling cell slot number by examination of journaling cell slot capacities of at least a portion of the page strips of the page grid and the predetermined order in which the page stripes are programmed, wherein the page stripes of the page grid are each associated with an ECC gear selected from a set of ECC gears, wherein at least a first page stripe is associated with a first gear such that the first page stripe has a first non-zero journaling slot capacity, wherein at least a second page stripe is associated with a second gear such that the second page stripe has a second non-zero journaling slot capacity different from the first non-zero journaling slot capacity, and wherein at least a third page stripe is associated with gear zero such that the third page stripe has a zero journaling slot capacity;

computing a local journaling cell slot number based at least partly on the grid journaling cell slot number, the journaling cell slot capacities of at least a portion of the page strips of the page grid, and the predetermined order in which the page stripes are programmed, wherein local journaling cell slot numbers uniquely identify journaling cell slots within the page stripe;

generating a first offset based at least partly on the page stripe number;

generating a second offset based at least partly on the local journaling cell slot number and a size associated with the journaling cell slots; and

generating a first physical address for the logical address by combining a second physical address associated with the page grid number, the first offset, and the second offset.

8. The method of claim 7, wherein associating the logical address with the page grid number and the grid journaling cell slot number is performed with reference to a lookup table.

9. The method of claim 7, wherein the first offset is generated by multiplying the page stripe number with a first predetermined number, wherein the second offset is generated by multiplying the local journaling cell slot number by a second predetermined number.

10. The method of claim 7, further comprising generating the first physical address by adding the second physical address, the first offset, and the second offset.

11. An apparatus for retrieving user data, the apparatus comprising:

a circuit configured to;

receive a logical address and a read request for the user data;

determine a journaling cell slot, a first page stripe, and a page grid corresponding to the logical address, wherein the page grid comprises a plurality of related page stripes including the first page stripe, wherein the page stripes of the page grid are related by having a grid error correction code having codewords spanning the page grid, wherein a page stripe of the plurality of related page stripes comprises a plurality of pages or integer fractions thereof, wherein the journaling cell slot is allocated to the first page stripe;

retrieve information indicative of a capacity of journaling cell slots per page stripe of the page grid, wherein the capacity is zero for at least a second page stripe of the page grid;

identify data corresponding to the at least second page stripe as identically zero for a decoder of the grid error correction code;

retrieve data from a set of page stripes of the page grid having non-zero journaling cell slot capacity, wherein page stripes having non-zero journaling cell slot capacity each have a primary error correction code within the page stripe; and

an ECC encoder/decoder configured to;

perform error correction within the page stripes of the page grid having non-zero journaling cell slot capacity;

decode the grid error correction code to correct errors throughout the page grid to generate a first corrected first page stripe;

perform primary error correction on the first corrected first page stripe to generate a second corrected first page stripe; and

provide the user data from the journaling cell slot of the second corrected first page stripe.

12. The apparatus of claim 11, wherein the ECC encoder/decoder is further configured to iterate the following until at least the first corrected page stripe decodes successfully or until a stopping criterion is reached:

performance of error correction within page stripes of the page grid having non-zero journaling cell slot capacity; and

decoding of the grid error correction code to correct errors throughout the page grid to generate corrected or partially corrected page stripes.

13. The apparatus of claim 11, wherein the ECC encoder/decoder is further configured to arrange primary corrected data from the page stripes of the page grid into grid ECC codewords for decoding of the grid error correction code.

14. The apparatus of claim 11, wherein the ECC encoder/decoder is further configured to mark as erasures, the data of primary codewords that were not successfully decoded, for performance of grid error correction.

15. The apparatus of claim 11, wherein the ECC encoder/decoder is further configured to mark as erasures, for the purpose of grid error correction, grid codeword symbols corresponding to locations in the failed page stripe when a page stripe of the page grid is determined to have failed.

16. The apparatus of claim 11, wherein:

the circuit is configured to, at least prior to retrieving data from the set of page stripes of the page grid having non-zero journaling cell slot capacity, read data stored in the journaling cell slot and a corresponding primary error correction code, wherein the primary error correction code is protective of errors within the first page stripe; and

the ECC encoder/decoder is configured to, at least prior to retrieving data from the set of page stripes of the page grid having non-zero journaling cell slot capacity, attempt to perform a first error correction decoding on at least a user data portion of the read data using only the primary error correction code, wherein the attempt results in a failure to error correction decode the user data portion correctly.

17. The apparatus of claim 11, wherein the circuit is further configured to:

associate the logical address with a page grid address and a grid journaling cell slot number, the page grid address identifying a page grid, the page grid comprising a plurality of page stripes, wherein each page stripe of the page grid is associated with a page stripe number, wherein page stripes of the page grid are programmed in a predetermined order;

compute which page stripe number for the page grid corresponds to the grid journaling cell slot number by examination of journaling cell slot capacities of at least a portion of the page strips of the page grid and the predetermined order in which the page stripes are programmed, wherein the page stripes of the page grid are each associated with an ECC gear selected from a set of ECC gears, wherein at least a first page stripe is associated with a first gear such that the first page stripe has a first non-zero journaling slot capacity, wherein at least a second page stripe is associated with a second gear such that the second page stripe has a second non-zero journaling slot capacity different from the first non-zero journaling slot capacity, and wherein at least a third page stripe is associated with gear zero such that the third page stripe has a zero journaling slot capacity;

compute a local journaling cell slot number based at least partly on the grid journaling cell slot number, the journaling cell slot capacities of at least a portion of the page strips of the page grid, and the predetermined order in which the page stripes are programmed, wherein local journaling cell slot numbers uniquely identify journaling cell slots within the page stripe;

generate a first offset based at least partly on the page stripe number;

generate a second offset based at least partly on the local journaling cell slot number and a size associated with the journaling cell slots; and

generate a first physical address for the logical address by combining a second physical address associated with the page grid number, the first offset, and the second offset.

18. The apparatus of claim 17, wherein the circuit is configured to associate the logical address with the page grid number and the grid journaling cell slot number with reference to a lookup table.

19. The apparatus of claim 17, wherein the circuit is configured to generate the first offset by multiplying the page stripe number with a first predetermined number, wherein the first circuit is configured to generate the second offset by multiplying the local journaling cell slot number by a second predetermined number.

20. The apparatus of claim 17, further the circuit is configured to generate the first physical address by adding the second physical address, the first offset, and the second offset.