New Frontiers in Coding Theory: Reed-Muller and Polar Codes

编码理论是信息论与实际系统之间的重要桥梁，信息论研究数据传输的基本限制，而实际系统需要低复杂度的高效计算算法。本研究计划研究两个密切相关的码族——里德-穆勒码和极性码的基本理论和实际设计。在理论方面，我们计划攻击长期存在的猜测，即Reed-Muller码是在二进制无内存对称信道上的最大后先验解码下实现的容量。我们将从信道极化的角度来理解Reed-Muller码，并以Kudekar， Kumar, Modelli, Pfister， Sasoglu和Urbanke的令人兴奋的进展为基础，他们在二进制擦除信道的特殊情况下建立了码的最优性。在实践方面，我们计划研究最近发明的极性编码，这些编码已被新发布的5G NR（新无线电）标准所采用。首先，我们的目标是通过结合Peres的随机比特生成器的思想来提高极性码的有限长度性能。其次，我们计划在点对点通信之外的新应用中探索极化原理，例如无线网络中的多用户通信，新兴数据存储系统中的分布式压缩，内容交付网络的缓存技术，组测试的传感矩阵设计等。

Coding theory is an important bridge between information theory, which studies the fundamental limits of data transmission, and practical systems, which require low-complexity computationally efficient algorithms. This research program investigates fundamental theories as well as practical designs of two closely related families of codes---Reed-Muller codes and polar codes. On the theory side, we plan to attack the long-standing conjecture that Reed-Muller codes are capacity achieving under maximum a posteriori decoding over binary memoryless symmetric channels. We will perceive Reed-Muller codes from a channel polarization perspective and build on the exciting progress by Kudekar, Kumar, Modelli, Pfister, Sasoglu, and Urbanke, who established optimality of the code over the special case of binary erasure channels. On the practical side, we plan to investigate the recently invented polar codes, which have been adopted in the newly released 5G NR (New Radio) standard. First, we aim to improve the finite-length performance of polar codes by incorporating ideas from Peres's random-bit generator. Second, we plan to explore the polarization principle in new applications beyond point-to-point communication, such as multi-user communication in wireless networks, distributed compression in emerging data storage systems, caching techniques for content delivery networks, sensing matrix design for group testing, among others.