Correcting insertions/deletions as well as substitution errors simultaneously plays an important role in DNA-based storage systems as well as in classical communications. This paper 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 non-asymptotic redundancy of such a code of length$n$has to be at least$(s+1) \log _{q} n$. An explicit construction of binary single-deletion single-substitution correcting codes with at most$6 \log n + 8$redundancy bits is presented.

This paper 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$({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$-criss-cross deletionsif${t_{\mathrm {r}}}$rows and${t_{\mathrm {c}}}$columns are deleted, while a code correcting these deletion patterns is called a$({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$-criss-cross deletion correction code. The definitions forcriss-cross insertionsare similar. It is first shown that when$t_{r}=t_{c}$the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper 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+2\log 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$5\log n + 5$bits of redundancy to the construction.

Correcting insertions/deletions as well as substitution errors simultaneously plays an important role in DNA-based storage systems as well as in classical communications. This paper 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 singledeletion single-substitution correcting codes is derived, showing that the redundancy of such a code of length n has to be at least 2 log n. The bound is presented both for binary and non-binary codes while an extension to single deletion and multiple substitutions is presented for binary codes. An explicit construction of single-deletion single-substitution correcting codes with at most 6 log n + 8 redundancy bits is derived. Note that the best known construction for this problem has to use 3-deletion correcting codes whose best known redundancy is roughly 24 log n.