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