Soft-input soft-output component code decoder for generalized low-density parity-check codes

Abstract

Disclosed are devices, systems and methods for improved decoding of a binary linear code. An example method includes receiving a noisy codeword; computing a syndrome based on the noisy codeword; identifying N error patterns that correspond to the syndrome; selecting M error patterns from the N error patterns, wherein M≤N are positive integers, wherein a distance between a codeword corresponding to each of the M error patterns and the noisy codeword is less than a distance between a codeword corresponding to any other error pattern and the noisy codeword, and wherein the distance excludes a Hamming distance; modifying the noisy codeword based on each of the M error patterns one-at-a-time; and decoding the modified noisy codeword one-at-a-time until a successful decoding is achieved.

What is claimed is: 
     
       1. A method for improved decoding of a binary linear code, comprising:
 receiving a noisy codeword; 
 computing a syndrome based on the noisy codeword; 
 identifying N error patterns that correspond to the syndrome; 
 selecting M error patterns from the N error patterns, wherein N and M are positive integers, wherein M is less than or equal to N, wherein a distance between a codeword corresponding to each of the M error patterns and the noisy codeword is less than a distance between a codeword corresponding to any other error pattern and the noisy codeword, and wherein the distance excludes a Hamming distance; 
 modifying the noisy codeword based on each of the M error patterns one-at-a-time; and 
 decoding the modified noisy codeword one-at-a-time until a successful decoding is achieved. 
 
     
     
       2. The method of  claim 1 , wherein the binary linear code is a (n, k, d) Hamming code that is a component code of a generalized low-density parity-check (G-LDPC) code. 
     
     
       3. The method of  claim 2 , wherein n=7, k=3 and d=3. 
     
     
       4. The method of  claim 1 , wherein the distance is a Euclidean distance. 
     
     
       5. The method of  claim 1 , wherein selecting the M error patterns from the N error patterns comprises:
 calculating a reliability metric for each of the N error patterns; and 
 selecting an error pattern of the M error patterns based on a comparison of the reliability metric of the error pattern and a first threshold. 
 
     
     
       6. The method of  claim 5 , wherein the reliability metric is a log-likelihood ratio. 
     
     
       7. The method of  claim 5 , wherein the reliability metric is a probability. 
     
     
       8. The method of  claim 5 , wherein selecting the M error patterns from the N error patterns is further based on a comparison of a sum of the reliability metric of each of the M error patterns and a second threshold. 
     
     
       9. The method of  claim 1 , wherein achieving the successful decoding corresponds to a successful read operation in a non-volatile memory. 
     
     
       10. The method of  claim 9 , wherein the non-volatile memory is a NAND flash memory. 
     
     
       11. A system for improved decoding of a binary linear code, comprising:
 a processor and a memory including instructions stored thereupon, wherein the instructions upon execution by the processor cause the processor to:
 receive a noisy codeword; 
 compute a syndrome based on the noisy codeword; 
 identify N error patterns that correspond to the syndrome; 
 select M error patterns from the N error patterns, wherein N and M are positive integers, wherein M is less than or equal to N, wherein a distance between a codeword corresponding to each of the M error patterns and the noisy codeword is less than a distance between a codeword corresponding to any other error pattern and the noisy codeword, and wherein the distance excludes a Hamming distance; 
 modify the noisy codeword based on each of the M error patterns one-at-a-time; and 
 decode the modified noisy codeword one-at-a-time until a successful decoding is achieved. 
 
 
     
     
       12. The system of  claim 11 , wherein the binary linear code is a (7, 4, 3) Hamming code that is a component code of a generalized low-density parity-check (G-LDPC) code. 
     
     
       13. The system of  claim 11 , wherein the instructions upon execution by the processor further cause the processor, as part of selecting the M error patterns from the N error patterns, to:
 calculate a reliability metric for each of the N error patterns; and 
 select an error pattern of the M error patterns based on a comparison of the reliability metric of the error pattern and a first threshold. 
 
     
     
       14. The system of  claim 13 , wherein the reliability metric is a probability or a log-likelihood ratio. 
     
     
       15. The system of  claim 13 , wherein selecting the M error patterns from the N error patterns is further based on a comparison of a sum of the reliability metric of each of the M error patterns and a second threshold. 
     
     
       16. The system of  claim 11 , wherein the distance is a Euclidean distance. 
     
     
       17. A non-transitory computer-readable storage medium having instructions stored thereupon for improved decoding of a binary linear code, comprising:
 instructions for receiving a noisy codeword; 
 instructions for computing a syndrome based on the noisy codeword; 
 instructions for identifying N error patterns that correspond to the syndrome; 
 instructions for selecting M error patterns from the N error patterns, wherein N and M are positive integers, wherein M is less than or equal to N, wherein a distance between a codeword corresponding to each of the M error patterns and the noisy codeword is less than a distance between a codeword corresponding to any other error pattern and the noisy codeword, and wherein the distance excludes a Hamming distance; 
 instructions for modifying the noisy codeword based on each of the M error patterns one-at-a-time; and 
 instructions for decoding the modified noisy codeword one-at-a-time until a successful decoding is achieved. 
 
     
     
       18. The storage medium of  claim 17 , wherein the binary linear code is a (7, 4, 3) Hamming code that is a component code of a generalized low-density parity-check (G-LDPC) code. 
     
     
       19. The storage medium of  claim 17 , wherein the instructions for selecting the M error patterns from the N error patterns comprises:
 instructions for calculating a reliability metric for each of the N error patterns; and 
 instructions for selecting an error pattern of the M error patterns based on a comparison of the reliability metric of the error pattern and a first threshold. 
 
     
     
       20. The storage medium of  claim 19 , wherein the reliability metric is a probability or a log-likelihood ratio. 
     
     
       21. The storage medium of  claim 19 , wherein selecting the M error patterns from the N error patterns is further based on a comparison of a sum of the reliability metric of each of the M error patterns and a second threshold. 
     
     
       22. The storage medium of  claim 17 , wherein achieving the successful decoding corresponds to a successful read operation in a NAND flash memory.