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

Semi-Deterministic Subspace Selection for Sparse Recursive Projection-Aggregation Decoding of Reed-Muller Codes

Voigt, Johannes, Holger Jäkel, Laurent Schmalen

Published Nov 2, 2022• 1 citation
arXivHTMLPDF

Abstract

Recursive projection aggregation (RPA) decoding as introduced in [1] is a novel decoding algorithm which performs close to the maximum likelihood decoder for short-length Reed-Muller codes. Recently, an extension to RPA decoding, called sparse multi-decoder RPA (SRPA), has been proposed [2]. The SRPA approach makes use of multiple pruned RPA decoders to lower the amount of computations while keeping the performance loss small compared to RPA decoding. However, the use of multiple sparse decoders again increases the computational burden. Therefore, the focus is on the optimization of sparse single-decoder RPA decoding to keep the complexity small. In this paper, a novel method is proposed, to select subsets of subspaces used in the projection and aggregation step of SRPA decoding in order to decrease the decoding error probability on AWGN channels. The proposed method replaces the random selection of subspace subsets with a semi-deterministic selection method based on a figure of merit that evaluates the performance of each subspace. Our simulation results show that the semi-deterministic subspace selection improves the decoding performance up to $0.2\,\text{dB}$ compared to SRPA. At the same time, the complexity of SRPA decoding for RM codes of order $r\geq 3$ is reduced by up to 81% compared to SRPA.

DOI
10.48550/arxiv.2211.01204

Related papers

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

Multi-Factor Pruning for Recursive Projection-Aggregation Decoding of RM Codes

Marzieh Hashemipour-Nazari, Kees G. W. Goossens, Alexios Balatsoukas‐Stimming

The recently introduced recursive projection aggregation (RPA) decoding method for Reed-Muller (RM) codes can achieve near-maximum likelihood (ML) decoding performance. However, its high computational complexity makes its implementation challenging for time- and resource-critical applications. In this work, we present a complexity reduction technique called multi-factor pruning that reduces the computational complexity of RPA significantly. Our simulation results show that the proposed pruning approach with appropriately selected factors can reduce the complexity of RPA by up to 92% for RM(8, 3) while keeping a comparable error-correcting performance.

arXiv:2208.13659•SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Nov 2, 2022•8 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

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

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

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
Recursive projection aggregation (RPA) decoding as introduced in [1] is a novel decoding algorithm which performs close to the maximum likelihood decoder for short-length Reed-Muller codes. Recently, an extension to RPA decoding, called sparse multi-decoder RPA (SRPA), has been proposed [2]. The SRPA approach makes use of multiple pruned RPA decoders to lower the amount of computations while keeping the performance loss small compared to RPA decoding. However, the use of multiple sparse decoders again increases the computational burden. Therefore, the focus is on the optimization of sparse single-decoder RPA decoding to keep the complexity small. In this paper, a novel method is proposed, to select subsets of subspaces used in the projection and aggregation step of SRPA decoding in order to decrease the decoding error probability on AWGN channels. The proposed method replaces the random selection of subspace subsets with a semi-deterministic selection method based on a figure of merit that evaluates the performance of each subspace. Our simulation results show that the semi-deterministic subspace selection improves the decoding performance up to 0.2 dB0.2\,\text{dB}0.2dB compared to SRPA. At the same time, the complexity of SRPA decoding for RM codes of order r≥3r\geq 3r≥3 is reduced by up to 81% compared to SRPA.
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 recently introduced recursive projection aggregation (RPA) decoding method for Reed-Muller (RM) codes can achieve near-maximum likelihood (ML) decoding performance. However, its high computational complexity makes its implementation challenging for time- and resource-critical applications. In this work, we present a complexity reduction technique called multi-factor pruning that reduces the computational complexity of RPA significantly. Our simulation results show that the proposed pruning approach with appropriately selected factors can reduce the complexity of RPA by up to 92% for RM(8, 3) while keeping a comparable error-correcting 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.
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.
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.
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.