# US 8,788,910 B1 · Systems and methods for low latency, high reliability error correction in a flash drive

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,788,910 B1
- Document ID: US8788910B1
- Status: Granted
- Kind: B1
- Application number: 13/477,595
- Filed: 2012-05-22
- Granted: 2014-07-22
- Earliest claimed: 2012-05-22
- Assignees: PMC-Sierra, Inc.
- Applicants: Philip L. Northcott
- Inventors: Philip L. Northcott
- Web page: https://patentgrep.com/patent/US8788910B1

## CPC

- G06F 11/1012: {using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence)}
- G06F 11/108: {Parity data distribution in semiconductor storages, e.g. in SSD}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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 implemented using relatively inexpensive MLC Flash for an enterprise storage application.

## Claims

### Claim 1

A method of decoding data with low latency, the method comprising:
receiving a request for data stored in at least one of a plurality of flash memory devices;
identifying a page stripe that includes the requested data, wherein the page stripe comprises a grouping of one or more equally-sized flash pages or integer fractions of flash pages, wherein each page or each integer fraction of the page stripe contains primary parity symbols for error correction of data stored within the page or integer fraction, and wherein the pages or integer fractions of the page stripe contain secondary parity symbols for error correction of data stored throughout the page stripe;
determining a portion of the page stripe that contains an integer number of a first set of primary codewords containing the requested data and associated primary parity symbols such that retrieval and decoding of the requested data is performed with a first amount of latency;
retrieving from flash memory the first set of primary codewords containing the requested data;
performing error correction on the first set of primary codewords to determine if the raw requested data contains errors and if the errors, if any, are correctable, to generate first corrected requested data;
releasing the first corrected requested data based at least partly on a determination that the first corrected requested data has been decoded with a likelihood of error below a predetermined acceptable uncorrectable bit error rate (aUBER) when the first corrected requested data cannot be considered to be error free to within the aUBER, performing the following:
reading the page stripe containing the requested data such that a second set of primary codewords is retrieved, wherein reading of page stripe is performed with a second latency longer than the first latency;
performing error correction on the second set of primary codewords of the page stripe to generate an updated page stripe;
interleaving data from the updated page stripe to arrange secondary codewords;
performing error correction on the secondary codewords to generate corrected secondary codewords, wherein execution of error correction on the secondary codewords is not performed in parallel with execution of error correction on the primary codewords;
de-interleaving the corrected secondary codewords to generate a further updated page stripe having an updated second set of primary codewords;
performing error correction on at least a portion of the updated second set of primary codewords to generate updated corrected requested data; and
releasing the second corrected requested data based at least partly on a determination that the likelihood of the requested data containing an error is less than a predetermined acceptable failure rate;
wherein at least performing error correction is performed by an integrated circuit;
wherein at least performing error correction is performed concurrently with a read operation for an end user.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first set of primary codewords comprises a minimum set of primary codewords containing the requested data.

### Claim 3 (depends on 1)

The method of claim 1, wherein each page of the page stripe is from a different integrated circuit die or plane of the plurality of flash memory devices.

### Claim 4 (depends on 1)

The method of claim 1, further comprising releasing the first corrected requested data based at least partly on the determination that: (a) the first corrected requested data has been decoded without error and (b) a number of bits corrected in every primary codeword containing requested data is less than or equal to a release parameter, wherein the release parameter is equal to a correction capability for the primary codeword minus a safety factor.

### Claim 5 (depends on 1)

The method of claim 1, further comprising releasing the first corrected requested data based at least partly on the determination that (a) the first corrected requested data has been decoded without error, (b) a number of bits corrected in every primary codeword containing requested data is less than or equal to a release parameter, wherein the release parameter is equal to a correction capability for the primary codeword minus a safety factor, and (c) no primary codeword containing requested data contains all zeroes after error correction.

### Claim 6 (depends on 5)

The method of claim 5, wherein the release parameter varies with a selected error correction strength of the primary codewords.

### Claim 7 (depends on 6)

