CRII: CCF: Low-Complexity Coding at Optimal Length

编码理论长期以来一直专注于设计纠错码，假设传输消息的长度可以尽可能地大。然而，诸如物联网和机器对机器通信之类的现代设置要求设备在保持高度可靠性的同时以非常小的延迟传送短消息。这就引出了编码理论中一个长期存在的挑战：设计低复杂度的信道码，提供高可靠性和低延迟。本计画的目的是发展能适应资讯基础架构发展的错误更正技术，并将探讨两种丰富的编码设计：串流编码与Reed-Muller编码。流码，最近提出的研究人员和共同作者，联合收割机，结合了卷积编码和迭代解码的强大功能，而里德-穆勒码是经典的代码设计，最近已被证明可以实现擦除信道的容量。初步研究显示，流码和Reed-Muller码在短码长下都有显著的性能，但使用高度复杂的译码器，这就提出了能否找到计算效率高的译码器的问题，本项目集中于开发新的算法和分析框架，旨在：（i）设计有效的译码算法;（ii）开发新的理论框架用于分析所提出的算法;（iii）开发新的算法和分析框架。和（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.