Search

Resistive memories, such as phase change memories and resistive random access memories have attracted significant attention in recent years due to their better scalability, speed, rewritability, and yet non-volatility. However, their limited endurance is still a major drawback that has to be improved before they can be widely adapted in large-scale systems. In this work, in order to reduce the wear out of the cells, we propose a new coding scheme, called endurance-limited memories (ELM) codes, that increases the endurance of these memories by limiting the number of cell programming operations. Namely, an $\ell $ -change $t$ -write ELM code is a coding scheme that allows to write $t$ messages into some $n$ binary cells while guaranteeing that each cell is programmed at most $\ell $ times. In case $\ell =1$ , these codes coincide with the well-studied write-once memory (WOM) codes. We study some models of these codes which depend upon whether the encoder knows on each write the number of times each cell was programmed, knows only the memory state, or even does not know anything. For the decoder, we consider these similar three cases. We fully characterize the capacity regions and the maximum sum-rates of three models where the encoder knows on each write the number of times each cell was programmed. In particular, it is shown that in these models the maximum sum-rate is $\log \sum _{i=0}^{\ell } {\binom{t }{ i}}$. We also study and expose the capacity regions of the models where the decoder is informed with the number of times each cell was programmed. Finally we present the most practical model where the encoder read the memory before encoding new data and the decoder has no information about the previous states of the memory. [ABSTRACT FROM AUTHOR]

In this paper, we study a model that mimics the programming operation of memory cells. This model was first introduced by Lastras-Montano et al. for continuous-alphabet channels, and later by Bunte and Lapidoth for discrete memoryless channels (DMC). Under this paradigm we assume that cells are programmed sequentially and individually. The programming process is modeled as transmission over a channel, such that it is possible to read the cell state in order to determine its programming success, and in case of programming failure, to reprogram the cell again. Reprogramming a cell can reduce the bit error rate, however this comes with the price of increasing the overall programming time and thereby affecting the writing speed of the memory. An iterative programming scheme is an algorithm which specifies the number of attempts to program each cell. Given the programming channel and constraints on the average and maximum number of attempts to program a cell, we study programming schemes which maximize the number of bits that can be reliably stored in the memory. We extend the results by Bunte and Lapidoth and study this problem when the programming channel is either discrete-input memoryless symmetric channel (including the BSC,BEC, BI-AWGN) or the $Z$ channel. For the BSC and the BEC our analysis is also extended for the case where the error probabilities on consecutive writes are not necessarily the same. Lastly, we also study a related model which is motivated by the synthesis process of DNA molecules. [ABSTRACT FROM AUTHOR]

Motivated by the rank modulation scheme, a recent study by Sala and Dolecek explored the idea of constraint codes for permutations. The constraint studied by them is inherited by the inter-cell interference phenomenon in flash memories, where high-level cells can inadvertently increase the level of low-level cells. A permutation \sigma \in Sn satisfies the single-neighbor $k$ -constraint if \sigma (i+1)-\sigma (i)\leq k$ for all 1\leq i\leq n-1$ . In this paper, this model is extended into two constraints. A permutation k$ -constraint if for all 2 \leq i \leq n-1$ , \sigma (i)-\sigma (i-1)\leq k$ or \sigma (i \,\, + \,\, 1)-\sigma (i)\leq k$ , and it satisfies the asymmetric two-neighbor k$ -constraint if for all 2 \leq i \leq n-1$ , and the capacity of the second constraint is 1 regardless for any positive $k$ . We also extend our results and study the capacity of these two constraints combined with error-correcting codes in the Kendall $\tau $ -metric. [ABSTRACT FROM AUTHOR]

In this paper, we study a new model of defect memory cells, called partially stuck-at memory cells, which is motivated by the behavior of multi-level cells in non-volatile memories, such as flash memories and phase change memories. If a cell can store the q levels 0, 1, {\dots }, q-1 , we say that it is partially stuck-at level s$ , where $1 \leq s \leq q-1$ , if it can only store values, which are at least $s$ . We follow the common setup where the encoder knows the positions and levels of the partially stuck-at cells whereas the decoder does not. Our main contribution in this paper is the study of codes for masking $u$ partially stuck-at cells. We first derive lower and upper bounds on the redundancy of such codes. The upper bounds are based on two trivial constructions. We then present three code constructions over an alphabet of size $q$ , by first considering the case where the cells are partially stuck-at level $s=1$ . The first construction works for $u

Error-correcting codes for permutations have received considerable attention in the past few years, especially in applications of the rank modulation scheme for flash memories. While codes over several metrics have been studied, such as the Kendall $\tau $ , Ulam, and Hamming distances, no recent research has been carried out for erasures and deletions over permutations. In rank modulation, flash memory cells represent a permutation, which is induced by their relative charge levels. We explore problems that arise when some of the cells are either erased or deleted. In each case, we study how these erasures and deletions affect the information carried by the remaining cells. In particular, we study models that are symbol-invariant, where unaffected elements do not change their corresponding values from those in the original permutation, or permutation-invariant, where the remaining symbols are modified to form a new permutation with fewer elements. Our main approach in tackling these problems is to build upon the existing works of error-correcting codes and leverage them in order to construct codes in each model of deletions and erasures. The codes we develop are in certain cases asymptotically optimal, while in other cases, such as for codes in the Ulam distance, improve upon the state of the art results. [ABSTRACT FROM PUBLISHER]

