Multiple insertion/deletion correcting and detecting codes : structural analysis, constructions and applications

D.Ing.This thesis is dedicated to an analysis of fundamental topics and issues related to deterministic insertion/deletion correcting and detecting codes. The most important contributions in this respect are the construction of a multiple insertion/deletion correcting code for run-length limited sequences and the construction and applications of multiple deletion (insertion) detecting codes. It is shown how run-length constraints and higher order moments can be combined to create a code which is simultaneously multiple insertion/deletion error correcting and runlength constrained. A systematic form of this code is presented, whereby any arbitrary run-length constrained sequence can be made into a multiple insertion/deletion correcting codeword by adding a prefix. This prefix is appended to the run-length constrained sequence in such a way that the resulting codeword is itself run-length constrained. Furthermore, it is shown that, despite the run-length constraints, the resulting code is guaranteed to have a better asymptotic rate than the Helberg code, the only other known non-trivial deterministic multiple insertion/deletion correcting code. We consider insertion/deletion detecting codes and present a multiple deletion (insertion) detecting code. It is shown that this code, which is systematic, is optimal in the sense that there exists no other systematic multiple deletion (insertion) detecting code with a better rate. Furthermore, we present a number of applications of such codes. In addition, further related topics of interest are considered. Firstly, jitter as a fundamental cause of insertion/deletion errors is investigated and as a result a counterpart to the signal-to-noise ratio in the amplitude domain is proposed for the time domain. Secondly, motivated by the correspondence of Levenshtein and Varshamov-Tenengol’ts codes, we investigate the insertion/deletion correcting capability of the single asymmetric error correcting Constantin-Rao codes within a wider framework of asymmetric error correcting and insertion/deletion correcting code structure correspondences. Finally, we propose a generalisation of Tenengol’ts’ construction for multiple non-binary insertion/deletion correction