Abstract
For over sixty years, Reed-Muller (RM) codes have been a cornerstone of coding theory, yet their ability to achieve Shannon capacity remained an unproven conjecture. This paper provides the formal proof that RM codes achieve capacity on the Binary Erasure Channel (BEC) under Maximum A Posteriori (MAP) decoding. By combining the information-theoretic properties of Extrinsic Information Transfer (EXIT) functions with the high degree of symmetry inherent in RM codes—specifically 2-transitivity—the authors demonstrate that these codes exhibit a sharp threshold at the theoretical limit of communication. This result not only settles a long-standing open problem but also extends to other symmetric codes, such as extended BCH codes.
Introduction
Since Claude Shannon's seminal 1948 work, the primary goal of coding theory has been to identify practical codes that can reach "capacity"—the maximum rate of reliable information transfer over a noisy channel. While Polar codes were the first to be mathematically proven to achieve capacity with efficient decoding, Reed-Muller (RM) codes, introduced in 1954, have long been observed to perform exceptionally well in practice, often outperforming Polar codes under optimal decoding.
Despite their historical significance and empirical success, proving that RM codes achieve capacity for all rates $0 < R < 1$ remained elusive. Unlike Polar codes, RM codes lack a simple recursive structure that facilitates easy analysis. This paper bridges this gap for the Binary Erasure Channel (BEC), where bits are either received correctly or lost entirely, by leveraging the deep mathematical symmetries of the RM code family.
Methodology
The proof is constructed upon four theoretical pillars that link information theory with the analysis of Boolean functions:
1. EXIT Functions and the Area Theorem
The authors utilize the Extrinsic Information Transfer (EXIT) function, which measures the probability that a specific bit cannot be recovered given the information from all other received bits. A fundamental result in coding theory, the Area Theorem, states that the integral of the average EXIT function over all erasure probabilities $\epsilon \in [0, 1]$ is exactly equal to the code's rate $R$. This provides a "budget" for the EXIT function's behavior.
2. The Role of 2-Transitivity
RM codes possess a high degree of symmetry known as 2-transitivity. This property implies that for any two pairs of bit positions, there exists a permutation in the code's automorphism group that maps one pair to the other. For the proof, this ensures that the EXIT functions for every single bit in the codeword are identical, allowing the authors to analyze the global behavior of the code by looking at a single bit.
3. Sharp Thresholds
Drawing from the study of monotone Boolean functions and the Friedgut-Kalai Theorem, the authors show that for highly symmetric codes, the EXIT function must behave like a step function as the block length $N$ tends toward infinity. It remains near zero (indicating successful recovery) until a specific noise threshold is reached, at which point it jumps almost instantaneously to one (indicating total failure).
Key Insights: Symmetry as a Proxy for Performance
The central breakthrough of this work is the realization that the exact structural details of a code are less important than its symmetry. Because RM codes are 2-transitive, the EXIT function is forced to be a sharp step function.
When this sharp step behavior is combined with the Area Theorem, the location of the "step" is mathematically constrained. Since the area under the step function must equal the rate $R$, the jump from 0 to 1 must occur at the erasure probability $\epsilon = 1 - R$. This value is precisely the Shannon capacity limit for the BEC. Thus, the symmetry of RM codes effectively forces them to be optimal.
Results and Implications
- Capacity Achievement: The paper formally proves that the sequence of Reed-Muller codes $RM(n, r)$ achieves capacity on the BEC under bit-MAP decoding as the block length $N = 2^n$ approaches infinity.
- Universality: The proof is "generic" in nature. It applies to any sequence of codes that are 2-transitive. Consequently, the authors note that extended Bose-Chaudhuri-Hocquenghem (BCH) codes are also capacity-achieving on the BEC.
- Independent Convergence: This finding was reinforced by the simultaneous and independent work of Kumar and Pfister, who reached the same conclusion using a nearly identical approach.
Limitations and Future Directions
While this work marks a significant theoretical milestone, several challenges remain for practical implementation:
- Decoding Complexity: The proof assumes Maximum A Posteriori (MAP) decoding, which is generally NP-hard for arbitrary codes. Future research is needed to determine if low-complexity decoders, such as Belief Propagation or Successive Cancellation, can also achieve capacity for RM codes.
- Channel Generalization: The current proof is specific to the Binary Erasure Channel. Extending these results to the Binary Symmetric Channel (BSC) or Additive White Gaussian Noise (AWGN) channels requires establishing monotonicity for "Generalized EXIT" (GEXIT) functions, which is significantly more complex.
- Scaling Laws: While the paper proves capacity in the infinite limit, the "scaling exponent"—how quickly the code approaches capacity as the block length increases—remains an active area of investigation to determine how RM codes compare to Polar codes in finite-length regimes.
Summary updated