ECC decoding using raid-type parity

Abstract

A device includes a memory and a controller. The controller is configured to read codewords of a data structure from the memory. The codewords include a number of undecodable codewords that are undecodable at an error correction coding (ECC) decoder according to a first correction scheme. The data structure further includes stripe parity corresponding to portions of the codewords encoded according to a stripe correction scheme. The controller is configured, in response to the number of the undecodable codewords exceeding an erasure correction capacity of the stripe correction scheme, to provide information from a stripe decoding operation to an input of a ECC decoding operation corresponding to an undecodable codeword.

What is claimed is: 
     
       1. A device comprising:
 a memory; and 
 a controller configured to read codewords of a data structure from the memory, wherein the codewords include a number of undecodable codewords that are undecodable at an error correction coding (ECC) decoder according to a first correction scheme, the data structure further including stripe parity corresponding to portions of the codewords encoded according to a stripe correction scheme, wherein the controller is further configured, in response to the number of the undecodable codewords exceeding an erasure correction capacity of the stripe correction scheme, to provide information including soft bits from a stripe decoding operation to an input of a ECC decoding operation corresponding to an undecodable codeword, the soft bits based on bit values of a reconstructed version of the undecodable codeword. 
 
     
     
       2. The device of  claim 1 , wherein the controller is configured to perform the stripe decoding operation to generate the reconstructed version of the undecodable codeword. 
     
     
       3. The device of  claim 2 , wherein the controller is configured to generate the information by accessing a lookup table to access soft bit values corresponding to exclusive-OR values. 
     
     
       4. The device of  claim 1 , wherein the stripe correction scheme corresponds to a redundant array of independent disks (RAID)-type exclusive-OR (XOR) scheme and wherein the first correction scheme corresponds to a low density parity check (LDPC) scheme. 
     
     
       5. The device of  claim 4 , wherein the controller is configured to perform decoding using belief propagation message-passing between the ECC decoder and a XOR stripe decoder. 
     
     
       6. The device of  claim 1 , further comprising a memory configured to store representations of each of the codewords, and wherein the controller is configured to update the stored representation of each particular codeword after processing the particular codeword at the ECC decoder. 
     
     
       7. The device of  claim 6 , wherein each representation includes data corresponding to log-likelihood ratios (LLRs), wherein the controller is configured to combine the LLRs from the codewords other than a particular codeword to generate particular information of the particular codeword from the stripe decoding operation, wherein the controller is configured to add the particular information to the particular codeword as an input to the ECC decoder. 
     
     
       8. The device of  claim 7 , wherein the controller is configured to subtract the particular information from an output of the ECC decoder to generate the representation of the particular codeword in response to the ECC decoder failing to decode the input. 
     
     
       9. The device of  claim 7 , wherein the controller is configured to retain the representation of the particular codeword in response to the ECC decoder failing to decode the input and to replace the representation of the particular codeword with hard bits output from the ECC decoder with indications of high reliability in response to the ECC decoder decoding the input. 
     
     
       10. The device of  claim 7 , wherein the data corresponding to the LLRs includes a hard bit and a 2-bit reliability value. 
     
     
       11. The device of  claim 7 , wherein the data corresponding to the LLRs includes a hard bit and a 1-bit reliability value. 
     
     
       12. A method comprising:
 in a data storage device that includes a controller and a memory, performing:
 reading codewords of a data structure from the memory, wherein the codewords include a number of undecodable codewords that are undecodable at an error correction coding (ECC) decoder according to a first correction scheme, the data structure further including stripe parity corresponding to portions of the codewords encoded according to a stripe correction scheme; 
 in response to the number of the undecodable codewords exceeding an erasure correction capacity of the stripe correction scheme, providing information from a stripe decoding operation to an input of an ECC decoding operation corresponding to an undecodable codeword; and 
 decoding using belief propagation message-passing between the ECC decoder and an exclusive-OR (XOR) stripe decoder. 
 
 
     
     
       13. The method of  claim 12 , wherein the controller performs the stripe decoding operation to generate a reconstructed version of the undecodable codeword, and wherein the information includes soft bits based on bit values of the reconstructed version of the undecodable codeword. 
     
     
       14. The method of  claim 13 , further comprising generating the information by accessing a lookup table to access soft bit values corresponding to exclusive-OR values. 
     
     
       15. The method of  claim 12 , wherein the stripe correction scheme corresponds to a redundant array of independent disks (RAID)-type exclusive-OR (XOR) scheme and wherein the first correction scheme corresponds to a low density parity check (LDPC) scheme. 
     
     
       16. The method of  claim 12 , further comprising updating stored representation of each particular codeword after processing the particular codeword at the ECC decoder. 
     
     
       17. The method of  claim 16 , wherein each representation includes data corresponding to log-likelihood ratios (LLRs), and further comprising:
 combining the LLRs from the codewords other than a particular codeword to generate particular information of the particular codeword from the stripe decoding operation; and 
 adding the particular information to the particular codeword as an input to the ECC decoder. 
 
     
     
       18. The method of  claim 17 , further comprising subtracting the particular information from an output of the ECC decoder to generate the representation of the particular codeword in response to the ECC decoder failing to decode the input. 
     
     
       19. The method of  claim 17 , further comprising:
 retaining the representation of the particular codeword in response to the ECC decoder failing to decode the input; or 
 replacing the representation of the particular codeword with hard bits output from the ECC decoder with indications of high reliability in response to the ECC decoder decoding the input. 
 
     
     
       20. A device comprising:
 a memory device; and 
 a controller configured to:
 read codewords of a data structure from the memory device, wherein the codewords include a number of undecodable codewords that are undecodable at an error correction coding (ECC) decoder according to a first correction scheme, the data structure further including stripe parity corresponding to portions of the codewords encoded according to a stripe correction scheme; 
 in response to the number of the undecodable codewords exceeding an erasure correction capacity of the stripe correction scheme, provide information from a stripe decoding operation to an input of a ECC decoding operation corresponding to an undecodable codeword; and 
 update a stored representation of each particular codeword after processing the particular codeword at the ECC decoder.