Linear programming based decoding for memory devices

• US 9,424,945 B2
• Filed: 11/14/2014
• Issued: 08/23/2016
• Est. Priority Date: 02/27/2013
• Status: Active Grant

• Current Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Ma, Xudong
• Primary Examiner(s): HIDALGO, FERNANDO N
• Application Number:
  US14/541,588
• Publication Number:
  US 20150070985A1
• Time in Patent Office: 648 Days
• Field of Search: 365/185.18, 365/185.22, 365/185.09, 365/185.02
• US Class Current: 1/1
• CPC Class Codes: G11C 11/5642 Sensing or reading circuits; Data output circuits
• CPC Class Codes: G11C 16/26 Sensing or reading circuits; Data output circuits
• CPC Class Codes: G11C 16/3431 Circuits or methods to detect disturbed nonvolatile memory cells, e.g. which still read as programmed but with threshold less than the program verify threshold or read as erased but with threshold greater than the erase verify threshold, and to reverse the disturbance via a refreshing programming or erasing step
• CPC Class Codes: G11C 7/02 with means for avoiding parasitic signals

Abstract

Technologies are generally described herein for linear programming based decoding for memory devices. In some examples, a cell threshold voltage level of a memory cell is detected. An interference voltage level of an interference cell that interferes with the memory cell can be determined. The cell threshold voltage level can be decoded in accordance with a set of beliefs to determine the value of the memory cell. The set of beliefs can include a minimization of an objective function of a linear program representing inter-cell interference between the memory cell and the interference cell.

Claims

1. A system to determine a value of a memory cell, the system comprising:

a memory; and

a controller configured to;

detect a cell threshold voltage level of a memory cell of the memory,

determine an interference voltage level of an interference cell of the memory that interferes with the memory cell, and

decode the cell threshold voltage level in accordance with a set of probabilities to determine the value of the memory cell, wherein the set of probabilities are associated with a minimization of a linear program that represents inter-cell interference between the memory cell and the interference cell.

2. The system of claim 1, wherein the set of probabilities comprise marginal probabilities that satisfy a constraint associated with the linear program.

3. The system of claim 1, wherein the controller is further configured to utilize a model that comprises the set of probabilities and represents inter-cell interferences associated with cells of the memory.

4. The system of claim 1, wherein the set of probabilities is obtained by:

modeling the inter-cell interference between the memory cell and the interference cell as an integer programming problem;

relaxing the integer programming problem to obtain the linear program; and

solving the linear program obtain the set of probabilities.

5. The system of claim 1, wherein the controller is further configured to:

identify, for signals written to memory cells of the memory, measured threshold voltage levels and resulting threshold voltage values; and

determine, based at least in part upon the resulting threshold voltage values, a configuration used to write to the memory cells, wherein the configuration minimizes a Euclidean distance between the resulting threshold voltage values and the measured threshold voltage levels.

6. The system of claim 5, wherein the controller is further configured to:

determine an integer programming problem that represents the Euclidean distance between the resulting threshold voltage values and the measured threshold voltage levels;

relax the integer programming problem to obtain a linear programming problem; and

identify the set of probabilities that correspond to marginal probabilities that minimize the linear programming problem.

7. The system of claim 1, wherein the controller is configured to detect the cell threshold voltage level by detecting the cell threshold voltage level in response to receipt of a request to read the value of the memory cell.

8. The system of claim 1, wherein the controller is configured to decode the cell threshold voltage level by:

compensating for the inter-cell interference between the memory cell and the interference cell by multiplication of the cell threshold voltage level by a marginal probability that corresponds to at least one of the set of probabilities; and

determining the value of the memory cell in accordance with a result of multiplication of the cell threshold voltage level by the marginal probability.

9. The system of claim 1, wherein the controller is configured to decode the cell threshold voltage level by:

determining a probability that the value of the memory cell is equal to zero;

determining a further probability that the value of the memory cell is equal to one;

in response to a determination that the probability is greater than the further probability, determining the value of the memory cell is zero; and

in response to a determination that the further probability is greater than the probability, determining the value of the memory cell is one.

10. A computing device, operative to:

detect a cell threshold voltage level of a memory cell of a flash memory device;

determine an interference voltage level of an interference cell that interferes with the memory cell; and

decode the cell threshold voltage level in accordance with a set of probabilities to determine a value of the memory cell, wherein the set of probabilities comprises a minimization of a linear program that represents inter-cell interference between the memory cell and the interference cell.

11. The computing device of claim 10, wherein the set of probabilities comprise marginal probabilities that satisfy a constraint associated with the linear program.

12. The computing device of claim 10, further operative to:

model the inter-cell interference between the memory cell and the interference cell as an integer programming problem;

relax the integer programming problem to obtain the linear program; and

solve the linear program to obtain the set of probabilities.

13. The computing device of claim 10, further operative to:

identify, for a plurality of signals written to a plurality of cells of the flash memory device, measured threshold voltage levels and resulting threshold voltage values; and

determine, based upon the resulting threshold voltage values, a configuration used to write to the plurality of cells, wherein the configuration minimizes a Euclidean distance between the resulting threshold voltage values and the measured threshold voltage levels.

14. The computing device of claim 13, further operative to:

determine an integer programming, problem that represents the Euclidean distance between the resulting threshold voltage values and the measured threshold voltage levels;

relax the integer programming problem to obtain a linear programming problem; and

identify the set of probabilities, wherein the set of probabilities correspond to marginal probabilities that minimize the linear programming problem.

15. The computing device of claim 10, wherein the computing device is operative to detect the cell threshold voltage level by detecting the cell threshold voltage level in response to a request to read the value of the memory cell.

16. The computing device of claim 10, wherein the computing device is operative to decode the cell threshold voltage level by:

multiplying the cell threshold voltage level by a marginal probability that corresponds to at least one of the set of probabilities to compensate for the inter-cell interference between the memory cell and the interference cell; and

determining the value of the memory cell in accordance with a result of multiplication of the cell threshold voltage level by the marginal probability.

17. The computing device of claim 10, wherein the computing device is operative to decode the cell threshold voltage level by:

determining a probability that the value of the memory cell is equal to a first value and determining a further probability that the value of the memory cell is equal to a second value; and

in response to a determination that the probability is greater than the further probability, determining the value of the memory cell is zero.

18. The computing device of claim 10, wherein the computing device is operative to decode the cell threshold voltage level by:

determining a probability that the value of the memory cell is equal to a first value and determining a further probability that the value of the memory cell is equal to a second value; and

in response to a determination that the further probability is greater than the probability, determining the value of the memory cell is one.

19. The computing device of claim 10, further operative to obtain a mathematical model that represents inter-cell interferences of the memory cell and the interference cell, wherein the mathematical model comprises a set of marginal probabilities that satisfy constraints associated with the mathematical model.

20. The computing device of claim 10, further operative to:

identify, for signals written to cells of the flash memory device, measured threshold voltage levels and resulting threshold voltage values,

determine, based upon the resulting threshold voltage values, a configuration used to write to the cells, wherein the configuration minimizes a Euclidean distance between the resulting threshold voltage values and the measured threshold voltage levels, and

generate a mathematical model based, at least partially, upon the Euclidean distance.