The method of claim 6, wherein the safety factor for the release parameter is selected such that the following is satisfied:
(
2
⁢
⁢
T
⁢
⁢
p
N
⁢
⁢
p
)
·
(
1
T
⁢
⁢
p
⁢
!
)
⁢
·
∏
i
=
1
Tp
-
Qp
-
1
⁢
(
T
⁢
⁢
p
-
i
+
1
N
⁢
⁢
p
)
<
aUBER
,
wherein “!” indicates factorial, Qp corresponds to the release parameter, Tp corresponds to the correction capability of the primary parity symbols of a primary codeword, Np corresponds to the size of a primary codeword, and aUBER corresponds to a predetermined acceptable uncorrected bit error rate.

### Claim 8 (depends on 7)

The method of claim 7, wherein a value for aUBER corresponds to 1E-16.

### Claim 9 (depends on 1)

The method of claim 1, further comprising, when the second corrected data is not released, returning to performing error correction on the page stripe using updated primary parity symbols such that errors are iteratively corrected.

### Claim 10 (depends on 9)

The method of claim 9, further comprising iterating between error correction with primary codewords and error correction with secondary codewords until at least one of the following occurs:
the requested data is released;
no new corrections were made during error correction using primary parity symbols; or
a loop counter associated with iteration has reached a predetermined limit.

### Claim 11 (depends on 9)

The method of claim 9, further comprising:
iterating between error correction with primary codewords and error correction with secondary codewords; and
determining whether or not to increase a strength of error correction for subsequent programming of the page stripe or to retire the page stripe if the page stripe had already been encoded at the page stripe's highest strength of error correction when at least one of the following conditions is true:
a number of corrected bits for the page stripe read exceeds a predetermined threshold for a current strength of error correction; or
a number of iterations exceeds a predetermined threshold.

### Claim 12 (depends on 9)

The method of claim 9, further comprising:
iterating between error correction with primary codewords and error correction with secondary codewords to attempt to correct errors in the page stripe;
when the page stripe is ultimately unsuccessfully corrected via correction of the primary codewords and the secondary codewords, performing the following:
retrieving data from a page grid associated with the page stripe, wherein the retrieved data includes tertiary codewords;
performing error correction using the tertiary codewords; and
increasing a strength of error correction for subsequent programming of the page stripe or retiring of the page stripe if the page stripe had already been encoded at the page stripe's highest strength of error correction based at least partly on performing tertiary error correction of the page grid.

### Claim 13 (depends on 1)

The method of claim 1, wherein performing error correction on the second set of primary codewords further comprises performing error correction on the secondary parity symbols using primary on secondary parity symbols (PoSP).

### Claim 14 (depends on 1)

The method of claim 1, wherein the primary codewords and the secondary codewords comprise Bose, Chaudhuri, and Hocquenghem (BCH) codewords.

### Claim 15 (depends on 1)

The method of claim 1, wherein the secondary codewords are disjoint or at least partially orthogonal to the primary codewords.

### Claim 16 (depends on 1)

The method of claim 1, wherein the flash memory devices comprise multi-level memory cells.

### Claim 17 (depends on 1)

The method of claim 1, further comprising scrambling the data with a pseudo-random pattern prior to ECC encoding, and descrambling the data with a pseudo-random sequence after it has been decoded.

### Claim 18 (depends on 1)

The method of claim 1, wherein each primary codeword is retrieved from a single page and each secondary codeword is retrieved from across the page stripe.

### Claim 19 (depends on 1)

The method of claim 1, further comprising calculating a fingerprint based at least partly on a physical address of a flash page, and comparing the calculated fingerprint to a retrieved fingerprint of the flash page to determine whether or not a correct page was read.

### Claim 20 (depends on 1)

The method of claim 1, further comprising performing the following when decoding via primary codewords and secondary codewords has been unsuccessful:
wherein a page grid comprises the page stripe and other page stripes that are associated with the page stripe to form the page grid, wherein each page of the page grid is from a different integrated circuit die, wherein at least one page stripe has tertiary parity symbols encoded therein such that the page grid contains tertiary codewords, wherein the primary codewords, the secondary codewords, and the tertiary codewords are disjoint or at least partially orthogonal with respect to each other;
reading the other page stripes of the page grid;
error correction decoding the other page stripes of the page grid;
interleaving data from the page grid to arrange tertiary codewords;
performing error correction decoding with parity symbols of the tertiary codewords to correct the tertiary codewords, wherein execution of error correction decoding of the tertiary codewords has greater latency than execution of error correction encoding of the secondary codewords, wherein error correction decoding of the tertiary codewords is not performed in parallel with error correction decoding of the primary codewords or the secondary codewords;
de-interleaving the now corrected tertiary codewords to generate a corrected version of the page grid;
interleaving data from the corrected version of the page grid to generate revised secondary codewords;
error correction decoding the secondary codewords using secondary parity symbols of the secondary codewords;
de-interleaving the now corrected secondary codewords to generate a further updated version of the page grid;
error correction decoding primary codewords of at least a portion of the further updated version of the page grid with the primary parity symbols of the primary codewords of the further updated version of the page grid; and
releasing the newly corrected requested data based at least partly on a determination that the newly corrected requested data has been decoded without error.

