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 proposes an enhanced guessing codeword decoding (GCD) algorithm, termed GCD with most reliable cyclic basis (MRCB-GCD), specifically tailored for BCH codes. Unlike original GCD, the proposed method selects the k consecutive bits with the highest aggregate reliability as the re-encoding basis, leveraging the cyclic structure of BCH codes. To further enhance search efficiency, a local constraint (LC) mechanism is introduced, where the extended reliable bits of length k+δ enable the algorithm to skip numerous unnecessary test error patterns (TEPs). To stop the search process, we introduce two termination criteria and prove that the proposed approach with the trivial termination criterion forms a non-exhaustive-search maximum likelihood (ML) decoding algorithm. A saddlepoint-based numerical method is developed to approximately calculate the upper bound on the performance gap to the ML decoding and estimate the average number of searches, showing the advantages of the proposed MRCB-GCD over the original GCD in terms of both decoding performance and search efficiency. Simulation results demonstrate that: 1) MRCB- GCD outperforms original GCD in both frame error rate (FER) and number of searches, 2) the LC mechanism and termination criteria further reduce the number of searches, and 3) the proposed approach achieves finite-length capacity across various code rates but without requiring Gaussian elimination.

We propose a class of codes, referred to as staircase matrix codes (SMCs), which have staircase-like generator matrices or parity-check matrices. We illustrate that polar codes and Reed-Muller (RM) codes are (equivalent to) two instances of SMCs. The most distinguished feature of the SMCs is that the staircase-like matrices enable parallel implementation of the Gaussian elimination (GE). Then we propose a representative ordered statistics decoding (ROSD) algorithm for the SMCs. Different from the conventional OSD, which forms the most reliable basis (MRB) by selecting reliable bits globally, the proposed ROSD forms an extended basis by selecting relatively reliable bits locally at least one from each staircase. We demonstrate by simulation that the ROSD has a similar performance to the OSD with local constraints (LC-OSD) and that the proposed random SMCs can outperform the RM codes and the polar codes. To further reduce the decoding delay and improve the performance, we propose a heuristic construction of staircase generator matrix codes (SGMCs) and analyze the ensemble weight spectrum (related to performance) and the quality of MRB (related to average number of test error patterns (TEPs)) for the heuristic construction. The simulation results show that, the proposed heuristic construction can reduce the average number of TEPs of the ROSD and provide a potential reduction in average decoding delay in the high signal-to-noise ratio (SNR) region. Furthermore, the proposed heuristic construction can approach the RCU bounds in a wide range of code rates.

In this paper, we propose a two-stage soft-decision decoding (SDD) algorithm for BCH codes. At the first stage, we search for test error patterns (TEPs) according to the reliabilities of the received bits by using the flipping pattern tree (FPT) algorithm or the ordered reliability bits (ORB) technique, with a bounded number of searches. At the second stage, traditional algebraic hard-decision decoding (HDD), say, Berlekamp-Massey (BM) algorithm, is performed for these TEPs to find codewords. The proposed algorithm, referred to as FPT-BM algorithm or ORB-BM algorithm, can achieve near-optimal performance with a significantly small number of searches (dozens to hundreds). This enables efficient parallel implementation, ensuring low decoding latency and high throughput. To justify the sufficiency of the small number of searches, we provide qualitative reasoning and quantitative evaluation (using saddlepoint approximation) to show that the transmitted codeword under the proposed FPT-BM decoding strategy is reached much earlier in the search list than that under the single stage decoding (FPT-only). To analyze the performance, we calculate the upper bound on the performance gap between the proposed algorithm and maximum likelihood (ML) decoding based on the saddlepoint approximation, showing that the proposed algorithm can effectively approach the ML lower bound for high rate BCH codes. To reduce computational complexity, we introduce a filtering criterion, where the algebraic hard-decision decoding (BM decoding) is performed only for those candidates satisfying a sufficient number of parity-check equations. To determine the key parameters, we provide an intuitive criterion for the threshold in the filtering step based on the statistical analysis and a quantitative criterion for the maximum list size based on the upper bound on the performance gap to ML decoding. Numerical results demonstrate that: 1) By introducing the filtering criterion, the proposed FPT-BM algorithm effectively reduces the number of BM calls by half, with negligible performance loss, and outperforms the Chase-BM algorithm under the same filtering criterion; 2) The proposed decoding algorithm outperforms single stage decoding (FPT only) under limited search sizes; 3) For high rate BCH codes, the proposed decoding algorithm can approach the finite-length capacity, while for medium rate regions, the proposed decoding algorithm also exhibits better performance over FPT-only and BM-only decoding algorithms.

