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:2607.09602

Density Evolution of Soft-Decision Collapsed Projection-Aggregation Decoding for Reed-Muller Codes over the BIAWGN Channel

Jiajie Li, Marvin Rübenacke, Warren J. Gross

Published Jul 10, 2026• 0 citations
arXivHTMLPDF

Abstract

Reed-Muller (RM) codes have been shown to achieve capacity over a range of channels, and recently proposed projection-aggregation (PA) decoding has been experimentally shown to achieve near-maximum-likelihood decoding performance. These recent achievements motivate theoretical research on PA decoding. In this work, we analyze the density function of the soft output from collapsed projection-aggregation (CPA) decoding for RM codes over the binary-input additive white Gaussian noise (BIAWGN) channel. We prove that soft-decision CPA decoding returns an exact marginal probability and is symmetric. Based on the analysis, we build a density evolution model for CPA decoding. To simplify the density evolution, we approximate the projection and the fast Hadamard transform decoding using hard-decision decoding. Simulation results over the BIAWGN channel show that our proposed density evolution model captures the fast reduction in the mean and the variance of the soft information returned from the CPA decoding, which qualitatively explains the decoding mechanism and the fast convergence speed of the CPA decoding. We perform an asymptotic analysis based on the proposed density evolution, and we show that CPA decoding can achieve a vanishing error probability for RM codes with a vanishing code rate.

DOI
10.48550/arxiv.2607.09602

Related papers

Reed-Muller Subcodes: Machine Learning-Aided Design of Efficient Soft Recursive Decoding

Mohammad Vahid Jamali, Xiyang Liu, Ashok Vardhan Makkuva +3 more

Reed-Muller (RM) codes are conjectured to achieve the capacity of any binary-input memoryless symmetric (BMS) channel, and are observed to have a comparable performance to that of random codes in terms of scaling laws. On the negative side, RM codes lack efficient decoders with performance close to that of a maximum likelihood decoder for general parameters. Also, they only admit certain discrete sets of rates. In this paper, we focus on subcodes of RM codes with flexible rates that can take any code dimension from 1 to$n$. where$n$is the blocklength. We first extend the recursive projection-aggregation (RPA) algorithm proposed recently by Ye and Abbe for decoding RM codes. To lower the complexity of our decoding algorithm, referred to as subRPA, we investigate different ways for pruning the projections. We then derive the soft-decision based version of our algorithm, called soft-subRPA, that is shown to improve upon the performance of subRPA. Furthermore, it enables training a machine learning (ML) model to search for good sets of projections that minimize the decoding error rate. Training our ML model enables achieving very close to the performance of full-projection decoding with a significantly reduced number of projections. For instance, our simulation results on a (64,14) RM subcode show almost identical performance for full-projection decoding and pruned-projection decoding with 15 projections picked via training our ML model. This is equivalent to lowering the complexity by a factor of more than 4 without sacrificing the decoding performance.

arXiv:2102.01671•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•16 citations

A Layered CPA Decoder for Reed-Muller Codes

Jiajie Li, Warren J. Gross

When decoding low-rate and short-length Reed-Muller (RM) codes, the recently proposed projection-aggregation (PA) decoder yields near maximum-likelihood decoding performance. However, the practicability of the PA decoder's implementation is nevertheless negatively impacted by its high computational cost. It has been demonstrated that this decoder is closely connected to the belief propagation (BP) decoder based on the parity-check matrix. Techniques inspired by the layered decoding and the broadcast modification for the BP decoder used by the low-density parity-check codes are proposed in this work. The proposed broadcast modification reduces the computational overhead induced by the proposed layered decoding for the collapsed PA (CPA) decoder. The proposed layered and broadcast-based CPA decoder has negligible degradation in decoding performance, and it produces a 47% reduction in the average complexity at$E_{b}/N_{0}=2.5\text{dP}$, when decoding RM(8, 3) codes.

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Oct 27, 2024•2 citations

Machine Learning-Aided Efficient Decoding of Reed–Muller Subcodes