### Claim 21 (depends on 20)

The method of claim 20, wherein the primary codewords and the secondary codewords correspond to Bose, Chaudhuri, and Hocquenghem codewords and wherein the tertiary codewords correspond to Reed-Solomon codewords.

### Claim 22 (depends on 20)

The method of claim 20, wherein before performing error correction decoding with parity symbols of the tertiary codewords:
analyzing fingerprints of pages of the page grids to identify a page considered to be more unreliable than other pages; and
marking symbols of the identified page as erasures.

### Claim 23

An apparatus comprising:
a first circuit configured to receive a request for data stored in at least one of a plurality of flash memory devices;
the first circuit configured to identify a page stripe that includes the requested data, wherein the page stripe comprises a grouping of one or more equally-sized flash pages or integer fractions of flash pages, wherein each page or each integer fraction of the page stripe contains primary parity symbols for error correction of data stored within the page or integer fraction, and wherein the pages or integer fractions of the page stripe contain secondary parity symbols for error correction of data stored throughout the page stripe;
the first circuit configured to determine a portion of the page stripe that contains an integer number of a first set of primary codewords containing the requested data and associated primary parity symbols such that retrieval and decoding of the requested data is performed with a first amount of latency;
the first circuit configured to retrieve from flash memory the first set of primary codewords containing the requested data;
a second circuit configured to perform error correction on the first set of primary codewords to determine if the raw requested data contains errors and if the errors, if any, are correctable, to generate first corrected requested data;
the first circuit configured to release the first corrected requested data based at least partly on a determination that the first corrected requested data has been decoded with a likelihood of error below a predetermined acceptable uncorrectable bit error rate (aUBER), and when the first corrected requested data cannot be considered to be error free to within the aUBER:
the first circuit is configured to read the page stripe containing the requested data such that a second set of primary codewords is retrieved, wherein reading of page stripe is performed with a second latency longer than the first latency;
the second circuit is configured to perform error correction on the second set of primary codewords of the page stripe to generate an updated page stripe;
the first circuit is configured to interleave data from the updated page stripe to arrange secondary codewords;
the second circuit is configured to perform error correction on the secondary codewords to generate corrected secondary codewords, wherein execution of error correction on the secondary codewords is not performed in parallel with execution of error correction on the primary codewords;
the first circuit is configured to de-interleave the corrected secondary codewords to generate a further updated page stripe having an updated second set of primary codewords;
the second circuit is configured to perform error correction on at least a portion of the updated second set of primary codewords to generate updated corrected requested data; and
the first circuit is configured to release the second corrected requested data based at least partly on a determination that the likelihood of the requested data containing an error is less than a predetermined acceptable failure rate;
wherein the second circuit is configured to perform error correction concurrently with a read operation for an end user.

### Claim 24 (depends on 23)

The apparatus of claim 23, wherein the first set of primary codewords comprises a minimum set of primary codewords containing the requested data.

### Claim 25 (depends on 23)

The apparatus of claim 23, wherein each page of the page stripe is from a different integrated circuit die or plane of the plurality of flash memory devices.

### Claim 26 (depends on 23)

The apparatus of claim 23, wherein the first circuit is further configured to release the first corrected requested data based at least partly on the determination that: (a) the first corrected requested data has been decoded without error and (b) a number of bits corrected in every primary codeword containing requested data is less than or equal to a release parameter, wherein the release parameter is equal to a correction capability for the primary codeword minus a safety factor.

### Claim 27 (depends on 23)

The apparatus of claim 23, wherein the first circuit is further configured to release the first corrected requested data based at least partly on the determination that (a) the first corrected requested data has been decoded without error, (b) a number of bits corrected in every primary codeword containing requested data is less than or equal to a release parameter, wherein the release parameter is equal to a correction capability for the primary codeword minus a safety factor, and (c) no primary codeword containing requested data contains all zeroes after error correction.

