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.

Non-volatile resistive memories, such as phase change memories and resistive random access memories, have attracted significant attention recently due to their scalability, speed, and rewritability. However, in order to use these memories in large-scale memory and storage systems, the limited endurance deficiency of these memories must be addressed. In a recent paper, we proposed a new coding scheme, called endurance-limited memories (ELM) codes, which increases the endurance of these memories by limiting the number of cell programming operations. Namely, an l-change t-write ELM code is a coding scheme that allows to write t messages into some n binary cells while guaranteeing that the number of times each cell is programmed is at most l. There are several models of these codes which depend upon the information that is available to the encoder and the decoder before each write. This information can be one of the following three options: 1. the number of times each cell has been programmed, 2. only the memory state before programming, or 3. no information is available on the cells' state or previous writes. In this paper, we study the models in which the decoder knows on each write the number of times each cell has been programmed before the last write, while for the encoder we consider the aforementioned three possibilities.

In this paper, we study a model that mimics the programming operation of memory cells. This model was first introduced by Lastras-Montanoet 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. Aniterative programming schemeis 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.

Motivated by the error behavior in the DNA storage channel, in this paper, we extend the previously studied sequence reconstruction problem by Levenshtein. The reconstruction problem studies the model in which the information is read through multiple noisy channels, and the decoder, which receives all channel estimations, is required to decode the information. For the combinatorial setup, the assumption is that all the channels cause at most some t errors. Levenshtein considered the case in which all the channels have the same behavior, and we generalize this model and assume that the channels are not identical. Thus, different channels may cause different maximum numbers of errors. For example, we assume that there are N channels, which cause at most t1or t2errors, where t12, and the number of channels with at most t1errors is at least pN, for some fixed 0 <; p <; 1. If the information codeword belongs to a code with minimum distance d, the problem is then to find the minimum number of channels that guarantees successful decoding in the worst case. A different problem we study in this paper is where the number of channels is fixed, and the question is finding the minimum distance d that provides exact reconstruction. We study these problems and show how to apply them for the cases of substitutions and transpositions.

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 wearout of the cells, we propose a new coding scheme, called Endurance-Limited Memories (ELM) code, that increases the endurance of these memories by limiting the number of cell programming operations. Namely, an ℓ-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 ℓ times. In case ℓ = 1 then these codes coincide with the well-studied write-once memory (WOM) codes. We study four models of these codes which depend upon whether the encoder knows, on each write, the number of times each cell was programmed or only knows its state. For the decoder, we consider two cases which depend upon whether the decoder knows the previous state of the memory or not. For two of these models we fully characterize the capacity regions and present partial results for another model. Although only one of the four models is suitable for resistive memories, we consider all four in order to carry out a complete information-theory study of endurance-limited codes.

Motivated by the error behavior in DNA storage channels, in this work we extend the previously studied sequence reconstruction problem by Levenshtein. The reconstruction problem studies the model in which the information is read through multiple noisy channels, and the decoder, which receives all channel estimations, is required to decode the information. For the combinatorial setup, the assumption is that all the channels cause at most some t errors. However, since the channels do not necessarily have the same behavior, we generalize this model and assume that the channels are not identical and thus may cause a different maximum number of errors. For example, we assume that there are N channels that cause at most t1or t2errors, where t12, and the number of channels with at most t1errors is at least [pN], for some fixed 0 <; p <; 1. If the information codeword belongs to a code with minimum distance d, the problem is then to find the minimum number of channels that guarantees successful decoding in the worst case.

Recent research studies on mail search have shown that the longer the query, the better the quality of results, yet a majority of mail queries remain very short and searchers struggle with formulating queries. A known mechanism to assist users in this task is query auto-completion, which has been highly successful in Web search, where it leverages huge logs of queries issued by hundreds of millions of users. This approach cannot be applied directly to mail search as personal query logs are small, mailboxes are not shared and other users' queries are not necessarily generalizable to all. We therefore propose here to leverage the mailbox content in order to generate suggestions, taking advantage of mail-specific features. We then compare this approach to a recent study that augments an individual user's mail search history with query logs from "similar users'', where the similarity is driven by demographics. Finally we show how combining both types of approaches allows for better suggestions quality but also increases the chance that the desired message be retrieved. We validate our claims via a manual qualitative evaluation and large scale quantitative experiments conducted on the query log of Yahoo Mail.

