Stuck bits encoding and decoding on a storage device

Patent metadata

Field	Value
Publication number	US-12362029-B2
Application number	US-202318389155-A
Country	US
Kind code	B2
Filing date	Nov 13, 2023
Priority date	Nov 13, 2023
Publication date	Jul 15, 2025
Grant date	Jul 15, 2025

Abstract

A storage device processes storage-free stuck bits information when writing and reading stored on the memory device. A controller encodes the data with cyclic error-correcting codes to generate a codeword and determines that a location in the memory device where codeword is be stored includes a stuck bit. Rather than storing the stuck bits information, when storing the codeword, the controller generates an encoding mask, adds the encoding mask to the codeword to generate encoded data, and stores the encoded data on the memory device. When reading the encoded data, the controller generates a list of decoding masks including the encoding mask, goes through the lists and adds a decoding mask to the encoded data. The controller decodes the encoded data with the encoding mask from the list and returns the data.

First claim

We claim:

1. A storage device to process storage-free stuck bits information when writing data to a memory device and reading the data from the memory device, the storage device comprises:
a controller to:
encode the data with cyclic error-correcting codes to generate a codeword and determine that a location in the memory device where the codeword is to be stored includes a stuck bit;
store the codeword, wherein in storing the codeword, the controller generates an encoding mask, adds the encoding mask to the codeword to generate mask encoded data, and stores the mask encoded data on the memory device wherein a value in one or more bits in the mask encoded data is the same as a value in one or more stuck bits on the memory device; and
read the mask encoded data, wherein in reading the mask encoded data, the controller generates a list of decoding masks including the encoding mask, goes through the list and adds a decoding mask to the mask encoded data, decodes the mask encoded data with the encoding mask from the list, and returns the data.

2. The storage device of claim 1 , wherein in storing the codeword, the controller determines that the location includes one stuck bit and one of:
determines that a value of a bit in the codeword to be stored in a stuck bit location is the same as a stuck bit value, and the controller stores the codeword on the memory device, and
determines that the value of the bit in the codeword to be stored in the stuck bit location is not the same as the stuck bit value, and the controller inverts the codeword and stores an inverted codeword on the memory device.

3. The storage device of claim 1 , wherein in reading the mask encoded data the controller executes a first stuck bit scheme to obtain the data, wherein the controller reads the codeword, adds a first mask to the codeword, decodes the codeword, and if decoding of the codeword is successful, the controller returns the data, and
if decoding the codeword added to the first mask is not successful, the controller adds a second mask to the codeword, decodes the codeword, and if decoding of the codeword is successful, the controller returns the data.

4. The storage device of claim 1 , wherein in storing the codeword, the controller determines that the location includes two stuck bits, and the controller executes a second stuck bit scheme, wherein the controller adds one of a predefined number of masks to the codeword to generate the mask encoded data.

5. The storage device of claim 1 , wherein in reading the mask encoded data, the controller generates a list of masks, and going through the list of masks, adds a mask to the mask encoded data until one mask from the list decodes the mask encoded data.

6. The storage device of claim 5 , wherein the controller generates the list of masks algorithmically, wherein the list of masks is valid for any location in the memory device, wherein for any two bits positions, i and j with stuck bits, there may exist four masks such that bit values in positions i and j are respectively, 00, 01, 10, 11.

7. The storage device of claim 6 , wherein the controller builds the list of masks used to execute a second stuck bit scheme via a linear scheme, wherein when a length (n) of the data is greater than or equal to three, the controller constructs a solution with n+1 masks, with a first mask, m 0 , being all zeros and masks m i , i∈{1, . . . , n}, are all ones, except m i [i−1]=0.

8. The storage device of claim 6 , wherein the controller builds the list of masks used to execute a second stuck bit scheme via a recursive scheme, wherein the controller generates a first mask with all zeros and a second mask with all ones to cover a 00 pattern and a 11 pattern and the controller checks for a 01 pattern and a 10 pattern recursively for bit positions in different halves of the first and second masks.

9. The storage device of claim 6 , wherein the controller builds the list of masks used to execute a second stuck bit scheme via a generalized recursive scheme to optimize a number of masks generated via a recursive scheme.

10. A storage device to process stuck bits information when writing data to a memory device and reading the data from the memory device, the storage device comprises:
a controller to:
encode the data with cyclic error-correcting codes to generate a codeword and determine that a location in the memory device where the codeword is to be stored includes a stuck bit;
store the codeword, wherein in storing the codeword, the controller generates an encoding mask, adds the encoding mask to the codeword to generate mask encoded data, and stores the mask encoded data on the memory device wherein a value in one or more bits in the mask encoded data is the same as a value in one or more stuck bits on the memory device;
obtain an optimal number of decoding masks including the encoding mask using a solving engine; and
read the mask encoded data, wherein in reading the mask encoded data, the controller goes through a list including the optimal number of decoding masks and adds a decoding mask from the list to the mask encoded data, decodes the mask encoded data with the encoding mask from the list, and returns the data.

11. A method for processing storage-free stuck bits information in a storage device when writing data to a memory device and reading the data from the memory device, the storage device comprises a controller to perform the method comprising:
encoding the data with cyclic error-correcting codes to generate a codeword and determining that a location in the memory device where the codeword is to be stored includes a stuck bit;
storing the codeword by generating an encoding mask, adding the encoding mask to the codeword to generate mask encoded data, and storing the mask encoded data on the memory device, wherein a value in one or more bits in the mask encoded data is the same as a value in one or more stuck bits on the memory device; and
reading the mask encoded data by generating a list of decoding masks including the encoding mask, going through the list and adding a decoding mask to the mask encoded data, decoding the mask encoded data with the encoding mask from the list, and returning the data.

12. The method of claim 11 , wherein the storing comprises determining that the location includes one stuck bit and one of:
determining that a value of a bit in the codeword to be stored in a stuck bit location is the same as a stuck bit value, and storing the codeword on the memory device, and
determining that the value of the bit in the codeword to be stored in the stuck bit location is not the same as the stuck bit value, inverting the codeword and storing an inverted codeword on the memory device.

13. The method of claim 11 , wherein the reading comprises executing a first stuck bit scheme to obtain the data by reading the codeword, adding a first mask to the codeword, decoding the codeword, and if decoding of the codeword is successful, returning the data, and
if decoding the codeword added to the first mask is not successful, adding a second mask to the codeword, decoding the codeword, and if decoding of the codeword is successful, returning the data.

14. The method of claim 11 , wherein the storing comprises determining that the location includes two stuck bits and executing a second stuck bit scheme by adding one of a predefined number of masks to the codeword to generate the mask encoded data.

15. The method of claim 11 , wherein the reading comprises generating a list of masks, going through the list of masks, and adding a mask to the mask encoded data until one mask from the list decodes

Assignees

• Western Digital Tech Inc

Inventors

• Mateescu Robert
• Guyot Cyril
• Djurdjevic Ivana

Classifications

• G11C29/42 Primary

  using error correcting codes [ECC] or parity check · CPC title