### Claim 28 (depends on 27)

The apparatus of claim 27, wherein the release parameter varies with a selected error correction strength of the primary codewords.

### Claim 29 (depends on 28)

The apparatus of claim 28, wherein the safety factor for the release parameter is selected such that the following is satisfied:
(
2
⁢
⁢
T
⁢
⁢
p
N
⁢
⁢
p
)
·
(
1
T
⁢
⁢
p
⁢
!
)
⁢
·
∏
i
=
1
Tp
-
Qp
-
1
⁢
(
T
⁢
⁢
p
-
i
+
1
N
⁢
⁢
p
)
<
aUBER
,
wherein “!” indicates factorial, Qp corresponds to the release parameter, Tp corresponds to the correction capability of the primary parity symbols of a primary codeword, Np corresponds to the size of a primary codeword, and aUBER corresponds to a predetermined acceptable uncorrected bit error rate.

### Claim 30 (depends on 29)

The apparatus of claim 29, wherein a value for aUBER corresponds to 1E-16.

### Claim 31 (depends on 23)

The apparatus of claim 23, wherein the first circuit is further configured to, when the second corrected data is not released, return to perform error correction on the page stripe with updated primary parity symbols such that errors are iteratively corrected.

### Claim 32 (depends on 31)

The apparatus of claim 31, wherein the second circuit is further configured to iterate between error correction with primary codewords and error correction with secondary codewords until at least one of the following occurs:
the requested data is released;
no new corrections were made during error correction using primary parity symbols; or
a loop counter associated with iteration has reached a predetermined limit.

### Claim 33 (depends on 31)

The apparatus of claim 31, wherein:
the second circuit is further configured to iterate between error correction with primary codewords and error correction with secondary codewords; and
the first circuit is further configured to determine whether or not to increase a strength of error correction for subsequent programming of the page stripe or to retire the page stripe if the page stripe had already been encoded at the page stripe's highest strength of error correction when at least one of the following conditions is true:
a number of corrected bits for the page stripe read exceeds a predetermined threshold for a current strength of error correction; or
a number of iterations exceeds a predetermined threshold.

### Claim 34 (depends on 31)

The apparatus of claim 31, wherein:
the second circuit is further configured to iterate between error correction with primary codewords and error correction with secondary codewords to attempt to correct errors in the page stripe;
when the page stripe is ultimately unsuccessfully corrected via correction of the primary codewords and the secondary codewords:
the first circuit is configured to retrieve data from a page grid associated with the page stripe, wherein the retrieved data includes tertiary codewords;
the second circuit is configured to perform error correction with the tertiary codewords; and
the first circuit is configured to increase a strength of error correction for subsequent programming of the page stripe or to retire of the page stripe if the page stripe had already been encoded at the page stripe's highest strength of error correction based at least partly on performance of tertiary error correction of the page grid.

### Claim 35 (depends on 23)

The apparatus of claim 23, wherein the second circuit is further configured to perform error correction on the secondary parity symbols using primary on secondary parity symbols (PoSP).

### Claim 36 (depends on 23)

The apparatus of claim 23, wherein the primary codewords and the secondary codewords comprise Bose, Chaudhuri, and Hocquenghem (BCH) codewords.

### Claim 37 (depends on 23)

The apparatus of claim 23, wherein the secondary codewords are disjoint or at least partially orthogonal to the primary codewords.

### Claim 38 (depends on 23)

The apparatus of claim 23, wherein the flash memory devices comprise multi-level memory cells.

### Claim 39 (depends on 23)

The apparatus of claim 23, wherein the first circuit is further configured to scramble the data with a pseudo-random pattern prior to ECC encoding, and to descramble the data with a pseudo-random sequence after it has been decoded.

### Claim 40 (depends on 23)

The apparatus of claim 23, wherein each primary codeword is retrieved from a single page and each secondary codeword is retrieved from across the page stripe.

### Claim 41 (depends on 23)

The apparatus of claim 23, wherein the first circuit is further configured to calculate a fingerprint based at least partly on a physical address of a flash page, and compare the calculated fingerprint to a retrieved fingerprint of the flash page to determine whether or not a correct page was read.

### Claim 42 (depends on 23)

