Decoding systems and methods for local reinforcement
Embodiments of the present disclosure provide a scheme for decoding over a small subgraph which highly likely includes some errors. A controller is configured to: control the first decoder to decode the data, read from the memory device, using a parity check matrix for the error correction code; extract one or more subgraphs from the entire bipartite graph of the parity check matrix, which is defined by a plurality of variable nodes and a plurality of check nodes when a particular condition satisfied; and control the second decoder to decode the decoding result of the first decoder using a submatrix of the parity check matrix corresponding to the extracted subgraphs.
1. A system comprising:
a memory device storing data encoded with an error correction code; and
a controller including a first decoder with a first precision and a second decoder with a second precision greater than the first precision,
wherein the controller is configured to:
control the first decoder to decode the data read from the memory device by using a parity check matrix for the error correction code;
extract one or more subgraphs from the entire bipartite graph of the parity check matrix, which is defined by a plurality of variable nodes and a plurality of check nodes when a particular condition is satisfied, the one or more subgraphs to be extracted based on unsatisfied check nodes and neighbors selected from among multiple neighbors of satisfied check nodes; and
control the second decoder to decode the decoding result of the first decoder using a submatrix of the parity check matrix corresponding to the extracted subgraphs.
2. The system of claim 1 , wherein the first decoder includes a bit-flipping (BF) decoder and the second decoder includes a min-sum (MS) decoder.
3. The system of claim 1 , wherein the particular condition includes when a checksum along consecutive decoding iterations using the first decoder is less than a threshold.
4. The system of claim 1 , wherein the particular condition includes when an oscillation of the first decoder is detected.
5. The system of claim 1 , wherein the selected neighbors have a set distance from the unsatisfied check nodes.
6. The system of claim 1 , wherein each of the subgraphs includes a first group of variable nodes connected to the unsatisfied check nodes and a second group of variable nodes connected to the satisfied check nodes and being neighbors from the first group of variable nodes with a distance-1 or a distance-2.
7. The system of claim 1 , wherein the first group of variable nodes include variable nodes with a first distribution from the unsatisfied check nodes and the second group of variable nodes include variable nodes with a second distribution from the unsatisfied check nodes and a distance-2 weight from the first group of variable nodes.
8. The system of claim 1 , wherein the controller terminates a decoding operation when a maximum number of iterations for the first decoder is reached.
9. A method for operating a system including a memory device storing data encoded with an error correction code and a controller, the method comprising:
controlling a first decoder with a first precision to decode the data read from the memory device, by using a parity check matrix for the error correction code;
extracting one or more subgraphs from the entire bipartite graph of the parity check matrix, which is defined by a plurality of variable nodes and a plurality of check nodes when a particular condition is satisfied, the one or more subgraphs to be extracted based on unsatisfied check nodes and neighbors selected from among multiple neighbors of satisfied check nodes; and
controlling a second decoder with a second precision greater than the first precision to decode the decoding result of the first decoder using a submatrix of the parity check matrix corresponding to the extracted subgraphs.
10. The method of claim 9 , wherein the first decoder includes a bit-flipping (BF) decoder and the second decoder includes a min-sum (MS) decoder.
11. The method of claim 9 , wherein the particular condition includes when a checksum along consecutive decoding iterations using the first decoder is less than a threshold.
12. The method of claim 9 , wherein the particular condition includes when an oscillation of the first decoder is detected.
13. The method of claim 9 , wherein the selected neighbors have a set distance from the unsatisfied check nodes.
14. The method of claim 9 , wherein each of the subgraphs includes a first group of variable nodes connected to the unsatisfied check nodes and a second group of variable nodes connected to the satisfied check nodes and being neighbors from the first group of variable nodes with a distance-1 or a distance-2.
15. The method of claim 9 , wherein the first group of variable nodes include variable nodes with a first distribution from the unsatisfied check nodes and the second group of variable nodes include variable nodes with a second distribution from the unsatisfied check nodes and a distance-2 weight from the first group of variable nodes.
16. The method of claim 9 , further comprising terminating a decoding operation when a maximum number of iterations for the first decoder is reached.