Reed–Muller (RM) codes are known for their good maximum likelihood (ML) performance in the short block-length regime. Despite being one of the oldest classes of channel codes, finding a low complexity soft-input decoding scheme is still an open problem. In this work, we present a belief propagation (BP) decoding architecture for RM codes based on their rich automorphism group. The decoding algorithm can be seen as a generalization of multiple-bases belief propagation (MBBP) using polar BP as constituent decoders. We provide extensive errorrate performance simulations and compare our results to existing decoding schemes. We report a near-ML performance for the RM(3,7)-code (e.g., 0.05 dB away from the ML bound at BLER of 10−4) at a competitive computational cost. To the best of our knowledge, our proposed decoder achieves the best performance of all iterative RM decoders presented thus far.Reed–Muller (RM) codes are known for their good maximum likelihood (ML) performance in the short block-length regime. Despite being one of the oldest classes of channel codes, finding a low complexity soft-input decoding scheme is still an open problem. In this work, we present a belief propagation (BP) decoding architecture for RM codes based on their rich automorphism group. The decoding algorithm can be seen as a generalization of multiple-bases belief propagation (MBBP) using polar BP as constituent decoders. We provide extensive errorrate performance simulations and compare our results to existing decoding schemes. We report a near-ML performance for the RM(3,7)-code (e.g., 0.05 dB away from the ML bound at BLER of 10−4) at a competitive computational cost. To the best of our knowledge, our proposed decoder achieves the best performance of all iterative RM decoders presented thus far.

arXiv:2107.12613International Symposium on Turbo Codes and Iterative Information ProcessingAug 30, 20211 citation

Low-Complexity Automorphism Ensemble Decoding of Reed-Muller Codes Using Path Pruning

Kairui Tian, Rongke Liu, Zheng Lu

The newly developed automorphism ensemble decoder (AED) leverages the rich automorphisms of Reed-Muller (RM) codes to achieve near maximum likelihood (ML) performance at short code lengths. However, the performance gain of AED comes at the cost of high complexity, as the ensemble size required for near ML decoding grows exponentially with the code length. In this work, we address this complexity issue by focusing on the factor graph permutation group (FGPG), a subgroup of the full automorphism group of RM codes, to generate permutations for AED. We propose a uniform partitioning of FGPG based on the affine bijection permutation matrices of automorphisms, where each subgroup of FGPG exhibits permutation invariance (PI) in a Plotkin construction-based information set partitioning for RM codes. Furthermore, from the perspective of polar codes, we exploit the PI property to prove a subcode estimate convergence (SEC) phenomenon in the AED that utilizes successive cancellation (SC) or SC list (SCL) constituent decoders. Observing that strong SEC correlates with low noise levels, where the full decoding capacity of AED is often unnecessary, we perform path pruning to reduce the decoding complexity without compromising the performance. Our proposed SEC-aided path pruning allows only a subset of constituent decoders to continue decoding when the intensity of SEC exceeds a preset threshold during decoding. Numerical results demonstrate that, for the FGPG-based AED of various short RM codes, the proposed SEC-aided path pruning technique incurs negligible performance degradation, while achieving a complexity reduction of up to 67.6%.The newly developed automorphism ensemble decoder (AED) leverages the rich automorphisms of Reed-Muller (RM) codes to achieve near maximum likelihood (ML) performance at short code lengths. However, the performance gain of AED comes at the cost of high complexity, as the ensemble size required for near ML decoding grows exponentially with the code length. In this work, we address this complexity issue by focusing on the factor graph permutation group (FGPG), a subgroup of the full automorphism group of RM codes, to generate permutations for AED. We propose a uniform partitioning of FGPG based on the affine bijection permutation matrices of automorphisms, where each subgroup of FGPG exhibits permutation invariance (PI) in a Plotkin construction-based information set partitioning for RM codes. Furthermore, from the perspective of polar codes, we exploit the PI property to prove a subcode estimate convergence (SEC) phenomenon in the AED that utilizes successive cancellation (SC) or SC list (SCL) constituent decoders. Observing that strong SEC correlates with low noise levels, where the full decoding capacity of AED is often unnecessary, we perform path pruning to reduce the decoding complexity without compromising the performance. Our proposed SEC-aided path pruning allows only a subset of constituent decoders to continue decoding when the intensity of SEC exceeds a preset threshold during decoding. Numerical results demonstrate that, for the FGPG-based AED of various short RM codes, the proposed SEC-aided path pruning technique incurs negligible performance degradation, while achieving a complexity reduction of up to 67.6%.

