Symbol-based variable node updates for binary LDPC codes
Systems and methods for implementing data protection techniques with symbol-based variable node updates for binary low-density parity-check (LDPC) codes are described. A semiconductor memory (e.g., a NAND flash memory) may read a set of data from a set of memory cells, determine a set of data state probabilities for the set of data based on sensed threshold voltages for the set of memory cells, generate a valid codeword for the set of data using an iterative LDPC decoding with symbol-based variable node updates and the set of data state probabilities, and store the valid codeword within the semiconductor memory or transfer the valid codeword from the semiconductor memory. The iterative LDPC decoding may utilize a message passing algorithm in which outgoing messages from a plurality of multi-variable nodes are generated using incoming messages (e.g., log-likelihood ratios or L-values) from a plurality of check nodes.
1. An apparatus, comprising:
a semiconductor memory including a set of multi-level memory cells; and
one or more control circuits configured to:
determine a set of data state probabilities for the set of multi-level memory cells and
generate a graph that includes a multi-variable node with edges to a plurality of check nodes, the set of data state probabilities comprises probabilities for each possible data state of the set of multi-level memory cells,
generate a set of outgoing messages for the multi-variable node using the set of data state probabilities and
transfer the set of outgoing messages for the multi-variable node to the plurality of check nodes,
detect that a valid codeword has been found based on a set of incoming messages from the plurality of check nodes and
store the valid codeword using the semiconductor memory in response to detection that the valid codeword has been found, the determination of the set of data state probabilities for the set of multi-level memory cells includes only oversampling a first subset of data states less than each possible data state of the set of multi-level memory cells, the first subset of data states and a second subset of data states less than each possible data state of the set of multi-level memory cells combined comprise each possible data state of the set of multi-level memory cells, each data state within the first subset of data states is different from any of the data states within the second subset of data states.
2. The apparatus of claim 1 , wherein:
the set of multi-level memory cells comprises two-bits-per-cell memory cells and the determination of the set of data state probabilities for the set of multi-level memory cells includes oversampling only two data states out of the four possible data states for the two-bits-per-cell memory cells acid not oversampling the other two data states out of the four possible data states for the two-bits-per-cell memory cells.
3. The apparatus of claim 1 , wherein:
the one or more control circuits configured to determine a number of data states stored per memory cell for the set of multi-level memory cells and generate the multi-variable node based on the number of data states stored per memory cell for the set of multi-level memory cells.
4. The apparatus of claim 3 , wherein:
the one or more control circuits configured to generate a message of the set of outgoing messages using data state probabilities for each data state of the number of data states stored per memory cell for the set of multi-level memory cells.
5. The apparatus of claim 1 , wherein:
the one or more control circuits configured to determine a set of sensed threshold voltages for the set of multi-level memory cells and determine the set of data state probabilities for the set of multi-level memory cells based on the set of sensed threshold voltages, the one or more control circuits configured to acquire a mapping table and determine the set of data state probabilities using the mapping table and the set of sensed threshold voltages.
6. The apparatus of claim 5 , wherein:
the one or more control circuits configured to detect that a sensed threshold voltage of the set of sensed threshold voltages for a memory cell of the set of multi-level memory cells is within an edge region of a threshold voltage window and determine a subset of the set of data state probabilities based on detection that the sensed threshold voltage is within the edge region of the threshold voltage window.
7. The apparatus of claim 1 , wherein:
the set of multi-level memory cells comprises NAND Flash memory cells.
8. The apparatus of claim 1 , wherein:
the semiconductor memory comprises a non-volatile memory that is monolithically formed in out or more physical levels of memory cells having active areas disposed above a silicon substrate.
9. A method for operating a semiconductor memory, comprising:
determining a set of data state probabilities far a set of multi-level memory cells of the semiconductor memory;
generating a graph that includes a multi-variable node with edges to a plurality of check nodes, the set of data state probabilities comprises possibilities for each possible data state of the set of multi level memory cells, the determining the set of data state probabilities includes only oversampling a first subset of data states of the set of multi-level memory cells, the first subset of data states and a second subset of data states of the set of multi-level memory cells combined comprise each possible data state of the set of multi-level memory cells, each data state within the first subset of data states is different from any of the data states within the second subset of data states;
generating a set of outgoing messages for the multi-variable node using the set of data state probabilities, the set of outgoing messages comprises at least two different outgoing messages;
transferring the set of outgoing messages for the multi-variable node to the plurality of check nodes;
detecting that a valid codeword has been found subsequent to transferring the set of outgoing messages to the plurality of check nodes; and
storing the valid codeword using the semiconductor memory in response to detecting that the valid codeword has been found.
10. The method of claim 9 , further comprising:
determining a set of sensed threshold voltages for the set of multi-level memory cells of the semiconductor memory; and
determining the set of data state probabilities for the set of multi-level memory cells using the set of sensed threshold voltages, the determining the set of data state probabilities for the set of multi-level memory cells includes acquiring a mapping table and determining the set of data state probabilities using the mapping table and the set of sensed threshold voltages.
11. The method of claim 10 , wherein:
the determining the set of data state probabilities for the set of multi-level memory cells includes detecting that a sensed threshold voltage of the set of sensed threshold voltages for a memory cell of the set of multi-level memory cells is associated with one of a plurality of threshold voltage windows for a particular data state.
12. The method of claim 10 , wherein:
the determining the set of data state probabilities for the set of multi-level memory cells includes detecting that a sensed threshold voltage of the set of sensed threshold voltages for a memory cell of the set of multi-level memory cells is within an edge region of a threshold voltage window.
13. The method of claim 9 , wherein:
the set of data state probabilities for the set of multi-level memory cells includes a set of data state probabilities corresponding with each possible data state for a first memory cell of the set of multi-level memory cells.
14. The method of claim 9 , further comprising:
determining the number of data states stored per memory cell for the set of multi-level memory cells and generating the multi-variable node based on the number of data states stored per memory cell for the set of multi-level memory cells.
15. The method of claim 14 , wherein:
the generating the set of outgoing messages for the multi-variable node includes generating a message of the set of outgoing messages using data state probabilities for each data state of the number of data states stored per memory cell for the set of multi-level memory cells.
16. The method of claim 14 , wherein:
the number of data states stored per memory cell for the set of multi-level memory cells comprises eight data states.
17. The method of claim 14 , wherein:
the at least two different outgoing messages includes a first outgoing message generated using a plurality of input channel probabilities corresponding with each data state of the number of data states and a second outgoing message generated using the plurality of input channel probabilities.
18. The method of claim 9 , wherein:
the set of multi-level memory cells comprises NAND Flash memory cells;
the first subset of data states of the set of multi-level memory cells comprises two data states; and
the second subset of data states of the set of multi-level memory cells comprises at least one data state.
19. A semiconductor memory, comprising:
a set of memory cells, each memory cell of the set of memory cells comprises a multi-level memory cell; and
one or more council circuits configured to:
determine a set of stored threshold voltages for the set of memory cells and identify a set of data state probabilities for the set of stored threshold voltages,
generate a graph that includes a multi-variable node with edges to a plurality of check nodes, the set of data state probabilities comprises probabilities for each possible data state of the set of memory cells, the identification of the set of data state probabilities includes oversampling a first subset of data states of the set of memory cells, the first subset of data states and a second subset of data states of the set of memory cells combined comprise each possible data state of the set of memory cells, each data state within the first subset of data states is different from any of the data states within the second subset of data states,
determine a number of data states per memory cell for the set of memory cells and generate the multi-variable node based on the number of data states per memory cell for the set of memory cells,
generate a set of outgoing messages for the multi-variable node based on the set of data state probabilities and
transfer the set of outgoing messages for the multi-variable node to the plurality of check nodes,
detect that a valid codeword has been found based on a set of incoming messages from the plurality of check nodes and
store the valid codeword in response to detection that the valid codeword has been found.
20. The semiconductor memory of claim 19 , wherein:
the one or more control circuits configured to generate a message of the set of outgoing messages using data state probabilities for each data state of the number of data states per memory cell for the set of memory cells, the first subset of data states includes the B and C data states.