The apparatus of claim 23, wherein a page grid comprises the page stripe and other page stripes that are associated with the page stripe to form the page grid, wherein each page of the page grid is from a different integrated circuit die, wherein at least one page stripe has tertiary parity symbols encoded therein such that the page grid contains tertiary codewords, wherein the primary codewords, the secondary codewords, and the tertiary codewords are disjoint or at least partially orthogonal with respect to each other, wherein, when decoding via primary codewords and secondary codewords has been unsuccessful:
the first circuit is configured to read the other page stripes of the page grid;
the second circuit is configured to error correction decode the other page stripes of the page grid;
the first circuit is configured to interleave data from the page grid to arrange tertiary codewords;
the second circuit is configured to perform error correction decoding with parity symbols of the tertiary codewords to correct the tertiary codewords, wherein execution of error correction decoding of the tertiary codewords has greater latency than execution of error correction encoding of the secondary codewords, wherein error correction decoding of the tertiary codewords is not performed in parallel with error correction decoding of the primary codewords or the secondary codewords;
the first circuit is configured to de-interleave the now corrected tertiary codewords to generate a corrected version of the page grid;
the first circuit is configured to interleave data from the corrected version of the page grid to generate revised secondary codewords;
the second circuit is configured to error correction decode the secondary codewords with secondary parity symbols of the secondary codewords;
the first circuit is configured to de-interleave the now corrected secondary codewords to generate a further updated version of the page grid;
the second circuit is configured to error correction decode primary codewords of at least a portion of the further updated version of the page grid with the primary parity symbols of the primary codewords of the further updated version of the page grid; and
the first circuit is configured to release the newly corrected requested data based at least partly on a determination that the newly corrected requested data has been decoded without error.

### Claim 43 (depends on 42)

The apparatus of claim 42, wherein the primary codewords and the secondary codewords correspond to Bose, Chaudhuri, and Hocquenghem codewords and wherein the tertiary codewords correspond to Reed-Solomon codewords.

### Claim 44 (depends on 42)

The apparatus of claim 42, wherein the first circuit is configured to, before the second circuit performs error correction decoding with parity symbols of the tertiary codewords:
analyze fingerprints of pages of the page grids to identify a page considered to be more unreliable than other pages; and
mark symbols of the identified page as erasures.

### Claim 45

An apparatus for decoding data with low latency, the apparatus comprising:
a means for receiving a request for data stored in at least one of a plurality of flash memory devices;
a means for identifying a page stripe that includes the requested data, wherein the page stripe comprises a grouping of one or more equally-sized flash pages or integer fractions of flash pages, wherein each page or each integer fraction of the page stripe contains primary parity symbols for error correction of data stored within the page or integer fraction, and wherein the pages or integer fractions of the page stripe contain secondary parity symbols for error correction of data stored throughout the page stripe;
a means for determining a portion of the page stripe that contains an integer number of a first set of primary codewords containing the requested data and associated primary parity symbols such that retrieval and decoding of the requested data is performed with a first amount of latency;
a means for retrieving from flash memory the first set of primary codewords containing the requested data;
a means for performing error correction on the first set of primary codewords to determine if the raw requested data contains errors and if the errors, if any, are correctable, to generate first corrected requested data;
a means for interleaving;
a means for de-interleaving;
a means for releasing the first corrected requested data based at least partly on a determination that the first corrected requested data has been decoded with a likelihood of error below a predetermined acceptable uncorrectable bit error rate (aUBER) when the first corrected requested data cannot be considered to be error free to within the aUBER:
the retrieving means is configured to read the page stripe containing the requested data such that a second set of primary codewords is retrieved, wherein reading of page stripe is performed with a second latency longer than the first latency;
the error correction means is configured to perform error correction on the second set of primary codewords of the page stripe to generate an updated page stripe;
the interleaving means is configured to interleave data from the updated page stripe to arrange secondary codewords;
the error correction means configured to perform error correction on the secondary codewords to generate corrected secondary codewords, wherein execution of error correction on the secondary codewords is not performed in parallel with execution of error correction on the primary codewords;
the de-interleaving means is configured to de-interleave the corrected secondary codewords to generate a further updated page stripe having an updated second set of primary codewords;
the error correction means configured to perform error correction on at least a portion of the updated second set of primary codewords to generate updated corrected requested data; and
the releasing means configured to release the second corrected requested data based at least partly on a determination that the likelihood of the requested data containing an error is less than a predetermined acceptable failure rate;
wherein at least performing error correction is performed concurrently with a read operation for an end user.

