Coding for the Correction of Synchronization Errors

Synchronisation is often assumed by the information engineer when working with data. However, diverse systems such as magnetic and optic storage systems, semiconductor devices as well as communication networks are affected by uncertainties in timing. This timing noise introduces or removes spurious symbols in the symbol stream, known as insertion or deletion errors. These errors differ from additive errors and erasure errors in that both the position and value of the error must be determined before correction can take place. In this seminar a brief survey of previous work in synchronization error correction coding is given. We start by introducing definitions for different synchronization errors, followed by definitions for synchronization error correction. The foundation for correcting synchronization errors provided by VI Levenshtein is then discussed. We finally present a general construction of binary algebraic block codes for the correction of multiple random insertion/deletion errors. The talk is concluded with some open problems and possible novel applications of synchronization error correction adjacent to the field of Network Coding. Synchronization error correcting coding is seldom mentioned in literature, due to the lack of understanding of the theory of synchronization channels as well as a lack of adequate mathematical models for this class of errors. This seminar should be of interest to anyone that haven’t come across these codes before and aims to stimulate interest in this research field.