Bounds for codes correcting insertion, deletion and substitution errors

Abstract

When data is stored, transmitted or read, errors occur. In order to be able to
correct these errors, error-correcting codes are used. These codes add redundant
information, in order to be able to correct errors that might occur. There are
three types of errors hat might occur, namely substitution, insertion and deletion errors. Substitution errors are errors where the original symbol is wrongly
decoded or stored and the receiver reads another symbol. Insertion errors are
errors where the receiver reads a symbol at location where there should not
be a symbol and a deletion error is an error where the receiver does not read a
symbol while the reader should have. Substitution errors are the most common
and therefore, codes which correct these type of errors are ore extensively examined. There are however methods of storing data, for example storing data
using DNA as medium, for which insertion and deletion or indel errors occur at
a significant rate and therefore error-correcting codes should not only be able
to correct substitution errors, but also indel errors.We want codes to be
as efficient as possible, in other words, to be able to correct as many errors as
possible by adding as few redundant symbols as possible. The size of a code
is the number of codewords in a code and we would like this number to be as
big as possible. Ward Spee has done research into the maximum size of error-
correcting codes that can correct exactly t' deletions, exactly t′′ insertions and
at most s substitutions for his masters thesis at the University of Technology
Delft. In his research he has found various bounds on he size of these error-
correcting codes. These bounds contain the size of a set V which is not known.
This bachelor thesis project revolves around determining bounds on this size.