### Claim 46 (depends on 45)

The apparatus of claim 45, wherein the first set of primary codewords comprises a minimum set of primary codewords containing the requested data.

### Claim 47 (depends on 45)

The apparatus of claim 45, wherein each page of the page stripe is from a different integrated circuit die or plane of the plurality of flash memory devices.

### Claim 48 (depends on 45)

The apparatus of claim 45, wherein the releasing means is further configured to release the first corrected requested data based at least partly on the determination that: (a) the first corrected requested data has been decoded without error and (b) a number of bits corrected in every primary codeword containing requested data is less than or equal to a release parameter, wherein the release parameter is equal to a correction capability for the primary codeword minus a safety factor.

### Claim 49 (depends on 45)

The apparatus of claim 45, wherein the releasing means is further configured to release the first corrected requested data based at least partly on the determination that (a) the first corrected requested data has been decoded without error, (b) a number of bits corrected in every primary codeword containing requested data is less than or equal to a release parameter, wherein the release parameter is equal to a correction capability for the primary codeword minus a safety factor, and (c) no primary codeword containing requested data contains all zeroes after error correction.

### Claim 50 (depends on 49)

The apparatus of claim 49, wherein the release parameter varies with a selected error correction strength of the primary codewords.

### Claim 51 (depends on 50)

The apparatus of claim 50, wherein the safety factor for the release parameter is selected such that the following is satisfied:
(
2
⁢
⁢
T
⁢
⁢
p
N
⁢
⁢
p
)
·
(
1
T
⁢
⁢
p
⁢
!
)
⁢
·
∏
i
=
1
Tp
-
Qp
-
1
⁢
(
T
⁢
⁢
p
-
i
+
1
N
⁢
⁢
p
)
<
aUBER
,
wherein “!” indicates factorial, Qp corresponds to the release parameter, Tp corresponds to the correction capability of the primary parity symbols of a primary codeword, Np corresponds to the size of a primary codeword, and aUBER corresponds to a predetermined acceptable uncorrected bit error rate.

### Claim 52 (depends on 51)

The apparatus of claim 51, wherein a value for aUBER corresponds to 1E-16.

### Claim 53 (depends on 45)

The apparatus of claim 45, wherein the error correction means is further configured to, when the second corrected data is not released, return to perform error correction on the page stripe using updated primary parity symbols such that errors are iteratively corrected.

### Claim 54 (depends on 53)

The apparatus of claim 53, wherein the error correction means is further configured to iterate between error correction with primary codewords and error correction with secondary codewords until at least one of the following occurs:
the requested data is released;
no new corrections were made during error correction using primary parity symbols; or
a loop counter associated with iteration has reached a predetermined limit.

### Claim 55 (depends on 53)

The apparatus of claim 53, wherein:
the error correction means is further configured to iterate between error correction with primary codewords and error correction with secondary codewords;
further comprising means for determining whether or not to increase a strength of error correction for subsequent programming of the page stripe or to retire the page stripe if the page stripe had already been encoded at the page stripe's highest strength of error correction when at least one of the following conditions is true:
a number of corrected bits for the page stripe read exceeds a predetermined threshold for a current strength of error correction; or
a number of iterations exceeds a predetermined threshold.

### Claim 56 (depends on 53)

The apparatus of claim 53, wherein:
the error correction means is further configured to iterate between error correction with primary codewords and error correction with secondary codewords to attempt to correct errors in the page stripe;
when the page stripe is ultimately unsuccessfully corrected via correction of the primary codewords and the secondary codewords:
the retrieving means is further configured to retrieve data from a page grid associated with the page stripe, wherein the retrieved data includes tertiary codewords;
the error correction means is further configured to perform error correction using the tertiary codewords; and
a means for increasing strength is configured to increase a strength of error correction for subsequent programming of the page stripe or retiring of the page stripe if the page stripe had already been encoded at the page stripe's highest strength of error correction based at least partly on performing tertiary error correction of the page grid.

### Claim 57 (depends on 45)

The apparatus of claim 45, wherein the error correction means is further configured to perform error correction on the second set of primary codewords further comprises performing error correction on the secondary parity symbols using primary on secondary parity symbols (PoSP).

