On the Error Probability of RPA Decoding of Reed-Muller Codes over BMS Channels

Technical Summary: On the Error Probability of RPA Decoding of Reed-Muller Codes over BMS Channels

Problem Statement
Reed-Muller (RM) codes are a fundamental family of binary linear codes known to achieve channel capacity over Binary Memoryless Symmetric (BMS) channels. While the theoretical capacity-achieving property is established, practical decoding remains a challenge. The Recursive Projection-Aggregation (RPA) decoder, introduced by Ye and Abbe, has demonstrated near-maximum likelihood (ML) performance for RM codes over the Binary Symmetric Channel (BSC). However, rigorous analytical performance guarantees for RPA decoding over general BMS channels were previously lacking. While recent work by Rameshwar and Lalitha (2025) provided such guarantees for the BSC, extending these results to arbitrary BMS channels is non-trivial; a direct generalization of their proof strategy requires restrictive assumptions on the channel (e.g., bounded output alphabet size and bounded log-likelihood ratios). This paper addresses the gap by deriving explicit error probability bounds for RPA decoding over general BMS channels without such restrictive assumptions.

Methodology
The authors develop a proof strategy that generalizes the approach used for the BSC by leveraging a specific structural equivalence between the RPA decoder and polar code construction.

1. Channel Equivalence: The core technical insight is identifying an equivalence between the projection operation in RPA decoding and the "channel combining" phase in polar code construction. Specifically, projecting an RM code along a one-dimensional subspace induces a new channel, denoted as $W^-$, which is identical to the channel resulting from combining two independent uses of the original BMS channel $W$.
2. Bhattacharyya Parameter Analysis: Using this equivalence, the authors analyze the evolution of the Bhattacharyya parameter ($Z$) through the recursion tree of the RPA decoder. They establish that the Bhattacharyya parameter of the induced channel at each step satisfies $Z(W^-) \leq 1 - (1 - Z(W))^2$. This allows them to bound the channel quality at the "leaves" of the recursion tree (where first-order RM codes are decoded) in terms of the initial channel parameter.
3. Recursive Error Bounding: The analysis focuses on the case where a single iteration of the RPA decoder suffices for convergence. The authors derive recurrence relations for the error probability at each node of the RPA recursion tree.
   • Base Case: For the leaf nodes (first-order RM codes), they employ a generic union bound on the ML error probability. Crucially, this bound holds for any BMS channel, avoiding the need for specific channel constraints.
   • Recursive Step: For higher-order nodes, the error probability is bounded by the probability of errors in child nodes and the probability of error in the aggregation step, conditioned on correct child decoding.
4. Unrolling the Recursion: By unrolling these recurrence relations, the authors derive a closed-form upper bound on the total block error probability, $P_{err}(RM(m, r))$, as a function of the blocklength $n = 2^m$ and the code order $r$.

Key Contributions and Results
The primary contribution is Theorem 4, which provides an analytical guarantee for the vanishing error probability of the RPA decoder over general BMS channels.

• Main Result: The paper proves that for a BMS channel with Bhattacharyya parameter $Z$, the RPA decoder achieves vanishing error probability as the blocklength $n \to \infty$ (or equivalently $m \to \infty$) provided the RM order $r$ scales roughly as:
  $$r < \log_2 m - \log_2 \lambda$$
  where $\lambda = -\ln(1-Z)$.
• Asymptotic Scaling: This scaling implies that $r$ grows logarithmically with $m$ (i.e., $r \sim \log \log n$). This asymptotic behavior is identical to the result previously established for the BSC in [19].
• Generality: Unlike previous attempts to generalize the BSC proof, this technique requires no additional assumptions on the BMS channel (such as bounded log-likelihood ratios). The proof relies solely on the properties of the Bhattacharyya parameter and the structural equivalence to polar code combining.

Significance and Claims
The paper claims that its work is a significant generalization of the 2025 result by Rameshwar and Lalitha. By establishing that the RPA decoder provably achieves vanishing error probabilities for "low-rate" RM codes (where the order scales as $\log \log n$) over all BMS channels, the authors extend the theoretical understanding of RPA decoding beyond the BSC.

The authors note that while their derived bound for the BSC is slightly weaker than the specific bound in [19] (due to the generality required for arbitrary BMS channels), the asymptotic growth rate of the code order $r$ remains the same. They explicitly state that their analysis restricts attention to the regime where a single iteration of the decoder suffices. Consequently, they suggest that relaxing this restriction to analyze the correlations introduced by multiple iterations is a key direction for obtaining further asymptotic improvements in error probability, though this is not achieved in the current work.

In summary, the paper provides the first rigorous, assumption-free analytical proof that the RPA decoder is effective for RM codes over the broad class of BMS channels, confirming that the decoder's performance scales favorably with blocklength even in the absence of specific channel constraints.