Write-once memory (WOM) is a storage device consisting of q-ary cells that can only increase their value. A WOM code is a coding scheme that allows writing multiple times to the memory without decreasing the levels of the cells. In the conventional model, it is assumed that the encoder can read the memory state before encoding, while the decoder reads only the memory state after encoding. However, there are three more models in this setup, which depend on whether the encoder and the decoder are informed or uninformed with the previous state of the memory. These four models were first introduced by Wolf et al., where they extensively studied the WOM capacity in these models for the binary case. In the non-binary setup, only the model, in which the encoder is informed and the decoder is not, was studied by Fu and Vinck. In this paper, we first present constructions of WOM codes in the models where the encoder is uninformed with the memory state (that is, the encoder cannot read the memory prior to encoding). We then study the capacity regions and maximum sum-rates of non-binary WOM codes for all four models. We extend the results by Wolf et al. and show that the capacity regions for the models in which the encoder is informed and the decoder is informed or uninformed in both the ϵ-error and the zero-error cases are all identical. We also find the ϵ-error capacity region; in this case, the encoder is uninformed and the decoder is informed and show that, in contrary to the binary case, it is a proper subset of the capacity region in the first two models. Several more results on the maximum sum-rate are presented as well.

Write-once memory (WOM) is a storage device consisting of q-ary cells that can only increase their values. A WOM code is a scheme to write messages to the memory without decreasing the cells' levels. There are four models of WOM which depend on whether the encoder and decoder are informed or uninformed with the previous state of the memory. The WOM capacity of the four models was extensively studied by Wolf et al. for the binary case, however in the non-binary setup only the model, in which the encoder is informed and the decoder is not, was studied by Fu and Han Vinck. In this paper we study the capacity regions and maximum sum-rates of non-binary WOM codes for these four models. We extend the results by Wolf et al. and show that for the models in which the encoder is informed and the decoder is informed or uninformed the capacity region is the same both for the ε-error and the zero-error cases. We also find the ε-error capacity region in case the encoder is uninformed and the decoder is informed and show that, in contrary to the binary case, it is a proper subset of the capacity region in the first two models. Several more results on the maximum sum-rate are presented as well.

Write-once memory (WOM) is a storage device consisting of q-ary cells that can only increase their value. A WOM code is a coding scheme which allows one to write multiple times to the WOM without decreasing the levels of the cells. In the conventional model of WOM, it is assumed that the encoder can read the memory state before encoding, while the decoder reads only the memory state after encoding, but not before that. However, there are three more models in this setup. We follow an earlier work by Wolf et al. who studied the capacity results of all possible four models in which the encoder/decoder is or is not informed with the previous state of the memory before encoding, respectively. The two challenging models we study here assume that the encoder is uninformed with the memory state (that is, the encoder cannot read the memory prior to encoding). We show that if the decoder is also uninformed with the memory state before encoding, then codes in the Z channel provide constructions for the binary case, and codes correcting non-binary asymmetric errors are used for non-binary codes. In case the decoder is informed with the previous state, then erasure-correcting codes are invoked in the binary case, and codes in the Manhattan distance are used for the non-binary case.

Local rank modulation scheme was suggested recently for representing information in flash memories in order to overcome drawbacks of rank modulation. For 03, but the proofs will become more complicated. The enumeration problem is presented also as a purely combinatorial problem. Finally, we prove the conjecture that the size of a constant weight (1, 2, n)-LRM Gray code with weight two is at most 2n.

Snake-in-the-box code is a Gray code, which is capable of detecting a single error. Gray codes are important in the context of the rank modulation scheme, which was suggested recently for representing information in flash memories. For a Gray code in this scheme, the codewords are permutations, two consecutive codewords are obtained using the push-to-the-top operation, and distance measure is defined on permutations. In this paper, the Kendall's T-metric is used as the distance measure. We present a general method for constructing such Gray codes. We apply the method recursively to obtain a snake of length M2n+1= ((2n + 1)(2n) - 1)M2n-1for permutations of S2n+1, from a snake of length M2n-1for permutations of S2n-1. Thus, we have lim;n→∞ M2n+1/S2n+1≈0.4338, improving on the previous known ratio of lim;n→∞ 1/√(πn). Using the general method, we also present a direct construction. This direct construction is based on necklaces and it might yield snakes of length (2n + 1)!/2-2n + 1 for permutations of S2n+1. The direct construction was applied successfully for S7and S9, and hence lim;n→∞ M2n+1/S2n+1≈0.4743.