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 Transactions on Communications

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

Jiajie Li, Huayi Zhou, Marwan Jalaleddine, Warren J. Gross

Published Sep 12, 2024• 7 citations
Publisher

Abstract

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.

DOI
10.1109/tcomm.2024.3459851

Related papers

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

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

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

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

Pipelined Architecture for Soft-decision Iterative Projection Aggregation Decoding for RM Codes

Marzieh Hashemipour-Nazari, Ren, Yuqing, Kees G. W. Goossens +1 more

The recently proposed recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller codes has received significant attention as it provides near-ML decoding performance at reasonable complexity for short codes. However, its complicated structure makes it unsuitable for hardware implementation. Iterative projection-aggregation (IPA) decoding is a modified version of RPA decoding that simplifies the hardware implementation. In this work, we present a flexible hardware architecture for the IPA decoder that can be configured from fully-sequential to fully-parallel, thus making it suitable for a wide range of applications with different constraints and resource budgets. Our simulation and implementation results show that the IPA decoder has 41% lower area consumption, 44% lower latency, four times higher throughput, but currently seven times higher power consumption for a code with block length of 128 and information length of 29 compared to a state-of-the-art polar successive cancellation list (SCL) decoder with comparable decoding performance.

arXiv:2210.11069•Oct 20, 2022•0 citations

Pipelined Architecture for Soft-Decision Iterative Projection Aggregation Decoding for RM Codes

Marzieh Hashemipour-Nazari, Yuqing Ren, Kees G. W. Goossens +1 more

The recently proposed recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller codes has received significant attention as it provides near-ML decoding performance at reasonable complexity for short codes. However, its complicated structure makes it unsuitable for hardware implementation. Iterative projection-aggregation (IPA) decoding is a modified version of RPA decoding that simplifies the hardware implementation. In this work, we present a flexible hardware architecture for the IPA decoder that can be configured from fully-sequential to fully-parallel, thus making it suitable for a wide range of applications with different constraints and resource budgets. Our simulation and implementation results show that the IPA decoder has 41% lower area consumption, 44% lower latency, four times higher throughput, but currently seven times higher power consumption for a code with block length of 128 and information length of 29 compared to a state-of-the-art polar successive cancellation list (SCL) decoder with comparable decoding performance.

IEEE Transactions on Circuits and Systems I Regular Papers•Aug 31, 2023•10 citations
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 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.
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.
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 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 recently proposed recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller codes has received significant attention as it provides near-ML decoding performance at reasonable complexity for short codes. However, its complicated structure makes it unsuitable for hardware implementation. Iterative projection-aggregation (IPA) decoding is a modified version of RPA decoding that simplifies the hardware implementation. In this work, we present a flexible hardware architecture for the IPA decoder that can be configured from fully-sequential to fully-parallel, thus making it suitable for a wide range of applications with different constraints and resource budgets. Our simulation and implementation results show that the IPA decoder has 41% lower area consumption, 44% lower latency, four times higher throughput, but currently seven times higher power consumption for a code with block length of 128 and information length of 29 compared to a state-of-the-art polar successive cancellation list (SCL) decoder with comparable decoding performance.
The recently proposed recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller codes has received significant attention as it provides near-ML decoding performance at reasonable complexity for short codes. However, its complicated structure makes it unsuitable for hardware implementation. Iterative projection-aggregation (IPA) decoding is a modified version of RPA decoding that simplifies the hardware implementation. In this work, we present a flexible hardware architecture for the IPA decoder that can be configured from fully-sequential to fully-parallel, thus making it suitable for a wide range of applications with different constraints and resource budgets. Our simulation and implementation results show that the IPA decoder has 41% lower area consumption, 44% lower latency, four times higher throughput, but currently seven times higher power consumption for a code with block length of 128 and information length of 29 compared to a state-of-the-art polar successive cancellation list (SCL) decoder with comparable decoding performance.