Efficient LDPC decoding with predefined iteration-dependent scheduling scheme
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.
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.