Mohammad Vahid Jamali, Xiyang Liu, Ashok Vardhan Makkuva +3 more

Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels and are conjectured to have a comparable performance to that of random codes in terms of scaling laws. However, such results are established assuming maximum-likelihood decoders for general code parameters. Also, RM codes only admit limited sets of rates. Efficient decoders such as successive cancellation list (SCL) decoder and recently-introduced recursive projection-aggregation (RPA) decoders are available for RM codes at finite lengths. In this paper, we focus on subcodes of RM codes with flexible rates. We first extend the RPA decoding algorithm to RM subcodes. To lower the complexity of our decoding algorithm, referred to as subRPA, we investigate different approaches to prune the projections. Next, we derive the soft-decision based version of our algorithm, called soft-subRPA, that not only improves upon the performance of subRPA but also enables a differentiable decoding algorithm. Building upon the soft-subRPA algorithm, we then provide a framework for training a machine learning (ML) model to search forgoodsets of projections that minimize the decoding error rate. Training our ML model enables achieving very close to the performance of full-projection decoding with a significantly smaller number of projections. We also show that the choice of the projections in decoding RM subcodes matters significantly, and our ML-aided projection pruning scheme is able to find agoodselection, i.e., with negligible performance degradation compared to the full-projection case, given a reasonable number of projections.

arXiv:2301.06251•IEEE Journal on Selected Areas in Information Theory•Jan 1, 2023•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

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

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

Dorsa Fathollahi, V. Arvind Rameshwar, V. Lalitha

We analyze the performance of the Recursive Projection-Aggregation (RPA) decoder of Ye and Abbe (2020), for Reed-Muller (RM) codes, over general binary memoryless symmetric (BMS) channels. Our work is a significant generalization of a recent result of Rameshwar and Lalitha (2025) that showed that the RPA decoder provably achieves vanishing error probabilities for "low-rate" RM codes, over the binary symmetric channel (BSC). While a straightforward generalization of the proof strategy in that paper will require additional, restrictive assumptions on the BMS channel, our technique, which employs an equivalence between the RPA projection operation and a part of the "channel combining" phase in polar codes, requires no such assumptions. Interestingly, such an equivalence allows for the use of a generic union bound on the error probability of the first-order RM code (the "base case" of the RPA decoder), under maximum-likelihood decoding, which holds for any BMS channel. We then exploit these observations in the proof strategy outlined in the work of Rameshwar and Lalitha (2025), and argue that, much like in the case of the BSC, one can obtain vanishing error probabilities, in the large $n$ limit (where $n$ is the blocklength), for RM orders that scale roughly as $\log \log n$, for all BMS channels.

