Decoder with selective iteration scheduling

Patent metadata

Field	Value
Publication number	US-9258015-B2
Application number	US-201314138809-A
Country	US
Kind code	B2
Filing date	Dec 23, 2013
Priority date	Dec 23, 2013
Publication date	Feb 9, 2016
Grant date	Feb 9, 2016

Abstract

A method includes decoding a code word of an Error Correction Code (ECC), which is representable by a set of check equations, by performing a sequence of iterations, such that each iteration involves processing of multiple variable nodes. For one or more selected variable nodes, a count of the check equations that are defined over one or more variables held respectively by the one or more selected variable nodes is evaluated, and, when the count meets a predefined skipping criterion, the one or more selected variable nodes are omitted from a given iteration in the sequence.

First claim

The invention claimed is:

1. A method, comprising:
decoding a code word of an Error Correction Code (ECC) by performing a sequence of iterations, such that each iteration involves processing of multiple variable nodes, wherein the ECC is represented by a set of check equations;
for one or more selected variable node processors, evaluating a number of unsatisfied check equations that are defined over one or more variables held respectively by the one or more selected variable node processors, and, omitting the one or more selected variable node processors from a given iteration in the sequence in response to determining that the number of unsatisfied check equations meets a predefined skipping criterion; and
clearing an indication that a particular variable node processor should be skipped in a current iteration in response to a determining that the particular variable node processor was skipped in a previous iteration.

2. The method according to claim 1 , wherein the given iteration immediately follows an iteration in which the skipping criterion is met.

3. The method according to claim 1 , wherein the one or more variables includes binary variables, and wherein performing the iterations includes conditionally flipping the binary variables based on a predefined bit flipping threshold, and comprising setting the skipping threshold depending on the bit flipping threshold.

4. The method according to claim 3 , wherein setting the skipping threshold comprises subtracting a positive integer from the bit flipping threshold.

5. The method according to claim 1 , wherein the given iteration includes an iteration in which the skipping criterion is met.

6. The method according to claim 5 , wherein variables that are associated with one or more selected variable node processors, are all common to a predefined subset of the check equations.

7. A decoder, comprising:
multiple variable node processors, each holding respective variables; and
logic circuitry, configured to:
decode a code word of an Error Correction Code (ECC), wherein the ECC is represented by a set of check equations;
evaluate, for one or more selected variable nodes, a number of unsatisfied check equations that are defined over one or more variables held respectively by the one or more selected variable node processors and
omit the one or more selected variable node processors from a given iteration in the sequence in response to a determination that the number of unsatisfied check equations meets a predefined skipping criterion;

wherein to decode the code word of the ECC, the logic circuitry is further configured to perform a sequence of iterations, wherein each iteration includes processing at least some of the multiple variable nodes; and
wherein the logic circuitry is further configured to clear an indication that a particular variable node processor should be skipped in a current iteration in response to a determination that the particular variable node processor was skipped in a previous iteration.

8. The decoder according to claim 7 , wherein the given iteration immediately follows an iteration in which the skipping criterion is met.

9. The decoder according to claim 7 , wherein the one or more variables include binary variables, and wherein to perform the sequence of iterations, the logic circuitry is further configured to flip the binary variables based on a predefined bit flipping threshold, and set the skipping threshold depending on the bit flipping threshold.

10. The decoder according to claim 9 , wherein to set the skipping threshold, the logic circuitry is further configured to subtract a positive integer from the bit flipping threshold.

11. The decoder according to claim 7 , wherein the given iteration includes an iteration in which the skipping criterion is met.

12. The decoder according to claim 11 , wherein variables that are associated with one or more selected variable node processors, are all common to a predefined subset of the set of check equations.

Assignees

• Apple Inc

Inventors

• Ish-Shalom Tomer
• Dar Ronen
• Anholt Micha

Classifications

• H03M13/1111 Primary

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

• H03M13/1128

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

• H03M13/114

  Shuffled, staggered, layered or turbo decoding schedules · CPC title

• H03M13/3715

  Adaptation to the number of estimated errors or to the channel state · CPC title