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)

Automorphism-Enhanced GCD Algorithm for Polar Codes

Qianfan Wang, Xiangping Zheng, Yiwen Wang, Peihong Yuan, Linqi Song, Xiao Ma

Published Jun 1, 2026• 0 citations
Publisher

Abstract

This paper presents AE–LCGCD, an automorphism-enhanced multi-basis guessing codeword decoding (GCD) algorithm for CRC–polar codes, which avoids on-the-fly Gaussian elimination (GE). The proposed decoder leverages a large set of code automorphisms to construct multiple candidate re-encoding bases, selects the most reliable basis for decoding, and generates candidates via a locally constrained search. To reduce the average number of searches, we propose CRC-gated early-termination rules tailored to AE–LCGCD and prove that, under the proposed rule and without a limit on the number of searches, the decoder is a non-exhaustive ML decoder. To analyze performance, we develop a tight upper bound on the frame error rate (FER) using a saddlepoint approximation. Simulations on 5G CRC–polar codes across low, medium, and high rates show that AE–LCGCD consistently outperforms CRC-aided SCL (CA–SCL), and, in particular, it closely approaches the finite-length bound at high rates. Additionally, the proposed decoder significantly outperforms the conventional LC–GCD in both FER and average number of searches, owing to the improved re-encoding bases enabled by multiple automorphisms.

DOI
10.1109/isit62367.2026.11654171

Related papers

A Universal List Decoding Algorithm With Application to Decoding of Polar Codes

Xiangping Zheng, Xiao Ma

This paper is concerned with a guessing codeword decoding (GCD) of linear block codes, which is optimal and typically requires a fewer number of searches than the naive exhaustive search decoding (ESD). Compared with the guessing random additive noise decoding (GRAND), which is only efficient for high-rate codes, the GCD is efficient for not only high-rate codes but also low-rate codes. We prove that the GCD typically requires a fewer number of queries than the GRAND. Compared with the conventional ordered statistics decoding (OSD), the GCD does not require the online Gaussian elimination (GE). In addition to limiting the maximum number of searches, we suggest limiting the radius of searches in terms of soft weights or tolerated performance loss to further reduce the decoding complexity, resulting in the so-called truncated GCD. The performance gap between the truncated GCD and the optimal decoding can be upper bounded approximately by the saddlepoint approach or other numerical approaches. The derived upper bound captures the relationship between the performance and the decoding parameters, enabling us to balance the performance and the complexity by optimizing the decoding parameters of the truncated GCD. We also introduce a parallel implementation of the (truncated) GCD algorithm to reduce decoding latency without compromising performance. Another contribution of this paper is the application of the GCD to the polar codes. We propose a multiple-bit-wise decoding algorithm over a pruned tree for the polar codes, referred to as the successive-cancellation list (SCL) decoding algorithm by GCD. First, we present a strategy for pruning the conventional polar decoding tree based on the complexity analysis rather than the specific bit patterns. Then we apply the GCD algorithm in parallel aided by the early stopping criteria to the leaves of the pruned tree. Simulation results show that, without any performance loss as justified by analysis, the proposed decoding algorithm can significantly reduce the decoding latency of the polar codes.

arXiv:2405.03252•IEEE Transactions on Information Theory•Dec 2, 2024•21 citations

Multiple-Cyclic-Basis GCD for BCH Codes

Yiwen Wang, Qianfan Wang, Jifan Liang +2 more

In this paper, we propose a Gaussian-elimination-free (GE-free) multiple-cyclic-basis guessing codeword decoding (MCB-GCD) algorithm for BCH codes. Unlike conventional ordered statistics decoding (OSD), which selects a single most reliable basis via GE, MCB-GCD employs multiple cyclic bases, each consisting of k consecutive bits that serve as the re-encoding basis. By leveraging the cyclic structure of BCH codes, the proposed algorithm completely eliminates online GE and supports parallel list decoding through multiple re-encoding bases. A local-constraint (LC) mechanism together with trivial and dynamic approximate ideal (DAI) stopping criteria is employed to reduce the average number of searches. We prove that, with unlimited searches and tailored early stopping, the proposed algorithm is a non-exhaustive-search ML decoding algorithm. Furthermore, a saddlepoint-based numerical method is derived to estimate the upper bound on frame error rate (FER) and the average number of searches for the proposed decoding algorithm, confirming that MCB-GCD closely approaches maximum-likelihood (ML) performance with dramatically reduced average number of searches. Simulation results over BPSK-AWGN channels demonstrate that the BCH codes decoded by the proposed MCB-GCD closely approach the finite-length capacity across all supported code rates, while outperforming that with OSD, GCD and LC-GCD under certain parameters.

