Reed-Muller Codes Achieve Capacity on Erasure Channels

Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, Rüdiger L. Urbanke

Abstract

We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori (MAP) decoding. Rather than relying on the precise algebraic structure of the codes, our method exploits code symmetry. Specifically, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. We show that symmetry alone implies near-optimal performance. An important consequence is that a sequence of Reed-Muller (RM) codes with increasing blocklength and converging rate achieves capacity, a result that extends to all affine-invariant codes, including extended primitive narrow-sense BCH codes.

Introduction

Since Claude Shannon’s 1948 seminal work, coding theorists have searched for practical, deterministic codes that can reach the theoretical limit of data transmission, known as capacity. While random codes achieve capacity with high probability, they are computationally impractical.

Reed-Muller codes, introduced in 1954, are among the oldest and most elegant classes of error-correcting codes. They are highly structured and have been used in historic missions like Mariner 9. For decades, researchers suspected that RM codes could achieve capacity, but a formal proof remained elusive for any rate other than 0 or 1. The challenge lay in the fact that RM codes lack the sparse structure of LDPC codes or the recursive structure of Polar codes, making traditional analysis techniques difficult to apply.

Methodology: Symmetry and EXIT Functions

The authors move away from analyzing the precise algebraic "recipe" of the code and instead exploit code symmetry. The proof relies on two primary tools: the Area Theorem for Extrinsic Information Transfer (EXIT) functions and the sharp threshold property for symmetric monotone boolean functions.

EXIT Functions and the Area Theorem

EXIT functions measure how much information a decoder can recover about a specific bit given observations of all other bits. A fundamental property used here is the Area Theorem, which states that the total area under the average EXIT curve is exactly equal to the code's rate ($r$).

Average EXIT functions for Reed-Muller codes of varying blocklengths N. As N increases, the transition becomes increasingly sharp, illustrating the threshold effect.

Double Transitivity and Sharp Thresholds

The core of the proof borrows from theoretical computer science: the study of monotone boolean functions. In contexts like random graphs, certain properties appear suddenly as a threshold is crossed. The authors demonstrate that if a code's permutation group is doubly transitive—meaning any pair of bit positions can be mapped to any other pair by a symmetry of the code—the EXIT function must exhibit a "sharp threshold."

As shown in the figure above, as the blocklength $N$ increases, the EXIT curve transitions from 0 to 1 almost instantaneously. This transition occurs at the exact point required by the Area Theorem ($1-r$), which is the mathematical definition of achieving capacity on the Binary Erasure Channel (BEC).

Key Insights

  • Symmetry is Power: The most profound insight is that near-optimal performance is a mathematical necessity for codes that are "symmetric enough." If a code is doubly transitive, its performance must converge to the Shannon limit as blocklength grows.
  • Boolean Function Analysis: By recognizing that the EXIT function of a linear code on an erasure channel is essentially a monotone boolean function, the authors applied tools like the Friedgut-Kalai theorem and the Margulis-Russo lemma—typically reserved for combinatorics—to coding theory.
  • Broad Applicability: Because the proof relies on symmetry rather than specific construction, it automatically proves capacity for Affine-Invariant codes, including extended primitive narrow-sense BCH codes and Quadratic-Residue codes.

Results and Implications

This work formally proves that sequences of Reed-Muller codes with increasing blocklength and converging rates achieve capacity on the BEC under both bit-MAP and block-MAP decoding. This settles a 60-year-old conjecture and provides the first proof that sequences of binary cyclic codes (specifically BCH codes) can be capacity-achieving.

Furthermore, the results extend to $F_q$-linear codes over $q$-ary erasure channels, showing that Generalized Reed-Muller codes also achieve capacity. This establishes a new framework for proving the optimality of deterministic codes based on their automorphism groups.

Limitations and Future Work

While this is a landmark result, it is currently tailored to the Binary Erasure Channel (BEC). Proving that RM codes achieve capacity on more complex channels, such as the Additive White Gaussian Noise (AWGN) channel, remains an open challenge because the "monotonicity" property used here does not translate directly to channels with noise.

Additionally, the proof focuses on MAP decoding, which is often computationally expensive. While RM codes have efficient decoding algorithms, this proof does not inherently guarantee that capacity can be reached with linear-time complexity. Future research may extend this symmetry-based approach using Generalized EXIT (GEXIT) functions to address a broader range of communication media.

Summary updated

Abstract

We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In other words, we show that symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing blocklength and converging rate achieves capacity. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proof are the sharp threshold property for symmetric monotone boolean functions and the area theorem for extrinsic information transfer functions.
BibTeX
@article{kudekar2017reed,
  author = {Shrinivas Kudekar and Santhosh Kumar and Marco Mondelli and Henry D. Pfister and Eren Sasoglu and Rüdiger L. Urbanke},
  title = {{Reed-Muller Codes Achieve Capacity on Erasure Channels}},
  journal = {IEEE Trans. Information Theory},
  year = {2017},
  url = {https://openreview.net/forum?id=o5MmXFBWjpZ},
}
Figure