CRII: CCF: Low-Complexity Coding at Optimal Length

长期以来，编码理论一直专注于设计纠错码，其假设是传输消息的长度可以根据需要变得尽可能长。然而，现代环境，如物联网和机器对机器通信，要求设备在保持高度可靠性的同时以非常小的延迟通信短消息。这就引出了编码理论中一个长期存在的挑战：设计提供高可靠性和低延迟的低复杂度信道码。该项目旨在开发适合于不断发展的信息基础设施的这种需求的纠错技术。本研究将研究两类丰富的代码设计：流代码和Reed-Muller代码。最近由研究人员和合著者提出的流编码结合了卷积编码和迭代译码的强大特性，而Reed-Muller码是最近被证明在擦除信道中达到容量的经典编码设计。初步研究表明，STREAM码和Reed-Muller码在较短的长度上都有显著的性能，但使用的译码复杂度很高，这带来了能否找到计算效率高的译码的问题。该项目致力于开发新的算法和分析框架，旨在：(I)设计高效的译码算法；(Ii)开发新的理论框架来分析所提出的算法；以及(Iii)在非渐近状态下建立基本的长度率和复杂性之间的权衡。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.