CIF: AF: Small: Data Processing Against Synchronization Errors

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

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.