CRII: CCF: Low-Complexity Coding at Optimal Length

长期以来，编码理论一直专注于设计纠错码，并假设传输信息的长度可以任意大。然而，现代设置，如物联网和机器对机器通信，要求设备以非常小的延迟进行短消息通信，同时保持高度可靠性。这让人想起了编码理论中一个长期存在的挑战：设计提供高可靠性和低延迟的低复杂性信道代码。该项目旨在开发非常适合不断发展的信息基础设施需求的纠错技术。本研究将探讨两类丰富的代码设计：流代码和里德-穆勒代码。最近由研究者和合著者提出的流码结合了卷积编码和迭代解码的强大功能，而Reed-Muller码是经典的代码设计，最近被证明可以在擦除信道中实现容量。初步研究表明，流码和里德-穆勒码在短长度下都有显著的性能，但使用高度复杂的解码器，这就提出了是否可以找到计算效率高的解码器的问题。该项目侧重于开发新的算法和分析框架，旨在：(i)设计高效的解码算法；（ii）开发新的理论框架来分析所提出的算法；（iii）在非渐近状态下建立基本的长度-利率-复杂性权衡。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Coding theory has for long focused on designing error-correcting codes with the assumption that the length of the transmission message can be made as large as desired. Modern settings, however, such as the Internet of Things and machine-to-machine communication, require devices to communicate short messages with very small delays while maintaining a high degree of reliability. This conjures up a long-standing challenge in coding theory: design low-complexity channel codes that provide high reliability and low latency. This project aims to develop error-correcting technologies well-suited to such demands of the evolving information infrastructure.This research will investigate two rich classes of code-designs: stream codes and Reed-Muller codes. Stream codes, recently proposed by the investigator and co-authors, combine the powerful features of convolutional encoding and iterative decoding, while Reed-Muller codes are classic code designs that have recently been shown to achieve capacity in erasure channels. Preliminary studies suggest that both stream and Reed-Muller codes have remarkable performance at short lengths, but using highly complex decoders, posing the issue of whether computationally efficient decoder may be found. This project focuses on developing novel algorithmic and analytical frameworks aiming to: (i) design efficient decoding algorithms; (ii) develop new theoretical frameworks for the analysis of the proposed algorithms; and (iii) establish fundamental length-rate-complexity trade-offs in the non-asymptotic regime.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.