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 errorcorrecting 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 errorcorrecting 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.