Bounds on the maximum size of deletion, insertion and substitution correcting codes

Abstract

Coding techniques for correcting
combinations of deletion, insertion and substitution errors are implemented in
novel data storage applications. Error correcting codes have been well-studied
for either substitution errors, or deletion and insertion (indel) errors, but
the understanding of codes that correct combinations of these errors falls
short. To achieve an efficient implementation in terms of redundancy, we are
interested in the maximal size of a code that can correct t indels and s
substitutions. Determining this maximal size in general is a difficult task,
and thus in many instances we have to rely on bounds. In this thesis, we review
existing bounds on the maximal size of both t-indel correcting codes and
s-substitution correcting codes. Thereafter, we study how these bounds can be
generalized to the setting of t-indel s-substitution correcting codes.  The main contributions of this thesis include
two new explicit lower bounds, which are based on generalizations of the
Gilbert-Varshamov bound. Furthermore, we show that the Singleton upper bound,
several existing sphere-packing upper bounds and an upper bound based on
matchings in hypergraphs can all be generalized to upper bounds on the maximal
size of t-indel s-substitution correcting codes. Several of these bounds provide
improvements upon existing results in literature. Moreover, we argue that the asymptotic
redundancy of maximally sized t-indel s-substitution correcting codes lies between
(t + s) logq(n) and 2(t + s) logq(n) + o(logq(n)).