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

Asilomar Conference on Signals, Systems and Computers (ACSSC)

A Layered CPA Decoder for Reed-Muller Codes

Jiajie Li, Warren J. Gross

Published Oct 27, 2024• 2 citations
Publisher

Abstract

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.

DOI
10.1109/ieeeconf60004.2024.10942623

Related papers

Reduced-Complexity Projection-Aggregation List Decoder for Reed-Muller Codes

Jiajie Li, Huayi Zhou, Marwan Jalaleddine +1 more

Projection-aggregation decoders have been used in conjunction with a list structure to achieve near maximum-likelihood decoding for short-length and low-rate Reed-Muller (RM) codes but suffer from high computational complexity. We reduce the worst-case computational complexity of projection-aggregation (PA) decoders by more than 50% using a scheduling scheme compared to PA decoders without the scheduling scheme, and propose a redesigned syndrome check pattern to avoid repeated syndrome computations in the decoder. A latency model based on the existing hardware architecture is proposed. Input distribution aware (IDA) decoding is adopted as a pre-possessing tool, and the average list size when using IDA decoding is analytically derived under additive white Gaussian noise and uncorrelated normalized Rayleigh fading channels. Using IDA, the average list size is reduced by 30% with less than 0.1 dB loss. The proposed list decoders require a smaller computational complexity than the state-of-the-art iterative decoder, automorphism ensemble decoding with the belief propagation constituent decoder (AED-BP) for decoding RM(7, 3) and RM(8, 3) codes. Based on the developed latency models, the PA list decoder has a smaller latency than the AED-BP and the successive cancellation list decoder to reach near maximum-likelihood decoding performance.

IEEE Transactions on Communications•Sep 12, 2024•7 citations

Optimization and Simplification of PCPA Decoder for Reed-Muller Codes

Jiajie Li, Warren J. Gross

The collapsed projection-aggregation (CPA) decoder reduces the computational complexity of the recursive projection-aggregation (RPA) decoder by removing the recursive structure. From simulations, the CPA decoder has similar error-correction performance as the RPA decoder, when decoding Reed-Muller (RM) (7, 3) and (8, 2) codes. The computational complexity can be further reduced by only selecting a subset of sub-spaces, which is achieved by pruning CPA decoders. In this work, optimization methods are proposed to find the pruned CPA (PCPA) decoder with small performance loss. Furthermore, the min-sum approximation is used to replace non-linear projection and aggregation functions, and a simplified list decoder based on the syndrome check is proposed. Under the same complexity, the optimized PCPA decoder has less performance loss than randomly constructed PCPA decoders in most case. The min-sum approximation incurs less than 0.15 dB performance loss at a target frame error rate of 10−4, and the simplified list decoder does not have noticeable performance loss.

IEEE Communications Letters•Mar 30, 2022•10 citations

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

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.

arXiv:2607.09602•Jul 10, 2026•0 citations

Decoding Reed–Muller Codes Using Redundant Code Constraints

Mengke Lian, Christian Häger, Henry D. Pfister

The recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller (RM) codes was recently introduced by Ye and Abbe. We show that the RPA algorithm is closely related to (weighted) belief-propagation (BP) decoding by interpreting it as a message-passing algorithm on a factor graph with redundant code constraints. We use this observation to introduce a novel decoder tailored to high-rate RM codes. The new algorithm relies on puncturing rather than projections and is called recursive puncturing-aggregation (RXA). We also investigate collapsed (i.e., non-recursive) versions of RPA and RXA and show some examples where they achieve similar performance with lower decoding complexity.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•45 citations

Sparse Multi-Decoder Recursive Projection Aggregation for Reed-Muller Codes

Dorsa Fathollahi, Nariman Farsad, Seyyed Ali Hashemi +1 more

Reed-Muller (RM) codes are one of the oldest families of codes. Recently, a recursive projection aggregation (RPA) decoder has been proposed, which achieves a performance that is close to the maximum likelihood decoder for short-length RM codes. One of its main drawbacks, however, is the large amount of computations needed. In this paper, we devise a new algorithm to lower the computational budget while keeping a performance close to that of the RPA decoder. The proposed approach consists of multiple sparse RPAs that are generated by performing only a selection of projections in each sparsified decoder. In the end, a cyclic redundancy check (CRC) is used to decide between output codewords. Simulation results show that our proposed approach reduces the RPA decoder's computations by up to 80% with negligible performance loss.

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

Reduced Complexity RPA Decoder for Reed-Muller Codes

Jiajie Li, Syed Mohsin Abbas, Thibaud Tonnellier +1 more

