Techniques for low complexity turbo product code decoding

Patent metadata

Field	Value
Publication number	US-9998148-B2
Application number	US-201615159331-A
Country	US
Kind code	B2
Filing date	May 19, 2016
Priority date	Dec 1, 2015
Publication date	Jun 12, 2018
Grant date	Jun 12, 2018

Abstract

Techniques are described for decoding a codeword, including, obtaining a first message comprising a plurality of information bits and a plurality of parity bits, wherein the message corresponds to a turbo product code (TPC) comprising two or more constituent codes, wherein each constituent code corresponds to a class of error correcting codes capable of correcting a pre-determined number of errors, performing an iterative TPC decoding using at least one of a first decoder corresponding to a first constituent code and a second decoder corresponding to a second constituent code on the first message to generate a second message, determining if the decoding was successful. Upon determining that the TPC decoding was not successful, determining one or more error locations in the second message based on a third constituent code using a third decoder. The third decoder determines the one or more error locations in a predetermined number of clock cycles.

First claim

What is claimed is:

1. An apparatus for decoding, comprising:
a memory;
a processor coupled to the memory, the processor configured to:
obtain a first message comprising a plurality of information bits and a plurality of parity bits, wherein the first message corresponds to a turbo product code (TPC) comprising two or more constituent codes, wherein each constituent code corresponds to a class of error correcting codes capable of correcting a pre-determined number of errors;
perform an iterative TPC decoding using at least one of a first decoder corresponding to a first constituent code and a second decoder corresponding to a second constituent code on the first message to generate a second message;
determine if the iterative TPC decoding was successful; and
upon determining that the TPC decoding was not successful, determine one or more error locations in the second message based on a third constituent code using a third decoder, wherein the third decoder determines the one or more error locations in a predefined number of clock cycles based on an additional iterative TPC decoding on the second message, wherein the additional iterative TPC decoding comprises:
generating a syndrome of the third constituent code in an initial iteration based on the second message;
updating a value of the syndrome by at least using the one or more error locations determined in the initial iteration; and
decoding the second message in a next iteration based on the updated value of the syndrome.

2. The apparatus of claim 1 , wherein the third decoder determines the one or more error locations directly from one or more syndrome values without performing a search.

3. The apparatus of claim 1 , wherein the processor is further configured to:
generate at least one of a first set of syndrome values corresponding to the first constituent code and a second set of syndrome values corresponding to the second constituent code based on the first message.

4. The apparatus of claim 3 , wherein the processor is further configured to:
perform a first set of decoding operations corresponding to the first decoder on the first message using the first set of syndrome values to generate a third message;
generate an adjusted set of syndrome values by adjusting at least one of the syndrome values in the second set of syndrome values based on the third message; and
perform a second set of decoding operations corresponding to the second decoder on the third message using the adjusted set of syndrome values to generate the second message.

5. The apparatus of claim 1 , wherein the processor is further configured to:
correct the second message based on the one or more error locations to generate a third message;
iteratively perform decoding operations on the third message using at least one of the first decoder or the second decoder.

6. The apparatus of claim 1 , wherein one or more of the first constituent code or the second constituent code correspond to a Bose-Chaudhuri-Hocquenghem (BCH) code.

7. The apparatus of claim 1 , wherein the predefined number of clock cycles is less than or equal to two clock cycles.

8. A method for decoding, comprising:
obtaining a first message comprising a plurality of information bits and a plurality of parity bits, wherein the first message corresponds to a turbo product code (TPC) comprising two or more constituent codes, wherein each constituent code corresponds to a class of error correcting codes capable of correcting a pre-determined number of errors;
performing an iterative TPC decoding using at least one of a first decoder corresponding to a first constituent code and a second decoder corresponding to a second constituent code on the first message to generate a second message;
determining if the iterative TPC decoding was successful; and
upon determining that the TPC decoding was not successful, determining one or more error locations in the second message based on a third constituent code using a third decoder, wherein the third decoder determines the one or more error locations in a predefined number of clock cycles based on an additional iterative TPC decoding on the second message, wherein the additional iterative TPC decoding comprises:
generating a syndrome of the third constituent code in an initial iteration based on the second message;
updating a value of the syndrome by at least using the one or more error locations determined in the initial iteration; and
decoding the second message in a next iteration based on the updated value of the syndrome.

9. The method of claim 8 , wherein the third decoder determines the one or more error locations directly from one or more syndrome values without performing a search.

10. The method of claim 8 , further comprising:
generating at least one of a first set of syndrome values corresponding to the first constituent code and a second set of syndrome values corresponding to the second constituent code based on the first message.

11. The method of claim 10 , further comprising:
performing a first set of decoding operations corresponding to the first decoder on the first message using the first set of syndrome values to generate a third message;
generating an adjusted set of syndrome values by adjusting at least one of the syndrome values in the second set of syndrome values based on the third message; and
performing a second set of decoding operations corresponding to the second decoder on the third message using the adjusted set of syndrome values to generate the second message.

12. The method of claim 8 , further comprising:
correcting the second message based on the one or more error locations to generate a third message;
iteratively performing decoding operations on the third message using at least one of the first decoder or the second decoder.

13. The method of claim 8 , wherein one or more of the first constituent code or the second constituent code correspond to a Bose-Chaudhuri-Hocquenghem (BCH) code.

14. The method of claim 8 , wherein the predefined number of clock cycles is less than or equal to two clock cycles.

15. A non-transitory processor-readable medium for decoding, comprising processor-readable instructions configured to cause one or more processors to:
obtain a first message comprising a plurality of information bits and a plurality of parity bits, wherein the first message corresponds to a turbo product code (TPC) comprising two or more constituent codes, wherein each constituent code corresponds to a class of error correcting codes capable of correcting a pre-determined number of errors;
perform an iterative TPC decoding using at least one of a first decoder corresponding to a first constituent code and a second decoder corresponding to a second constituent code on the first message to generate a second message;
determine if the iterative TPC decoding was successful; and
upon determining that the TPC decoding was not successful, determine one or more error locations in the second message based on a third constituent code using a third decoder, wherein the third decoder determines the one or more error locations in a predefined number of clock cycles based on an additional iterative TPC decoding on the second message, wherein the additional iterative TPC decoding comprises:
generating a syndrome of the third constituent code in an initial iteration based on the second message;
updating a value of the syndrome by at least using the one or more error locations determined in the initial iteration; and
decoding the second message in a next iteration based on the updated value of the syndrome.

Assignees

• Sk Hynix Inc

Inventors

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

Classifications

• H03M13/2918

  with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube · CPC title

• H03M13/152 Primary

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

• H03M13/1525

  Determination and particular use of error location polynomials · CPC title

• H03M13/2963

  Turbo-block codes, i.e. turbo codes based on block codes, e.g. turbo decoding of product codes · CPC title

• H03M13/1575

  Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance · CPC title