Low-complexity flash memory data-encoding techniques using simplified belief propagation

• US 9,859,925 B2
• Filed: 12/13/2013
• Issued: 01/02/2018
• Est. Priority Date: 12/13/2013
• Status: Expired due to Fees

• 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): Lamarre, Guy
• Application Number:
  US14/785,582
• Publication Number:
  US 20160080003A1
• Time in Patent Office: 1,481 Days
• Field of Search: 714733, 714731, 714726-727
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
• CPC Class Codes: H03M 13/3746 with iterative decoding
• CPC Class Codes: H03M 13/458 by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result

Abstract

Technologies and implementations for encoding and storing data in a solid-state memory device with a reduced number of erasures using a simplified belief-propagation algorithm that includes a set of message-calculation rules that have a low computational complexity are generally disclosed. Additionally, technologies and implementations for decoding data and for error correction are generally disclosed.

Claims

1. A method comprising:

receiving a first binary vector comprising a first group of data, the first group of data being encoded and stored in a memory block of a single-level cell-type flash memory as a second group of data subject to a current state of single-level cell-type flash memory cells in the memory block of the single-level cell-type flash memory, the second group of data corresponding to the encoded first group of data, each element of the first group of data corresponding to a row of a matrix parity-check equation, each element of the second group of data corresponding to a single-level cell-type flash memory cell in the memory block of the single-level cell-type flash memory and each element of the second group of data comprising an unknown variable of the matrix parity-check equation, wherein each row of the matrix parity-check equation corresponding to a check node of the matrix parity-check equation and each unknown variable corresponding to a variable node of the matrix parity-check equation;

determining a marginal probability of each element of the second group of data for a first selected configuration of the second group of data;

determining a value of at least one element of the second group of data according to the determined marginal probability of each element of the second group of data; and

iteratively determining the marginal probability of each remaining undetermined element of the second group of data for subsequently selected configurations of the remaining undetermined elements of the second group of data, and determining a value of at least one remaining undetermined element of the second group of data until all elements of the second group of data have been determined,

wherein solutions to the matrix parity-check equation are subject to a constraint that a value of an element of the second group of data is zero if the current state of a corresponding single-level cell-type flash memory cell in the memory block is zero.

2. The method according to claim 1, wherein the matrix parity-check equation comprises:

A{circumflex over (x)}=ŷ

,

in which vector {circumflex over (x)} comprises a second binary vector representing the second group of data, matrix A is a pre-designed sparse matrix, vector ŷ

comprises the first binary vector representing the first group of data to be encoded, and a vector ŝ

comprises current states of the single-level cell-type flash memory cells in the memory block of the single-level cell-type flash memory, and in which the solutions to the matrix parity-check equation are subject to the constraint x(n)=0 if s(n)=0 for the n-th element of {circumflex over (x)} and ŝ

, respectively.

3. The method according to claim 2, wherein the matrix A further comprises a low-density parity-check matrix.

4. The method according to claim 2, wherein determining the marginal probability of each element of the second group of data for the first selected configuration of the second group of data comprises exchanging messages between neighboring variable nodes and check nodes of the matrix parity-check equation, the messages exchanged from the variable nodes to the check nodes being determined based on message-calculation rules that comprise convex combination adjust terms.

5. The method according to claim 4, wherein the message-calculation rules for the messages exchanged from the variable nodes to the check nodes comprise:

6. The method according to claim 5, further comprising:

receiving a fourth group of data that was stored in the single-level cell-type flash memory; and

decoding the fourth group of data using the matrix parity-check equation.

7. The method according to claim 1, wherein determining the value of the at least one element of the second group of data comprises determining that the row of the matrix parity-check equation is satisfied.

8. A machine-readable non-transitory medium having stored therein instructions that, when executed by one or more processors, operatively enable a data encoding module to:

receive a first binary vector comprising a first group of data, the first group of data being encoded and stored in a memory block of a single-level cell-type flash memory as a second group of data subject to a current state of single-level cell-type flash memory cells in the memory block of the single-level cell-type flash memory, the second group of data corresponding to the encoded first group of data, each element of the first group of data corresponding to a row of a matrix parity-check equation, each element of the second group of data corresponding to a single-level cell-type flash memory cell in the memory block of the flash memory and each element of the second group of data comprising an unknown variable of the matrix parity-check equation, wherein each row of the matrix parity-check equation corresponding to a check node of the matrix parity-check equation and each unknown variable corresponding to a variable node of the matrix parity-check equation;

determine a marginal probability of each element of the second group of data for a first selected configuration of the second group of data;

determine a value of at least one element of the second group of data according to the determined marginal probability of each element of the second group of data; and

iteratively determine the marginal probability of each remaining undetermined element of the second group of data for subsequently selected configurations of the remaining undetermined elements of the second group of data, and determine a value of at least one remaining undetermined element of the second group of data until all elements of the second group of data have been determined,

