Coding techniques for insertion/deletion error correction

D. Ing.In Information Theory, synchronization errors can be modelled as the insertion and deletion of symbols. Error correcting codes are proposed in this research as a method of recovering from a single insertion or deletion error; adjacent multiple deletion errors; or multiple insertion, deletion and substitution errors. A moment balancing template is a single insertion or deletion correcting construction based on number theoretic codes. The implementation of this previously published technique is extended to spectral shaping codes, (d, k) constrained codes and run-length limited sequences. Three new templates are developed. The rst one is an adaptation to DC-free codes, and the second one is an adaptation to spectral null codes. The third one is a generalized moment balancing template for both (d, k) constrained codes and run-length limited sequences. Following this, two new coding methods are investigated to protect a binary sequence against adjacent deletion errors. The rst class of codes is a binary code derived from the Tenengolts non-binary single insertion or deletion correcting code, with additional selection rules. The second class of codes is designed by using interleaving techniques. The asymptotic cardinality bounds of these new codes are also derived. Compared to the previously published codes, the new codes are more exible, since they can protect against any given xed known length of adjacent deletion errors. Based on these two methods, a nested construction is further proposed to guarantee correction of adjacent deletion errors, up to a certain xed number