Search

MDS codes are erasure-correcting codes that can correct the maximum number of erasures given the number of redundancy or parity symbols. If an MDS code has r parities and no more than r erasures occur, then by transmitting all the remaining data in the code one can recover the original information. However, it was shown that in order to recover a single symbol erasure, only a fraction of 1/r of the information needs to be transmitted. This fraction is called the repair bandwidth (fraction). Explicit code constructions were given in previous works. If we view each symbol in the code as a vector or a column, then the code forms a 2D array and such codes are especially widely used in storage systems. In this paper, we ask the following question: given the length of the column l, can we construct high-rate MDS array codes with optimal repair bandwidth of 1/r, whose code length is as long as possible? In this paper, we give code constructions such that the code length is (r + l)log r l.

Motivated to understand the role of randomness in biological computation, we study a class of urn models that are characterized by urn functions. At each step, one ball is randomly sampled according to an urn function and replaced with a different colored ball. This process is repeated until the urn contains a single color, at which point the process halts. Such an urn can be thought of as a random switch; depending on the initial ball colors and the urn function, the urn population has some probability of converging to any of the initial ball colors. We find that these probabilities have surprisingly simple closed-form solutions and also derive expressions for the switching time. We demonstrate the application of such urn models to biological systems by deriving the urn function for the genetic network controlling the lysis-lysogeny decision in the Lambda phage virus. By applying our results to this system, we then derive an intriguing hypothesis on the role of dimers in genetic switches. Many open questions exist on further generalizations of such urn models and their applications to the understanding of randomness and biological computation.

Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance d H , the corresponding minimum pair distance is at least d H + 3. Our main contribution is proving that, for a given linear cyclic code with a minimum Hamming distance d H , the minimum pair distance is at least d H + [d H /2]. We also describe decoding algorithms, based upon bounded distance decoders for the cyclic code, whose pair-symbol error correcting capabilities reflects the larger minimum pair distance. In addition, we consider the case where a read channel output is a prescribed number, b > 2, of consecutive symbols and provide some generalizations of our results. We note that the symbol-pair read channel problem is a special case of the sequence reconstruction problem that was introduced by Levenshtein.

The limited endurance of flash memories is a major design concern for enterprise storage systems. We propose a method to increase it by using relative (as opposed to fixed) cell levels and by representing the information with Write Asymmetric Memory (WAM) codes. Overall, our new method enables faster writes, improved reliability as well as improved endurance by allowing multiple writes between block erasures. We study the capacity of the new WAM codes with relative levels, where the information is represented by multiset permutations induced by the charge levels, and show that it achieves the capacity of any other WAM codes with the same number of writes. Specifically, we prove that it has the potential to double the total capacity of the memory. Since capacity can be achieved only with cells that have a large number of levels, we propose a new architecture that consists of multi-cells — each an aggregation of a number of floating gate transistors.

The rank modulation scheme has been proposed recently for efficiently writing and storing data in nonvolatile memories. Error-correcting codes are very important for rank modulation, and they have attracted interest among researchers. In this work, we explore a new approach, systematic error-correcting codes for rank modulation. In an (n, k) systematic code, we use the permutation induced by the levels of n cells to store data, and the permutation induced by the first k cells (k < n) has a one-to-one mapping to information bits. Systematic codes have the benefits of enabling efficient information retrieval and potentially supporting more efficient encoding and decoding procedures. We study systematic codes for rank modulation equipped with the Kendall's τ-distance. We present (k + 2, k) systematic codes for correcting one error, which have optimal sizes unless perfect codes exist. We also study the design of multi-error-correcting codes, and prove that for any 2 ≤ k < n, there always exists an (n, k) systematic code of minimum distance n-k. Furthermore, we prove that for rank modulation, systematic codes achieve the same capacity as general error-correcting codes.

We study the problem of extracting a prescribed number of random bits by reading the smallest possible number of symbols from non-ideal stochastic processes. The related interval algorithm proposed by Han and Hoshi has asymptotically optimal performance; however, it assumes that the distribution of the input stochastic process is known. The motivation for our work is the fact that, in practice, sources of randomness have inherent correlations and are affected by measurement's noise. Namely, it is hard to obtain an accurate estimation of the distribution. This challenge was addressed by the concepts of seeded and seedless extractors that can handle general random sources with unknown distributions. However, known seeded and seedless extractors provide extraction efficiencies that are substantially smaller than Shannon's entropy limit. Our main contribution is the design of extractors that have a variable input-length and a fixed output length, are efficient in the consumption of symbols from the source, are capable of generating random bits from general stochastic processes and approach the information theoretic upper bound on efficiency.