Ph.D Thesis

Ph.D StudentBuzaglo Sarit
SubjectAlgebraic and Geometric Problems for Non-Volatile Memory
DepartmentDepartment of Computer Science
Supervisors PROF. Tuvi Etzion
Full Thesis textFull thesis text - English Version


Flash memory is the most important type of non-volatile memory (NVM) in use today. Flash devices are employed widely in mobile, embedded, and mass-storage applications, and the growth in this sector continues at a staggering pace. The high interest and many applications of such memories increase the importance of this research and lead to a wide range of stimulating problems.

Flash memory cells are electrically programmable to one of q discrete states and therefore, can store log2q bits. Reducing a cell state into a lower state requires the erasure of the whole block to which the cell belongs. In order to lower the probability of over-shooting errors, charge is injected into a cell over several iterations, which results in a slow programming. This PhD dissertation focus on two coding frameworks for flash memory: the asymmetric limited magnitude error model and the rank modulation scheme.

The asymmetric limited magnitude error model addresses the inherit asymmetric behavior of common error types in flash memory, under the reasonable assumption that errors are not likely to exceed a certain limit. In this context I mainly consider perfect codes. Using two concepts which are equivalent to perfect linear codes, namely, lattice tiling and group splitting, constructions of perfect linear codes are presented. These codes are of length n and can correct up to n-1 asymmetric errors with limited magnitude l, for every n and l. It is also proved that perfect linear codes do not exist for other parameters.

Rank modulation is a coding scheme that was designed to improve the efficiency of programming flash memory cells. Under this setup, data is encoded into permutations which are derived by the relative charge levels of the cells, rather than by their absolute levels. In this PhD dissertation the rank modulation scheme is studied for three fundamental concepts in coding theory; perfect codes, systematic codes, and constrained codes. The main results in this context include the nonexistence of some perfect single-error-correcting codes, construction of systematic codes, and capacity computations of codes under certain constraints.