The Taub Faculty of Computer Science Events and Talks

Correcting insertions/deletions as well as substitution errors simultaneously plays an important role in DNA-based storage systems as well as in classical communications. However, in DNA data storage as well as in file/symbol synchronization, not only insertions/deletions occur, but also classical substitution errors. Additionally, some cases feature array-like words and as such pose a new type of variance in insertions/deletions errors - column insertions/deletions as opposed to row insertions/deletions. In the work presented, both cases are studied. The first part of the work presented here deals with the fundamental task of constructing codes that can correct a single insertion or deletion along with a single substitution.A non-asymptotic upper bound on the size of non-binary single-deletion s-substitution correcting codes is derived, showing that the redundancy of such a code of length n has to be at least (s+1) log n. An explicit construction of binary single-deletion single-substitution correcting codes with at most 6 log n + 8 redundancy bits is presented. The seconds part of the work presented here studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an n\times n array can experience deletions of rows and columns. These deletion errors are referred to as (tr,tc)-criss-cross deletions if tr rows and tc columns are deleted, while a code correcting these deletion patterns is called a (tr,tc)-criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is shown that when tr=tc the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. In this section, the focus lies on the case of (1,1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1,1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least 2n-3+2log n bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most 2n+4 log n + 7 +2 log e. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra 5log n + 5 bits of redundancy to the construction.