Check node updates in bit flipping decoders
This application is directed to error correction for data stored in a memory device. In response to a request to validate a block of data, the memory device identifies a set of check nodes corresponding to a set of variable nodes that represent the block of data. First check node values of the check nodes are determined based on the block of data, and stored in first registers. The memory device implements a plurality of iterations of error correction by flipping a subset of variable nodes successively during each iteration; determining second check node values of the check nodes; and updating the first check node values stored in the first registers based on the second check node values once in each of a first set of iterations and successively with flipping of each variable node in a second set of iterations following the first set of iterations.
1. A method implemented at a memory device, comprising:
obtaining a request to validate a block of data stored in the memory device;
identifying a set of check nodes corresponding to a set of variable nodes that represent data bits of the block of data;
determining first check node values of the set of check nodes based on the data bits of the block of data represented by the set of variable nodes; and
implementing a plurality of iterations of error correction, including:
flipping a subset of variable nodes successively during each iteration;
in response to flipping of each of the subset of variable nodes, determining second check node values of the set of check nodes; and
updating the first check node values of the set of check nodes based on the second check node values (1) once in each of a first set of iterations and (2) successively with flipping of each variable node in a second set of iterations following the first set of iterations.
2. The method of claim 1 , wherein implementing the plurality of iterations of error correction further comprises, during each iteration:
identifying the subset of variable nodes based on the first check node values of the set of check nodes, wherein each of the subset of variable nodes corresponds to a subset of check nodes that satisfy a node flipping condition.
3. The method of claim 2 , wherein a portion of the first check node values of each of the subset of check nodes has a second value indicating existence of a data error, and the node flipping condition requires that each of the subset of variable nodes flip in accordance with a determination that the portion is greater than a predefined error limit.
4. The method of claim 1 , wherein implementing the plurality of iterations of error correction further comprises, during each iteration:
in accordance with a determination that the second check node values of the set of check nodes satisfy a data validity condition, terminating the plurality of iterations.
5. The method of claim 4 , further comprising:
after terminating the plurality of iteration, disclaiming the block of data that was originally stored in the memory device, and rewriting, in the memory device, the data bits of the set of variable nodes for use as the block of data.
6. The method of claim 4 , wherein in accordance with the data validity condition, all of the second check node values are equal to a predefined first value, indicating that corresponding variable nodes are free of errors.
7. The method of claim 1 , wherein implementing the plurality of iterations of error correction further comprises, during a final iteration:
in accordance with a determination that a number of iteration implemented prior to the final iteration reaches a predefined iteration limit, terminating the plurality of iterations, and returning a message indicating that errors in the block of data are uncorrectable.
8. The method of claim 1 , further comprising:
in response to flipping of each variable node, updating the second check node values of the set of check nodes.
9. The method of claim 8 , wherein implementing the plurality of iterations of error correction further comprises, during each iteration:
in accordance with a determination that a subset of the block of data is reconstructed, successively in response to flipping of each variable node, updating the first check node values of the set of check nodes with the second check node values determined for the set of check nodes.
10. The method of claim 8 , wherein implementing the plurality of iterations of error correction further comprises, during a first iteration:
determining that the first iteration has a number of iterations that are implemented immediately prior to the first iteration in the plurality of iterations; and
in accordance with a determination that the number of iterations is greater than a predefined iteration number, successively in response to flipping of each following variable node, updating the first check node values of the set of check nodes with the second check node values determined for the set of check nodes.
11. The method of claim 8 , wherein implementing the plurality of iterations of error correction further comprises, at a current time during a second iteration:
identifying, in the subset of variable nodes, a plurality of variable nodes that flip prior to the current time and during a continuous portion of the second iteration;
determining that each of the plurality of variable nodes has a degree that is less than a predefined degree number; and
in accordance with a determination that each of the plurality of variable nodes has the degree less than the predefined degree number, successively in response to flipping of each following variable node, updating the first check node values of the set of check nodes with the second check node values determined for the set of check nodes.
12. A memory device, comprising:
a memory controller; and
memory storing one or more programs thereon, the one or more programs further including instructions for:
obtaining a request to validate a block of data stored in a memory device;
identifying a set of check nodes corresponding to a set of variable nodes that represent data bits of the block of data;
determining first check node values of the set of check nodes based on the data bits of the block of data represented by the set of variable nodes; and
implementing a plurality of iterations of error correction, including:
flipping a subset of variable nodes successively during each iteration;
in response to flipping of each of the subset of variable nodes, determining second check node values of the set of check nodes; and
updating the first check node values of the set of check nodes based on the second check node values (1) once in each of a first set of iterations and (2) successively with flipping of each variable node in a second set of iterations following the first set of iterations.
13. The memory device of claim 12 , the one or more programs further comprising instructions for:
storing the first check node values of the set of check nodes in first registers; and
storing the second check node values of the set of check nodes in second registers.
14. The memory device of claim 12 , wherein determining the first check node values of the set of check nodes further comprises, for each of the set of check nodes:
identifying a subset of variable nodes that corresponds to the respective check node; and
combining the subset of variable nodes to determine the first check node value of the respective check node.
15. The memory device of claim 14 , wherein for each of the set of check nodes, combining the subset of variable nodes further comprises:
in accordance with a determination the subset of variable nodes includes a single variable node, setting the first check node value of the respective check node according to a data bit represented by the single variable node; and
in accordance with a determination the subset of variable nodes includes more than one variable node, applying an XOR based logic to combine the subset of variable nodes to determine the first check node value of the respective check node.
16. The memory device of claim 12 , wherein the first check node values of the set of check nodes is updated based on the second check node values once and consistently at a start, at an end, or after a predefined number of variable node flips, of each of the first set of iterations.
17. The memory device of claim 12 , wherein the first check node values of the set of check nodes is updated based on the second check node values once at a variable location of each of the first set of iterations.
18. A non-transitory computer-readable storage medium storing one or more programs, the one or more programs comprising instructions for:
obtaining a request to validate a block of data stored in a memory device;
identifying a set of check nodes corresponding to a set of variable nodes that represent data bits of the block of data;
determining first check node values of the set of check nodes based on the data bits of the block of data represented by the set of variable nodes; and
implementing a plurality of iterations of error correction, including:
flipping a subset of variable nodes successively during each iteration;
in response to flipping of each of the subset of variable nodes, determining second check node values of the set of check nodes; and
updating the first check node values of the set of check nodes based on the second check node values (1) once in each of a first set of iterations and (2) successively with flipping of each variable node in a second set of iterations following the first set of iterations.
19. The non-transitory computer-readable storage medium of claim 18 , wherein implementing the plurality of iterations of error correction further comprises, during each iteration:
identifying the subset of variable nodes based on the first check node values of the set of check nodes, wherein each of the subset of variable nodes corresponds to a subset of check nodes that satisfy a node flipping condition.
20. The non-transitory computer-readable storage medium of claim 18 , wherein implementing the plurality of iterations of error correction further comprises, during each iteration:
in accordance with a determination that the second check node values of the set of check nodes satisfy a data validity condition, terminating the plurality of iterations.