Ph.D Thesis | |

Ph.D Student | Horovitz Michal |
---|---|

Subject | Coding Schemes for Non-Volatile Memories |

Department | Department of Computer Science |

Supervisors | ASSOCIATE PROF. Eitan Yaakobi |

PROF. Tuvi Etzion | |

Full Thesis text |

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 *M _{2n}*
of permutations from

The local rank modulation (LRM) scheme
was suggested to overcome the drawbacks of RM. In the *(s,t,n)*-LRM
scheme, 0<*s*≤*t*≤*n* 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.