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

Multiple-Cyclic-Basis GCD for BCH Codes

Yiwen Wang, Qianfan Wang, Jifan Liang, Linqi Song, Xiao Ma

Published May 24, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1109/icc59461.2026.11586826

Related papers

Gaussian-Elimination-Free Ordered Statistics Decoding via Pre-Stored Systematic Matrices

Yiwen Wang, Qianfan Wang, Xiangping Zheng +2 more

This paper proposes an improved ordered statistics decoding (OSD) algorithm, termed OSD with pre-stored systematic matrices (PSM-OSD), which completely avoids online Gaussian elimination by pre-storing multiple systematic generator matrices (SGMs) and selecting one based on the received sequence for decoding. To further improve the search efficiency, the local-constraint mechanism is combined with the PSM-OSD, resulting in the LC-PSM-OSD. We then address three critical questions for design: how many SGMs should be pre-stored, how they should be constructed, and how to select one for decoding. For the first question, we introduce the notion of maximum reliable-information coverage, which characterizes how well the pre-stored SGMs match the reliable bit positions. For construction and selection, we introduce a Reed-Muller-based design to ensure high basis diversity, and the sum-reliability strategy provides superior decoding performance among the tested selection criteria. A saddlepoint-based analytical framework is developed to estimate both the frame error rate (FER) upper bound and the average number of searches, enabling pre-stored matrix design without exhaustive decoding simulations. We also prove that, with tailored early stopping and unlimited maximum number of searches, the proposed algorithm is a non-exhaustive-search ML decoding algorithm. Numerical results and analysis demonstrate that the proposed decoding algorithms are effective across various coding schemes, including random linear codes, BCH codes, and 5G polar codes. Moreover, the results show that the proposed LC-PSM-OSD can closely approach the finite-length capacity over almost all code rates for the considered codes, and outperforms conventional OSD, guessing codeword decoding (GCD), and LC-GCD. © 2026 IEEE.

IEEE Transactions on Communications•Jan 1, 2026•1 citation

Automorphism-Enhanced GCD Algorithm for Polar Codes

Qianfan Wang, Xiangping Zheng, Yiwen Wang +3 more

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.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

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

Gaussian Elimination-Free OSD via Pre-Stored Matrices

Yiwen Wang, Qianfan Wang, X B Zheng +2 more

This paper proposes an improved ordered statistics decoding (OSD) algorithm, termed OSD with pre-stored systematic matrices (PSM-OSD), which completely avoids online Gaussian elimination by utilizing multiple pre-stored systematic generator matrices (SGMs) and selecting one based on the received sequence for decoding. To further improve the search efficiency, the local-constraint mechanism is combined with the PSM-OSD, resulting in the LC-PSM-OSD. We also propose a saddlepointbased numerical method to evaluate a tight upper bound of the FER. Furthermore, leveraging our saddlepoint approximation method, we address two critical challenges to optimize the proposed decoding algorithms: 1) Matrix-selection criteria are evaluated across sum-reliability, max-min-reliability and coveragemaximization rules. We demonstrate that the introduced sumreliability rule yields the best performance among the considered methods, and exhibits the smallest gap to the ML performance; 2) Number of pre-stored matrices is set by our saddlepoint analysis, which determines the minimal number of SGMs needed to approach the ML performance. Numerical results and analysis demonstrate that the proposed algorithms are effective across various coding schemes including random linear codes and BCH codes. Moreover, the results show that the proposed LC-PSM-OSD can closely approach the finite-length capacity over almost all code rates for random linear codes, and outperforms conventional OSD, guessing codeword decoding (GCD), and LC-GCD.

IEEE Wireless Communications and Networking Conference•Apr 13, 2026•1 citation

Locally Constrained Guessing Codeword Decoding of Short Block Codes

Xiangping Zheng, Xiao Ma

This paper is concerned with a universal guessing codeword decoding (GCD) of linear block codes, referred to as locally constrained GCD (LC-GCD), which does not require the online Gaussian elimination (GE). Distinguished from the GCD algorithm, the proposed LC-GCD queries the partial error patterns using the serial list Viterbi algorithm (SLVA) over a trellis specified by a local parity-check matrix, typically reducing the number of queries. Moreover, we introduce a parallel implementation of the LC-GCD algorithm to reduce decoding latency without compromising performance. Numerical results show that the LC-GCD requires a fewer number of queries than the GCD without performance loss, indicating a lower complexity in general. The comparisons with other decoding algorithms are also provided to demonstrate the potential advantage in complexity of the LC-GCD.

IEEE Information Theory Workshop (ITW)•Nov 24, 2024•16 citations

Gaussian-Elimination-Free BP-OSD Algorithm for Short 5G LDPC Codes

Qianfan Wang, Yiwen Wang, Jiayi Yang +2 more

In this paper, we propose a two-stage belief-propagation ordered statistics decoding (BP-OSD)-like algorithm, hereafter referred to as BP-LCGCD, tailored to 5G low-density parity-check (LDPC) codes. When standard BP decoding fails, a modified BP (mBP) with an iteration limit determined by the code’s girth and a normalization factor$\alpha $is performed to generate reliable posterior log-likelihood ratios (LLRs) in the pre-processing stage. In the post-processing stage, a locally constrained guessing codeword decoding (LC-GCD) module uses these posterior LLRs from the mBP to efficiently produce candidate codewords without any online Gaussian elimination (GE), where numerous invalid test error patterns are skipped by the introduced local constraints. To predict the decoding performance, we derive an upper bound on FER and employ a saddlepoint method to approximate its dominant tail-probability term, resulting in a semi-analytical FER prediction. Furthermore, we propose to design the second-stage LC-GCD to match the non-uniform posterior reliability profile induced by the BP-like preprocessing stage. To this end, an offline quasi-reliable re-encoding basis is constructed for 5G LDPC codes, where protograph EXIT-chart analysis is used to identify highly reliable variable-node positions. Simulation results demonstrate that the proposed GE-free BP-LCGCD significantly outperforms standard BP, achieves FER closely approaching that of GE-based BP-OSD, and approaches the finite-length bound across multiple code rates for 5G LDPC codes, while requiring a significantly smaller number of re-encodings and eliminating the need for online GE.

