Minimizing redundancy for stuck bit coding

Patent metadata

Field	Value
Publication number	US-12450119-B2
Application number	US-202318533655-A
Country	US
Kind code	B2
Filing date	Dec 8, 2023
Priority date	Dec 8, 2023
Publication date	Oct 21, 2025
Grant date	Oct 21, 2025

Abstract

A storage device minimizes redundancy for stuck bit codes when writing a message to a memory device. A controller generates a set of masks that are codewords and that include values that correspond to stuck bit values. The set of masks may include full length codewords or shortened codewords. When the controller receives a message including a predefined number of label bits and determines that a location in the memory device where the message is be stored includes two stuck bits, the controller encodes the message to produce a first message codeword. The controller then locates a mask from the set of masks, wherein when the mask is added to the first message codeword, any two stuck message bits are masked. The controller computes a final message codeword using the first message codeword and the mask and stores the final message codeword on the memory device.

First claim

We claim:

1. A storage device to minimize redundancy for stuck bit codes when writing a message to a memory device and reading the message from the memory device, the storage device comprises:
one or more processors configured, individually or in combination, to:
generate a set of masks that are codewords and that include values that correspond to stuck bit values, wherein the set of masks includes one of full length codewords and shortened codewords;
receive a message including a predefined number of label bits and determine that a location in the memory device where the message is to be stored includes two stuck bits, encode the message to produce a first message codeword, locate a mask from the set of masks, wherein when the mask is added to the first message codeword, any two stuck message bits are masked, compute a final message codeword using the first message codeword and the mask, and store the final message codeword on the memory device; and
retrieve the final message codeword and errors from the memory device, decode the final message codeword to retrieve an output, obtain a mask label from the output, use the mask label to retrieve the mask, and apply the mask to the output to retrieve the message.

2. The storage device of claim 1 , wherein the one or more processors are configured, individually or in combination, to form an extended message by inserting zeros in label bit positions and to compute the first message codeword by adding parity to the extended message.

3. The storage device of claim 1 , wherein the mask label is a unique label that identifies the mask in the set of masks.

4. The storage device of claim 1 , wherein for full length codewords, the one or more processors are configured, individually or in combination, to encode masks in the set of masks by adding parity to the masks such that a first predefined number of bits of a codeword has the parity and a remaining number of bits of the codeword has the mask so that positions in the codeword without the parity cover the message.

5. The storage device of claim 4 , wherein the one or more processors are configured, individually or in combination, to cyclically shift each codeword three times to obtain the codewords that cover stuck bit combinations.

6. The storage device of claim 1 , wherein for shortened codewords, the one or more processors are configured, individually or in combination, to encode masks in the set of masks three times, wherein
during a first encoding the one or more processors configured, individually or in combination, to encode a mask by adding a first parity to a front of the mask such that a first predefined number of bits of a codeword has the parity and a remaining number of bits of the codeword has the mask and the remaining number of bits includes an unused portion;
during a second encoding the one or more processors are configured, individually or in combination, to encode the mask by adding a second parity to the front of the mask, a number of unused bits after the second parity, and the mask after the unused bits, wherein when the codeword is cyclic shifted, the mask may be at the front of the shortened codeword and the second parity may be at a back of the shortened codeword; and
during a third encoding the one or more processors are configured, individually or in combination, to encode the mask by dividing the mask into two, adding a third parity to the front of a second half of the mask, the number of unused bits after the second half of the mask, and a first half of the mask after the unused bits, wherein when the codeword is cyclic shifted, the first half of the mask may be at the front of a shortened codeword followed by the third parity and the second half of the mask.

7. The storage device of claim 1 , wherein the one or more processors are configured, individually or in combination, to perform a search to remove unnecessary masks and reduce a total number of masks in the set of masks and to store the set of masks.

8. The storage device of claim 1 , wherein the one or more processors are configured, individually or in combination, to store a set of label positions to cover labels for the set of masks.

9. A method for minimizing redundancy for stuck bit codes when writing a message to a memory device communicatively coupled to a storage device, the storage device comprises a controller to execute the method comprising:
generating a set of masks that are codewords and that include values that correspond to stuck bit values, wherein the set of masks includes one of full length codewords and shortened codewords;
receiving a message including a predefined number of label bits and determining that a location in the memory device where the message is to be stored includes two stuck bits;
encoding the message to produce a first message codeword;
locating a mask from the set of masks wherein when the mask is added to the first message codeword, any two stuck message bits are masked;
computing a final message codeword using the first message codeword and the mask; and
storing the final message codeword on the memory device.

10. The method of claim 9 , wherein the encoding comprises forming an extended message by inserting zeros in label bit positions and computing the first message codeword by adding parity to the extended message.

11. The method of claim 9 , wherein for the full length codewords the method comprises encoding masks in the set of masks by adding parity to the masks such that a first predefined number of bits of a codeword has the parity and a remaining number of bits of the codeword has the mask so that positions in the codeword without the parity cover the message.

12. The method of claim 9 , wherein generating the full length codewords comprises cyclically shifting each codeword three times to obtain the codewords that cover stuck bit combinations.

13. The method of claim 9 , wherein for the shortened codewords, the method comprises encoding masks in the set of masks three times.

14. The method of claim 13 , further comprising during a first encoding, the method comprises encoding the mask by adding a first parity to a front of the mask such that a first predefined number of bits of a codeword has the parity and a remaining number of bits of the codeword has the mask and the remaining number of bits includes an unused portion.

15. The method of claim 13 , further comprising during a second encoding, the method comprises encoding the mask by adding a second parity to a front of the mask, a number of unused bits after the second parity, and the mask after the unused bits, wherein when the codeword is cyclic shifted, the mask may be at the front of the shortened codeword and the second parity may be at a back of the shortened codeword.

16. The method of claim 13 , further comprising during a third encoding, the method comprises encoding the mask by dividing the mask into two, adding a third parity to a front of a second half of the mask, the number of unused bits after the second half of the mask, and a first half of the mask after the unused bits, wherein when the codeword is cyclic shifted, the first half of the mask may be at the front of a shortened codeword followed by the third parity and the second half of the mask.

17. The method of claim 9 , further comprising performing a search to remove unnecessary masks and reduce a total number of masks in the set of masks and storing the set of masks.

18. The method of claim 9 , further comprising storing a set of label positions to cover labels for the set of masks.

19. A

Assignees

• Western Digital Tech Inc

Inventors

• Djurdjevic Ivana
• Guyot Cyril
• Mateescu Robert

Classifications

• G06F11/102

  Error in check bits · CPC title

• G06F11/1068 Primary

  in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence) · CPC title