EntropyJul 28, 20250 citations

Decoding of Reed-Muller Codes Starting With a Higher-Rate Constituent Code.

Mikhail Kamenev

List versions of recursive decoding are known to approach maximum-likelihood (ML) performance for the short length Reed-Muller (RM) codes. The recursive decoder employs the Plotkin construction to split the original code into two shorter RM codes, with a lower-rate RM code being decoded first. In this paper, we consider non-iterative soft-input decoders for RM codes that, unlike recursive decoding, start decoding with a higher-rate constituent code. Although the error-rate performance of these algorithms is limited, it can be significantly improved by applying permutations from the automorphism group of the code, with permutations being selected on the fly based on soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms enhanced by a permutation selection technique is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short length $(\leq 256)$ RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for RM codes of length $2^m$ and order $m - 3$ with reasonable complexity.List versions of recursive decoding are known to approach maximum-likelihood (ML) performance for the short length Reed-Muller (RM) codes. The recursive decoder employs the Plotkin construction to split the original code into two shorter RM codes, with a lower-rate RM code being decoded first. In this paper, we consider non-iterative soft-input decoders for RM codes that, unlike recursive decoding, start decoding with a higher-rate constituent code. Although the error-rate performance of these algorithms is limited, it can be significantly improved by applying permutations from the automorphism group of the code, with permutations being selected on the fly based on soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms enhanced by a permutation selection technique is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short length $(\leq 256)$ RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for RM codes of length $2^m$ and order $m - 3$ with reasonable complexity.

Nov 28, 20210 citations

Recursive Decoding of Reed-Muller Codes Starting With the Higher-Rate Constituent Code

Mikhail Kamenev

Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length $(\leq 256)$ RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length $2^{m}$ and order $m-3$ with reasonable complexity.Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length$(\leq 256)$RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length$2^{m}$and order$m-3$with reasonable complexity.

arXiv:2101.11328IEEE Transactions on Information TheoryJul 29, 20225 citations

Machine Learning-Aided Efficient Decoding of Reed–Muller Subcodes

Mohammad Vahid Jamali, Xiyang Liu, Ashok Vardhan Makkuva +3 more

Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels and are conjectured to have a comparable performance to that of random codes in terms of scaling laws. However, such results are established assuming maximum-likelihood decoders for general code parameters. Also, RM codes only admit limited sets of rates. Efficient decoders such as successive cancellation list (SCL) decoder and recently-introduced recursive projection-aggregation (RPA) decoders are available for RM codes at finite lengths. In this paper, we focus on subcodes of RM codes with flexible rates. We first extend the RPA decoding algorithm to RM subcodes. To lower the complexity of our decoding algorithm, referred to as subRPA, we investigate different approaches to prune the projections. Next, we derive the soft-decision based version of our algorithm, called soft-subRPA, that not only improves upon the performance of subRPA but also enables a differentiable decoding algorithm. Building upon the soft-subRPA algorithm, we then provide a framework for training a machine learning (ML) model to search forgoodsets of projections that minimize the decoding error rate. Training our ML model enables achieving very close to the performance of full-projection decoding with a significantly smaller number of projections. We also show that the choice of the projections in decoding RM subcodes matters significantly, and our ML-aided projection pruning scheme is able to find agoodselection, i.e., with negligible performance degradation compared to the full-projection case, given a reasonable number of projections.Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels and are conjectured to have a comparable performance to that of random codes in terms of scaling laws. However, such results are established assuming maximum-likelihood decoders for general code parameters. Also, RM codes only admit limited sets of rates. Efficient decoders such as successive cancellation list (SCL) decoder and recently-introduced recursive projection-aggregation (RPA) decoders are available for RM codes at finite lengths. In this paper, we focus on subcodes of RM codes with flexible rates. We first extend the RPA decoding algorithm to RM subcodes. To lower the complexity of our decoding algorithm, referred to as subRPA, we investigate different approaches to prune the projections. Next, we derive the soft-decision based version of our algorithm, called soft-subRPA, that not only improves upon the performance of subRPA but also enables a differentiable decoding algorithm. Building upon the soft-subRPA algorithm, we then provide a framework for training a machine learning (ML) model to search forgoodsets of projections that minimize the decoding error rate. Training our ML model enables achieving very close to the performance of full-projection decoding with a significantly smaller number of projections. We also show that the choice of the projections in decoding RM subcodes matters significantly, and our ML-aided projection pruning scheme is able to find agoodselection, i.e., with negligible performance degradation compared to the full-projection case, given a reasonable number of projections.

