Mitigation of error correction failure due to trapping sets

1. An apparatus comprising:

a memory interface configured to process a plurality of read/write operations to/from a memory;

a host interface configured to receive data from a host; and

a control circuit configured to

generate a trapping set list of a plurality of trapping sets of a low-density parity check code,

access information that characterizes a plurality of occurrence probabilities of the plurality of trapping sets in response to receiving the data to be encoded,

classify a plurality of bit positions of the plurality of trapping sets as belonging to either a user bits field or a parity bits field of a codeword,

encode the data using the low-density parity check code to generate the codeword, and

transfer the codeword to the memory interface to write the codeword in the memory,

wherein

the memory interface, the host interface and the control circuit are part of a solid-state drive,

the generation of the codeword includes at least one of a shortening or a puncturing of a plurality of bit locations in the codeword in response to the classification of the plurality of bit positions of the plurality of trapping sets,

the plurality of bit locations that are shortened or punctured are selected based on the information that characterizes the plurality of occurrence probabilities of the plurality of trapping sets,

the plurality of bit locations that are shortened or punctured are selected independent of the trapping set list of the plurality of trapping sets,

all of the data is held in the plurality of bit locations of the codeword other than the bit locations that are shortened or punctured, and

the bit locations selected reduce a probability that an error correction of the codeword after the codeword is read from the memory of the solid-state drive fails due to the plurality of trapping sets.

2. The apparatus according to claim 1 , wherein

the codeword is shortened by setting a subset less than all of the plurality of bit locations to a predetermined value, and

each of the plurality of bit locations set to the predetermined value is part of one or more of the plurality of trapping sets.

3. The apparatus according to claim 2 , wherein

the selection of the plurality of bit locations that are set to the predetermined value is limited to the user bits field.

4. The apparatus according to claim 2 , wherein at least two of the plurality of bit locations that are set to the predetermined value are separated by one or more of the plurality of bit locations that hold the data.

5. The apparatus according to claim 1 , wherein

the codeword is punctured by removing a subset less than all of the plurality of bit locations, and

one or more of the plurality of bit locations removed is not part of any of the plurality of trapping sets.

6. The apparatus according to claim 5 , wherein

the selection of the plurality of bit locations that are removed comprises at least one location in the user bits field and at least one location in the parity bits field.

7. The apparatus according to claim 5 , wherein at least two of the plurality of bit locations that are removed are separated by one or more of the plurality of bit locations that hold the data.

8. The apparatus according to claim 1 , wherein before the codeword is stored in the memory the control circuit is further configured to remove the plurality of bit locations in the codeword that are shortened or punctured.

9. The apparatus according to claim 1 , where the control circuit is further configured to

read the codeword encoded with the low-density parity check code from the memory,

attempt to decode the codeword,

access the information that characterizes the plurality of occurrence probabilities of the plurality of trapping sets in response to a failure to decode the codeword, and

error correct the codeword over a plurality of cycles using the information that characterizes the plurality of occurrence probabilities of the plurality of trapping sets,

wherein

the error correction includes detection of a plurality of frequencies of respective unsatisfied check nodes produced during the plurality of cycles,

a plurality of log-likelihood ratio values used in the plurality of cycles are adjusted based on both the plurality of frequencies and the information that characterizes the plurality of occurrence probabilities of the plurality of trapping sets, and

the adjustment of the plurality of log-likelihood ratio values reduces the probability that the error correction of the codeword fails due to the plurality of trapping sets.

10. A solid-state drive comprising:

a memory configured to store data;

a host interface configured to receive data from a host; and

a controller configured to

generate a trapping set list of a plurality of trapping sets of a low-density parity check code,

access information that characterizes a plurality of occurrence probabilities of the plurality of trapping sets in response to receiving the data to be encoded,

classify a plurality of bit positions of the plurality of trapping sets as belonging to either a user bits field or a parity bits field of a codeword,

encode the data using the low-density parity check code to generate the codeword, and

