Iterative decoding with early termination criterion that permits errors in redundancy part

Patent metadata

Field	Value
Publication number	US-10848182-B2
Application number	US-201816130003-A
Country	US
Kind code	B2
Filing date	Sep 13, 2018
Priority date	Sep 13, 2018
Publication date	Nov 24, 2020
Grant date	Nov 24, 2020

Abstract

An apparatus includes an interface and a decoder. The interface is configured to receive a code word, produced in accordance with an Error Correction Code (ECC) represented by a set of parity check equations. The code word includes a data part and a redundancy part, and contains one or more errors. The decoder is configured to hold a definition of a partial subgroup of the parity check equations that, when satisfied, indicate that the data part is error-free with a likelihood of at least a predefined threshold, to decode the code word by performing an iterative decoding process on the parity check equations, so as to correct the errors, and during the iterative decoding process, to estimate whether the data part is error-free based only on the partial subgroup of the parity check equations, and if the data part is estimated to be error-free, terminate the iterative decoding process.

First claim

The invention claimed is:

1. An apparatus, comprising:
an interface configured to receive a code word, which was produced in accordance with an Error Correction Code (ECC) represented by a set of parity check equations, wherein the code word comprises a data part and a redundancy part and contains one or more errors; and
a decoder, configured to:
decode the code word by performing an iterative decoding process on the set of parity check equations, so as to correct the one or more errors; and
during the iterative decoding process, estimate whether the data part is error-free based on a partial subgroup of equations including fewer than all the parity check equations in the set, and, if the data part is estimated to be error-free, terminate the iterative decoding process,
wherein the decoder estimates whether the data part is error-free in a manner such that in some cases the iterative decoding process is terminated despite the decoded code word still including errors.

2. The apparatus according to claim 1 , wherein the decoder is configured to terminate the iterative decoding process even when one or more of the parity check equations, which do not belong to the partial subgroup, are not satisfied.

3. The apparatus according to claim 1 , wherein the decoder is configured to estimate whether the data part is error-free by calculating a syndrome only over the parity check equations in the subgroup, and checking whether the syndrome is indicative of at least one unsatisfied parity check equation in the subgroup.

4. The apparatus according to claim 1 , wherein each data bit in the data part of the code word participates in a predefined first number of the parity check equations, and wherein at least one redundancy bit in the redundancy part participates in a second number of the parity check equations that is smaller than the first number.

5. The apparatus according to claim 4 , wherein the parity check equations not included in the partial subgroup of the parity check equations are those parity check equations that depend on the at least one redundancy bit that participate in the second number of the parity check equations.

6. The apparatus according to claim 1 , wherein the decoder is configured to scan the parity check equations in W layers, wherein each of the W layers comprises a plurality of the parity check equations, and to hold the definition of the partial subgroup by identifying a partial subset of W′ layers, wherein W′<W.

7. The apparatus according to claim 1 , wherein each iteration of the iterative decoding process includes a complete scan over all the parity check equations, to correct errors.

8. The apparatus according to claim 1 , wherein the partial subgroup of the parity check equations includes seven eighths of the equations in the set of parity check equations.

9. The apparatus according to claim 1 , wherein the apparatus comprises a processor configured to verify that the decoded code word after termination of the iterative decoding process meets an error detection code, separate from the ECC.

10. An apparatus, comprising:
an interface configured to receive a code word, which was produced in accordance with an Error Correction Code (ECC) represented by a set of parity check equations, wherein the code word comprises a data part and a redundancy part and contains one or more errors; and
a decoder, configured to:
decode the code word by performing an iterative decoding process on the set of parity check equations, so as to correct the one or more errors; and
during the iterative decoding process, estimate whether the data part is error-free based on a partial subgroup of equations including fewer than all the parity check equations in the set, and, if the data part is estimated to be error-free, terminate the iterative decoding process,

wherein the decoder is configured to estimate whether the data part is error-free by calculating a syndrome only over the parity check equations in the subgroup, and checking whether the syndrome is indicative of at least one unsatisfied parity check equation in the subgroup,
wherein the decoder comprises (i) a register that stores decoded bits of the code word that update during the iterative decoding process, and (ii) a logic circuit that is hard-wired to bits of the register in accordance with the parity check equations in the subgroup, wherein the logic circuit is configured to perform, using the logic circuit, within a single clock cycle (i) reading the decoded bits from the register, and (ii) calculating the syndrome, based on the read bits, over the parity check equations in the subgroup.

11. A method, comprising:
in a decoder for an Error Correction Code (ECC) represented by a set of parity check equations, receiving a code word, which was produced in accordance with the ECC, wherein the code word comprises a data part and a redundancy part and contains one or more errors;
decoding the code word by performing an iterative decoding process on the set of parity check equations, so as to correct the one or more errors; and
during the iterative decoding process, estimating whether the data part is error-free based on a partial subgroup of equations including fewer than all the parity check equations in the set, and, if the data part is estimated to be error-free, terminating the iterative decoding process,
wherein estimating whether the data part is error-free is performed in a manner such that in some cases the iterative decoding process is terminated despite the decoded code word still including errors.

12. The method according to claim 11 , wherein terminating the iterative decoding process comprises terminating the decoding process even when one or more of the parity check equations, which do not belong to the partial subgroup, are not satisfied.

13. The method according to claim 11 , wherein estimating whether the data part is error-free comprises calculating a syndrome only over the parity check equations in the subgroup, and checking whether the syndrome is indicative of at least one unsatisfied parity check equation in the subgroup.

14. The method according to claim 13 , wherein the decoder comprises (i) a register that stores decoded bits of the code word that update during the iterative decoding process, and (ii) a logic circuit that is hard-wired to bits of the register in accordance with the parity check equations in the subgroup, wherein estimating whether the data part is error-free comprises performing, using the logic circuit, within a single clock cycle (i) reading the decoded bits from the register, and (ii) calculating the syndrome, based on the read bits, over the parity check equations in the subgroup.

15. The method according to claim 11 , wherein each data bit in the data part of the code word participates in a predefined first number of the parity check equations, and wherein at least one redundancy bit in the redundancy part participates in a second number of the parity check equations that is smaller than the first number.

16. The method according to claim 15 , wherein the parity check equations not included in the partial subgroup of the parity check equations are those parity check equations that depend on the at least one redundancy bit that participate in the second number of the parity check equations.

17. The method according to claim 11 , wherein decoding the code word comprises scanning the parity check equations in W layers, wherein each of the W layers comprises a plurality of the parity check equations, and wherein holding the definition of the partial subgroup comprises identifying a

Assignees

• Apple Inc

Inventors

• Tate Yonathan
• Sommer Naftali
• Landau Asaf
• Chocron Armand

Classifications

• H03M13/1128

  Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations · CPC title

• H03M13/2948

  Iterative decoding (H03M13/2957 takes precedence) · CPC title

• H03M13/1105 Primary

  Decoding · CPC title

• H03M13/255

  with Low Density Parity Check [LDPC] codes · CPC title

• H03M13/1111 Primary

  Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms · CPC title