Efficient convergence in iterative decoding

Patent metadata

Field	Value
Publication number	US-10128869-B2
Application number	US-201615156356-A
Country	US
Kind code	B2
Filing date	May 17, 2016
Priority date	May 17, 2016
Publication date	Nov 13, 2018
Grant date	Nov 13, 2018

Abstract

A decoder includes one or more Variable-Node Processors (VNPs) that hold respective variables, and logic circuitry. The logic circuitry is configured to decode 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 at least some of the variables, to hold one or more auxiliary equations derived from the check equations, so that a number of the auxiliary equations is smaller than a number of the check equations, to evaluate the auxiliary equations, during the sequence of iterations, using the variables, and, in response to detecting that the variables satisfy the auxiliary equations, to terminate the sequence of iterations and output the variables as the decoded code word.

First claim

The invention claimed is:

1. A decoder, comprising:
one or more Variable-Node Processors (VNPs), configured to hold multiple values of respective variables; and
logic circuitry, which is configured to:
receive a code word of an Error Correction Code (ECC), which is representable by a set of check equations,
initialize the variables held by the one or more variable node processors from the received code word,
perform a sequence of iterations such that each iteration involves processing of at least some of the variables held by the one or more variable node processors, based on corresponding check equations in which the variables appear,
hold one or more auxiliary equations, each derived from a plurality of the check equations, such that when the plurality of check equations from which a specific auxiliary equation is derived are satisfied, the specific auxiliary equation is also satisfied, wherein a number of the auxiliary equations is smaller than a number of the check equations,
during the sequence of iterations, evaluate whether current values of the variables satisfy the auxiliary equations, and
in response to detecting that the variables satisfy the auxiliary equations, terminate the sequence of iterations and output the variables as the decoded code word,
wherein the logic circuitry evaluates whether the current values of the variables satisfy the auxiliary equations by initializing an auxiliary syndrome based on the received code word, updating the auxiliary syndrome based on changes in the variables and determining when the auxiliary syndrome has a value of zero, and
wherein the auxiliary equations are represented by a quasi-cyclic matrix, and the logic circuitry holds the matrix in a reduced storage space based on knowledge of the quasi-cyclic attributes of the quasi-cyclic matrix.

2. The decoder according to claim 1 , wherein the one or more auxiliary equations comprise linear combinations of two or more of the check equations.

3. The decoder according to claim 1 , wherein the ECC comprises a Quasi-Cyclic (QC) Low Density Parity Check (LDPC) code whose check equations are organized in a parity-check matrix that comprises multiple block rows of L-by-L sub-matrices, and wherein the one or more auxiliary equations include an auxiliary equation comprising a linear combination of two or more check equations that belong to different respective block rows.

4. The decoder according to claim 1 , wherein the logic circuitry is configured to calculate an auxiliary syndrome corresponding to the auxiliary equations, and to detect that the variables satisfy the auxiliary equations by detecting that the auxiliary syndrome equals zero.

5. The decoder according to claim 4 , wherein the VNPs are configured to define the values of the variables in a Galois Field (GF), and wherein the logic circuitry is configured to update the auxiliary syndrome based on a vector of recently updated variables.

6. The decoder according to claim 1 , wherein the code word is received by the logic circuitry from a memory device.

7. The decoder according to claim 1 , wherein the code word is received by the logic circuitry in a communication signal.

8. The decoder according to claim 1 , wherein each of the auxiliary equations is derived from a fixed number of the check equations.

9. A method comprising:
receiving in a decoder, a code word of an Error Correction Code (ECC), which is representable by a set of check equations;
initializing variables held by the decoder, from the received code word;
performing a sequence of iterations such that each iteration involves processing of at least some of the variables held by the decoder, based on corresponding check equations in which the variables appear;
holding one or more auxiliary equations derived from the check equations, wherein a number of the auxiliary equations is smaller than a number of the check equations, and wherein the auxiliary equations are characterised in that when the plurality of check equations from which a specific auxiliary equation is derived are satisfied, the specific auxiliary equation is also satisfied;
during the sequence of iterations, evaluating whether current values of the variables satisfy the auxiliary equations; and
in response to detecting that the variables satisfy the auxiliary equations, terminating the sequence of iterations and outputting the variables as the decoded code word,
wherein evaluating whether the current values of the variables satisfy the auxiliary equations comprises initializing an auxiliary syndrome based on the received code word, updating the auxiliary syndrome based on changes in the variables and determining when the auxiliary syndrome has a value of zero, and
wherein the auxiliary equations are represented by a quasi-cyclic matrix, and holding one or more auxiliary equations comprises holding the quasi-cyclic matrix in a reduced storage space based on knowledge of the quasi-cyclic attributes of the quasi-cyclic matrix.

10. The method according to claim 9 , wherein holding the auxiliary equations comprises holding an auxiliary equation comprising a linear combination of two or more of the check equations.

11. The method according to claim 9 , wherein the ECC comprises a Quasi-Cyclic (QC) Low Density Parity Check (LDPC) code whose check equations are organized in a parity-check matrix that comprises multiple block rows of L-by-L sub-matrices, and wherein holding the auxiliary equations comprises holding an auxiliary equation comprising a linear combination of two or more check equations that belong to different respective block rows.

12. The method according to claim 9 , wherein evaluating the auxiliary equations comprises calculating an auxiliary syndrome corresponding to the auxiliary equations, and wherein detecting that the variables satisfy the auxiliary equations comprises detecting that the auxiliary syndrome equals zero.

13. The method according to claim 12 , wherein the values of the variables nodes are defined in a Galois Field (GF), and wherein evaluating the auxiliary equations comprises updating the auxiliary syndrome based on a vector of recently updated variables.

14. The method according to claim 9 , wherein receiving the code word comprises receiving from a memory device.

15. The method according to claim 9 , wherein receiving the code word comprises receiving the code word in a communication signal.

16. The method according to claim 9 , wherein each of the auxiliary equations is derived from a fixed number of the check equations.

Assignees

• Apple Inc

Inventors

• Tate Yonathan
• Teitel Moti

Classifications

• H03M13/116 Primary

  Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices · CPC title

• H03M13/1111

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

• H03M13/1108

  Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping · CPC title

• H03M13/1128

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