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 Communications Letters

Probability-Based Ordered-Statistics Decoding for Short Block Codes

Chentao Yue, Mahyar Shirvanimoghaddam, Giyoon Park, Ok-Sun Park, Branka S. Vucetic, Yonghui Li

Published Feb 12, 2021• 53 citations
Publisher

Abstract

This letter proposes an efficient probability-based ordered-statistics decoding (PB-OSD) algorithm for short block-length codes. In PB-OSD, we derive two probabilistic measures on the codeword estimates and test error patterns, respectively referred to as the success probability and promising probability. Based on these probabilities, a stopping criterion and a discarding criterion are developed to reduce the number of test error patterns and limit the decoding complexity. To further reduce the complexity, we propose a tree-based search strategy to find the most likely test error patterns in reprocessing stage of the OSD algorithm. Simulation results show that PB-OSD significantly reduces the decoding complexity under the same error performance, compared to the original OSD algorithm.

DOI
10.1109/lcomm.2021.3058978

Related papers

Segmentation-Discarding Ordered-Statistic Decoding for Linear Block Codes

Chentao Yue, Mahyar Shirvanimoghaddam, Yonghui Li +1 more

In this paper, we propose an efficient reliability based segmentation-discarding decoding (SDD) algorithm for short block-length codes. A novel segmentation- discarding technique is proposed along with the stopping rule to significantly reduce the decoding complexity without a significant performance degradation compared to ordered statistics decoding (OSD). In the proposed decoder, the list of test error patterns (TEPs) is divided into several segments according to carefully selected boundaries and every segment is checked separately during the reprocessing stage. Decoding is performed under the constraint of the discarding rule and stopping rule. Simulations results for different codes show that our proposed algorithm can significantly reduce the decoding complexity compared to the existing OSD algorithms in literature.

arXiv:1901.02603•Globecom•Dec 1, 2019•42 citations

A Low-Complexity Ordered Statistic Decoding of Short Block Codes

Jifan Liang, Yiwen Wang, Suihua Cai +1 more

This letter is concerned with a generalized ordered statistic decoding (OSD) algorithm, called locally constrained OSD (LC-OSD). Instead of order-$t$reprocessing on the most reliable independent bits, the LC-OSD searches for test error patterns using the serial list Viterbi algorithm (SLVA) over a trellis specified by a local parity-check matrix. We derive several early stopping criteria that can be used to reduce the number of searches. Numerical results show that the LC-OSD algorithm with the proposed stopping criteria has much lower time complexity than the original OSD but incurs negligible performance loss.

IEEE Communications Letters•Nov 17, 2022•52 citations

Ordered statistics-based list decoding techniques for linear binary block codes

Saif E. A. Alnawayseh, Pavel Loskot

The ordered statistics-based list decoding techniques for linear binary block codes of small to medium block length are investigated. The construction of a list of the test error patterns is considered. The original ordered-statistics decoding (OSD) is generalized by assuming segmentation of the most reliable independent positions (MRIPs) of the received bits. The segmentation is shown to overcome several drawbacks of the original OSD. The complexity of the ordered statistics-based decoding is further reduced by assuming a partial ordering of the received bits in order to avoid the complex Gauss elimination. The probability of the test error patterns in the decoding list is derived. The bit error rate performance and the decoding complexity trade-off of the proposed decoding algorithms is studied by computer simulations. Numerical examples show that, in some cases, the proposed decoding schemes are superior to the original OSD in terms of both the bit error rate performance as well as the decoding complexity.

EURASIP Journal on Wireless Communications and Networking•Oct 16, 2012•13 citations

Ordered Statistic Decoding for Short Polar Codes

Daolong Wu, Ying Li, Xudong Guo +1 more

In this letter, the ordered statistic decoding (OSD) is considered to decode short polar codes. Since the number of tested codewords is high in the original OSD, a threshold-based OSD is proposed to reduce the complexity. The analysis shows that the threshold affects the OSD in two ways. One is the error floor in high signal-to-noise ratio (SNR) region while the other is the reduction of the number of tested codewords. The estimation on the BLER performance in high SNR region and the average number of tested codewords are discussed. After that, CRC-aided OSD is proposed to further improve the performance of polar codes. Simulation results show that a well-designed threshold-based OSD can reduce the complexity without significant performance loss. And a higher order OSD decoder is needed if OSD is used to decoding moderate or long polar codes. It is also illustrated that the CRC-aided OSD outperforms the CRC-aided list decoding when the code rate is high. When code rate is low, the result inverses.

IEEE Communications Letters•Mar 7, 2016•50 citations

Order Skipping Ordered Statistics Decoding and its Performance Analysis

Xihao Li, Wenhao Chen, Li Chen +2 more

