Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.16240

RPA Decoding with Few Subspace Projections for Correcting Structured Error Patterns in RM Codes

Shiv Pratap Singh Rathore, Navin Kashyap

Published Oct 12, 2026• 0 citations
arXivHTMLPDF

Abstract

The Recursive Projection Aggregation (RPA) decoder for Reed-Muller codes uses, in its default implementation, all one-dimensional subspaces at each level of recursion. We restrict our attention to the case where the number of errors is $t
DOI
10.48550/arxiv.2610.16240

Related papers

Coset Error Patterns in Recursive Projection-Aggregation Decoding

Fanyun Chen, Bin Zhang, Qin Huang

The recursive projection-aggregation (RPA) algorithm provides state-of-the-art performance for Reed-Muller (RM) codes. It relies on projecting onto subspaces, decoding projections and voting. This paper explores the error-correction capability of RPA with a limited number of subspaces. By constructing a false vote matrix, it demonstrates that RPA may fail to correct coset error patterns, even when all projections are decoded successfully. These patterns severely degrade the decoding performance due to their small weights. Thus, two rules on the subspace selection are derived to guarantee the error-correction capability of RPA. Simulation results verify that the two rules dominate the decoding performance of RPA.

IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•2 citations

Efficient RPA Decoding of Reed-Muller Codes with Structured 2-D Subspace Projections

Vallabhaneni Kushal, Shiv Pratap Singh Rathore, Navin Kashyap

The recursive projection-aggregation (RPA) decoder achieves near-maximum likelihood (ML) performance for lowrate Reed-Muller (RM) codes but suffers from high computational complexity when applied to high-rate codes. To address this limitation, we propose a structured subspace projection framework tailored to the code order: specifically, 2-dimensional subspaces for third-order RM codes. We demonstrate that decoding via projections onto these carefully chosen subspaces achieves better performance compared to an equal number of projections onto randomly selected subspaces. Further, we integrate automorphism ensemble decoding (AED) with our pruned projections, leveraging the rich symmetry group of RM codes to recover performance degradation from subspace pruning.

National Conference on Communications•Feb 26, 2026•0 citations

Recursive/Iterative Unique Projection-Aggregation Decoding of Reed-Muller Codes

Marzieh Hashemipour-Nazari, Renate Debets, Kees G. W. Goossens +1 more

We describe recursive unique projection-aggregation (RUPA) decoding and iterative unique projection-aggregation (IUPA) decoding of Reed-Muller (RM) codes, which remove non-unique projections from the recursive projection-aggregation (RPA) and iterative projection-aggregation (IPA) algorithms respectively. We show that these algorithms have competitive error-correcting performance while requiring up to 95% projections lower than the baseline RPA algorithm.

IEEE International Conference on Acoustics Speech and Signal Processing•May 5, 2023•2 citations

An Upper Bound on the Error Probability of Rpa Decoding of Reed-Muller Codes Over the Bsc

V. Arvind Rameshwar, V. Lalitha

In this paper, we revisit the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Key components of our analysis are explicit estimates of the error probability of maximum likelihood (ML) decoding of first-order RM codes and of the error probabilities during the aggregation phase of the RPA decoder. Importantly, we focus on the events where a single iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Our results allow us to show that for RM codes with blocklength$N=2^{m}$, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically in$m$.

IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•2 citations

An Analysis of RPA Decoding of Reed-Muller Codes Over the BSC

V. Arvind Rameshwar, V. Lalitha

In this paper, we revisit the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Importantly, we focus on the events where a \emph{single} iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Key components of our analysis are explicit estimates of the probability of incorrect decoding of first-order RM codes using a maximum likelihood (ML) decoder, and estimates of the error probabilities during the aggregation phase of the RPA decoder. Our results allow us to show that for RM codes with blocklength $N = 2^m$, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically in $m$.

arXiv:2412.08129•Dec 11, 2024•0 citations

Recursive/Iterative unique Projection-Aggregation of RM codes

Marzieh Hashemipour-Nazari, Renate Debets, Kees G. W. Goossens +1 more

We describe recursive unique projection-aggregation (RUPA) decoding and iterative unique projection-aggregation (IUPA) decoding of Reed-Muller (RM) codes, which remove non-unique projections from the recursive projection-aggregation (RPA) and iterative projection-aggregation (IPA) algorithms respectively. We show that these algorithms have competitive error-correcting performance while requiring up to 95% projections less than the baseline RPA algorithm.

arXiv:2210.16227•Oct 28, 2022•0 citations
The recursive projection-aggregation (RPA) algorithm provides state-of-the-art performance for Reed-Muller (RM) codes. It relies on projecting onto subspaces, decoding projections and voting. This paper explores the error-correction capability of RPA with a limited number of subspaces. By constructing a false vote matrix, it demonstrates that RPA may fail to correct coset error patterns, even when all projections are decoded successfully. These patterns severely degrade the decoding performance due to their small weights. Thus, two rules on the subspace selection are derived to guarantee the error-correction capability of RPA. Simulation results verify that the two rules dominate the decoding performance of RPA.
The recursive projection-aggregation (RPA) decoder achieves near-maximum likelihood (ML) performance for lowrate Reed-Muller (RM) codes but suffers from high computational complexity when applied to high-rate codes. To address this limitation, we propose a structured subspace projection framework tailored to the code order: specifically, 2-dimensional subspaces for third-order RM codes. We demonstrate that decoding via projections onto these carefully chosen subspaces achieves better performance compared to an equal number of projections onto randomly selected subspaces. Further, we integrate automorphism ensemble decoding (AED) with our pruned projections, leveraging the rich symmetry group of RM codes to recover performance degradation from subspace pruning.
In this paper, we revisit the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Key components of our analysis are explicit estimates of the error probability of maximum likelihood (ML) decoding of first-order RM codes and of the error probabilities during the aggregation phase of the RPA decoder. Importantly, we focus on the events where a single iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Our results allow us to show that for RM codes with blocklengthN=2mN=2^{m}N=2m, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically inmmm.
In this paper, we revisit the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Importantly, we focus on the events where a \emph{single} iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Key components of our analysis are explicit estimates of the probability of incorrect decoding of first-order RM codes using a maximum likelihood (ML) decoder, and estimates of the error probabilities during the aggregation phase of the RPA decoder. Our results allow us to show that for RM codes with blocklength N=2mN = 2^mN=2m, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically in mmm.