ECC and raid-type decoding

Patent metadata

Field	Value
Publication number	US-10536172-B2
Application number	US-201715817535-A
Country	US
Kind code	B2
Filing date	Nov 20, 2017
Priority date	Mar 4, 2016
Publication date	Jan 14, 2020
Grant date	Jan 14, 2020

Abstract

A device includes a memory and a controller coupled to the memory. The controller is configured to read a codeword from a physical location of the memory. The controller is configured to write an inverse bit string to the physical location of the memory, the inverse bit string based on the codeword. The controller is configured to read a representation of the inverse bit string from the physical location of the memory. The controller is further configured to designate one or more bits of the codeword as one or more erased bits based on the codeword and the representation of the inverse bit string.

First claim

What is claimed is:

1. A device comprising:
a memory; and
a controller coupled to the memory, wherein the controller is configured to:
read a codeword from a physical location of the memory,
write an inverse bit string to the physical location of the memory, the inverse bit string based on the codeword,
read a representation of the inverse bit string from the physical location of the memory, and
designate one or more bits of the codeword as one or more erased bits based on the codeword and the representation of the inverse bit string.

2. The device of claim 1 , wherein a value of each bit of the inverse bit string is inverted with respect to a value of a corresponding bit of the codeword.

3. The device of claim 1 , wherein the inverse bit string is generated and written to the memory in response to a decoding failure associated with the codeword, the inverse bit string overwriting the codeword at the memory.

4. The device of claim 1 , wherein the controller is further configured to perform an exclusive-or (XOR) operation on the codeword and on the representation of the inverse bit string to determine the one or more erased bits.

5. The device of claim 4 , wherein the one or more erased bits correspond to one or more bits that have the same value in the codeword and in the representation of the inverse bit string.

6. The device of claim 1 , further comprising a decoder configured to decode the codeword and a modified codeword to generate user data, wherein at least one of the one or more erased bits in the codeword has a different value than a corresponding bit in the modified codeword.

7. The device of claim 6 , wherein the decoder is further configured to perform erasure decoding based on the one or more erased bits to decode the codeword and the modified codeword.

8. The device of claim 6 , wherein the controller is further configured to generate the modified codeword by inverting a corresponding value of each bit of the one or more erased bits in the codeword.

9. The device of claim 6 , wherein the decoder comprises a Bose-Chaudhuri-Hocquenghem (BCH) decoder.

10. The device of claim 1 , wherein the memory comprises a storage-class memory.

11. A method performed by a controller of a data storage device, the method comprising:
reading a plurality of codewords from a memory, the plurality of codewords including at least a first codeword and a second codeword;
generating a third codeword based on the second codeword and parity data accessed from the memory, the parity data associated with the plurality of codewords; and
generating a fourth codeword based at least in part on reliability information associated with the third codeword, wherein generating the fourth codeword includes replacing at least one bit of the first codeword with at least one bit of the third codeword.

12. The method of claim 11 , wherein generating the third codeword comprises performing an exclusive-or (XOR) operation with respect to the second codeword and the parity data.

13. The method of claim 11 , further comprising:
performing one or more read operations associated with the second codeword to generate second reliability information associated with the second codeword, wherein the plurality of codewords includes a fifth codeword;
performing one or more read operations associated with the fifth codeword to generate third reliability information associated with the fifth codeword; and
performing an AND operation with respect to the second reliability information and the third reliability information to generate the reliability information associated with the third codeword.

14. The method of claim 11 , further comprising performing erasure decoding on the fourth codeword based on a designation of one or more erased bits in the first codeword and a designation of one or more erased bits in the third codeword.

15. The method of claim 14 , further comprising:
storing the first codeword, the second codeword, and the parity data in a buffer prior to generating the third codeword; and
replacing the first codeword in the buffer with the fourth codeword based on a successful erasure decoding of the fourth codeword.

16. The method of claim 15 , wherein:
generating the third codeword, generating the fourth codeword, and replacing the first codeword with the fourth codeword are performed during a first iteration of a decoding process of the plurality of codewords, and
each iteration of the decoding process includes, for each codeword stored at the buffer that is undecodable by an error correction code (ECC) decoder, selectively modifying one or more bits of the codeword based at least in part on reliability information associated with other codewords stored at the buffer.

17. The method of claim 16 , wherein iterations of the decoding process are performed until a target codeword of the plurality of codewords is decodable by the ECC decoder or until no codewords stored at the buffer are modified during a particular iteration.

18. An apparatus comprising:
means for designating erased bits of a first codeword read from a physical location of a means for storing data based on at least the first codeword and a second codeword read from the physical location of the means for storing data after performance of a write command associated with an inverse bit string at the physical location, the inverse bit string based on the first codeword; and
means for erasure decoding at least the first codeword based on the erased bits.

19. The apparatus of claim 18 , wherein:
the means for erasure decoding is further configured to erasure decode a modified first codeword, and
values of the erased bits of the first codeword are inverses of values of corresponding bits of the modified first codeword.

20. The apparatus of claim 18 , wherein the means for designating is further configured to designate the erased bits as part of an iterative process to decode at least one undecodable codeword of a plurality of codewords read from the means for storing data based on the plurality of codewords, reliability information associated with the plurality of codewords, and parity data associated with the plurality of codewords.

Assignees

• Western Digital Tech Inc

Inventors

• Ilani Ishai
• Alrod Idan
• Sharon Eran
• Ghaly Mai

Classifications

• H03M13/152

  Bose-Chaudhuri-Hocquenghem [BCH] codes · CPC title

• H03M13/1102

  Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes · CPC title

• H03M13/373

  with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes · CPC title

• H03M13/3761

  using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes · CPC title

• G06F11/1076

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title