Coding Problems In Data Storage

Data storage can be seen everywhere in modern society.In real life,according to different application scenarios,people have various requirements for data storage devices,such as high storage density,high access speed,high reliability,low power consumption and long storage time.Flash memory is a non-volatile storage device and it can be electrically erased and re-programmed.It is widely used in reality because of its high storage density,fast reading and writing speed,low power consumption and low cost.On the other hand,DNA storage has been studied by many researchers in recent years because of its two characteristics:the storage density is much higher than that of all existing storage devices and it is capable of storing data for an extremely long time.Due to various reasons,there may be inevitable errors in the process of data storage.Therefore,it is necessary to apply coding technique to data storage.The main purpose of this thesis is to utilize tools form algebra,number theory and combinatorics to study mathematical problems related to coding schemes in flash memory and DNA storage.In Chapter 1,we introduce the research backgrounds of the subjects involved in this thesis,and briefly state our contributions to these fields.In Chapter 2,we study splitter sets,which have a close connection with coding problems in flash memories.The inherent asymmetry between cell programming(charge injection into cells)and cell erasure(charge removal from cells),as well as the slow process of charge leakage in cells,are two common reasons for data errors in flash memory.Taking into account these two error types and their properties,it is reasonable for us to apply the unbalanced limited-magnitude error model to the multi-level flash memory technology.In this model,the coding problem in multi-level flash memory is transformed into the problem of constructing splitter sets.Besides,perfect splitter sets correspond to perfect codes,which is of interest in practice.As for this problem,we forward the existing works.Firstly,we use tools from algebra to determine the necessary and sufficient conditions under which there exists a nonsingular perfect B[-k1,k2](p)set,where 0?k1?k2=4,and thus completely solve the problem for the case k2=4.When the conditions are satisfied,we present explicit constructions of perfect splitter sets.Secondly,using the tools from number theory,we give a simpler characterization of the existence of nonsingular perfect splitter sets when the parameters satisfy certain conditions.Thirdly,we give four new constructions of quasi-perfect splitter sets.Lastly,we connect splitter sets with Cayley graphs,which is helpful for us to find the maximum splitter sets via mathematical software.In Chapter 3,we study the sequence reconstruction problem,which has a close connection with DNA storage.The study of sequence reconstruction problem was initiated by Levenshtein in 2001.As a generalization of the classical error-correction,the reconstruction problem aims to correct errors by several noisy reads.In 2020,motivated by applications in racetrack memeories and DNA storages,Cai and Yaakobi et al.began to study the dual problem,that is,designing codes with redundancy as small as possible for a given number N of noisy reads.In this chapter,the minimum redundancy of such codes for binary channels with exactly two insertions are determined asymptotically for all values of N>6.For N=6,we reduce the current best known upper bound on the redundancy from 4log2(n)to 2log2(n)for length-n binary codes.The explicit constructions of codes are based on completely characterizing the conditions under which two binary sequences have a fixed number of common supersequences.In Chapter 4,we briefly introduce the author's other research works when pursuing his PhD degree.