International Conference on Communications•May 24, 2026•0 citations

CRC-Aided Belief Propagation List Decoding of Polar Codes

Marvin Geiselhart, Ahmed Elkelesh, Moustafa Ebada +2 more

Although iterative decoding of polar codes has recently made huge progress based on the idea of permuted factor graphs, it still suffers from a non-negligible performance degradation when compared to state-of-the-art CRC-aided successive cancellation list (CA-SCL) decoding. In this work, we show that iterative decoding of polar codes based on the belief propagation list (BPL) algorithm can approach the error-rate performance of CA-SCL decoding and, thus, can be efficiently used for decoding the standardized 5G polar codes. Rather than only utilizing the cyclic redundancy check (CRC) as a stopping condition (i.e., for error-detection), we also aim to benefit from the error-correction capabilities of the outer CRC code. For this, we develop two distinct soft-decision CRC decoding algorithms: a Bahl-Cocke-Jelinek-Raviv (BCJR)-based approach and a sum product algorithm (SPA)-based approach. Further, an optimized selection of permuted factor graphs is analyzed and shown to reduce the decoding complexity significantly. Finally, we benchmark the proposed CRC-aided belief propagation list (CA-BPL) decoding to state-of-the-art 5G polar codes under CA-SCL decoding and, thereby, showcase an error-rate performance not just close to the CA-SCL but also close to the maximum likelihood (ML) bound as estimated by ordered statistic decoding (OSD).

arXiv:2001.05303•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•56 citations

SCL-GRAND: Lower complexity and better flexibility for CRC-Polar Codes

Xuanyu Li, Kai Niu, Jincheng Dai +2 more

Guessing random additive noise decoding (GRAND) is a recently proposed decoding algorithm which can achieve the error performance of maximum likelihood (ML) decoding. However, GRAND and its variants are only suitable for some short codes with high code rates and have large average query numbers. To mitigate these problems, we propose a successive cancellation list (SCL)-GRAND decoding algorithm for the cyclic redundancy check concatenated polar (CRC-polar) codes. The proposed decoder first divides the received sequence into two subblocks. Then SCL is used to decode the upper subblock and output several candidates into the candidate list. For each candidate, GRAND is used to decode the lower subblock and finally choose the most-likely codeword as the decoded result. Since the SCL is integrated into the SCL-GRAND algorithm, this algorithm can achieve lower complexity and better flexibility than the original GRAND.

IEEE Wireless Communications and Networking Conference•Mar 1, 2023•7 citations

A Polar Subcode Approach to Belief Propagation List Decoding

Marvin Geiselhart, Ahmed Elkelesh, Jannis Clausius +1 more

Permutation decoding gained recent interest as it can exploit the symmetries of a code in a parallel fashion. Moreover, it has been shown that by viewing permuted polar codes as polar subcodes, the set of usable permutations in permutation decoding can be increased. We extend this idea to pre-transformed polar codes, such as cyclic redundancy check (CRC)-aided polar codes, which previously could not be decoded using permutations due to their lack of automorphisms. Using belief propagation (BP)-based subdecoders, we showcase a performance close to CRC-aided SCL (CA-SCL) decoding. The proposed algorithm outperforms the previously best performing iterative CRC-aided belief propagation list (CA-BPL) decoder both in error-rate performance and decoding latency.

arXiv:2205.06631•IEEE Information Theory Workshop (ITW)•Nov 1, 2022•8 citations

Automorphism Ensemble Decoding With Reduced Delay

Anna A. Fominykh, Kirill Shabunov

