Techniques for low complexity turbo product code decoding

• US 9,998,148 B2
• Filed: 05/19/2016
• Issued: 06/12/2018
• Est. Priority Date: 12/01/2015
• Status: Active Grant

• Current Assignee: SK Hynix Inc.
• Original Assignee: SK Hynix Inc.
• Inventors: Lin, Yi-Min, Bhatia, Aman, Kumar, Naveen, Yen, Johnson
• Primary Examiner(s): McMahon, Daniel
• Application Number:
  US15/159,331
• Publication Number:
  US 20170155407A1
• Time in Patent Office: 754 Days
• Field of Search: None
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/1525 Determination and particular use of error location polynomials
• CPC Class Codes: H03M 13/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 Class Codes: H03M 13/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 Class Codes: H03M 13/2963 Turbo-block codes, i.e. turbo codes based on block codes, e.g. turbo decoding of product codes

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.

Claims

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.

16. The non-transitory processor-readable medium of claim 15, wherein the third decoder determines the one or more error locations directly from one or more syndrome values without performing a search.

17. The non-transitory processor-readable medium of claim 15, wherein the processor-readable instructions are further configured to cause one or more processors 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.

18. The non-transitory processor-readable medium of claim 17, wherein the processor-readable instructions are further configured to cause one or more processors 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.

19. The non-transitory processor-readable medium of claim 15, wherein the processor-readable instructions are further configured to cause one or more processors 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.

20. The non-transitory processor-readable medium of claim 15, wherein one or more of the first constituent code or the second constituent code correspond to a Bose-Chaudhuri-Hocquenghem (BCH) code.