Non-binary low-density parity check (LDPC) decoding using trellis maximization
Data storage systems may include a solid-state memory array configured to store encoded data units and a controller configured to decode the encoded data units. Decoding the encoded data units may include updating a check node of a plurality of check nodes associated with a parity check matrix by identifying first and second sets of variable nodes in a plurality of variable nodes associated in the parity check matrix with the check node and constructing a trellis based on the second set of variable nodes. The trellis may be used to determine a message and, based at least in part on the message, a first set of messages to be sent from the check node to the first set of variable nodes may be determined. A second set of messages to be sent from the check node to each variable node in the second set of variable nodes also may be determined.
1. A data storage system, comprising:
a solid-state memory array configured to store a plurality of encoded data units; and
a controller configured to decode at least one encoded data unit of the plurality of encoded data units by updating a check node of a plurality of check nodes associated with a parity check matrix, the controller configured to update the check node by:
identifying first and second sets of variable nodes in a plurality of variable nodes associated in the parity check matrix with the check node;
constructing a trellis based on the second set of variable nodes and using the trellis to determine a message;
based at least in part on the message, determining a first set of messages to be sent from the check node to the first set of variable nodes; and
determining a second set of messages to be sent from the check node to each variable node in the second set of variable nodes.
2. The data storage system of claim 1 , wherein the controller is further configured to determine a message to be sent from the check node to a variable node in the second set of variable nodes by: 1) constructing an additional trellis based on the second set of variable nodes excluding the variable node for which the message is being determined, 2) using the additional trellis to determine the message to be sent to the variable node.
3. The data storage system of claim 2 , wherein the controller is further configured to determine the message to be sent to the variable node by: 1) using the additional trellis to determine an additional resulting message, 2) permuting the additional resulting message by a non-binary symbol, and 3) send the permuted additional resulting message to the variable node.
4. The data storage system of claim 1 , wherein the controller is further configured to determine a message to be sent from the check node to a variable node in the first set of variable nodes by: 1) selecting a largest likelihood from a plurality of likelihoods for a plurality of non-binary symbols associated with the variable node and 2) modifying the message with a non-binary symbol corresponding to the selected largest likelihood.
5. The data storage system of claim 1 , wherein the controller is further configured to detect and correct errors in the at least one encoded data unit stored in the solid-state memory array in order to determine a non-binary data value from the at least one encoded data unit.
6. The data storage system of claim 1 , wherein the controller is further configured to identify the first and second sets of variable nodes by: 1) determining a plurality of reliability metrics for the plurality of variable nodes and 2) assigning the variable nodes to one of the first and second sets based on comparing the plurality of reliability metrics with at least one reliability threshold.
7. An electronic system, comprising
a decoder configured to decode an encoded data unit received from a data source by updating a check node of a plurality of check nodes associated with a parity check matrix,
the decoder configured to update the check node by:
identifying first and second sets of variable nodes in a plurality of variable nodes associated in the parity check matrix with the check node, at least some of the variable nodes in the first set not being part of the second set;
constructing a trellis based on the second set of variable nodes and using the trellis to determine a resulting message;
based at least in part on the resulting message, determining a first set of messages to be sent from the check node to each variable node in the first set of variable nodes and sending the determined first set of messages to the first set of variable nodes; and
determining a second set of messages to be sent from the check node to each variable node in the second set of variable nodes and sending the determined second set of messages to the second set of variable nodes.
8. The electronic system of claim 7 , further comprising a solid-state memory array configured to store the plurality of encoded data units, and the plurality of encoded data units comprises data received from a host system.
9. The electronic system of claim 8 , wherein the solid-state memory array comprises multi-level cell (MLC) NAND memory configured to store non-binary data.
10. The electronic system of claim 7 , wherein the decoder is further configured to construct the trellis by: 1) associating a plurality of transitions between a plurality of trellis nodes with variable nodes in the second set of variable nodes and 2) connecting the plurality of trellis nodes by the plurality of transitions.
11. The electronic system of claim 10 , wherein:
the decoder is further configured to connect a first plurality of trellis nodes corresponding to a first variable node with a second plurality of trellis nodes corresponding to a second variable node by a subset of the plurality of transitions, each transition assigned a corresponding transition likelihood; and
the decoder is further configured to: 1) determine a plurality of summations of each transition likelihood associated with the plurality of transitions with a corresponding node likelihood assigned to each of the first plurality of trellis nodes and 2) select a transition corresponding to a maximum cumulative likelihood from the plurality of summations, the selected transition indicative of a most likely transition from the first variable node to the second variable node.
12. The electronic system of claim 10 , wherein the decoder is further configured to:
connect a first plurality of trellis nodes corresponding to a first variable node with a second plurality of trellis nodes corresponding to a second variable node by a subset of the plurality of transitions, each transition assigned a corresponding transition likelihood; and
select a transition with a maximum transition likelihood from the plurality of transitions, the selected transition corresponding to a most likely transition from the first variable node to the second variable node.
13. The electronic system of claim 10 , wherein the decoder is further configured to associate the plurality of transitions with a plurality of log-likelihood ratios grouped in a plurality of sets of log-likelihood ratios, each set normalized by largest log-likelihood ratio from the set.
14. The electronic system of claim 7 , wherein the decoder is further configured to: 1) select a largest likelihood from a plurality of likelihoods for a plurality of non-binary symbols associated with each variable node in the first set of variable nodes and 2) determine a plurality of non-binary symbols corresponding to a plurality of selected largest likelihoods.
15. The electronic system of claim 14 , wherein the decoder is further configured to determine the first set of messages to be sent from the check node to each variable node in the first set of variable nodes by permuting the resulting message with the determined plurality of non-binary symbols.
16. The electronic system of claim 14 , wherein the decoder is further configured to combine at least some of the plurality of non-binary symbols to determine a combined non-binary symbol and permute the resulting message with the combined non-binary symbol.
17. The electronic system of claim 16 , wherein the decoder is further configured to combine the plurality of non-binary symbols by performing Galois field addition on at least some of the plurality of non-binary symbols to determine the combined non-binary symbol.
18. The electronic system of claim 16 , wherein the decoder is further configured to determine the second set of messages to be sent from the check node to each variable node in the second set of variable nodes by: 1) for a variable node in the second set of variable nodes, constructing an additional trellis based on the second set of variable nodes excluding the variable node, 2) using the additional trellis to determine an additional resulting message, 3) permuting the additional resulting message by the combined non-binary symbol, and 4) send the permuted additional resulting message from the check node to the variable node.
19. The electronic system of claim 7 , wherein the decoder is further configured to perform non-binary low-density parity check (LDPC) decoding in order to correctly detect a non-binary message from the encoded data unit.
20. The electronic system of claim 7 , wherein the decoder is further configured to identify the first and second sets of variable nodes by: 1) determining a plurality of reliability metrics for the plurality of variable nodes and 2) assigning the variable nodes to one of the first and second sets based on comparing the plurality of reliability metrics with at least one reliability threshold.
21. The electronic system of claim 7 , wherein the decoder is further configured to: 1) identify the first and second sets of variable nodes during performing a decoding iteration and 2) identify third and fourth sets of variable nodes different from the first and second sets of variable nodes during performing a different decoding iteration.
22. A method for decoding data, the method comprising:
decoding at least one encoded data unit received from a data source by updating a check node of a plurality of check nodes associated with a parity check matrix,
wherein updating the check node comprises:
identifying first and second sets of variable nodes in a plurality of variable nodes associated in the parity check matrix with the check node, at least some of the variable nodes in the first set not being part of the second set;
constructing a trellis based on the second set of variable nodes and using the trellis to determine a message;
based at least in part on the message, determining a first set of messages to be sent from the check node to each variable node in the first set of variable nodes and sending the determined first set of messages to the first set of variable nodes; and
determining a second set of messages to be sent from the check node to each variable node in the second set of variable nodes and sending the determined second set of messages to the second set of variable nodes,
wherein the method is performed by a decoder.
23. The method of claim 22 , further comprising determining a message to be sent from the check node to a variable node in the second set of variable nodes by: 1) constructing an additional trellis based on the second set of variable nodes excluding the variable node for which the message is being determined, 2) using the additional trellis to determine the message to be sent to the variable node.
24. The method of claim 23 , further comprising determining the message to be sent to the variable node by: 1) using the additional trellis to determine an additional resulting message, 2) permuting the additional resulting message by a non-binary symbol, and 3) send the permuted additional resulting message to the variable node.
25. The method of claim 22 , further comprising determining a message to be sent from the check node to a variable node in the first set of variable nodes by: 1) selecting a largest likelihood from a plurality of likelihoods for a plurality of non-binary symbols associated with the variable node and 2) modifying the message with a non-binary symbol corresponding to the selected largest likelihood.
26. The method of claim 22 , further comprising performing non-binary low-density parity check (LDPC) decoding in order to correctly detect a non-binary message from the at least one encoded data unit.
27. The method of claim 22 , further comprising identifying the first and second sets of variable nodes by: 1) determining a plurality of reliability metrics for the plurality of variable nodes and 2) assigning the variable nodes to one of the first and second sets based on comparing the plurality of reliability metrics with at least one reliability threshold.