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) 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.
A syndrome-based ordered statistics decoding(SOSD) algorithm for LDPC codes is proposed based on ordered statistics decoding(OSD) algorithm and syndrome-based decoding algorithm.The indexed systematic form of parity check matrix is obtained based on the least reliable independent positions(LRIPs) by performing Gaussian eliminations,which leads to that candidate codes are generated in the SOSD processing by using several binary vector additions,instead of using the re-encoding process,computation complexity in thereby reduced.A block accumulated log-likelihood ratio(LLR) strategy is further proposed to reconstruct the ordered information sequence,which can reduce the sensitivity of accumulated parameter selection to performance fluctuation.
Ordered statistics decoding (OSD) algorithm and syndrome-based decoding algorithm are investigated in this work, based on which, a syndrome-based ordered statistics decoding (SOSD) algorithm for LDPC codes is proposed. The indexed systematic form of parity check matrix is obtained based on the least reliable independent positions (LRIPs) by performing Gaussian eliminations, which promises that the SOSD processing need not the re-encoding process, but only several binary vector additions, therefore achieves noticeable computation complexity reduction.
Polar codes have been used to guarantee high reliability in communication due to their excellent performance. In this letter, we propose a guessing error pattern ordered statistic decoding (GEPOSD) algorithm to further improve the performance of short polar codes. It outperforms the widely used cyclic redundancy check-aided successive cancellation list (CA-SCL) decoding under a code length of 64. The GEPOSD algorithm utilizes a strategy based on the maximum a posteriori probability rule to select the error pattern on the most reliable independent bits. Subsequently, an error pattern set is extended using a tree search approach. To minimize computational complexity, we introduce two early stopping criteria that limit the number of error patterns tested in decoding. The simulation results show that the complexity of GEPOSD is significantly reduced compared to the original OSD algorithm.
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.
Polar codes are considered a promising candidate for URLLC. Due to the inevitable decoding delay and error propagation brought by successive cancellation (SC) based decoders, the ordered statistic decoding (OSD) algorithm, which has a parallel structure, raises much attention in polar decoding, especially for the short codelength cases. However, the OSD algorithm contains many unnecessary attempts for different error patterns (EPs), increasing the complexity and decoding delay. To address this issue, we propose a novel stochastic flipping decoding (SFD) algorithm. Instead of processing all EPs in the search space, each time, the proposed SFD decoder only processes a small set of EPs generated by stochastic flipping and then chooses the one that has the best distance to get the new reference codeword. The flipping probability vector depends on how the flip of each bit potentially affects the overall distance, and it is updated progressively towards all-zero. The complexity of the algorithm can be further reduced by eliminating all the duplicated EPs. Numerical results show that improved SFD with adequately selected parameters outperforms OSD while the search space of these two algorithms is close.