### Claim 58 (depends on 45)

The apparatus of claim 45, wherein the primary codewords and the secondary codewords comprise Bose, Chaudhuri, and Hocquenghem (BCH) codewords.

### Claim 59 (depends on 45)

The apparatus of claim 45, wherein the secondary codewords are disjoint or at least partially orthogonal to the primary codewords.

### Claim 60 (depends on 45)

The apparatus of claim 45, wherein the flash memory devices comprise multi-level memory cells.

### Claim 61 (depends on 45)

The apparatus of claim 45, further comprising means for scrambling the data with a pseudo-random pattern prior to ECC encoding, and descrambling the data with a pseudo-random sequence after it has been decoded.

### Claim 62 (depends on 45)

The apparatus of claim 45, wherein each primary codeword is retrieved from a single page and each secondary codeword is retrieved from across the page stripe.

### Claim 63 (depends on 45)

The apparatus of claim 45, further comprising means for calculating a fingerprint based at least partly on a physical address of a flash page, and means for comparing the calculated fingerprint to a retrieved fingerprint of the flash page to determine whether or not a correct page was read.

### Claim 64 (depends on 45)

The apparatus of claim 45, wherein a page grid comprises the page stripe and other page stripes that are associated with the page stripe to form the page grid, wherein each page of the page grid is from a different integrated circuit die, wherein at least one page stripe has tertiary parity symbols encoded therein such that the page grid contains tertiary codewords, wherein the primary codewords, the secondary codewords, and the tertiary codewords are disjoint or at least partially orthogonal with respect to each other, wherein, when decoding via primary codewords and secondary codewords has been unsuccessful:
the retrieving means is further configured to read the other page stripes of the page grid;
the error correction means is further configured to error correction decod the other page stripes of the page grid;
the interleaving means is further configured to interleave data from the page grid to arrange tertiary codewords;
the error correction means is further configured to perform error correction decoding with parity symbols of the tertiary codewords to correct the tertiary codewords, wherein execution of error correction decoding of the tertiary codewords has greater latency than execution of error correction encoding of the secondary codewords, wherein error correction decoding of the tertiary codewords is not performed in parallel with error correction decoding of the primary codewords or the secondary codewords;
the de-interleaving means is further configured to de-interleave the now corrected tertiary codewords to generate a corrected version of the page grid;
the interleaving means is further configured to interleave data from the corrected version of the page grid to generate revised secondary codewords;
the error correction decoding means is further configured to error correction decode the secondary codewords using secondary parity symbols of the secondary codewords;
the de-interleaving means is further configured to de-interleave the now corrected secondary codewords to generate a further updated version of the page grid;
the error correction means is further configured to error correction decode primary codewords of at least a portion of the further updated version of the page grid with the primary parity symbols of the primary codewords of the further updated version of the page grid; and
the releasing means is further configured to release the newly corrected requested data based at least partly on a determination that the newly corrected requested data has been decoded without error.

### Claim 65 (depends on 64)

The apparatus of claim 64, wherein the primary codewords and the secondary codewords correspond to Bose, Chaudhuri, and Hocquenghem codewords and wherein the tertiary codewords correspond to Reed-Solomon codewords.

### Claim 66 (depends on 64)

The apparatus of claim 64, further comprising a means for analyzing fingerprints and a means for marking symbols, wherein before the error correction means performs error correction decoding with parity symbols of the tertiary codewords:
the analyzing means is configured to analyze fingerprints of pages of the page grids to identify a page considered to be more unreliable than other pages; and
the marking means is configured to marking symbols of the identified page as erasures.

### Claim 67

