Priori information based post-processing in low-density parity-check code decoders
View Patent ↗A low-density parity-check decoder utilizes information about hard errors in a storage medium to identify bit locations to flip log-likelihood ratios while attempting to decode codewords. The decoder iteratively flips and saturates log-likelihood ratios for bits at hard error locations and re-decodes until a valid codeword is produced. The decoder also identifies variable nodes associated with trapping sets for iterative log-likelihood ratio bit flipping.
1. A memory storage system, comprising:
a processor;
memory connected to the processor;
a data storage element connected to the processor; and
non-transitory computer executable program code embodied in the memory, configured to execute on the processor,
wherein the computer executable program code is configured to:
receive a low-density parity-check encoded codeword;
identify one or more variable nodes associated with one or more unsatisfied check nodes in the codeword;
identify all backtracking nodes also belonging to trapping sets;
identify one or more backtracking nodes based on a probability that each of the one or more variable nodes belongs to a trapping set of a low-density parity-check code;
select one of the backtracking nodes;
flip a log-likelihood ratio associated with the selected backtracking node;
saturate a magnitude of the log-likelihood ratio associated with the selected backtracking node;
detect two or more hard error locations associated with bits in the codeword;
erase multiple log-likelihood ratios associated with the detected hard error locations; and
decode the codeword based on the erased log-likelihood ratios.
2. The memory storage system of claim 1 , wherein the computer executable program code is further configured to receive a list of one or more hard error locations associated with a bit in a codeword.
3. The memory storage system of claim 1 , wherein the computer executable program code is further configured to:
select a log-likelihood ratio associated with a hard error location in the two or more hard error locations; and
saturate the selected log-likelihood ratio.
4. The memory storage system of claim 1 , wherein the computer executable program code is further configured to flip each log-likelihood ratio associated with the hard error locations during a post-processing procedure after an erasure decoding failure.
5. The memory storage system of claim 1 , wherein the computer executable program code is further configured to:
identify one or more variable nodes associated with one or more unsatisfied check nodes in the codeword;
identify one or more trapping set variable nodes from the one or more variable nodes based on a probability that each of the one or more variable nodes belongs to a trapping set of a low-density parity-check code;
select one of the trapping set variable nodes;
flip a log-likelihood ratio associated with the selected trapping set variable node; and
decode the codeword.
6. A method for decoding low-density parity-check encoded words, comprising:
identifying one or more hard error locations associated with bits in a codeword;
selecting one hard error location;
erasing a log-likelihood ratio associated with the selected hard error location;
decoding the codeword based on the erased log-likelihood ratio;
identifying one or more variable nodes associated with one or more unsatisfied check nodes in the codeword;
identifying all backtracking nodes also belonging to trapping sets;
identifying one or more backtracking nodes based on a probability that each of the one or more variable nodes belongs to a trapping set of a low-density parity-check code;
selecting one of the backtracking nodes;
flipping a log-likelihood ratio associated with the selected backtracking node;
saturating a magnitude of the log-likelihood ratio associated with the selected backtracking node; and
decoding the codeword.
7. The method of claim 6 , further comprising receiving a list of one or more hard error locations associated with a bit in a codeword.
8. The method of claim 6 , further comprising saturating the log-likelihood ratio.
9. The method of claim 6 , further comprising:
iteratively selecting a previously unselected hard error location;
flipping a log-likelihood ratio associated with the previously unselected hard error location; and
decoding the codeword based on the modified log-likelihood ratio.
10. The method of claim 9 , further comprising saturating the log-likelihood ratio.
11. The computer apparatus of claim 10 , further comprising:
iteratively selecting a previously unselected trapping set variable node from the one or more trapping set variable nodes;
flipping a log-likelihood ratio associated with the previously unselected trapping set variable node; and
decoding the codeword based on the modified log-likelihood ratio.
12. A computer apparatus, comprising:
a processor; and
non-transitory computer executable program code embodied in a memory, configured to execute on the processor,
wherein the computer executable program code is configured to:
identify one or more hard error locations associated with bits in a low-density parity-check codeword;
detect two or more hard error locations associated with bits in the codeword;
erase multiple log-likelihood ratios associated with the detected hard error locations;
decode the codeword based on the erased log-likelihood ratios
identify one or more variable nodes associated with one or more unsatisfied check nodes in the codeword;
identify all backtracking nodes also belonging to trapping sets;
identify one or more backtracking nodes based on a probability that each of the one or more variable nodes belongs to a trapping set of a low-density parity-check code;
select one of the backtracking nodes;
flip a log-likelihood ratio associated with the selected backtracking node;
saturate a magnitude of the log-likelihood ratio associated with the selected backtracking node; and
decode the codeword.
13. The computer apparatus of claim 12 , wherein the computer executable program code is further configured to flip the log-likelihood ratios associated with the detected hard error locations during a post-processing procedure after an erasure decoding failure.
14. The computer apparatus of claim 12 , wherein and the computer executable program code is further configured to:
select a log-likelihood ratio associated with a hard error location in the two or more hard error locations; and
saturate the log likelihood ratio.
15. The computer apparatus of claim 12 , wherein the computer executable program code is further configured to:
iteratively select a previously unselected trapping set variable node from the one or more trapping set variable nodes;
flip a log-likelihood ratio associated with the previously unselected trapping set variable node; and
decode the codeword based on the flipped log-likelihood ratio.