write the codeword in the memory,

wherein

the generation of the codeword includes at least one of a shortening or a puncturing of a plurality of bit locations in the codeword in response to the classification of the plurality of bit positions of the plurality of trapping sets,

the plurality of bit locations that are shortened or punctured are selected based on the information that characterizes the plurality of occurrence probabilities of the plurality of trapping sets,

the plurality of bit locations that are shortened or punctured are selected independent of the trapping set list of the plurality of trapping sets,

all of the data is held in the plurality of bit locations of the codeword other than the bit locations that are shortened or punctured, and

the bit locations selected reduce a probability that an error correction of the codeword after the codeword is read from the memory of the solid-state drive fails due to the plurality of trapping sets.

11. A solid-state drive comprising:

a memory interface configured to process a plurality of read/write operations to/from a memory;

a host interface configured to present data to a host; and

a control circuit configured to

generate a trapping set list of a plurality of trapping sets of a low-density parity check code,

read a codeword encoded with the low-density parity check code from the memory,

classifying a plurality of bit positions of the plurality of trapping sets as belonging to either a user bits field or a parity bits field of the codeword,

lengthen the codeword to account for a plurality of bit locations that have been at least one of shortened or punctured in response to the classification of the plurality of bit positions of the plurality of trapping sets,

attempt to decode the codeword to recover data,

access information that characterizes a plurality of occurrence probabilities of the plurality of trapping sets in response to a failure to decode the codeword,

error correct the codeword over a plurality of cycles using the information that characterizes the plurality of occurrence probabilities of the plurality of trapping sets, and

transfer the error corrected codeword to the host interface for presentation to the host,

wherein

all of the data is held in the plurality of bit locations of the codeword other than the bit locations that were shortened or punctured,

the error correction includes detection of a plurality of frequencies of respective unsatisfied check nodes produced during the plurality of cycles,

a plurality of log-likelihood ratio values used in the plurality of cycles are adjusted based on both the plurality of frequencies and the information that characterizes the plurality of occurrence probabilities of the plurality of trapping sets, and

the adjustment of the plurality of log-likelihood ratio values reduces a probability that the error correction of the codeword read from the memory of the solid-state drive fails due to the plurality of trapping sets.

12. The solid-state drive according to claim 11 , wherein

the adjustment of the plurality of log-likelihood ratio values dampens all of the plurality of log-likelihood ratio values after each of the plurality of cycles, and

an amount of dampening in each of the plurality of cycles is based on a number of the plurality of cycles that have previously failed to correct the codeword.

13. The solid-state drive according to claim 11 , wherein the plurality of log-likelihood ratio values comprise a plurality of output log-likelihood ratio values generated during the attempt to decode the codeword.

14. The solid-state drive according to claim 11 , wherein the plurality of log-likelihood ratio values comprise a plurality of posterior log-likelihood ratio values.

15. The solid-state drive according to claim 11 , wherein

the information that characterizes the plurality of occurrence probabilities of the plurality of trapping sets comprises a characterization list that characterizes less than all of the plurality of trapping sets, and

the control circuit is further configured to determine a partial match between the plurality of unsatisfied check nodes and the characterization list to determine the plurality of log-likelihood ratio values to adjust.

16. The solid-state drive according to claim 11 , wherein the information that characterizes the plurality of occurrence probabilities of the plurality of trapping sets comprises a characterization list that characterizes at least one of a plurality of non-dominant trapping sets or a plurality of dominant trapping sets.

17. The solid-state drive according to claim 11 , wherein the control circuit is further configured to select among the plurality of log-likelihood ratio values to adjust based on a plurality of posterior log-likelihood ratio values associated with a plurality of variable nodes.

18. The solid-state drive according to claim 11 , wherein the control circuit is further configured to select among the plurality of log-likelihood ratio values to adjust based on how many of the plurality of unsatisfied check nodes are connected to each of a plurality of variable nodes.