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

International Symposium on Turbo Codes and Iterative Information Processing

Reduced Complexity RPA Decoder for Reed-Muller Codes

Jiajie Li, Syed Mohsin Abbas, Thibaud Tonnellier, Warren J. Gross

Published Aug 30, 2021• 16 citations
Publisher

Abstract

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.

DOI
10.1109/istc49272.2021.9594060

Related papers

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

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

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
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 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.
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.
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 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.