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

IEEE International Symposium on Information Theory (ISIT)

Coset Error Patterns in Recursive Projection-Aggregation Decoding

Fanyun Chen, Bin Zhang, Qin Huang

Published Jul 7, 2024• 2 citations
Publisher

Abstract

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.

DOI
10.1109/isit57864.2024.10619095

Related papers

Coset Error Pattern in Projection-Aggregation Decoding

Bin Zhang, Fanyun Chen, Qin Huang

Projection-aggregation decoding provides state-of-the-art performance for decoding Reed-Muller codes. This type of decoding relies on projecting onto subspaces, decoding the projections, and voting with the decoded projections. This paper investigates the decoding with a limited number of subspaces. By defining a false vote matrix, it demonstrates that this decoding suffers from coset error patterns, even when all projections are decoded successfully. These error patterns are of very small weights and thus induce a significant performance loss. Two rules are then proposed of which one reveals a trade-off between the subspace number and the error-correcting capability and the other provides a guideline for subspace selection. Simulation results verify that following the two rules alleviates the performance loss caused by the coset error patterns.

IEEE Transactions on Information Theory•Jun 5, 2025•3 citations

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

Shiv Pratap Singh Rathore, Navin Kashyap

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

arXiv:2610.16240•Oct 12, 2026•0 citations

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

Voigt, Johannes, Holger Jäkel, Laurent Schmalen

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.

arXiv:2211.01204•Nov 2, 2022•1 citation

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

Minimum Distance Decoding for Reed-Muller Codes using Projection-Aggregation

Bin Zhang, Qin Huang

This paper shows that projection-aggregation (PA) decoding of Reed-Muller (RM) codes can decode up to half the minimum distance d efficiently. By generalizing the false vote matrix from 1-dimensional to higher-dimensional subspaces, we prove that projecting onto disjoint subspaces, regardless of their dimensions, provides at most d/2 − 1 false votes for each codeword bit. Thus, d disjoint subspaces guarantee the correction for errors of d/2 − 1 or less. Moreover, the flexibility in subspace dimensions allows projecting into repetition codes directly, resulting in decoding efficiency. Finally, we prove that PA decoding with d disjoint subspaces decodes up to half the minimum distance in $O(n\sqrt n )$ for RM codes of length n and half rate or less.

IEEE Information Theory Workshop (ITW)•Sep 29, 2025•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.
Projection-aggregation decoding provides state-of-the-art performance for decoding Reed-Muller codes. This type of decoding relies on projecting onto subspaces, decoding the projections, and voting with the decoded projections. This paper investigates the decoding with a limited number of subspaces. By defining a false vote matrix, it demonstrates that this decoding suffers from coset error patterns, even when all projections are decoded successfully. These error patterns are of very small weights and thus induce a significant performance loss. Two rules are then proposed of which one reveals a trade-off between the subspace number and the error-correcting capability and the other provides a guideline for subspace selection. Simulation results verify that following the two rules alleviates the performance loss caused by the coset error patterns.
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.
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.
This paper shows that projection-aggregation (PA) decoding of Reed-Muller (RM) codes can decode up to half the minimum distance d efficiently. By generalizing the false vote matrix from 1-dimensional to higher-dimensional subspaces, we prove that projecting onto disjoint subspaces, regardless of their dimensions, provides at most d/2 − 1 false votes for each codeword bit. Thus, d disjoint subspaces guarantee the correction for errors of d/2 − 1 or less. Moreover, the flexibility in subspace dimensions allows projecting into repetition codes directly, resulting in decoding efficiency. Finally, we prove that PA decoding with d disjoint subspaces decodes up to half the minimum distance in O(nn)O(n\sqrt n )O(nn​) for RM codes of length n and half rate or less.