The current flash memory technology focuses on the cost minimization of its static storage capacity. However, the resulting approach supports a relatively small number of program-erase cycles. This technology is effective for consumer devices (e.g., smartphones and cameras) where the number of program-erase cycles is small. However, it is not economical for enterprise storage systems that require a large number of lifetime writes. The proposed approach in this paper for alleviating this problem consists of the efficient integration of two key ideas: 1) improving reliability and endurance by representing the information using relative values via the rank modulation scheme and 2) increasing the overall (lifetime) capacity of the flash device via rewriting codes, namely, performing multiple writes per cell before erasure. This paper presents a new coding scheme that combines rank-modulation with rewriting. The key benefits of the new scheme include: 1) the ability to store close to 2 bit per cell on each write with minimal impact on the lifetime of the memory and 2) efficient encoding and decoding algorithms that make use of capacity-achieving write-once-memory codes that were proposed recently. [ABSTRACT FROM PUBLISHER]

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on \(q\) levels. Each cell is initially in level 0 and can only increase its level. A \(t\) -write WOM code is a coding scheme, which allows one to store \(t\) messages to the WOM such that on consecutive writes every cell’s level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the \(t\) writes and number of memory cells, is bounded by \(\log (t+1)\) . Our main contribution in this paper is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, whereas the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. A key ingredient in our construction is a recent capacity achieving construction of two-write WOM codes, which uses the so-called Wozencraft ensemble of linear codes. In our construction, we encode information in the first and second write in a way that leaves a large number (roughly half) of the cells nonprogrammed. This allows us to use the above two-write construction in order to invoke a third write to the memory. We also give specific constructions of nonbinary two-write WOM codes and multiple writes, which give better sum-rate than the currently best known ones. In the construction of these codes, we build upon previous nonbinary constructions and show how tools such symbols relabeling can help in achieving high sum-rates. [ABSTRACT FROM PUBLISHER]

To the body of works on rewrite codes for constrained memories, we add a comprehensive study in a direction that is especially relevant to practical storage. The subject of this paper is codes for the \(q\) -ary extension of the write-once memories model, with input sizes that are fixed throughout the write sequence. Seven code constructions are given with guarantees on the number of writes they can support. For the parameters addressed by the constructions, we also prove upper bounds on the number of writes, which prove the optimality of three of the constructions. We concentrate on codes with short block lengths to keep the complexity of decoding and updates within the feasibility of practical implementation. Even with these short blocks the constructed codes are shown to be within a small additive constant from capacity for an arbitrarily large number of input bits. Part of the study addresses a new rewrite model where some of the input bits can be updated multiple times in a write sequence (hot bits), while other are updated at most once (cold bits). We refer to this new model as hot/cold rewrite codes. It is shown that adding cold bits to a rewrite code has a negligible effect on the total number of writes, while adding an important feature of leveling the physical wear of memory cells between hot and cold input data. [ABSTRACT FROM AUTHOR]

Multilevel flash memory contains blocks of cells that represent data by the amount of charge stored in them. The cell writing—or programming—process applies specified voltages in a sequential manner, injecting charge to achieve a desired level. Reducing a cell level requires a costly block erasure, so programming only increases cell levels. Parallel programming, whereby a common voltage is applied to a group of cells to inject charge simultaneously, simplifies circuitry and increases programming speed. However, cell-to-cell variations and limited programming round can adversely affect its precision. In this paper, we consider algorithms for efficient cell programming. Since cell levels are quantized to a discrete set of values, our objective is to minimize the number of cells that are not quantized to their target levels. For a specified number of programming rounds, we derive an optimal parallel programming algorithm with complexity that is polynomial in the number of cells. We extend the algorithm to account for intercell interference, where the voltage applied to a cell can affect the level of adjacent cells. We then consider noisy programming of a single cell, with and without feedback about the cell level. In both scenarios, we present an algorithm that, for a given number of programming rounds, minimizes the probability of an incorrect cell level. [ABSTRACT FROM AUTHOR]

Flash memory is a nonvolatile computer memory comprising blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes—known as floating codes (or flash codes) and buffer codes—have been designed in order to maximize the number of times that information stored in a flash memory can be written (and rewritten) prior to incurring a block erasure. An (n,k,t)q flash code \BBC is a coding scheme for storing k information bits in n cells in such a way that any sequence of up to t writes can be accommodated without a block erasure. The total number of available level transitions in n cells is n(q-1), and the write deficiency of \BBC, defined as \delta (\BBC)=n(q-1)-t, is a measure of how close the code comes to perfectly utilizing all these transitions. In this paper, we show a construction of flash codes with write deficiency O(qk\log k) if q\geqslant\log2k, and at most O(k\log^2k) otherwise. An (n,r,\ell,t)q buffer code is a coding scheme for storing a buffer of r~\ell-ary symbols such that for any sequence of t symbols, it is possible to successfully decode the last r symbols that were written. We improve upon a previous upper bound on the maximum number of writes t in the case where there is a single cell to store the buffer. Then, we show how to improve a construction by Jiang that uses multiple cells, where n\geqslant 2r. [ABSTRACT FROM AUTHOR]

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs include punch cards and optical disks. WOM-codes, introduced by Rivest and Shamir, permit the reuse of a WOM by taking into account the location of cells that have already been changed to the one state. The objective in designing WOM-codes is to use the fewest number of cells to store a specified number of information bits in each of several reuses of the memory. An [n,k,t] WOM-code \cal C is a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The rate of \cal C, defined by \cal R(\cal C)=kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions correcting a single cell-error were presented by Zémor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-code with a better rate. Our construction can be adapted also for single-error-detection, double-error-correction, and triple-error-correction. For the last case, we use triple-error-correcting BCH-like codes, which were presented by Kasami and more recently described again by Bracken and Helleseth. Finally, we show two constructions that can be combined for the correction of an arbitrary number of errors. [ABSTRACT FROM AUTHOR]