wherein solutions to the matrix parity-check equation are subject to a constraint that a value of an element of the second group of data is zero if the current state of a corresponding single-level cell-type flash memory cell in the memory block is zero.

9. The machine-readable non-transitory medium according to claim 8, wherein the matrix parity-check equation comprises:

A{circumflex over (x)}=ŷ

,

in which vector {circumflex over (x)} comprises a second binary vector representing the second group of data, matrix A is a pre-designed sparse matrix, vector ŷ

comprises the first binary vector representing the first group of data to be encoded, and a vector ŝ

comprises current states of the single-level cell-type flash memory cells in the memory block of the single-level cell-type flash memory, and in which the solutions to the matrix parity-check equation are subject to the constraint x(n)=0 if s(n)≦

0 for the n-th element of {circumflex over (x)} and ŝ

, respectively.

10. The machine-readable non-transitory medium according to claim 9, wherein the matrix A further comprises a low-density parity-check matrix.

11. The machine-readable non-transitory medium according to claim 9, wherein the determination of the marginal probability of each element of the second group of data for the first selected configuration of the second group of data comprises an exchange of messages between neighboring variable nodes and check nodes of the matrix parity-check equation, the messages exchanged from the variable nodes to the check nodes being determined based on message-calculation rules that comprise convex combination adjust terms.

12. The machine-readable non-transitory medium according to claim 11, wherein the message-calculation rules for the messages exchanged from the variable nodes to the check nodes comprise:

13. The machine-readable non-transitory medium according to claim 8, wherein the stored instructions that, when executed by the one or more processors, further operatively enable a decoder module to:

receive a fourth group of data that was stored in the single-level cell-type flash memory; and

decode the fourth group of data using the matrix parity-check equation.

14. The machine-readable non-transitory medium according to claim 8, wherein the determination of the value of the at least one element of the second group of data comprises a determination that the row of the matrix parity-check equation is satisfied.

15. A system, comprising:

a module configured to encode data;

a machine-readable non-transitory medium having stored therein instructions that, when executed by one or more processors, operatively enable the module to;

receive a first binary vector comprising a first group of data, the first group of data being encoded and stored in a memory block of a single-level cell-type flash memory as a second group of data subject to a current state of single-level cell-type flash memory cells in the memory block of the single-level cell-type flash memory, the second group of data corresponding to the encoded first group of data, each element of the first group of data corresponding to a row of a matrix parity-check equation, each element of the second group of data corresponding to a single-level cell-type flash memory cell in the memory block of the single-level cell-type flash memory and each element of the second group of data comprising an unknown variable of the matrix parity-check equation, wherein each row of the matrix parity-check equation corresponding to a check node of the matrix parity-check equation and each unknown variable corresponding to a variable node of the matrix parity-check equation;

determine a marginal probability of each element of the second group of data for a first selected configuration of the second group of data;

determine a value of at least one element of the second group of data according to the determined marginal probability of each element of the second group of data; and

iteratively determine the marginal probability of each remaining undetermined element of the second group of data for subsequently selected configurations of the remaining undetermined elements of the second group of data, and determine a value of at least one remaining undetermined element of the second group of data until all elements of the second group of data have been determined,

wherein solutions to the matrix parity-check equation are subject to a constraint that a value of an element of the second group of data is zero if the current state of a corresponding single-level cell-type flash memory cell in the memory block is zero.

16. The system according to claim 15, wherein the matrix parity-check equation comprises:

A{circumflex over (x)}=ŷ

,

in which vector {circumflex over (x)} comprises a second binary vector representing the second group of data, matrix A is a pre-designed sparse matrix, vector ŷ

comprises the first binary vector representing the first group of data to be encoded, and a vector ŝ

comprises current states of the single-level cell-type flash memory cells in the memory block of the single-level cell-type flash memory, and in which the solutions to the matrix parity-check equation are subject to the constraint x(n)=0 if s(n)=0 for the n-th element of {circumflex over (x)} and ŝ

, respectively.

17. The system according to claim 16, wherein the matrix A further comprises a low-density parity-check matrix.

18. The system according to claim 16, wherein the determination of the marginal probability of each element of the second group of data for the first selected configuration of the second group of data comprises an exchange of messages between neighboring variable nodes and check nodes of the matrix parity-check equation, the messages exchanged from the variable nodes to the check nodes being determined based on message-calculation rules that comprise convex combination adjust terms.

19. The system according to claim 18, wherein the message-calculation rules for the messages exchanged from the variable nodes to the check nodes comprise:

20. The system according to claim 15, wherein the stored instructions that, when executed by the one or more processors, further operatively enable a decoder module to:

receive a fourth group of data that was stored in the single-level cell-type flash memory; and

decode the fourth group of data using the matrix parity-check equation.

21. The system according to claim 15, wherein the determination of value of the at least one element of the second group of data comprises a determination that the row of the matrix parity-check equation is satisfied.