CIF: Small: New Coding Techniques for Synchronization Errors

编码理论促进了我们对如何有效地纠正符号损坏和擦除的理解。该理论开发的纠错码对技术和工程以及数学、理论计算机科学和其他领域产生了巨大的实际和理论影响。然而，虽然自20世纪60年代以来也在研究纠正密切相关的同步错误，如插入和删除，但迄今为止在很大程度上阻碍了进展。本提案的目标是缩小这一差距，并开发更好的理解和新的编码技术的同步错误。除了解决自然和基本误差模型的基本问题外，研究人员认为，该研究有可能指导使用有效编码技术来共同解决同步和噪声问题的系统设计，而不是花费大量资源来确保对同步的严格控制。该项目将建立在研究人员及其学生最近在这一领域的工作基础上，并研究新的编码方法来处理插入/缺失。对于大型有限字母表的情况，该项目将研究基于同步字符串的代码。同步字符串隔离并直接处理同步方面，该同步方面将插入和删除错误与符号损坏和擦除区分开，从而产生将它们减少为常规错误的有效方法。这样的转换可以利用常规纠错码在设计插入-删除码方面取得的巨大进展。该项目还将研究设置二进制或非常小的字母表的新方法，目的是更好地理解插入-删除代码的潜力以及有效的构造。除了简单的插入和删除之外，该项目还将研究更多来自实际应用的一般同步错误模型，如串联重复序列或块损坏。教育部分将把项目中的适当概念纳入调查人员讲授的课程，并利用该专题的易接近性和吸引力，除研究生的大量参与外，还将吸引本科生参与研究。该项目旨在加强计算机科学和信息理论界之间的知识联系，这两个团体都积极参与各种模型中代码的研究。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.