A method of reading data, the method comprising:
receiving a request for data stored in at least one of a plurality of flash memory devices;
identifying a page stripe that includes at least a portion of the requested data, wherein the page stripe comprises a grouping of one or more equally-sized flash pages or integer fractions of pages of flash pages, wherein each page or each integer fraction of the page stripe contains primary parity symbols for error correction of data stored within the page or integer fraction, and wherein the pages or integer fractions of the page stripe contain secondary parity symbols for error correction of data stored throughout the page stripe;
retrieving contents of the page stripe in raw form;
performing error correction on the primary codewords of the page stripe to generate an updated page stripe containing corrected requested data;
determining whether or not at least the corrected requested data contains error;
releasing the corrected requested data based at least partly on a determination that the likelihood of the requested data containing an error is less than a predetermined acceptable failure rate;
when the first corrected requested data is not released, performing the following:
interleaving data from the updated page stripe to arrange secondary codewords;
performing error correction decoding on the secondary codewords to generate updated secondary codewords, wherein execution of error correction on the secondary codewords is not performed in parallel with execution of error correction on the primary codewords;
de-interleaving the corrected secondary codewords to generate a further updated page stripe having an updated primary codewords;
performing error correction on at least a portion of the updated primary codewords to generate updated corrected requested data; and
releasing the updated corrected requested data based at least partly on the determination that the likelihood of the requested data containing an error is less than a predetermined acceptable failure rate;
wherein at least performing error correction is performed by an integrated circuit;
wherein at least performing error correction is performed concurrently with a read operation for an end user.

### Claim 68

An apparatus comprising:
a first circuit configured to receive a request for data stored in at least one of a plurality of flash memory devices;
the first circuit configured to identify a page stripe that includes at least a portion of the requested data, wherein the page stripe comprises a grouping of one or more equally-sized flash pages or integer fractions of pages of flash pages, wherein each page or each integer fraction of the page stripe contains primary parity symbols for error correction of data stored within the page or integer fraction, and wherein the pages or integer fractions of the page stripe contain secondary parity symbols for error correction of data stored throughout the page stripe;
the first circuit configured to retrieve contents of the page stripe in raw form;
a second circuit configured to perform error correction on the primary codewords of the page stripe to generate an updated page stripe containing corrected requested data;
the first circuit configured to determine whether or not at least the corrected requested data contains error;
the first circuit configured to release the corrected requested data based at least partly on a determination that the likelihood of the requested data containing an error is less than a predetermined acceptable failure rate;
when the first corrected requested data is not released:
the first circuit is configured to interleave data from the updated page stripe to arrange secondary codewords;
the second circuit is configured to perform error correction decoding on the secondary codewords to generate updated secondary codewords, wherein execution of error correction on the secondary codewords is not performed in parallel with execution of error correction on the primary codewords;
the first circuit is configured to de-interleave the corrected secondary codewords to generate a further updated page stripe having an updated primary codewords;
the second circuit is configured to perform error correction on at least a portion of the updated primary codewords to generate updated corrected requested data; and
the first circuit is configured to release the updated corrected requested data based at least partly on the determination that the likelihood of the requested data containing an error is less than a predetermined acceptable failure rate;
wherein the second circuit is configured to perform error correction concurrently with a read operation for an end user.

### Claim 69

An apparatus for reading data, the apparatus comprising:
a means for receiving a request for data stored in at least one of a plurality of flash memory devices;
a means for identifying a page stripe that includes at least a portion of the requested data, wherein the page stripe comprises a grouping of one or more equally-sized flash pages or integer fractions of pages of flash pages, wherein each page or each integer fraction of the page stripe contains primary parity symbols for error correction of data stored within the page or integer fraction, and wherein the pages or integer fractions of the page stripe contain secondary parity symbols for error correction of data stored throughout the page stripe;
a means for retrieving contents of the page stripe in raw form;
a means for performing error correction on the primary codewords of the page stripe to generate an updated page stripe containing corrected requested data;
a means for determining whether or not at least the corrected requested data contains error;
a means for interleaving;
a means for de-interleaving;
a means for releasing the corrected requested data based at least partly on a determination that the likelihood of the requested data containing an error is less than a predetermined acceptable failure rate;
when the first corrected requested data is not released:
the interleaving means is configured to interleave data from the updated page stripe to arrange secondary codewords;
the error correction means is configured to perform error correction decoding on the secondary codewords to generate updated secondary codewords, wherein execution of error correction on the secondary codewords is not performed in parallel with execution of error correction on the primary codewords;
the de-interleaving means is configured to de-interleave the corrected secondary codewords to generate a further updated page stripe having an updated primary codewords;
the error correction means is configured to perform error correction on at least a portion of the updated primary codewords to generate updated corrected requested data; and
the releasing means is configured to release the updated corrected requested data based at least partly on the determination that the likelihood of the requested data containing an error is less than a predetermined acceptable failure rate;
wherein the error correction means is configured to perform error correction concurrently with a read operation for an end user.