IEEE Transactions on Communications•Jan 1, 2026•0 citations
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.
This paper proposes an improved ordered statistics decoding (OSD) algorithm, termed OSD with pre-stored systematic matrices (PSM-OSD), which completely avoids online Gaussian elimination by pre-storing multiple systematic generator matrices (SGMs) and selecting one based on the received sequence for decoding. To further improve the search efficiency, the local-constraint mechanism is combined with the PSM-OSD, resulting in the LC-PSM-OSD. We then address three critical questions for design: how many SGMs should be pre-stored, how they should be constructed, and how to select one for decoding. For the first question, we introduce the notion of maximum reliable-information coverage, which characterizes how well the pre-stored SGMs match the reliable bit positions. For construction and selection, we introduce a Reed-Muller-based design to ensure high basis diversity, and the sum-reliability strategy provides superior decoding performance among the tested selection criteria. A saddlepoint-based analytical framework is developed to estimate both the frame error rate (FER) upper bound and the average number of searches, enabling pre-stored matrix design without exhaustive decoding simulations. We also prove that, with tailored early stopping and unlimited maximum number of searches, the proposed algorithm is a non-exhaustive-search ML decoding algorithm. Numerical results and analysis demonstrate that the proposed decoding algorithms are effective across various coding schemes, including random linear codes, BCH codes, and 5G polar codes. Moreover, the results show that the proposed LC-PSM-OSD can closely approach the finite-length capacity over almost all code rates for the considered codes, and outperforms conventional OSD, guessing codeword decoding (GCD), and LC-GCD. © 2026 IEEE.
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.
This paper proposes an improved ordered statistics decoding (OSD) algorithm, termed OSD with pre-stored systematic matrices (PSM-OSD), which completely avoids online Gaussian elimination by utilizing multiple pre-stored systematic generator matrices (SGMs) and selecting one based on the received sequence for decoding. To further improve the search efficiency, the local-constraint mechanism is combined with the PSM-OSD, resulting in the LC-PSM-OSD. We also propose a saddlepointbased numerical method to evaluate a tight upper bound of the FER. Furthermore, leveraging our saddlepoint approximation method, we address two critical challenges to optimize the proposed decoding algorithms: 1) Matrix-selection criteria are evaluated across sum-reliability, max-min-reliability and coveragemaximization rules. We demonstrate that the introduced sumreliability rule yields the best performance among the considered methods, and exhibits the smallest gap to the ML performance; 2) Number of pre-stored matrices is set by our saddlepoint analysis, which determines the minimal number of SGMs needed to approach the ML performance. Numerical results and analysis demonstrate that the proposed algorithms are effective across various coding schemes including random linear codes and BCH codes. Moreover, the results show that the proposed LC-PSM-OSD can closely approach the finite-length capacity over almost all code rates for random linear codes, and outperforms conventional OSD, guessing codeword decoding (GCD), and LC-GCD.
This paper is concerned with a universal guessing codeword decoding (GCD) of linear block codes, referred to as locally constrained GCD (LC-GCD), which does not require the online Gaussian elimination (GE). Distinguished from the GCD algorithm, the proposed LC-GCD queries the partial error patterns using the serial list Viterbi algorithm (SLVA) over a trellis specified by a local parity-check matrix, typically reducing the number of queries. Moreover, we introduce a parallel implementation of the LC-GCD algorithm to reduce decoding latency without compromising performance. Numerical results show that the LC-GCD requires a fewer number of queries than the GCD without performance loss, indicating a lower complexity in general. The comparisons with other decoding algorithms are also provided to demonstrate the potential advantage in complexity of the LC-GCD.
In this paper, we propose a two-stage belief-propagation ordered statistics decoding (BP-OSD)-like algorithm, hereafter referred to as BP-LCGCD, tailored to 5G low-density parity-check (LDPC) codes. When standard BP decoding fails, a modified BP (mBP) with an iteration limit determined by the code’s girth and a normalization factor$\alpha $is performed to generate reliable posterior log-likelihood ratios (LLRs) in the pre-processing stage. In the post-processing stage, a locally constrained guessing codeword decoding (LC-GCD) module uses these posterior LLRs from the mBP to efficiently produce candidate codewords without any online Gaussian elimination (GE), where numerous invalid test error patterns are skipped by the introduced local constraints. To predict the decoding performance, we derive an upper bound on FER and employ a saddlepoint method to approximate its dominant tail-probability term, resulting in a semi-analytical FER prediction. Furthermore, we propose to design the second-stage LC-GCD to match the non-uniform posterior reliability profile induced by the BP-like preprocessing stage. To this end, an offline quasi-reliable re-encoding basis is constructed for 5G LDPC codes, where protograph EXIT-chart analysis is used to identify highly reliable variable-node positions. Simulation results demonstrate that the proposed GE-free BP-LCGCD significantly outperforms standard BP, achieves FER closely approaching that of GE-based BP-OSD, and approaches the finite-length bound across multiple code rates for 5G LDPC codes, while requiring a significantly smaller number of re-encodings and eliminating the need for online GE.