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:1807.03912 · International Symposium on Turbo Codes and Iterative Information Processing

Decoding Reed-Muller and Polar Codes by Successive Factor Graph Permutations

Seyyed Ali Hashemi, Nghia Doan, Marco Mondelli, Warren J. Gross

Published Dec 1, 2018• 45 citations
arXivHTMLPDF

Abstract

Reed-Muller (RM) and polar codes are a class of capacity-achieving channel coding schemes with the same factor graph representation. Low-complexity decoding algorithms fall short in providing a good error-correction performance for RM and polar codes. Using the symmetric group of RM and polar codes, the specific decoding algorithm can be carried out on multiple permutations of the factor graph to boost the error-correction performance. However, this approach results in high decoding complexity. In this paper, we first derive the total number of factor graph permutations on which the decoding can be performed. We further propose a successive permutation (SP) scheme which finds the permutations on the fly, thus the decoding always progresses on a single factor graph permutation. We show that SP can be used to improve the error-correction performance of RM and polar codes under successive-cancellation (SC) and SC list (SCL) decoding, while keeping the memory requirements of the decoders unaltered. Our results for RM and polar codes of length 128 and rate 0.5 show that when SP is used and at a target frame error rate of 10-4, up to 0.5 dB and 0.1 dB improvement can be achieved for RM and polar codes respectively.

DOI
10.1109/istc.2018.8625281

Related papers

Decoding Reed-Muller Codes with Successive Factor-Graph Permutations.

Nghia Doan, Seyyed Ali Hashemi, Marco Mondelli +1 more

This paper presents a novel successive factor-graph permutation (SFP) scheme that significantly improves the error-correction performance of Reed-Muller (RM) codes under successive-cancellation list (SCL) decoding. In particular, we perform maximum-likelihood decoding on the symmetry group of RM codes to carefully select a good factor-graph permutation on the fly. We further propose an SFP-aided fast SCL decoding that significantly reduces the decoding latency while preserving the error-correction performance of the code. The simulation results show that for the third and fourth order RM codes of length $256$, the proposed decoder reduces up to $85\%$ of the memory consumption, $78\%$ of the decoding latency, and more than $99\%$ of the computational complexity of the state-of-the-art recursive projection-aggregation decoder at the frame error rate of $10^{-3}$.

•Sep 5, 2021•1 citation

Improved Hybrid RM-Polar Codes and Decoding on Stable Permuted Factor Graphs

Wu Wei, Zhen Zhai, Paul H. Siegel

A new family of modified polar codes and a new permutation selection scheme for belief propagation list (BPL) decoding are presented. We first propose a new code construction methodology to interpolate between Reed-Muller (RM) codes and polar codes. By taking advantage of an existing partial order on bit-channels whose corresponding indices share the same Hamming weight, we analyze the complexity of the new construction method. It is shown that we need to compute the reliability of roughly a fraction 1/log3/2N of all the bit-channels contained in the subset. Then, we explore a special family of factor-graph layer permutations called stable permutations (SPs) that preserve a specified information set when the corresponding bit permutations are applied to message bit indices. Simulation results show that the error-rate performance of the new family of codes is better than that of 5G polar codes under successive cancellation list (SCL) decoding. In addition, the SP selection scheme stands out as a preferred one for BPL decoding in terms of error-rate performance, while the average number of iterations per belief propagation (BP) decoder on the permuted factor graph is close to that of the original BP decoder when an early stopping condition is applied.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 30, 2021•3 citations

Improved Permutation-Based Successive Cancellation Decoding of Polar Codes

Mikhail Kamenev

Polar codes have been recently shown to have an automorphism group larger than the lower-triangular affine group. Permutations from this group can be used in an automorphism successive cancellation (SC) decoding algorithm providing a lower latency compared to that of successive cancellation list decoding. In this paper, we demonstrate that any permutation from the automorphism group of Reed-Muller codes is suitable for permutation-based SC decoding of polar codes. Specifically, a code obtained by a permutation that is not in the automorphism group of the code, but is in the automorphism group of Reed-Muller codes, is shown to be a polar subcode. Simulations results show that these additional permutations allow improving performance of the automorphism SC decoding algorithm limited to the permutations from the automorphism group of the code.

