Data dependency mitigation in parallel decoders for flash storage

Patent metadata

Field	Value
Publication number	US-10498366-B2
Application number	US-201715582278-A
Country	US
Kind code	B2
Filing date	Apr 28, 2017
Priority date	Jun 23, 2016
Publication date	Dec 3, 2019
Grant date	Dec 3, 2019

Abstract

A memory device can include a memory array, a processor coupled to the memory array, and a decoding apparatus. The decoding apparatus is configured to perform parallel decoding of codewords. Each of the codewords has a plurality of data blocks, each data block having a number of data bits. The decoding apparatus is configured to decode in parallel two or more codewords, which share a common data block, to determine error information associated with each codeword. For each error, the error information identifies a data block having the and associated error bit patterns. The decoding apparatus is configured to update the two or more codewords based on the identified data blocks having errors and the associated error bit patterns.

First claim

What is claimed is:

1. A decoding apparatus configured for decoding a plurality of codewords in parallel, comprising:
a memory;
a processor coupled to the memory, the processor configured to read encoded data including a plurality of codewords from the memory, the plurality of codewords being encoded in a product code in which each codeword has multiple data blocks, each data block having a number of data bits, wherein the plurality of codewords are encoded such that codewords belonging to a same pair of codewords share a common data block; and
one or more decoders, configured to perform parallel decoding of two codewords, wherein decoding of one of the two codewords at least partially overlaps in time with decoding of the other one of the two codewords;
wherein the decoding apparatus is configured to:
perform parallel decoding of a first codeword and a second codeword sharing a common data block to determine error information associated with each codeword, wherein the error information identifies one or more data blocks having one or more errors and associated error bit patterns;
update the first codeword based on the error information indicating an error;
if the error information indicates an error in the decoding of the second codeword, determine whether to update the second codeword as follows:
determine if the common data block between the first codeword and the second codeword has been identified as having an error in the decoding of the first codeword;
upon determining that the common data block has not been identified as having an error, update the second codeword based on the error information;
upon determining that the common data block has been identified as having an error and that an error bit pattern in the common data block identified in the decoding of the second codeword is the same as an error bit pattern in the common data block identified from the error information based on the decoding of the first codeword, update data blocks other than the common data block in the second codeword without updating the common data block; and
upon determining that the common data block has been identified as having an error and that the error bit pattern in the common data block identified in the decoding of the second codeword is different from the error bit pattern in the common data block identified from the error information based on the decoding of the first codeword, skip the updating of the second codeword.

2. The apparatus of claim 1 , wherein the apparatus is further configured to perform sequential decoding, in which the codewords are decoded sequentially, wherein the apparatus is configured to perform sequential decoding only if it is determined that the parallel decoding has failed to decode the plurality of codewords.

3. The apparatus of claim 1 , wherein the parallel decoding is repeated until the plurality of codewords are successfully decoded or until a predetermined number of iterations has been reached.

4. The apparatus of claim 1 , wherein the parallel decoding is performed by a single decoder with a pipeline structure.

5. The apparatus of claim 1 , wherein the parallel decoding is performed by two or more decoders.

6. The apparatus of claim 1 , wherein the plurality of codewords are encoded in the product code by arranging a plurality of data blocks in a triangular matrix of N columns by N rows, N being an integer, such that column 1 comprises one data block, column 2 comprises two data blocks, . . . , column N comprises N data blocks, and that row 1 comprises N data blocks, row 2 comprises N−1 data blocks, . . . , row N comprises one data block, and
wherein the codewords are formed such that:
codeword 1 comprises N data blocks in row 1 ;
codeword 2 comprises one data block in column 1 and N−1 data blocks in row 2 ;
codeword 3 comprise two data blocks of column 2 , and N−2 data blocks in row 3 ;
codeword 4 comprise three data blocks of column 3 , and N−3 data blocks in row 4 ;
. . . ;
codeword N−1 comprises N−2 data blocks of column N−2 and two data blocks in row N−1;
codeword N comprises N−1 data blocks of column N−1 and one data block in row N;

or the codewords are formed as described above, with rows and columns reversed;
whereby each data block is included in two codewords.

7. The apparatus of claim 1 , wherein:
the encoded data comprises a group of data bits arranged in data blocks, the data blocks including blocks of information bits;
each codeword including a number of data blocks and parity bits, the parity bits formed by encoding the data blocks using an error-correcting coding scheme;
the encoded data further including parity-on-parity (POP) bits, which are formed by encoding the parity bits of the codewords using a second error-correcting coding scheme;
wherein each data block is included in two or more codewords, and wherein codewords belonging to a same pair of codewords share a common data block.

8. The apparatus of claim 7 , wherein the apparatus is configured to:
decode the plurality of codewords, wherein, in each parallel decoding operation, two or more codewords are decoded in parallel, and a codeword is updated to correct errors unless a shared common data block is previously updated in said parallel decoding operation;
if the plurality of codewords are not decoded successfully, decode and update the parity bits and the POP bits; and
repeat the above parallel decoding operations until all codewords are decoded successfully or until a preset number of iterations is reached and the parallel decoding operation is determined to be unsuccessful.

9. The apparatus of claim 8 , wherein, if the parallel decoding operation is determined to be unsuccessful, a sequential decoding is performed, in which the apparatus is configured to:
decode the plurality of codewords, wherein each codeword is decoded sequentially and updated to correct errors;
if the plurality of codewords are not decoded successfully, decode and update the parity bits and the POP bits; and
repeat the above decoding operations until all codewords are decoded successfully or until a preset number of iterations is reached.

10. A memory device, comprising:
a memory array;
a processor coupled to the memory array; and
a decoding apparatus configured to perform parallel decoding of codewords, each of the codewords having a plurality of data blocks, each data block having a number of data bits, wherein the codewords are encoded such that codewords belonging to a same pair of codewords share a common data block;
wherein the decoding apparatus is configured to:
decode in parallel two or more codewords, wherein each pair of codewords shares a common data block, to determine error information associated with each codeword, wherein, for each error, the error information identifies a data blocks having the error and associated error bit pattern; and
update the two or more codewords based on the identified one or more data blocks having errors and the associated error bit patterns.

11. The memory device of claim 10 , wherein the decoding apparatus is configured to:
update a first codeword according to the error information; and
update a second codeword according to the error information associated with the second codeword, unless the common data block is updated in the updating of the first codeword and the error bit pattern in the common data block identified in the decoding of the second codeword is different from the error bit pattern in the common data block identified in the decoding of the first codeword.

12. The memory device of claim 10 , wherein the decoding apparatus is configured to decode a plurality of

Assignees

• Sk Hynix Inc

Inventors

• Lin Yi-Min
• Bhatia Aman
• Kumar Naveen
• Yen Johnson

Classifications

• H03M13/2909 Primary

  Product codes · CPC title

• H03M13/152

  Bose-Chaudhuri-Hocquenghem [BCH] codes · CPC title

• H03M13/2927

  Decoding strategies · CPC title

• H03M13/3707

  Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code · CPC title

• H03M13/6561

  Parallelized implementations · CPC title