arXiv:2601.09581•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•1 citation
Reed-Muller (RM) codes have been shown to achieve capacity over a range of channels, and recently proposed projection-aggregation (PA) decoding has been experimentally shown to achieve near-maximum-likelihood decoding performance. These recent achievements motivate theoretical research on PA decoding. In this work, we analyze the density function of the soft output from collapsed projection-aggregation (CPA) decoding for RM codes over the binary-input additive white Gaussian noise (BIAWGN) channel. We prove that soft-decision CPA decoding returns an exact marginal probability and is symmetric. Based on the analysis, we build a density evolution model for CPA decoding. To simplify the density evolution, we approximate the projection and the fast Hadamard transform decoding using hard-decision decoding. Simulation results over the BIAWGN channel show that our proposed density evolution model captures the fast reduction in the mean and the variance of the soft information returned from the CPA decoding, which qualitatively explains the decoding mechanism and the fast convergence speed of the CPA decoding. We perform an asymptotic analysis based on the proposed density evolution, and we show that CPA decoding can achieve a vanishing error probability for RM codes with a vanishing code rate.
Reed-Muller (RM) codes are conjectured to achieve the capacity of any binary-input memoryless symmetric (BMS) channel, and are observed to have a comparable performance to that of random codes in terms of scaling laws. On the negative side, RM codes lack efficient decoders with performance close to that of a maximum likelihood decoder for general parameters. Also, they only admit certain discrete sets of rates. In this paper, we focus on subcodes of RM codes with flexible rates that can take any code dimension from 1 tonnn. wherennnis the blocklength. We first extend the recursive projection-aggregation (RPA) algorithm proposed recently by Ye and Abbe for decoding RM codes. To lower the complexity of our decoding algorithm, referred to as subRPA, we investigate different ways for pruning the projections. We then derive the soft-decision based version of our algorithm, called soft-subRPA, that is shown to improve upon the performance of subRPA. Furthermore, it enables training a machine learning (ML) model to search for good sets of projections that minimize the decoding error rate. Training our ML model enables achieving very close to the performance of full-projection decoding with a significantly reduced number of projections. For instance, our simulation results on a (64,14) RM subcode show almost identical performance for full-projection decoding and pruned-projection decoding with 15 projections picked via training our ML model. This is equivalent to lowering the complexity by a factor of more than 4 without sacrificing the decoding performance.
When decoding low-rate and short-length Reed-Muller (RM) codes, the recently proposed projection-aggregation (PA) decoder yields near maximum-likelihood decoding performance. However, the practicability of the PA decoder's implementation is nevertheless negatively impacted by its high computational cost. It has been demonstrated that this decoder is closely connected to the belief propagation (BP) decoder based on the parity-check matrix. Techniques inspired by the layered decoding and the broadcast modification for the BP decoder used by the low-density parity-check codes are proposed in this work. The proposed broadcast modification reduces the computational overhead induced by the proposed layered decoding for the collapsed PA (CPA) decoder. The proposed layered and broadcast-based CPA decoder has negligible degradation in decoding performance, and it produces a 47% reduction in the average complexity atEb/N0=2.5dPE_{b}/N_{0}=2.5\text{dP}Eb​/N0​=2.5dP, when decoding RM(8, 3) codes.
Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels and are conjectured to have a comparable performance to that of random codes in terms of scaling laws. However, such results are established assuming maximum-likelihood decoders for general code parameters. Also, RM codes only admit limited sets of rates. Efficient decoders such as successive cancellation list (SCL) decoder and recently-introduced recursive projection-aggregation (RPA) decoders are available for RM codes at finite lengths. In this paper, we focus on subcodes of RM codes with flexible rates. We first extend the RPA decoding algorithm to RM subcodes. To lower the complexity of our decoding algorithm, referred to as subRPA, we investigate different approaches to prune the projections. Next, we derive the soft-decision based version of our algorithm, called soft-subRPA, that not only improves upon the performance of subRPA but also enables a differentiable decoding algorithm. Building upon the soft-subRPA algorithm, we then provide a framework for training a machine learning (ML) model to search forgoodsets of projections that minimize the decoding error rate. Training our ML model enables achieving very close to the performance of full-projection decoding with a significantly smaller number of projections. We also show that the choice of the projections in decoding RM subcodes matters significantly, and our ML-aided projection pruning scheme is able to find agoodselection, i.e., with negligible performance degradation compared to the full-projection case, given a reasonable number of projections.
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.
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.
We analyze the performance of the Recursive Projection-Aggregation (RPA) decoder of Ye and Abbe (2020), for Reed-Muller (RM) codes, over general binary memoryless symmetric (BMS) channels. Our work is a significant generalization of a recent result of Rameshwar and Lalitha (2025) that showed that the RPA decoder provably achieves vanishing error probabilities for "low-rate" RM codes, over the binary symmetric channel (BSC). While a straightforward generalization of the proof strategy in that paper will require additional, restrictive assumptions on the BMS channel, our technique, which employs an equivalence between the RPA projection operation and a part of the "channel combining" phase in polar codes, requires no such assumptions. Interestingly, such an equivalence allows for the use of a generic union bound on the error probability of the first-order RM code (the "base case" of the RPA decoder), under maximum-likelihood decoding, which holds for any BMS channel. We then exploit these observations in the proof strategy outlined in the work of Rameshwar and Lalitha (2025), and argue that, much like in the case of the BSC, one can obtain vanishing error probabilities, in the large nnn limit (where nnn is the blocklength), for RM orders that scale roughly as log⁡log⁡n\log \log nloglogn, for all BMS channels.