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 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.
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.
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 two-stage beliefpropagation ordered statistics decoding (BP-OSD)-like algorithm, referred to as BP-LCGCD, tailored to 5G low-density paritycheck (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 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 mBP to produce candidate codewords without online Gaussian elimination (GE), where numerous invalid test error patterns (TEPs) are skipped by the introduced local constraints. To predict the performance, we derive an upper bound on FER and employ a saddlepoint method to compute its dominant tail-probability term. Furthermore, we propose an offline EXIT-chart-based method to select a fixed quasi-reliable basis, where variable nodes with the highest mutual information are chosen. Simulation results demonstrate that the proposed GE-free BP-LCGCD significantly outperforms standard BP, achieves FER very close to GE-based BP-OSD, and approaches the finite-length bound across multiple code rates for 5G LDPC codes, while requiring significantly fewer re-encodings and eliminating the need for online GE.
This paper is concerned with the ordered statistic decoding with local constraints (LC-OSD) of binary linear block codes, which is a near maximum-likelihood decoding algorithm. Compared with the conventional OSD, the LC-OSD significantly reduces both the maximum and the average number of searches. The former is achieved by performing the serial list Viterbi algorithm (SLVA) or a two-way flipping pattern tree (FPT) algorithm with local constraints on the test error patterns, while the latter is achieved by incorporating tailored early termination criteria. The main objective of this paper is to explore the relationship between the performance of the LC-OSD and decoding parameters, such as the constraint degree and the maximum list size. To this end, we approximate the local parity-check matrix as a totally random matrix and then estimate the performance of the LC-OSD by analyzing with a saddlepoint approach the performance of random codes over the channels associated with the most reliable bits (MRBs). The random coding approach enables us to derive an upper bound on the performance and predict the average rank of the transmitted codeword in the list delivered by the LC-OSD. This allows us to balance the constraint degree and the maximum list size for the average (or maximum) time complexity reduction. Simulation results show that the approximation by random coding approach is numerically effective and powerful. Simulation results also show that the RS codes decoded by the LC-OSD can approach the random coding union (RCU) bounds, verifying the efficiency and universality of the LC-OSD.
In this paper, we propose a new ordered statistics decoding (OSD) for linear block codes, which is referred to as local constraint-based OSD (LC-OSD). Distinguished from the conventional OSD, which chooses the most reliable basis (MRB) for re-encoding, the LC-OSD chooses an extended MRB on which local constraints are naturally imposed. A list of candidate codewords is then generated by performing a serial list Viterbi algorithm (SLVA) over the trellis specified with the local constraints. To terminate early the SLVA for complexity reduction, we present a simple criterion which monitors the ratio of the bound on the likelihood of the unexplored candidate codewords to the sum of the hard-decision vector’s likelihood and the up-to-date optimal candidate’s likelihood. Simulation results show that the LC-OSD can have a much less number of test patterns than that of the conventional OSD but cause negligible performance loss. Comparisons with other complexity-reduced OSDs are also conducted, showing the advantages of the LC-OSD in terms of complexity.