• Diese Seite als PDF öffnen.

Analysis of Criss-Cross Deletion in Arrays

Description

yle="font-weight: normal;" lang="de-DE" align="left">In this project we study two dimensional deletion/insertion problem introduced in https://arxiv.org/pdf/2004.14740.pdf. An array of n rows and n columns is transmitted through a specific deletion channel which for example occurs in DNA storage systems and racetrack memories. After transmission the receiver observes an array of dimension (n-1)*(n-1). The goal is to allow the receiver to know exactly which n*n array was transmitted by using error-correction techniques.

The goal of the project is to derive bounds on the deletion ball of any two-dimensional array. A deletion ball of an array X is the set of unique arrays resulting from the deletion of any possible combination of a column and a row in X. Deriving such bounds is not trivial since it depends heavily on the structure of the array. Thus, it is important to investigate useful characteristics representing the structure of an array for this particular setting. Furthermore, having this bound will be helpful to characterize the optimal redundancy of a deletion-correcting code for this setting.

Supervisor:

• Diese Seite als PDF öffnen.

Deletion Substitution Correcting Codes

Description

Topic for "Hauptseminar Digitale Kommunikationssysteme" (MSEI) (https://www.ei.tum.de/index.php?id=5492) NOT for "Seminar on Topics in Communications Engineering" (MSCE).

In recent years DNA storage has become an uprising topic due to its high-density and long-term storage capabilities. However, stored sequences experience multiple types of errors such as deletion, insertion and substitutions. Therefore, finding codes correcting the combination of such errors is of high interest.

The student's task is to understand and investigate the coding scheme of [1], which  the combination of a single-deletion and multiple substitutions errors. They use techniques proposed in [2] and [3].

References

• [1] Song, Wentu, and Kui Cai. "Systematic Single-Deletion Multiple-Substitution Correcting Codes." arXiv preprint arXiv:2006.11516 (2020).

• [2] Smagloy, Ilia, et al. "Single-Deletion Single-Substitution Correcting Codes." arXiv preprint arXiv:2005.09352 (2020).

• [3] J. Sima and J. Bruck, “Optimalk-deletion correcting codes,” 2019,Available online at: https://arxiv.org/abs/1910.12247

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

Error Correction in DNA Storage

Keywords:
DNA storage, Error Correction, Deletion, Insertion, Substitutions

Description

DNA storage is an uprising topic in the research field of storage systems. Due its natural longetivity, robustness, and density properties the main application would arise in high-dense long-term storage systems. The interest has become larger and larger due the large amount of data nowadays and the relative new biological advances in DNA synthesis and sequencing processes (e.g. polymerase chain reaction). In contrary to conventional storing methods, due to the nature of DNA and the involved biological processes special error patterns such as insertion, deletion, and substitution errors occur. To tackle these errors novel methods for correction have to be investigated. Moreover, the model of the DNA storage channel needs to be investigated thorougly, e.g. capacity statements.

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

Concatenated Codes for Recovery from Multiple Insertion/Deletion/Substitution Channels

Description

Due to occurence of syncronization erros in the uprising topic "DNA storage", efficient and good performing coding schemes have to be studied.

In this work a concatenated coding scheme will be investiagted which tackles the loss of symbol synchronization at the receiver's side but simultenously exploiting the gain of having multiple corrupted reads of the same stored sequence.

Supervisor:

Student