Upper bounds for deletion correcting codes
J.D.H. Ladd (TU Delft - Electrical Engineering, Mathematics and Computer Science)
J.H. Weber – Mentor (TU Delft - Discrete Mathematics and Optimization)
JAM de Groot – Graduation committee member (TU Delft - Mathematical Physics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The world can’t keep up with its own data and therefore needs new ways to store it. Research is being done into new types of experimental data storage like DNA sampling or racetrack memory, which could completely revolutionize the way storage works. However, such storage media are prone to certain type of errors like deletion errors where information is lost. Consequently, there has been a surge in interest in developing deletion correcting codes to address this challenge. We are interested in the maximal size of a code correcting up to a certain number of deletions. Nevertheless, constructing these codes can be quite intricate and therefore we are often limited to working with bounds.
In this thesis, we will study and evaluate upper bounds for these codes. We will compare bounds that were derived analytically to bounds that have been computed with the use of linear programs. We will compute upper bounds for 1-, 2- and 3-deletion correcting codes. Moreover, we will show how to compute these bounds with a linear program, by posing the problem of finding a largest deletion correcting code as finding the transversal number on a hypergraph. It will become clear that the bounds computed through linear programming are much stronger than any bound derived analytically.