U. S.-Russian Collaborative Research: Codes for Multiple-Access Channels, Genetic Testing, Deletion-Insertion Correction, and Synchronization

同步是数据可靠传输的重要组成部分。利用代数编码理论和组合编码理论研究了异步多址信道中的冲突避免问题。集合的差分系统是一种组合结构，用于促进具有良好同步特性的代码的设计。在没有字同步的情况下，无逗号编码在冲突信道传输协议的组织中发挥了作用。组测试技术在故障检测、错误控制代码和实验设计中有许多应用。近年来，群体检测在多址通信、遗传信息分析、染色体定位和DNA文库筛选等领域的新应用得到了广泛的研究。本项目探讨了最优的两阶段测试方案和最小化预期测试数量的组合设计之间的联系，以及通过其子序列或超序列重建序列的算法。丢包是Internet传输中常见的错误来源，它重新引起了对删除纠错码的兴趣。关于删除和插入纠错码的研究将集中在寻找具有规定纠错能力的码的最佳大小的界，以及超过吉尔伯特界的良好的2-删除纠错码的构造，以及产生最佳删除-插入纠错码的有序斯坦纳系统的构造。提出的研究计划提供了一个极好的机会，向研究生和高年级本科生介绍使用计算机来学习和解决涉及大规模代数和组合运算的问题，这些问题应用于规模庞大的数据结构上，并利用计算机作为学习和解决当今信息时代科学和工程各个领域出现的现实问题的工具。

Synchronization is an important component of reliabledata transmission. The problem of avoiding conflicts in asynchronousmultiple-access channels is investigated by utilizing methods fromalgebraic and combinatorial coding theory.Difference systems of sets are combinatorial structuresthat are being used to facilitate the design of codes with goodsynchronization properties. Comma-free codes are brought into play in the organization of protocols for transmission over collision channels in the absence of word synchronization. Group testing techniques have numerous applications in fault detection, error-control codes, and experimental designs.In recent years, group testing has been studied in connection with emerging new applications in multi-access communications,the analysis of genetic information, chromosome mapping,and DNA library screening. This project explores the link between optimal 2-stage testing schemes and combinatorial designs that minimize the expected number of tests, as well as algorithms for the reconstruction of sequences by their subsequences or super-sequences. Packet loss is a common source of errors in Internet transmissions that has renewed the interest in deletion-correcting codes. The research concerning deletion and insertion correcting codes will focus on finding bounds on the optimal size of a code with prescribed error-correcting capacity, as well asconstructions of good 2-deletion-correcting codes that exceedthe Gilbert bound, and constructions of ordered Steinersystems that yield optimal deletion-insertion correctingcodes. The proposed research program presents an excellent opportunity for introducing graduate and upper level undergraduatestudents to the use of computers for learning and solving problemsthat involve large scale algebraic and combinatorial operations applied on data structures of formidable size, and utilizingthe computer as a tool for learning and solving real-world problemsthat arise in various areas of science and engineeringof today's information age.