Ph.D Thesis

Ph.D StudentHorovitz Michal
SubjectCoding Schemes for Non-Volatile Memories
DepartmentDepartment of Computer Science
Supervisors ASSOCIATE PROF. Eitan Yaakobi
PROF. Tuvi Etzion
Full Thesis textFull thesis text - English Version


Flash memory is one of the most non-volatile memories. However, the asymmetry between memory cell programming and removing charge from cell motivates the design of rewriting schemes as Write-Once Memory (WOM) codes and Rank Modulation (RM).

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 to write 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 before encoding, while the decoder knows only the last memory state. However, there are three more models, which depend on whether the encoder and decoder are informed or uninformed with the previous state. These models were first introduced by Wolf et al. They extensively studied the capacity in the binary case of these four models. Yet, in the non-binary case only the conventional model, encoder informed and decoder uninformed, was studied by Fu and Vinck. We first provide constructions of WOM codes for the encoder uninformed models. Then, we study the capacity regions and maximum sum-rates of non-binary WOM for all models.

Jiang et al. suggested the RM scheme to cope with the overshooting and the charge leakage problems. Snake-in-the-box code is a Gray code which can detect a single error. Two consecutive codewords in RM Gray code are obtained by using the minimal cost operation "push-to-the-top". We consider the Kendall's τ-metric due to its relevance for common errors. We proposed two constructions for snakes. The recursive construction for snake of length M2n of permutations from S2n attains limn→∞ M2n/|S2n| ≈ 0.4338, improving on the previous ratio of 1/sqrt(πn) given by Yehezkeally and Schwartz who also proved an upperbound of 0.5 for this ratio. The second is a direct construction for snakes of asymptotically optimal length (2n)!/2-2n. The proof of this construction was completed later by Zhang and Ge.

The local rank modulation (LRM) scheme was suggested to overcome the drawbacks of RM. In the (s,t,n)-LRM scheme, 0<stn with s divides n, the n cells are locally viewed cyclically through a sliding window of size t which requires less comparisons and less distinct values. The gap between two windows is s. We consider the encoding, decoding, and asymptotic enumeration of the (1,t,n)-LRM scheme.

Lastly, motivated by DNA storage, we consider the sequence reconstruction problem, which was first studied by Levenshtein. We assume that the number of errors in different channels can vary, and we define two main problems. First, we study the minimum number of channels required for exact reconstruction for a given code. Then, we find the minimum distance of the code that guarantees exact reconstruction where the number of channels is given. In both problems, we define three models depend on whether the decoder knows the number of errors in each channel, the distribution for the number of errors, or only the average number of errors.