arXiv:2301.06251IEEE Journal on Selected Areas in Information TheoryJan 1, 20232 citations

Automorphism Ensemble Decoding on GPU: Achieving High Throughput and Low Latency for Polar and RM Codes

Yansong Li, Kairui Tian, Rongke Liu

Automorphism ensemble decoding (AED) is a highly parallel approach that enables decoding of polar and Reed-Muller (RM) codes with automorphisms, offering a practical solution with near-maximum likelihood (ML) performance and manageable computational complexity. To meet the growing demands for high throughput and low latency in cloud and virtual random access networks, this paper presents a graphics processing unit (GPU)-based AED architecture for polar and RM codes, utilizing low-complexity successive cancellation (SC) and small list SC (SCL) decoders as the constituent of AED. The proposed architecture exploits the inherent parallelism of AED to optimize decoding tasks on the GPU, significantly enhancing throughput by efficiently harnessing the extensive parallel processing capabilities of the GPU. Additionally, improved thread mapping and data management techniques markedly reduce latency for automorphism ensemble SC (Aut-SC) decoding, while a low-latency sorting mechanism further accelerates automorphism ensemble SCL (Aut-SCL) decoding. Experimental results on an NVIDIA RTX 4090 demonstrate that the proposed Aut-SC decoder, with an ensemble size of 8, achieves a throughput exceeding 17 Gbps. Compared to the state-of-the-art softwarebased SCL decoders, the proposed GPU-based Aut-SC and Aut-SCL architectures outperform existing solutions by factors of up to 28× and 10×, respectively, in normalized throughput while maintaining the same or even superior error correction performance.Automorphism ensemble decoding (AED) is a highly parallel approach that enables decoding of polar and Reed-Muller (RM) codes with automorphisms, offering a practical solution with near-maximum likelihood (ML) performance and manageable computational complexity. To meet the growing demands for high throughput and low latency in cloud and virtual random access networks, this paper presents a graphics processing unit (GPU)-based AED architecture for polar and RM codes, utilizing low-complexity successive cancellation (SC) and small list SC (SCL) decoders as the constituent of AED. The proposed architecture exploits the inherent parallelism of AED to optimize decoding tasks on the GPU, significantly enhancing throughput by efficiently harnessing the extensive parallel processing capabilities of the GPU. Additionally, improved thread mapping and data management techniques markedly reduce latency for automorphism ensemble SC (Aut-SC) decoding, while a low-latency sorting mechanism further accelerates automorphism ensemble SCL (Aut-SCL) decoding. Experimental results on an NVIDIA RTX 4090 demonstrate that the proposed Aut-SC decoder, with an ensemble size of 8, achieves a throughput exceeding 17 Gbps. Compared to the state-of-the-art softwarebased SCL decoders, the proposed GPU-based Aut-SC and Aut-SCL architectures outperform existing solutions by factors of up to 28× and 10×, respectively, in normalized throughput while maintaining the same or even superior error correction performance.

IEEE Transactions on Signal ProcessingJan 1, 20251 citation

(\leq 256)

RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for RM codes of length

2^m

and order

m - 3

with reasonable complexity.

Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length

(\leq 256)

RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length

2^{m}

and order

m-3

with reasonable complexity.