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

Ordered Statistic Decoding for Short Polar Codes

Daolong Wu, Ying Li, Xudong Guo, Yue Ming Sun

Published Mar 7, 2016• 50 citations
Publisher

Abstract

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.

DOI
10.1109/lcomm.2016.2539170

Related papers

A Low-Complexity Ordered Statistics Decoding Algorithm for Short Polar Codes

Yusheng Xing, Guofang Tu

In this paper, we propose a low-complexity ordered statistics decoding (OSD) algorithm called threshold-based OSD (TH-OSD) that uses a threshold on the discrepancy of the candidate codewords to speed up the decoding of short polar codes. To determine the threshold, we use the probability distribution of the discrepancy value of the maximal likelihood codeword with a predefined parameter controlling the trade-off between the error correction performance and the decoding complexity. We also derive an upper-bound of the word error rate (WER) for the proposed algorithm. The complexity analysis shows that our algorithm is faster than the conventional successive cancellation (SC) decoding algorithm in mid-to-high signal-to-noise ratio (SNR) situations and much faster than the SC list (SCL) decoding algorithm. Our addition of a list approach to our proposed algorithm further narrows the error correction performance gap between our TH-OSD and OSD. Our simulation results show that, with appropriate thresholds, our proposed algorithm achieves performance close to OSD’s while testing significantly fewer codewords than OSD, especially with low SNR values. Even a small list is sufficient for TH-OSD to match OSD’s error rate in short-code scenarios. The algorithm can be easily extended to longer code lengths.

Applied Sciences•Feb 26, 2019•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•3 citations

Segmented CRC-Aided Order Statistical Decoding with Multiple Biases for Short Polar Codes

Hao Tang, Ming Zhan, Liangxi Liu +4 more

With the advent of 5th generation (5G) mobile communication era, higher requirements are put forward for ultra-reliable and low-latency transmission compared with 4G, especially in the field of short packet communication. In this paper, we propose a segmented cyclic redundancy check aided order statistical decoding algorithm with multiple biases (BIAS- SCRC-OSD) for short polar codes. This algorithm constructs multiple information sets by repeatedly adding bias value, and selects more effective information sets to improve the decoding performance. For further improving the decoding performance, we change the original cyclic redundancy check (CRC) into segment check. The simulation results show that a suitable bias value can significantly improve the decoding performance with a small increase in computational complexity. Compared with the original CRC-aided order statistical decoding (OSD) algorithm, the proposed algorithm has a gain of about 0.8 dB at target bit error rate (BER) 10-4with code rate R = 0.5 and code length N = 64.

International Conference on Information Science and Technology•May 21, 2021•0 citations

Belief Propagation List Ordered Statistics Decoding of Polar Codes

Guy Mogilevsky, David Burshtein

It is shown how to combine ordered statistics decoding (OSD) with CRC-aided belief propagation list (CBPL) decoding of polar codes. Even when the reprocessing order of the OSD is as low as one, the new decoder is shown to significantly improve on CBPL. For reprocessing orders higher than one, we suggest partial reprocessing, where only error patterns associated with the least reliable part of the belief propagation decoded most reliable independent bits are considered. This type of partial reprocessing offers a trade-off between performance and computational complexity.

arXiv:2102.07994•Feb 16, 2021•0 citations

Pre-Configured Error Pattern Ordered Statistics Decoding for CRC-Polar Codes

Xuanyu Li, Kai Niu, Yuxin Han +3 more

In this paper, we propose a pre-configured error pattern ordered statistics decoding (PEPOSD) algorithm and discuss its application to short cyclic redundancy check (CRC)-polar codes. Unlike the traditional OSD that changes the most reliable independent symbols, we regard the decoding process as testing the error patterns, like guessing random additive noise decoding (GRAND). Also, the pre-configurator referred from ordered reliability bits (ORB) GRAND can better control the range and testing order of EPs. An offline-online structure can accelerate the decoding process. Additionally, we also introduce two orders to optimize the search order for testing EPs. Compared with CRC-aided OSD and list decoding, PEPOSD can achieve a better trade-off between accuracy and complexity.

arXiv:2309.11836•Entropy•Sep 30, 2023•6 citations

Probability-Based Ordered-Statistics Decoding for Short Block Codes

Chentao Yue, Mahyar Shirvanimoghaddam, Giyoon Park +3 more

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.

IEEE Communications Letters•Feb 12, 2021•53 citations
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.
In this paper, we propose a low-complexity ordered statistics decoding (OSD) algorithm called threshold-based OSD (TH-OSD) that uses a threshold on the discrepancy of the candidate codewords to speed up the decoding of short polar codes. To determine the threshold, we use the probability distribution of the discrepancy value of the maximal likelihood codeword with a predefined parameter controlling the trade-off between the error correction performance and the decoding complexity. We also derive an upper-bound of the word error rate (WER) for the proposed algorithm. The complexity analysis shows that our algorithm is faster than the conventional successive cancellation (SC) decoding algorithm in mid-to-high signal-to-noise ratio (SNR) situations and much faster than the SC list (SCL) decoding algorithm. Our addition of a list approach to our proposed algorithm further narrows the error correction performance gap between our TH-OSD and OSD. Our simulation results show that, with appropriate thresholds, our proposed algorithm achieves performance close to OSD’s while testing significantly fewer codewords than OSD, especially with low SNR values. Even a small list is sufficient for TH-OSD to match OSD’s error rate in short-code scenarios. The algorithm can be easily extended to longer code lengths.
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.
With the advent of 5th generation (5G) mobile communication era, higher requirements are put forward for ultra-reliable and low-latency transmission compared with 4G, especially in the field of short packet communication. In this paper, we propose a segmented cyclic redundancy check aided order statistical decoding algorithm with multiple biases (BIAS- SCRC-OSD) for short polar codes. This algorithm constructs multiple information sets by repeatedly adding bias value, and selects more effective information sets to improve the decoding performance. For further improving the decoding performance, we change the original cyclic redundancy check (CRC) into segment check. The simulation results show that a suitable bias value can significantly improve the decoding performance with a small increase in computational complexity. Compared with the original CRC-aided order statistical decoding (OSD) algorithm, the proposed algorithm has a gain of about 0.8 dB at target bit error rate (BER) 10-4with code rate R = 0.5 and code length N = 64.
It is shown how to combine ordered statistics decoding (OSD) with CRC-aided belief propagation list (CBPL) decoding of polar codes. Even when the reprocessing order of the OSD is as low as one, the new decoder is shown to significantly improve on CBPL. For reprocessing orders higher than one, we suggest partial reprocessing, where only error patterns associated with the least reliable part of the belief propagation decoded most reliable independent bits are considered. This type of partial reprocessing offers a trade-off between performance and computational complexity.
In this paper, we propose a pre-configured error pattern ordered statistics decoding (PEPOSD) algorithm and discuss its application to short cyclic redundancy check (CRC)-polar codes. Unlike the traditional OSD that changes the most reliable independent symbols, we regard the decoding process as testing the error patterns, like guessing random additive noise decoding (GRAND). Also, the pre-configurator referred from ordered reliability bits (ORB) GRAND can better control the range and testing order of EPs. An offline-online structure can accelerate the decoding process. Additionally, we also introduce two orders to optimize the search order for testing EPs. Compared with CRC-aided OSD and list decoding, PEPOSD can achieve a better trade-off between accuracy and complexity.
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.