This paper proposes a reduced complexity ordered statistics decoding (OSD) algorithm for linear block codes, the namely order skipping (OS)-OSD algorithm. An approximated correlation distance lower bound (CDLB) is derived by utilizing likelihood of the received symbols over the least reliable positions (LRPs). It enables the assessment of whether the higher-order decoding can yield a more likely codeword estimation. If not, they can be skipped. Error-correction performance of the OSOSD is analyzed. In particular, the decoding error probability of OS-OSD with order one is theoretically characterized. Our simulation results verify that the OS-OSD can achieve a significant complexity reduction over the state-of-the-art OSD without compromising the decoding performance.

IEEE Information Theory Workshop (ITW)•Nov 24, 2024•3 citations

Local Constraint-Based Ordered Statistics Decoding for Short Block Codes

Yiwen Wang, Jifan Liang, Xiao Ma

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.

IEEE Information Theory Workshop (ITW)•Nov 1, 2022•39 citations
This letter proposes an efficient probability-based ordered-statistics decoding (PB-OSD) algorithm for short block-length codes. In PB-OSD, we derive two probabilistic measures on the codeword estimates and test error patterns, respectively referred to as the success probability and promising probability. Based on these probabilities, a stopping criterion and a discarding criterion are developed to reduce the number of test error patterns and limit the decoding complexity. To further reduce the complexity, we propose a tree-based search strategy to find the most likely test error patterns in reprocessing stage of the OSD algorithm. Simulation results show that PB-OSD significantly reduces the decoding complexity under the same error performance, compared to the original OSD algorithm.
In this paper, we propose an efficient reliability based segmentation-discarding decoding (SDD) algorithm for short block-length codes. A novel segmentation- discarding technique is proposed along with the stopping rule to significantly reduce the decoding complexity without a significant performance degradation compared to ordered statistics decoding (OSD). In the proposed decoder, the list of test error patterns (TEPs) is divided into several segments according to carefully selected boundaries and every segment is checked separately during the reprocessing stage. Decoding is performed under the constraint of the discarding rule and stopping rule. Simulations results for different codes show that our proposed algorithm can significantly reduce the decoding complexity compared to the existing OSD algorithms in literature.
This letter is concerned with a generalized ordered statistic decoding (OSD) algorithm, called locally constrained OSD (LC-OSD). Instead of order-tttreprocessing on the most reliable independent bits, the LC-OSD searches for test error patterns using the serial list Viterbi algorithm (SLVA) over a trellis specified by a local parity-check matrix. We derive several early stopping criteria that can be used to reduce the number of searches. Numerical results show that the LC-OSD algorithm with the proposed stopping criteria has much lower time complexity than the original OSD but incurs negligible performance loss.
The ordered statistics-based list decoding techniques for linear binary block codes of small to medium block length are investigated. The construction of a list of the test error patterns is considered. The original ordered-statistics decoding (OSD) is generalized by assuming segmentation of the most reliable independent positions (MRIPs) of the received bits. The segmentation is shown to overcome several drawbacks of the original OSD. The complexity of the ordered statistics-based decoding is further reduced by assuming a partial ordering of the received bits in order to avoid the complex Gauss elimination. The probability of the test error patterns in the decoding list is derived. The bit error rate performance and the decoding complexity trade-off of the proposed decoding algorithms is studied by computer simulations. Numerical examples show that, in some cases, the proposed decoding schemes are superior to the original OSD in terms of both the bit error rate performance as well as the decoding complexity.
In this letter, the ordered statistic decoding (OSD) is considered to decode short polar codes. Since the number of tested codewords is high in the original OSD, a threshold-based OSD is proposed to reduce the complexity. The analysis shows that the threshold affects the OSD in two ways. One is the error floor in high signal-to-noise ratio (SNR) region while the other is the reduction of the number of tested codewords. The estimation on the BLER performance in high SNR region and the average number of tested codewords are discussed. After that, CRC-aided OSD is proposed to further improve the performance of polar codes. Simulation results show that a well-designed threshold-based OSD can reduce the complexity without significant performance loss. And a higher order OSD decoder is needed if OSD is used to decoding moderate or long polar codes. It is also illustrated that the CRC-aided OSD outperforms the CRC-aided list decoding when the code rate is high. When code rate is low, the result inverses.
This paper proposes a reduced complexity ordered statistics decoding (OSD) algorithm for linear block codes, the namely order skipping (OS)-OSD algorithm. An approximated correlation distance lower bound (CDLB) is derived by utilizing likelihood of the received symbols over the least reliable positions (LRPs). It enables the assessment of whether the higher-order decoding can yield a more likely codeword estimation. If not, they can be skipped. Error-correction performance of the OSOSD is analyzed. In particular, the decoding error probability of OS-OSD with order one is theoretically characterized. Our simulation results verify that the OS-OSD can achieve a significant complexity reduction over the state-of-the-art OSD without compromising the decoding performance.
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.