IP Library › Granted Patent US 10,396,817
Granted Patent B2
US 10,396,817 · App. 15/368,973 · Granted Aug 27, 2019

Priori information based post-processing in low-density parity-check code decoders

View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 10,396,817
App. No.
15/368,973
Granted
Aug 27, 2019
Kind
B2
Abstract

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.

Claims (73)

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 a trapping set of a low-density parity-check code associated with the codeword;

select one of the backtracking nodes based on a probability that each of the one or more variable nodes belongs to a trapping set;

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 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:

select a hard error location from one or more hard error locations associated with bits in the codeword; and

erase a log-likelihood ratio associated with the selected hard error location.

3. The memory storage system of claim 2 , wherein the computer executable program code is further configured to receiving a list of one or more hard error locations associated with a bit in the codeword.

4. The memory storage system of claim 2 , wherein the computer executable program code is further configured to:

iteratively select a previously unselected hard error location; and

flip a log-likelihood ratio associated with the previously unselected hard error location.

5. The memory storage system of claim 4 , wherein the computer executable program code is further configured to saturate the flipped log-likelihood ratio.

6. The memory storage system of claim 1 , wherein the computer executable program code is further configured to:

identify a plurality of hard error locations associated with bits in the codeword; and

erase a plurality of log-likelihood ratios, each associated with an identified hard error location.

7. 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.

8. The memory storage system of claim 1 , wherein the computer executable program code is further configured to:

iteratively select a previously unselected backtracking node; and

flip a log-likelihood ratio associated with the previously unselected backtracking node.

9. A method for decoding low-density parity-check encoded words, comprising:

identifying one or more variable nodes associated with one or more unsatisfied check nodes in a codeword;

identifying all backtracking nodes also belonging to a trapping set of a low-density parity-check code associated with the codeword;

selecting one of the backtracking nodes based on a probability that each of the one or more variable nodes belongs to a trapping set;

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.

10. The method of claim 9 , further comprising:

selecting a hard error location from one or more hard error locations associated with bits in the codeword; and

erasing a log-likelihood ratio associated with the selected hard error location.

11. The method of claim 10 , further comprising receiving a list of one or more hard error locations associated with a bit in the codeword.

12. The method of claim 10 , further comprising identifying one or more hard error locations associated with bits in the codeword.

13. The method of claim 10 , further comprising:

iteratively selecting a previously unselected hard error location; and

flipping a log-likelihood ratio associated with the previously unselected hard error location.

14. The method of claim 13 , further comprising saturating the flipped log-likelihood ratio.

15. The computer apparatus of claim 13 , further comprising:

iteratively selecting a previously unselected trapping set variable node from the one or more trapping set variable nodes; and

flipping a log-likelihood ratio associated with the previously unselected trapping set variable node.

16. 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:

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 a trapping set of a low-density parity-check code associated with the codeword;

select one of the backtracking nodes based on a probability that each of the one or more variable nodes belongs to a trapping set;

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 based on the erased log-likelihood ratios.

17. The apparatus of claim 16 , wherein the computer executable program code is further configured to:

iteratively select a hard error location from a list of hard error locations associated with bits in the codeword;

flip a log-likelihood ratio associated with the selected hard error location; and

saturate the flipped log-likelihood ratio.

18. The apparatus of claim 16 , wherein the computer executable program code is further configured to:

identify the plurality of hard error locations associated with bits in the codeword; and

erase a plurality of log-likelihood ratios, each associated with an identified hard error location.

19. The apparatus of claim 16 , 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.

20. The apparatus of claim 16 , wherein the computer executable program code is further configured to:

iteratively select a previously unselected backtracking node; and

flip a log-likelihood ratio associated with the previously unselected backtracking node.