The recursive projection-aggregation (RPA) decoder is a recently proposed near maximum likelihood (ML) decoder for Reed-Muller (RM) codes with low rates and short code lengths. However, the high computational complexity of RPA decoding is a major bottleneck for using RPA in applications that have a limited resource and energy budget. In this work, syndrome-based early stopping techniques as well as a scheduling scheme are proposed for the RPA decoder, which help in reducing the computational complexity while keeping similar decoding performance. Comparing to the baseline RPA decoder, the proposed techniques result in a 69−98% reduction in the average computational complexity for a target frame error rate (FER) of 10−5. Additionally, this work introduces hardware-friendly approximation functions to replace the RPA’s computationally expensive transcendental projection function.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 30, 2021•16 citations
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.
Projection-aggregation decoders have been used in conjunction with a list structure to achieve near maximum-likelihood decoding for short-length and low-rate Reed-Muller (RM) codes but suffer from high computational complexity. We reduce the worst-case computational complexity of projection-aggregation (PA) decoders by more than 50% using a scheduling scheme compared to PA decoders without the scheduling scheme, and propose a redesigned syndrome check pattern to avoid repeated syndrome computations in the decoder. A latency model based on the existing hardware architecture is proposed. Input distribution aware (IDA) decoding is adopted as a pre-possessing tool, and the average list size when using IDA decoding is analytically derived under additive white Gaussian noise and uncorrelated normalized Rayleigh fading channels. Using IDA, the average list size is reduced by 30% with less than 0.1 dB loss. The proposed list decoders require a smaller computational complexity than the state-of-the-art iterative decoder, automorphism ensemble decoding with the belief propagation constituent decoder (AED-BP) for decoding RM(7, 3) and RM(8, 3) codes. Based on the developed latency models, the PA list decoder has a smaller latency than the AED-BP and the successive cancellation list decoder to reach near maximum-likelihood decoding performance.
The collapsed projection-aggregation (CPA) decoder reduces the computational complexity of the recursive projection-aggregation (RPA) decoder by removing the recursive structure. From simulations, the CPA decoder has similar error-correction performance as the RPA decoder, when decoding Reed-Muller (RM) (7, 3) and (8, 2) codes. The computational complexity can be further reduced by only selecting a subset of sub-spaces, which is achieved by pruning CPA decoders. In this work, optimization methods are proposed to find the pruned CPA (PCPA) decoder with small performance loss. Furthermore, the min-sum approximation is used to replace non-linear projection and aggregation functions, and a simplified list decoder based on the syndrome check is proposed. Under the same complexity, the optimized PCPA decoder has less performance loss than randomly constructed PCPA decoders in most case. The min-sum approximation incurs less than 0.15 dB performance loss at a target frame error rate of 10−4, and the simplified list decoder does not have noticeable performance loss.
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.
The recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller (RM) codes was recently introduced by Ye and Abbe. We show that the RPA algorithm is closely related to (weighted) belief-propagation (BP) decoding by interpreting it as a message-passing algorithm on a factor graph with redundant code constraints. We use this observation to introduce a novel decoder tailored to high-rate RM codes. The new algorithm relies on puncturing rather than projections and is called recursive puncturing-aggregation (RXA). We also investigate collapsed (i.e., non-recursive) versions of RPA and RXA and show some examples where they achieve similar performance with lower decoding complexity.
Reed-Muller (RM) codes are one of the oldest families of codes. Recently, a recursive projection aggregation (RPA) decoder has been proposed, which achieves a performance that is close to the maximum likelihood decoder for short-length RM codes. One of its main drawbacks, however, is the large amount of computations needed. In this paper, we devise a new algorithm to lower the computational budget while keeping a performance close to that of the RPA decoder. The proposed approach consists of multiple sparse RPAs that are generated by performing only a selection of projections in each sparsified decoder. In the end, a cyclic redundancy check (CRC) is used to decide between output codewords. Simulation results show that our proposed approach reduces the RPA decoder's computations by up to 80% with negligible performance loss.
The recursive projection-aggregation (RPA) decoder is a recently proposed near maximum likelihood (ML) decoder for Reed-Muller (RM) codes with low rates and short code lengths. However, the high computational complexity of RPA decoding is a major bottleneck for using RPA in applications that have a limited resource and energy budget. In this work, syndrome-based early stopping techniques as well as a scheduling scheme are proposed for the RPA decoder, which help in reducing the computational complexity while keeping similar decoding performance. Comparing to the baseline RPA decoder, the proposed techniques result in a 69−98% reduction in the average computational complexity for a target frame error rate (FER) of 10−5. Additionally, this work introduces hardware-friendly approximation functions to replace the RPA’s computationally expensive transcendental projection function.