Efficient LDPC decoding with predefined iteration-dependent scheduling scheme

Patent metadata

Field	Value
Publication number	US-10389388-B2
Application number	US-201715856107-A
Country	US
Kind code	B2
Filing date	Dec 28, 2017
Priority date	Dec 28, 2017
Publication date	Aug 20, 2019
Grant date	Aug 20, 2019

Abstract

A decoder includes multiple variable-node circuits and logic circuitry. The variable-node circuits hold variables of an Error Correction Code (ECC), defined by a set of check equations over multiple variables corresponding to the variable-node circuits. The logic circuitry is configured to receive a code word encoded using the ECC, to hold, prior to decoding in a sequence of iterations, a scheduling scheme that specifies, for each iteration, whether each of the variable-node circuits is to be processed or skipped in that iteration, to perform the iterations in the sequence, including selecting for processing, in each iteration, only variable-node circuits specified for processing in that iteration, to determine for each selected variable-node circuit, a count of unsatisfied check equations in which the respective variable participates, and to make a decision on flipping a binary value of the variable based on the count and apply the decision by the respective variable-node circuit.

First claim

The invention claimed is:

1. A decoder, comprising:
multiple variable-node circuits holding respective variables of an Error Correction Code (ECC) that is representable by a set of check equations over multiple variables corresponding respectively to the variable-node circuits; and
logic circuitry, which is configured to:
receive for decoding a code word that was encoded using the ECC;
prior to iterative decoding of the ECC in a sequence of iterations, hold a scheduling scheme that specifies, for each iteration in the sequence, whether each of the variable-node circuits is to be processed or skipped in that iteration;
decode the received code word by performing the iterations in the sequence, including selecting for processing, in each of the iterations, only variable-node circuits that are specified for processing in the respective iteration, by the scheduling scheme;
for each selected variable-node circuit, determine a count of unsatisfied check equations in which the respective variable participates; and
make a decision whether or not to flip a binary value of the respective variable, based on the count, and apply the decision by the respective variable-node circuit.

2. The decoder according to claim 1 , wherein the ECC comprises an irregular Low-Density Parity-Check (LDPC) code, in which at least a first variable and a second variable among the multiple variables of the ECC participate in different respective first and second numbers of the check equations.

3. The decoder according to claim 1 , wherein the scheduling scheme assigns to a given iteration in the sequence a respective predefined flipping threshold, wherein the logic circuitry is configured, when processing a given variable-node circuit in the given iteration, to flip the binary value of the respective variable when the count of the given variable-node circuit exceeds the flipping threshold assigned to the given iteration.

4. The decoder according to claim 3 , wherein the scheduling scheme specifies that a variable-node circuit in a given iteration is to be skipped when the flipping threshold assigned to the given iteration is larger than a number of check equations in which the respective variable participates.

5. The decoder according to claim 3 , wherein the scheduling scheme assigns to successive iterations in the sequence respective numerical flipping thresholds that form a non-increasing sequence.

6. The decoder according to claim 3 , wherein for each iteration in the sequence, the scheduling scheme assigns multiple different flipping thresholds to multiple respective variable-node circuits whose variables appear in different respective numbers of check-equations.

7. The decoder according to claim 1 , wherein the variable-node circuits are partitioned into groups so that at least one of the groups comprises multiple variable-node circuits, wherein the scheduling scheme specifies processing or skipping the variable-node circuits at a group level, and wherein the logic circuitry is configured to process or skip an entire group of variable-node circuits in accordance with the scheduling scheme.

8. The decoder according to claim 1 , wherein the logic circuitry is configured to stop decoding when all of the check equations are satisfied or when a number of processed iterations exceeds a predefined maximal number.

9. A method for decoding, comprising:
in a decoder that comprises multiple variable-node circuits that hold respective variables of an Error Correction Code (ECC) that is representable by a set of check equations over multiple variables corresponding respectively to the variable-node circuits, receiving for decoding a code word that was encoded using the ECC;
prior to iterative decoding of the ECC in a sequence of iterations, holding a scheduling scheme that specifies, for each iteration in the sequence, whether each of the variable-node circuits is to be processed or skipped in that iteration;
decoding the received code word by performing the iterations in the sequence, including selecting for processing, in each of the iterations, only variable-node circuits that are specified for processing in the respective iteration, by the scheduling scheme;
for each selected variable-node circuit, determining a count of unsatisfied check equations in which the respective variable participates; and
making a decision whether or not to flip a binary value of the respective variable, based on the count, and applying the decision by the respective variable-node circuit.

10. The method according to claim 9 , wherein the ECC comprises an irregular Low-Density Parity-Check (LDPC) code, in which at least a first variable and a second variable among the multiple variables of the ECC participate in different respective first and second numbers of the check equations.

11. The method according to claim 9 , wherein the scheduling scheme assigns to a given iteration in the sequence a respective predefined flipping threshold, wherein performing the iterations comprises, when processing a given variable-node circuit in the given iteration, flipping the binary value of the respective variable when the count of the given variable-node circuit exceeds the flipping threshold assigned to the given iteration.

12. The method according to claim 11 , wherein the scheduling scheme specifies that a variable-node circuit in a given iteration is to be skipped when the flipping threshold assigned to the given iteration is larger than a number of check equations in which the respective variable participates.

13. The method according to claim 11 , wherein the scheduling scheme assigns to successive iterations in the sequence respective numerical flipping thresholds that form a non-increasing sequence.

14. The method according to claim 11 , wherein for each iteration in the sequence, the scheduling scheme assigns multiple different flipping thresholds to multiple respective variable-node circuits whose variables appear in different respective numbers of check-equations.

15. The method according to claim 9 , wherein the variable-node circuits are partitioned into groups so that at least one of the groups comprises multiple variable-node circuits, wherein the scheduling scheme specifies processing or skipping variable-node circuits at a group level, and wherein making the decision comprises deciding to process or skip an entire group of variable-node circuits in accordance with the scheduling scheme.

16. The method according to claim 9 , wherein performing the iterations comprises stopping decoding when all of the check equations are satisfied or when a number of processed iterations exceeds a predefined maximal number.

Assignees

• Apple Inc

Inventors

• Tate Yonathan
• Ish-Shalom Tomer

Classifications

• H03M13/1131

  Scheduling of bit node or check node processing · CPC title

• H03M13/43

  Majority logic or threshold decoding · CPC title

• H03M13/11

  using multiple parity bits · CPC title

• H03M13/3746 Primary

  with iterative decoding · CPC title

• H03M13/39

  Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes · CPC title