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

IEEE Vehicular Technology Conference

Representative Ordered Statistics Decoding of Polar Codes

Yiwen Wang, Qianfan Wang, Jifan Liang, Xiao Ma

Published Jun 24, 2024• 4 citations
Publisher

Abstract

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.

DOI
10.1109/vtc2024-spring62846.2024.10683273

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

Improved Syndrome-Based Ordered Statistic Decoding Algorithm

Feng Guang-zeng

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.

Journal of Nanjing University of Posts and Telecommunications•Jan 1, 2011•0 citations

Improved syndrome-based ordered statistic decoding algorithm for LDPC codes

Dong Zijian, Liu Fei, Song Yaolian

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.

International Conference on Signal Processing Systems (ICSPS)•Jul 1, 2010•2 citations

Guessing Error Pattern Ordered Statistic Decoding for Short Polar Codes

Yuxin Han, Kai Niu, Xuanyu Li

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.

IEEE Communications Letters•Sep 28, 2023•4 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

Stochastic Flipping Decoding for Short Polar Codes

Yuzhou Shang, Zhaoyang Zhang

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.

IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2021•2 citations
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.
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.
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.