Generalized product codes for flash storage

Patent metadata

Field	Value
Publication number	US-10388400-B2
Application number	US-201615158425-A
Country	US
Kind code	B2
Filing date	May 18, 2016
Priority date	May 18, 2015
Publication date	Aug 20, 2019
Grant date	Aug 20, 2019

Abstract

Memory systems may include an encoder suitable for arranging data in rows of data blocks as a plurality of codewords, and permuting the data block rows and constructing row parities on the permuted rows, and a decoder suitable for decoding the codewords, and correcting stuck error patterns when decoding of the codewords fails.

First claim

What is claimed is:

1. A memory system, comprising:
an encoder suitable for:
arranging data in rows of blocks;
permuting the data in each single row of blocks and constructing row parities on the permuted data for the corresponding row of blocks to generate a corresponding codeword, of a plurality of codewords, one of which is generated for each row of blocks; and
combining, column-wise, a parity bit of the row parities of each of the plurality of codewords to generate combined parities; and

a decoder suitable for:
decoding the plurality of codewords to generate decoded codewords; and
correcting stuck error patterns in one or more unsuccessfully decoded codewords, among the decoded codewords, based at least in part on one or more of the combined parities.

2. The memory system of claim 1 , wherein the data in the rows of blocks are permuted such that each block is included in at least two rows.

3. The memory system of claim 1 , wherein each block includes a same number of bits.

4. The memory system of claim 1 , wherein the encoder is further suitable for generating an XOR parity and storing the XOR parity in at least one of the rows of blocks.

5. The memory system of claim 4 , wherein the XOR parity is generated by taking an XOR of the data in a single select row of blocks and a predetermined number of the constructed row parities.

6. The memory system of claim 4 , wherein the decoder is suitable for correcting stuck error patterns by:
constructing an XOR parity from the decoded codewords; and
determining a location of a stuck error pattern based on a difference between the XOR parity constructed by the decoder and the XOR parity generated by the encoder.

7. The memory system of claim 4 , wherein the decoder is suitable for correcting stuck error patterns by:
determining an error location intersection of two of the one or more unsuccessfully decoded codewords; and
flipping a bit at the error location intersection.

8. A method, comprising:
arranging, with an encoder, data in rows of blocks;
permuting, with the encoder, the data in each single row of blocks and constructing row parities on the permuted data for the corresponding row of blocks to generate a codeword, of a plurality of codewords, one of which is generated for each row of blocks;
combining, column-wise, with the encoder, a parity bit of the row parities of each of the plurality of codewords to generate combined parities;
decoding, with a decoder, the plurality of codewords to generate decoded codewords; and
correcting, with the decoder, stuck error patterns in one or more unsuccessfully decoded codewords, among the decoded codewords, based at least in part on one or more of the combined parities.

9. The method of claim 8 , wherein the data in the rows of blocks are permuted such that each block is included in at least two rows.

10. The method of claim 8 , wherein each block includes a same number of bits.

11. The method of claim 8 , further comprising generating, with the encoder, an XOR parity and storing the XOR parity in at least one of the rows of blocks.

12. The method of claim 11 , wherein the XOR parity is generated by taking an XOR of the data in a single select row of blocks and a predetermined number of the constructed codeword parities.

13. The method of claim 11 , wherein the correcting error patterns step further comprises:
constructing, with the decoder, an XOR parity from the decoded codewords; and
determining a location of a stuck error pattern based on a difference between the XOR parity constructed by the decoder and the XOR parity generated by the encoder.

14. The method of claim 11 , wherein the correcting error patterns step includes:
determining, with the decoder, an error location intersection of two of the one or more unsuccessfully decoded codewords; and
flipping a bit at the error location intersection.

15. A memory device, comprising:
an encoder configured to:
arrange data in rows of blocks;
permute the data in each single row of blocks and construct row parities on the permuted data for the corresponding row of blocks to generate a codeword, of a plurality of codewords, one of which is generated for each row of blocks; and
combine, column-wise, a parity bit of the row parities each of the plurality of codewords to generate combined parities; and

a decoder configured to:
decode the plurality of codewords to generate decoded codewords; and
correct stuck error patterns in one or more unsuccessfully decoded codewords, among the decoded codewords, based at least in part on one or more of the combined parities.

16. The memory device of claim 15 , wherein the encoder is further configured to generate an XOR parity and store the XOR parity in at least one of the rows of blocks.

17. The memory device of claim 16 , wherein the XOR parity is generated by taking an XOR of the data in a single select row of blocks and a predetermined number of the constructed codeword parities.

18. The memory device of claim 17 , wherein the decoder is further configured to correct stuck error patterns by:
constructing an XOR parity from the decoded codewords; and
determining a location of a stuck error pattern based on a difference between the XOR parity constructed by the decoder and the XOR parity generated by the encoder.

Assignees

• Sk Hynix Inc

Inventors

• Kumar Naveen
• Bhatia Aman
• Zeng Lingqi

Classifications

• G06F11/1096

  Parity calculation or recalculation after configuration or reconfiguration of the system · CPC title

• G11C16/349

  Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles · CPC title

• G06F11/108

  Parity data distribution in semiconductor storages, e.g. in SSD · CPC title

• G11C29/52 Primary

  Protection of memory contents; Detection of errors in memory contents · CPC title

• G06F2211/109

  Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation · CPC title