CIF: AF: Small: Data Processing Against Synchronization Errors

CIF：AF：小：针对同步错误的数据处理

基本信息

批准号：
2006455
负责人：
Mahdi Cheraghchi Bashi Astaneh
金额：
$ 48.92万
依托单位：
Regents of the University of Michigan - Ann Arbor
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-10-01 至 2023-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006455&HistoricalAwards=false
关键词：
CIF AF Small Data Processing

项目摘要

This research project addresses fundamental challenges caused by imperfect or lacking synchronization in communications and information systems. Timing disparity, for example, between a sender and receiver pair or different components of a high-throughput processing unit may cause these errors. In such cases, the communicated symbols may be missed or registered multiple times by the receiver unit. In high-speed optical communications, data is encoded in the form of intensity variations of light beams. As photons travel through the communications medium, they may be absorbed or arrive at the destination in an unpredictable order. The photon detecting receiver will then need to translate the unreliable photon counts over time to the precise digital data being sent. More recently, reliable and extremely compact storage of massive digital data in DNA molecules has been an active subject of study. In such applications, the stored information is retrieved via existing DNA sequencing technologies that are also prone to synchronization errors. The scientific impacts of the project span the above-mentioned technologies that are of key significance to the processing, transmission, and storage of massive data. Educational aspects of the project include training postgraduate and undergraduate students and incorporating elements of the project into coursework.The above examples divide the specific goals of the project into three main categories. First, Shannon capacity of the deletion channel, as well as related communications channels, will be studied. A main goal will be to obtain provable and improved bounds on the information capacity. Second, Shannon capacity of the Poisson channel, a classical model for optical communications, will be studied. The project sets forth the novel hypothesis that the deletion and Poisson capacity problems, two of the longest-standing open problems in classical information theory since the 1960s, have remained unresolved due to shared mathematical difficulties, and thus should be studied with a shared perspective. Finally, the project studies the complexity of the trace reconstruction problem which provides a mathematical model to study the capacity of DNA storage systems.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.

该研究项目解决了由通信和信息系统中不完美或缺乏同步造成的基本挑战。例如，定时差异，例如，发件人对和接收器对或高通量处理单元的不同组件可能会导致这些错误。在这种情况下，接收器单位可能会多次遗漏传达的符号或注册。在高速光学通信中，数据以光束强度变化的形式编码。当光子穿过通信介质时，它们可能会被吸收或以不可预测的顺序到达目的地。然后，光子检测接收器将需要将不可靠的光子计数随时间转换为发送的精确数字数据。最近，DNA分子中大量数字数据的可靠且极其紧凑的存储一直是一个积极的研究主题。在这样的应用中，通过现有的DNA测序技术检索了存储的信息，这些技术也容易出现同步误差。该项目的科学影响涵盖了上述技术，这些技术对大量数据的处理，传输和存储至关重要。该项目的教育方面包括培训研究生和本科生，并将项目的要素纳入课程工作。以上示例将项目的特定目标分为三个主要类别。首先，将研究删除渠道的香农容量以及相关的通信渠道。一个主要目标是获得有关信息能力的可证明和改进的界限。其次，将研究Poisson Channel的Shannon容量，这是一种用于光学通信的经典模型。该项目阐述了一个新的假设，即自1960年代以来，删除和泊松容量问题是经典信息理论中最长的两个开放问题，由于共同的数学困难而无法解决，因此应以共同的观点进行研究。最后，该项目研究了痕量重建问题的复杂性，该问题提供了一个数学模型来研究DNA存储系统的能力。该奖项反映了NSF的法定任务，并认为使用基金会的知识分子和更广泛的影响审查标准，认为值得通过评估来支持。

项目成果

期刊论文数量（11）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Mean-Based Trace Reconstruction Over Oblivious Synchronization Channels

基于平均值的迹线重建在不经意的同步通道上

DOI：
10.1109/tit.2022.3157383
发表时间：
2022
期刊：
IEEE Transactions on Information Theory
影响因子：
2.5
作者：
Cheraghchi, Mahdi;Downs, Joseph;Ribeiro, Joao;Veliche, Alexandra
通讯作者：
Veliche, Alexandra

One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

MCSP 的一带图灵机和分支程序下界

DOI：
10.4230/lipics.stacs.2021.23
发表时间：
2021
期刊：
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021
影响因子：
0
作者：
Cheraghchi, Mahdi;Hirahara, Shuichi;Myrisiotis, Dimitrios;Yoshida, Yuichi
通讯作者：
Yoshida, Yuichi

Non-Asymptotic Capacity Upper Bounds for the Discrete-Time Poisson Channel With Positive Dark Current

正暗电流离散时间泊松通道的非渐近容量上限