In this paper, we present a class of codes, referred to as random staircase generator matrix codes (SGMCs), which have staircase-like generator matrices. In the infinite-length region, we prove that the random SGMC is capacity-achieving over binary-input output-symmetric (BIOS) channels. In the finite-length region, we propose the generalized representative ordered statistics decoding with local constraints (LC-ROSD) algorithm for the SGMCs. The most distinguished feature of the SGMCs with LC-ROSD is that the staircase-like matrices enable parallel implementation of the Gaussian elimination (GE), avoiding the serial GE of conventional OSD and supporting a potential low decoding latency, as implied from simulations. To analyze the performance of random SGMCs in the finite-length region, we derive the ensemble weight spectrum and invoke the conventional union bound. We also derive a partially random coding union (RCU) bound, which is tighter than the conventional one and is used as a criterion to design the SGMCs. Staircase-like generator matrices allow us to derive a series of (tighter and tighter) lower bounds based on the second-order Bonferroni inequality with the incremental number of codewords. The numerical results show that the decoding performance can match well with the proposed partially RCU bound for different code rates and different profiles. The numerical results also show that the tailored SGMCs with the LC-ROSD algorithm can approach the finite-length performance bound, outperforming the 5G low-density parity-check (LDPC) codes, 5G polar codes, and Reed-Muller (RM) codes.

In this paper, we propose a class of codes, referred to as random staircase generator matrix codes (SGMCs), which have staircase-like generator matrices. In the infinite-length region, we prove that the random SGMC is capacity-achieving over binary-input output-symmetric (BIOS) channels. In the finite-length region, we present the representative ordered statistics decoding with local constraints (LC-ROSD) for the SGMCs. The most distinguished feature of the SGMCs with LC-ROSD is that the staircase-like matrices enable parallel implementation of the Gaussian elimination (GE), avoiding the serial GE of conventional OSD and supporting a potential low decoding latency, as implied from simulations. To analyze the performance of random SGMCs in the finite-length region, we derive the ensemble weight spectrum and invoke the conventional union bound. We also derive a partially random coding union (RCU) bound, which is tighter than the conventional one and can be used as a criterion to design the SGMCs. The numerical results show that the random SGMCs with the LC-ROSD exhibit a significant decoding time improvement compared to that with the conventional OSD. They also show that the tailored SGMCs with the LC-ROSD can approach the finite-length performance bound, outperforming the 5G low-density parity-check (LDPC) codes, 5G polar codes and Reed-Muller (RM) codes.

In this paper, we propose a new ordered statistics decoding (OSD) algorithm called representative OSD (ROSD), specifically designed for polar codes. The generator matrices of polar codes are composed of the rows indexed by an information index set in a lower triangular matrix with ones on the diagonal. Therefore, the generator matrices of polar codes have a staircase-like structure that enables us to present the parallel implemen-tation of Gaussian elimination (GE) in ROSD avoiding the serial GE in conventional OSD. Different from the conventional OSD which forms the most reliable basis (MRB) by selecting reliable bits globally, the proposed ROSD forms an extended basis by selecting relatively reliable bits locally at least one from each staircase. Simulation results show that the ROSD has a similar performance to the LC-OSD and conventional OSD for 5G polar codes and Reed-Muller (RM) construction polar codes.

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.