论文标题
芦苇 - 穆勒代码：理论和算法
Reed-Muller Codes: Theory and Algorithms
论文作者
论文摘要
Reed-Muller（RM）代码是最古老，最简单，也许最无处不在的代码系列之一。它们在电气工程和计算机科学的许多领域中都用于编码理论。但是，他们的许多重要特性仍在研究中。本文涵盖了有关重量枚举者的一些最新发展以及RM代码的能力调整特性以及一些算法的发展。特别是，本文讨论了RM代码，布尔函数的阈值，极化理论，超收缩率以及使用较低程度多项式近似低体重代码字的技术之间建立的连接。然后，它概述了一些具有性能保证的算法，以及某些具有最先进性能的算法。最后，本文结束了一些开放问题。
Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials. It then overviews some of the algorithms with performance guarantees, as well as some of the algorithms with state-of-the-art performances in practical regimes. Finally, the paper concludes with a few open problems.
