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

Applied Sciences

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

Yusheng Xing, Guofang Tu

Published Feb 26, 2019• 2 citations
Publisher

Abstract

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.

DOI
10.3390/app9050831

Related papers

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

A Hybrid OSD-SC Decoding Algorithm for Polar Codes

Yusheng Xing, Guofang Tu

In this paper, we propose a low complexity hybrid ordered statistics decoding (OSD) successive cancellation (SC) decoding algorithm for the polar codes. By replacing smaller size SC decoder with OSD decoder, we can improve the error correcting performance of the SC algorithm. The size of the OSD decoder can be changed to control the trade-off between the decoding complexity and the error correcting performance of the proposed algorithm. We also provide a method to further simplify the proposed algorithm. Simulation results show that the proposed algorithm offers about 0.3 dB gain comparing to the SC at target bit error rate (BER) 10-5with code length N = 1024, 512,256 and code rate R = 1 /3. The impact of the OSD size is also simulated and analyzed.

IEEE Information Technology, Networking, Electronic and Automation Control Conference (ITNEC)•Mar 1, 2019•4 citations

Successive Syndrome-Check Decoding of Polar Codes

Seyyed Ali Hashemi, Marco Mondelli, J.M. Cioffi +1 more

A two-part successive syndrome-check decoding of polar codes is proposed with the first part successively refining the received codeword and the second part checking its syndrome. A new formulation of the successive-cancellation (SC) decoding algorithm is presented that allows for successively refining the received codeword by comparing the log-likelihood ratio value of a frozen bit with its predefined value. The syndrome of the refined received codeword is then checked for possible errors. In case there are no errors, the decoding process is terminated. Otherwise, the decoder continues to refine the received code-word. The proposed method is extended to the case of SC list (SCL) decoding by terminating the decoding process when the syndrome of the best candidate in the list indicates no errors. Simulation results show that the proposed method reduces the time-complexity of SC and SCL decoders and their fast variants, especially at high signal-to-noise ratios.

arXiv:2112.00057•Asilomar Conference on Signals, Systems and Computers (ACSSC)•Oct 31, 2021•5 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

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

Low complexity list successive cancellation decoding of polar codes

Congzhe Cao, Zesong Fei, Jinhong Yuan +1 more

The authors propose a low complexity list successive cancellation (LCLSC) decoding algorithm, where the advantages of the successive cancellation (SC) decoding and the list successive cancellation (LSC) decoding are both considered. In the proposed decoding, SC decoding instead of LSC decoding is implemented when all information bits from bad subchannels are received reliably. While the reliability of each information bit is estimated by its likelihood ratio (LR), the bit channel quality is measured via its Bhattacharyya parameter. To achieve this goal, the authors introduce two thresholds: LR threshold and Bhattacharyya parameter threshold. Also, the methods to determine them are both elaborated. The numerical results suggest that the complexity of LCLSC decoding is much lower than LSC decoding and can be close to that of SC decoding, while the error performance is almost equal to that of LSC decoding. Especially, when the code rate is in low region, the advantage of our decoding is more obvious.

arXiv:1309.3173•IET Communications•Sep 12, 2014•26 citations
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.
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 hybrid ordered statistics decoding (OSD) successive cancellation (SC) decoding algorithm for the polar codes. By replacing smaller size SC decoder with OSD decoder, we can improve the error correcting performance of the SC algorithm. The size of the OSD decoder can be changed to control the trade-off between the decoding complexity and the error correcting performance of the proposed algorithm. We also provide a method to further simplify the proposed algorithm. Simulation results show that the proposed algorithm offers about 0.3 dB gain comparing to the SC at target bit error rate (BER) 10-5with code length N = 1024, 512,256 and code rate R = 1 /3. The impact of the OSD size is also simulated and analyzed.
A two-part successive syndrome-check decoding of polar codes is proposed with the first part successively refining the received codeword and the second part checking its syndrome. A new formulation of the successive-cancellation (SC) decoding algorithm is presented that allows for successively refining the received codeword by comparing the log-likelihood ratio value of a frozen bit with its predefined value. The syndrome of the refined received codeword is then checked for possible errors. In case there are no errors, the decoding process is terminated. Otherwise, the decoder continues to refine the received code-word. The proposed method is extended to the case of SC list (SCL) decoding by terminating the decoding process when the syndrome of the best candidate in the list indicates no errors. Simulation results show that the proposed method reduces the time-complexity of SC and SCL decoders and their fast variants, especially at high signal-to-noise ratios.
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.
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.
The authors propose a low complexity list successive cancellation (LCLSC) decoding algorithm, where the advantages of the successive cancellation (SC) decoding and the list successive cancellation (LSC) decoding are both considered. In the proposed decoding, SC decoding instead of LSC decoding is implemented when all information bits from bad subchannels are received reliably. While the reliability of each information bit is estimated by its likelihood ratio (LR), the bit channel quality is measured via its Bhattacharyya parameter. To achieve this goal, the authors introduce two thresholds: LR threshold and Bhattacharyya parameter threshold. Also, the methods to determine them are both elaborated. The numerical results suggest that the complexity of LCLSC decoding is much lower than LSC decoding and can be close to that of SC decoding, while the error performance is almost equal to that of LSC decoding. Especially, when the code rate is in low region, the advantage of our decoding is more obvious.