CIF: Small: New Coding Techniques for Synchronization Errors

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Coding theory has advanced our understanding of how to efficiently correct symbol corruptions and erasures. The error-correcting codes developed by this theory have had a tremendous practical and theoretical impact on technology and engineering as well as mathematics, theoretical computer science, and other fields. Correcting closely related synchronization errors, such as insertions and deletions, however, while also studied since the 1960s, has largely resisted progress so far. The goal of this proposal is to close this gap and develop a better understanding of and new coding techniques for synchronization errors. In addition to resolving fundamental questions on natural and basic error models, the investigators believe that the study has the potential to guide the design of systems which use efficient coding techniques to address synchronization and noise issues jointly, instead of spending significant resources on ensuring very tight controls on synchronization. The project will build on the recent work in this area by the investigators and their students, and investigate new coding approaches for coping with insertions/deletions. For the case of large finite alphabets, the project will investigate codes based on synchronization strings. Synchronization strings isolate and directly tackle the synchronization aspect which distinguishes insertion and deletion errors from symbol corruptions and erasures, yielding an efficient way to reduce them to regular errors. Such a transformation can then leverage the tremendous progress made on regular error-correcting codes toward the design of insertion-deletion codes. The project will also investigate new approaches for the setting of binary or very small alphabets with the goal of better understanding the potential of insertion-deletion codes together with efficient constructions. Beyond simple insertions and deletions, the project will also study more general synchronization error models stemming from practical applications such as tandem repeats or block corruptions. The educational component will infuse appropriate concepts from the project into courses taught by the investigators, and take advantage of the accessible and attractive nature of the topic to engage undergraduates in research, in addition to the substantial involvement of graduate students. The project will aim to forge stronger intellectual ties between the computer science and information theory communities which are both actively engaged in study of codes in various models. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.