International Siberian workshops and tutorials on electron devices and materials•Jun 30, 2021•8 citations

On the Decoding of Polar Codes on Permuted Factor Graphs

Nghia Doan, Seyyed Ali Hashemi, Marco Mondelli +1 more

Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length 1024, the error-correction performance of the proposed decoder is more than 0.25 dB better than that of the BP decoder with the same number of random permutations at the frame error rate of 10-4.

arXiv:1806.11195•Globecom•Dec 1, 2018•87 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.

arXiv:2101.11328•IEEE Transactions on Information Theory•Jul 29, 2022•5 citations

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

Entropy•Jul 28, 2025•0 citations
Reed-Muller (RM) and polar codes are a class of capacity-achieving channel coding schemes with the same factor graph representation. Low-complexity decoding algorithms fall short in providing a good error-correction performance for RM and polar codes. Using the symmetric group of RM and polar codes, the specific decoding algorithm can be carried out on multiple permutations of the factor graph to boost the error-correction performance. However, this approach results in high decoding complexity. In this paper, we first derive the total number of factor graph permutations on which the decoding can be performed. We further propose a successive permutation (SP) scheme which finds the permutations on the fly, thus the decoding always progresses on a single factor graph permutation. We show that SP can be used to improve the error-correction performance of RM and polar codes under successive-cancellation (SC) and SC list (SCL) decoding, while keeping the memory requirements of the decoders unaltered. Our results for RM and polar codes of length 128 and rate 0.5 show that when SP is used and at a target frame error rate of 10-4, up to 0.5 dB and 0.1 dB improvement can be achieved for RM and polar codes respectively.
This paper presents a novel successive factor-graph permutation (SFP) scheme that significantly improves the error-correction performance of Reed-Muller (RM) codes under successive-cancellation list (SCL) decoding. In particular, we perform maximum-likelihood decoding on the symmetry group of RM codes to carefully select a good factor-graph permutation on the fly. We further propose an SFP-aided fast SCL decoding that significantly reduces the decoding latency while preserving the error-correction performance of the code. The simulation results show that for the third and fourth order RM codes of length 256256256, the proposed decoder reduces up to 85%85\%85% of the memory consumption, 78%78\%78% of the decoding latency, and more than 99%99\%99% of the computational complexity of the state-of-the-art recursive projection-aggregation decoder at the frame error rate of 10−310^{-3}10−3.
A new family of modified polar codes and a new permutation selection scheme for belief propagation list (BPL) decoding are presented. We first propose a new code construction methodology to interpolate between Reed-Muller (RM) codes and polar codes. By taking advantage of an existing partial order on bit-channels whose corresponding indices share the same Hamming weight, we analyze the complexity of the new construction method. It is shown that we need to compute the reliability of roughly a fraction 1/log3/2N of all the bit-channels contained in the subset. Then, we explore a special family of factor-graph layer permutations called stable permutations (SPs) that preserve a specified information set when the corresponding bit permutations are applied to message bit indices. Simulation results show that the error-rate performance of the new family of codes is better than that of 5G polar codes under successive cancellation list (SCL) decoding. In addition, the SP selection scheme stands out as a preferred one for BPL decoding in terms of error-rate performance, while the average number of iterations per belief propagation (BP) decoder on the permuted factor graph is close to that of the original BP decoder when an early stopping condition is applied.
Polar codes have been recently shown to have an automorphism group larger than the lower-triangular affine group. Permutations from this group can be used in an automorphism successive cancellation (SC) decoding algorithm providing a lower latency compared to that of successive cancellation list decoding. In this paper, we demonstrate that any permutation from the automorphism group of Reed-Muller codes is suitable for permutation-based SC decoding of polar codes. Specifically, a code obtained by a permutation that is not in the automorphism group of the code, but is in the automorphism group of Reed-Muller codes, is shown to be a polar subcode. Simulations results show that these additional permutations allow improving performance of the automorphism SC decoding algorithm limited to the permutations from the automorphism group of the code.
Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length 1024, the error-correction performance of the proposed decoder is more than 0.25 dB better than that of the BP decoder with the same number of random permutations at the frame error rate of 10-4.
Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length(≤256)(\leq 256)(≤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 length2m2^{m}2mand orderm−3m-3m−3with reasonable complexity.
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%.