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

点击翻译按钮获取中文摘要

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.