Reed-Muller Codes
By Emmanuel Abbe, Mathematics Institute and the School of Computer and Communication Sciences, EPFL, Switzerland, emmanuel.abbe@epfl.ch | Ori Sberlo, Blavatnik School of Computer Science, Tel Aviv University, Israel, ori.sberlo@gmail.com | Amir Shpilka, Blavatnik School of Computer Science, Tel Aviv University, Israel, shpilka@tauex.tau.ac.il | Min Ye, Tsinghua-Berkeley Shenzhen Institute, Tsinghua Shenzhen International Graduate School, China, yeemmi@gmail.com
Abstract
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 work covers some of the developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, it discusses 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, giving 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, some applications of RM codes in theoretical computer science and signal processing are given.
Reed-Muller Codes
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.
In this monograph the authors consider some of the most recent developments in RM codes that are having major impacts on the design of modern communication systems. These include weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, they discuss connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords. They then overview some of the algorithms for decoding RM codes. The monograph concludes by looking at some applications of RM codes in theoretical computer science and signal processing.
This monograph is written in a tutorial style, introducing the reader to the basics of RM codes before building in each chapter to cover the wide-ranging topics that make this a comprehensive overview of RM codes for current and future communication systems.