Projected requirements for 6G ultra-reliable low-latency communications (URLLC) scenario require extremely low latency and efficient error correction akin to maximum likelihood (ML) performance. The quest for codes and decoding methods that balance low latency, energy efficiency, and error correction ability is at its height. Polar codes known for their capacity achievement in symmetric memoryless channels have shown promise in 5G applications. Advancing further existing decoding techniques like successive cancellation list (SCL) algorithm offer a path towards ML performance, whilst at the expense of having increased computational complexity. The introduction of automorphism ensemble (AE) decoding provided a novel approach for parallel decoding, particularly beneficial for codes with rich automorphism group like Reed-Muller (RM) codes. This work introduces a novel modification of AE decoding termed reduced-delay AE (RD-AE) decoder. RD-AE leverages a tailored set of automorphisms with the primary aim at diminishing decoding delay but also offering the flexibility to prioritize either delay reduction or error correction performance.

IEEE Globecom Workshops (GC Wkshps)•Dec 8, 2024•1 citation
This paper presents AE–LCGCD, an automorphism-enhanced multi-basis guessing codeword decoding (GCD) algorithm for CRC–polar codes, which avoids on-the-fly Gaussian elimination (GE). The proposed decoder leverages a large set of code automorphisms to construct multiple candidate re-encoding bases, selects the most reliable basis for decoding, and generates candidates via a locally constrained search. To reduce the average number of searches, we propose CRC-gated early-termination rules tailored to AE–LCGCD and prove that, under the proposed rule and without a limit on the number of searches, the decoder is a non-exhaustive ML decoder. To analyze performance, we develop a tight upper bound on the frame error rate (FER) using a saddlepoint approximation. Simulations on 5G CRC–polar codes across low, medium, and high rates show that AE–LCGCD consistently outperforms CRC-aided SCL (CA–SCL), and, in particular, it closely approaches the finite-length bound at high rates. Additionally, the proposed decoder significantly outperforms the conventional LC–GCD in both FER and average number of searches, owing to the improved re-encoding bases enabled by multiple automorphisms.
This paper is concerned with a guessing codeword decoding (GCD) of linear block codes, which is optimal and typically requires a fewer number of searches than the naive exhaustive search decoding (ESD). Compared with the guessing random additive noise decoding (GRAND), which is only efficient for high-rate codes, the GCD is efficient for not only high-rate codes but also low-rate codes. We prove that the GCD typically requires a fewer number of queries than the GRAND. Compared with the conventional ordered statistics decoding (OSD), the GCD does not require the online Gaussian elimination (GE). In addition to limiting the maximum number of searches, we suggest limiting the radius of searches in terms of soft weights or tolerated performance loss to further reduce the decoding complexity, resulting in the so-called truncated GCD. The performance gap between the truncated GCD and the optimal decoding can be upper bounded approximately by the saddlepoint approach or other numerical approaches. The derived upper bound captures the relationship between the performance and the decoding parameters, enabling us to balance the performance and the complexity by optimizing the decoding parameters of the truncated GCD. We also introduce a parallel implementation of the (truncated) GCD algorithm to reduce decoding latency without compromising performance. Another contribution of this paper is the application of the GCD to the polar codes. We propose a multiple-bit-wise decoding algorithm over a pruned tree for the polar codes, referred to as the successive-cancellation list (SCL) decoding algorithm by GCD. First, we present a strategy for pruning the conventional polar decoding tree based on the complexity analysis rather than the specific bit patterns. Then we apply the GCD algorithm in parallel aided by the early stopping criteria to the leaves of the pruned tree. Simulation results show that, without any performance loss as justified by analysis, the proposed decoding algorithm can significantly reduce the decoding latency of the polar codes.
In this paper, we propose a Gaussian-elimination-free (GE-free) multiple-cyclic-basis guessing codeword decoding (MCB-GCD) algorithm for BCH codes. Unlike conventional ordered statistics decoding (OSD), which selects a single most reliable basis via GE, MCB-GCD employs multiple cyclic bases, each consisting of k consecutive bits that serve as the re-encoding basis. By leveraging the cyclic structure of BCH codes, the proposed algorithm completely eliminates online GE and supports parallel list decoding through multiple re-encoding bases. A local-constraint (LC) mechanism together with trivial and dynamic approximate ideal (DAI) stopping criteria is employed to reduce the average number of searches. We prove that, with unlimited searches and tailored early stopping, the proposed algorithm is a non-exhaustive-search ML decoding algorithm. Furthermore, a saddlepoint-based numerical method is derived to estimate the upper bound on frame error rate (FER) and the average number of searches for the proposed decoding algorithm, confirming that MCB-GCD closely approaches maximum-likelihood (ML) performance with dramatically reduced average number of searches. Simulation results over BPSK-AWGN channels demonstrate that the BCH codes decoded by the proposed MCB-GCD closely approach the finite-length capacity across all supported code rates, while outperforming that with OSD, GCD and LC-GCD under certain parameters.
Although iterative decoding of polar codes has recently made huge progress based on the idea of permuted factor graphs, it still suffers from a non-negligible performance degradation when compared to state-of-the-art CRC-aided successive cancellation list (CA-SCL) decoding. In this work, we show that iterative decoding of polar codes based on the belief propagation list (BPL) algorithm can approach the error-rate performance of CA-SCL decoding and, thus, can be efficiently used for decoding the standardized 5G polar codes. Rather than only utilizing the cyclic redundancy check (CRC) as a stopping condition (i.e., for error-detection), we also aim to benefit from the error-correction capabilities of the outer CRC code. For this, we develop two distinct soft-decision CRC decoding algorithms: a Bahl-Cocke-Jelinek-Raviv (BCJR)-based approach and a sum product algorithm (SPA)-based approach. Further, an optimized selection of permuted factor graphs is analyzed and shown to reduce the decoding complexity significantly. Finally, we benchmark the proposed CRC-aided belief propagation list (CA-BPL) decoding to state-of-the-art 5G polar codes under CA-SCL decoding and, thereby, showcase an error-rate performance not just close to the CA-SCL but also close to the maximum likelihood (ML) bound as estimated by ordered statistic decoding (OSD).
Guessing random additive noise decoding (GRAND) is a recently proposed decoding algorithm which can achieve the error performance of maximum likelihood (ML) decoding. However, GRAND and its variants are only suitable for some short codes with high code rates and have large average query numbers. To mitigate these problems, we propose a successive cancellation list (SCL)-GRAND decoding algorithm for the cyclic redundancy check concatenated polar (CRC-polar) codes. The proposed decoder first divides the received sequence into two subblocks. Then SCL is used to decode the upper subblock and output several candidates into the candidate list. For each candidate, GRAND is used to decode the lower subblock and finally choose the most-likely codeword as the decoded result. Since the SCL is integrated into the SCL-GRAND algorithm, this algorithm can achieve lower complexity and better flexibility than the original GRAND.
Permutation decoding gained recent interest as it can exploit the symmetries of a code in a parallel fashion. Moreover, it has been shown that by viewing permuted polar codes as polar subcodes, the set of usable permutations in permutation decoding can be increased. We extend this idea to pre-transformed polar codes, such as cyclic redundancy check (CRC)-aided polar codes, which previously could not be decoded using permutations due to their lack of automorphisms. Using belief propagation (BP)-based subdecoders, we showcase a performance close to CRC-aided SCL (CA-SCL) decoding. The proposed algorithm outperforms the previously best performing iterative CRC-aided belief propagation list (CA-BPL) decoder both in error-rate performance and decoding latency.
Projected requirements for 6G ultra-reliable low-latency communications (URLLC) scenario require extremely low latency and efficient error correction akin to maximum likelihood (ML) performance. The quest for codes and decoding methods that balance low latency, energy efficiency, and error correction ability is at its height. Polar codes known for their capacity achievement in symmetric memoryless channels have shown promise in 5G applications. Advancing further existing decoding techniques like successive cancellation list (SCL) algorithm offer a path towards ML performance, whilst at the expense of having increased computational complexity. The introduction of automorphism ensemble (AE) decoding provided a novel approach for parallel decoding, particularly beneficial for codes with rich automorphism group like Reed-Muller (RM) codes. This work introduces a novel modification of AE decoding termed reduced-delay AE (RD-AE) decoder. RD-AE leverages a tailored set of automorphisms with the primary aim at diminishing decoding delay but also offering the flexibility to prioritize either delay reduction or error correction performance.