Single-Deletion Single-Substitution Correcting Codes

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.