California Institute of Technology

The Texas A&m University System

Anxiao Jiang

Jehoshua Bruck

Eyal En Gad

Yue Li

Michael Langberg

Moshe Schwartz

Eitan Yaakobi

Joerg Kliewer

Zhiying Wang

Bruck Jehoshua

HongChao Zhou

Robert Mateescu

Jie Gao

Vasken Z Bohossian

Techniques are disclosed for generating codes for representation of data in memory devices that may avoid the block erasure operation in changing data values. Data values comprising binary digits (bits) can be encoded and decoded using the generated codes, referred to as codewords, such that the codewords may comprise a block erasure-avoiding code, in which the binary digits of a data message m can be encoded such that the encoded data message can be stored into multiple memory cells of a data device and, once a memory cell value is changed from a first logic value to a second logic value, the value of the memory cell may remain at the second logic value, regardless of subsequently received messages, until a block erasure operation on the memory cell. Similarly, a received data message comprising an input codeword, in which source data values of multiple binary digits have been encoded with the disclosed block erasure-avoiding code, can be decoded in the data device to recover an estimated source data message.

Asymmetric error correction and flash-memory rewriting using polar codes

The reliability of NAND flash memory decreases rapidly as density increases, preventing the wide adoptions of flash-based storage systems. A novel data representation scheme named rank modulation (RM) is discussed for improving NAND flash reliability. RM encodes data using the relative orders of memory cell voltages, which is inherently resilient to asymmetric errors. For studying the effectiveness of RM in flash, RM is adapted to make it simple to implement with existing flash memories. The implementation is evaluated under different types of noise of 20 nm flash memory. Results show that RM offers significantly lower cell error rates compared to the current data representation in flash at typical P/E cycles. RM is applied to flash-based archival storage and shows that RM brings up to six times longer data retention time for 16 nm flash memory.

NAND flash reliability with rank modulation

Both rewriting and error correction are technologies usable for non-volatile memories, such as flash memories. A coding scheme is disclosed herein that combines rewriting and error correction for the write-once memory model. In some embodiments, code construction is based on polar codes, and supports any number of rewrites and corrects a substantial number of errors. The code may be analyzed for a binary symmetric channel. The results can be extended to multi-level cells and more general noise models.

Joint rewriting and error correction in write-once memories

Rank modulation has been recently proposed as a scheme for storing information in flash memories. Three improved aspects are disclosed. In one aspect the minimum push-up scheme, for storing data in flash memories is provided. It aims at minimizing the cost of changing the state of the memory. In another aspect, multi-cells, used for storing data in flash memories is provided. Each transistor is replaced with a multi-cell of mm transistors connected in parallel. In yet another aspect, multi-permutations, are provided. The paradigm of representing information with permutations is generalized to the case where the number of cells in each level is a constant greater than one. In yet another aspect, rank-modulation rewriting schemes which take advantage of polar codes, are provided for use with flash memory.

Rank-modulation rewriting codes for flash memories

Rank modulation has been recently proposed as a scheme for storing information in flash memories. Three improved aspects are disclosed. In one aspect the minimum push-up scheme, for storing data in flash memories is provided. It aims at minimizing the cost of changing the state of the memory. In another aspect, multi-cells, used for storing data in flash memories is provided. Each transistor is replaced with a multi-cell of m transistors connected in parallel. In yet another aspect, multi-permutations, are provided. The paradigm of representing information with permutations is generalized to the case where the number of cells in each level is a constant greater than one.

Flash memories using minimum push up, multi-cell and multi-permutation schemes for data storage

Rank modulation has been recently proposed as a scheme for storing information in flash memories. Three improved aspects are disclosed. In one aspect the minimum push-up scheme, for storing data in flash memories is provided. It aims at minimizing the cost of changing the state of the memory. In another aspect, multi-cells, used for storing data in flash memories is provided. Each transistor is replaced with a multi-cell of mm transistors connected in parallel. In yet another aspect, multi-permutations, are provided. The paradigm of representing information with permutations is generalized to the case where the number of cells in each level is a constant greater than one.

A memory device having a plurality of cells, each of which stores a value, where the values of the cells are mapped to discrete levels and the discrete levels represent data, is programmed by determining a maximum number of cell levels in the memory device, and determining the set of values that are associated with each of the cell levels. The maximum number of cell levels for the memory device is determined by an adaptive programming system connected to the memory device, based on a plurality of cell values attained by at least one cell of the memory device, in response to voltage applied by the adaptive programming system to the cells of the memory device. The adaptive programming system associates, for each of the cell levels, a different set of cell values of the plurality of cell values attained by the cells to which voltage is applied. This technique increases the number of cell levels that can be configured in a memory device as compared with conventional techniques, and increases the number of data values that can be programmed into the cells of a memory device.

Information representation and coding for nonvolatile memories

We investigate a novel storage technology, Rank Modulation, for flash memories. In this scheme, a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. The resulting scheme eliminates the need for discrete cell levels, and overshoot errors when programming cells (a serious problem that reduces the writing speed), as well as mitigate the problem of asymmetric errors. We present schemes for Gray codes, rewriting and joint coding in the rank modulation paradigm.

Rank modulation for flash memories

We investigate error-correcting codes for a novel storage technology, which we call the rank-modulation scheme. In this scheme, a set of n cells stores information in the permutation induced by the different levels of the individual cells. The resulting scheme eliminates the need for discrete cell levels, and overshoot errors when programming cells (a serious problem that reduces the writing speed), as well as mitigates the problem of asymmetric errors. In this discussion, the properties of error correction in rank modulation codes are studied. We show that the adjacency graph of permutations is a subgraph of a multi-dimensional array of a special size, a property that enables code designs based on Lee-metric codes and L-metric codes. We present a one-error-correcting code whose size is at least half of the optimal size. We also present additional error-correcting codes and some related bounds.

Error correcting codes for rank modulation

Routing in a wireless network of communication devices that are located within a network boundary moves network traffic from a first communication device to a second communication device. A geometric indicator of network connectivity is constructed that identifies a curve on which network nodes are located and a network location for each node of the wireless network is determined, so that the network location of a node p identifies a node on the geometric indicator curve that is closest to the node p and indicates connectivity from the node p to the closest node of the geometric indicator curve. A routing scheme is determined, to route in the wireless network from the first communication device to the second communication device based on the respective determined network locations for the first and second communication devices.

Geometric routing in wireless networks

Systems and methods, including computer software products, can be used to update or modify data stored in a memory. One or more variables are represented with one or more cell values in a memory. Each variable is associated with one or more of the cell values. Multiple states of the one or more variables are defined, and each defined state of the one or more variables includes a current store value for each variable and at least one previous store value for the variable. One or more single cell values influence the current store value and previous store value of at least one variable.

Growing community of inventors

College Station, TX, United States of America

Anxiao Jiang