Reed-Muller Codes: Theory and Algorithms
Reed-Muller Codes: Theory and Algorithms
复制标题
DOI：
10.1109/tit.2020.3004749
复制
发表时间：
2021-06-01
影响因子：
2.5
通讯作者：
Ye, Min
中科院分区：
文献类型：
--
作者：
Abbe, Emmanuel;Shpilka, Amir;Ye, Min
Reed-Muller（RM）码是最古老、最简单、也可能是最普遍的一种码族。它们被用于电气工程和计算机科学中编码理论的许多领域。然而，它们的许多重要性质仍在研究中。本文涵盖了一些最新的发展，关于重量枚举和容量实现性能的RM码，以及一些算法的发展。特别是，本文讨论了RM码，布尔函数的阈值，极化理论，hypercontractivity，以及使用低次多项式近似低权重码字的技术（当码字被视为m个变量的r次多项式的评价向量时）之间最近建立的联系。然后概述了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 (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems.