CIF: AF: Small: Data Processing Against Synchronization Errors

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

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.