System and method for parallel decoding of codewords sharing common data

Patent metadata

Field	Value
Publication number	US-10484020-B2
Application number	US-201715668565-A
Country	US
Kind code	B2
Filing date	Aug 3, 2017
Priority date	Feb 3, 2016
Publication date	Nov 19, 2019
Grant date	Nov 19, 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, and each data block having a number of data bits. The decoding apparatus is configured to decode, in parallel, a first codeword with one or more other codewords to determine error information associated with each codeword. For errors in a common data block shared between two codewords being decoded in parallel, the error information includes a data block identifier and associated error bit patterns. Further, the decoding apparatus is configured to update the codewords based on the error information.

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 or more codewords, wherein decoding of each codeword at least partially overlaps in time with decoding of one or more other codewords;
wherein the decoding apparatus is configured to:
perform parallel decoding of a first codeword with one or more other codewords to determine error information associated with each codeword, the first codeword sharing a respective common data block with each of the one or more other codewords, wherein the error information identifies one or more data blocks having one or more errors and associated error bit pattern;
update the one or more other codewords based on the error information;
determine whether to update the first codeword as follows:
determine if common data blocks shared between the first codeword with the one or more other codewords have been identified as having errors in the decoding of the first codeword;
upon determining that the common data blocks have no errors, update the first codeword based on the error information;
for each of the common data blocks in the first codeword that has an error, compare the error bit pattern for the data block in the first codeword with the error bit pattern for a corresponding common data block in the other codewords;
if the error bit patterns match for all the common data blocks that have errors, update data blocks other than the common data blocks in the first codeword without updating the common data blocks; and
if the error bit patterns do not match for any one of the common data blocks that have errors, skip updating of the first codeword;
whereby comparing error bit pattern in updating the first codeword allows reducing skip procedures and reducing a number of codewords that include data blocks which have errors but have not been updated, thus shortening latency loss and increasing decoding throughput.

2. The decoding apparatus of claim 1 , wherein, if the error bit patterns match for all the common data blocks that have errors, the decoding apparatus is further configured to nullify the error bit patterns in the error information.

3. The decoding apparatus of claim 1 , wherein, if the error bit patterns do not match for any one of the common data blocks that have errors, the decoding apparatus is further configured to nullify the error bit patterns in the error information.

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

5. The decoding 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.

6. The decoding apparatus of claim 1 , wherein the parallel decoding is performed by a single decoder with a pipeline structure or by two or more decoders.

7. The decoding 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.

8. The decoding apparatus of claim 7 , wherein the decoding 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 parity-on-parity (POP) bits; and
repeat 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 decoding apparatus of claim 8 , wherein, if the parallel decoding operation is determined to be unsuccessful, a sequential decoding is performed, in which the decoding 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 parity-on-parity (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 multiple 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, a first codeword with one or more other codewords to determine error information associated with each codeword, wherein decoding the first codeword at least partially overlaps in time with decoding of the one or more other codewords, and wherein, for errors in a common data block shared between two codewords being decoded in parallel, the error information includes a data block identifier and associated error bit pattern; and
update the codewords based on the error information;
whereby comparing error bit pattern in updating the first codeword allows reducing a number of skip procedures and reducing a number of codewords that include data blocks which have errors but have not been updated, thus shortening latency loss and increasing decoding throughput.

11. The memory device of claim 10 , wherein the decoding apparatus is configured to:
update the one or more other codewords according to the error information;
identify data blocks in the first codeword that have errors and are common data blocks shared between the first codeword with the one or more other codewords;
identify error bit patterns for each of the identified data blocks; and
update the first codeword to correct errors only if each one of identified data blocks is also identified as having a same error bit pattern in the decoding of one of the other codewords.

12. The memory device of claim 10 , wherein the decoding apparatus is configured to decode encoded data, wherein:
the encoded data includes codewords, each codeword having a number of data blocks and parity bits, the parity bits being formed by encoding the data blocks using a first error-correcting coding scheme;
the encoded data further includes parity-on-parity (POP) bits, which are

Assignees

• Sk Hynix Inc

Inventors

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

Classifications

• H03M13/2927

  Decoding strategies · CPC title

• H03M13/2909 Primary

  Product codes · CPC title

• H03M13/3977

  using sequential decoding, e.g. the Fano or stack algorithms · CPC title

• H03M13/2942

  wherein a block of parity bits is computed only from combined information bits or only from parity bits, e.g. a second block of parity bits is computed from a first block of parity bits obtained by systematic encoding of a block of information bits, or a block of parity bits is obtained by an XOR combination of sub-blocks of information bits · CPC title

• H03M13/152

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