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 Information Technology, Networking, Electronic and Automation Control Conference (ITNEC)

A Hybrid OSD-SC Decoding Algorithm for Polar Codes

Yusheng Xing, Guofang Tu

Published Mar 1, 2019• 4 citations
Publisher

Abstract

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.

DOI
10.1109/itnec.2019.8729275

Related papers

Hybrid BP-SC/SCF Decoding for Polar Codes

Chih-Heng Cheng, Cheng-Hung Dixson Lin

There are two main algorithms, successive cancellation (SC) algorithm and brief propagation (BP) algorithm, for decoding polar code. The SC algorithm has better error-correcting performance and the BP algorithm has low latency. The hybrid BP-SC decoding combines these two decoding algorithms and achieves improvements. Furthermore, the successive cancellation flip (SCF) algorithm improves the error-correcting performance for the SC algorithm, but it has higher computation complexity and latency. Based on the hybrid BP-SC decoding, we proposed a hybrid BP-SC/SCF decoding for polar codes in this paper to further improve the error-correcting performance. The result shows our approach outperforms to frame error rates (FER) of the SC decoding and BP decoding at least 0.5-dB and outperforms hybrid BP-SC decoding by 0.2-dB to 0.4-dB. Compared with the SCF decoding, the hybrid BPSC/SCF decoding has a small degradation of FER in a highquality channel but it significantly reduces the average computation complexity.

IEEE International Conference on Consumer Electronics - Taiwan (ICCE-Taiwan)•Sep 15, 2021•1 citation

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

Improved Parity Check Aided Successive Cancellation Flip Polar Decoders

Dwaipayan Ghosh, Sudipta Chattopadhyay

Polar Codes achieve average error correction performance at finite code lengths, when decoded using Successive Cancellation (SC) decoding. Successive Cancellation Flip (SC-Flip) based decoders provide a viable low complexity substitute of the high performing high complexity Successive Cancellation List (SCL) decoders, providing a considerable improvement in the performance. A novel approach to identify and flip multiple erroneous bits in each decoding attempt has been aimed in this paper. Moreover, a faster version of the proposed decoder is also presented, which provides better performance throughout the entire decoding range. The performance of the proposed decoders have been evaluated with respect to frame error correction rate along with average normalized complexity and then compared with some of the existing works for validating the outperformance.

International Conference on Advances in Electrical, Computing, Communication and Sustainable Technologies (ICAECT)•Jan 11, 2024•1 citation

A Low-Latency Successive Cancellation Hybrid Decoder for Convolutional Polar Codes

Yu Wang, Shikai Qiu, Lirui Chen +4 more

By adopting successive cancellation list decoding (SCL), polar codes demonstrate competitive error correction performance over LDPC and Turbo codes. However, SCL decoding suffers from high computational complexity and long decoding latency, especially when the list size is very large. Successive cancellation flip (SCF), as another decoding algorithm that can achieve high error correction performance, has a complexity that is close to that of successive cancellation (SC) decoding. With the observation that SCL and SCF decoding are similar at giving more chances to inspect possible codewords simultaneously or sequentially, a novel hybrid decoder is proposed in this paper, which essentially combines the ideas of SCF and SCL decoders. Moreover, in order to compensate for the degradation of performance caused by the reduction of path splitting and further reduce the decoding latency, the convolutional polar codes are adopted with a designed bit-flipping set. Simulation results demonstrate that the proposed decoder achieves the reduction of decoding latency while attaining better performance than conventional CRC-aided SCL decoder.

IEEE International Conference on Acoustics Speech and Signal Processing•Apr 9, 2020•1 citation

A Low Complexity Segmented Parity SC Flip Decoding Algorithm for Polar Codes

Dwaipayan Ghosh, Shriya Das, Leuna Das +2 more

The Successive Cancellation decoder cannot provide satisfactory error correcting performance for finite length polar codes. The error performance can be improved by using Successive Cancellation Flip decoders at the expense of higher complexity. In line with this, a novel decoding approach has been developed in this paper, where distributed parity bits are used to divide the codeword into multiple segments having equal probability of error occurrence, allowing early termination. The proposed Segmented Parity Successive Cancellation Flip (SP-SC Flip) Decoder achieves lower normalized complexity and average decoding latency compared to some related existing decoders, without degrading the error correcting performance. Further improvement in decoder performance is observed when code words are divided into a greater number of segments.

IEEE International Conference on Advanced Networks and Telecommunications Systems•Dec 15, 2024•0 citations

Successive-Cancellation Flip and Perturbation Decoder of Polar Codes

Charles Pillet, Ilshat Sagitov, Dominic Deslandes +1 more

In this paper, two decoding algorithms based on Successive-Cancellation (SC) are proposed to improve the error-correction performance of cyclic redundancy check (CRC)-aided polar codes while aiming for a low-complexity implementation. Comparisons with Dynamic SC Flip (DSCF) and SC Perturbation (SCP) are carried out since the proposed DSCF and Perturbation (DSCFP) and Perturbed DSCF (PDSCF) algorithms combine both methods. The analysis includes comparisons with several code lengths$N$and various number of decoding attempts$T_{max}$. For$N=1024$and the coding rate$R= 1/2$, the DSCF and the SCP algorithms with$T_{\max}= 17$are bested by approximately 0.1 dB at block-error rate (BLER) of 0.001. At BLER = 10−6and for$T_{max}= 64$, the gain is of 0.375 dB and > 0.5 dB with respect to DSCF and SCP, respectively. At high signal-to-noise ratio, the average computational complexity of the proposed algorithms is virtually equivalent to that of SC.

arXiv:2504.12102•IEEE Wireless Communications and Networking Conference•Mar 24, 2025•0 citations
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.
There are two main algorithms, successive cancellation (SC) algorithm and brief propagation (BP) algorithm, for decoding polar code. The SC algorithm has better error-correcting performance and the BP algorithm has low latency. The hybrid BP-SC decoding combines these two decoding algorithms and achieves improvements. Furthermore, the successive cancellation flip (SCF) algorithm improves the error-correcting performance for the SC algorithm, but it has higher computation complexity and latency. Based on the hybrid BP-SC decoding, we proposed a hybrid BP-SC/SCF decoding for polar codes in this paper to further improve the error-correcting performance. The result shows our approach outperforms to frame error rates (FER) of the SC decoding and BP decoding at least 0.5-dB and outperforms hybrid BP-SC decoding by 0.2-dB to 0.4-dB. Compared with the SCF decoding, the hybrid BPSC/SCF decoding has a small degradation of FER in a highquality channel but it significantly reduces the average computation complexity.
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 achieve average error correction performance at finite code lengths, when decoded using Successive Cancellation (SC) decoding. Successive Cancellation Flip (SC-Flip) based decoders provide a viable low complexity substitute of the high performing high complexity Successive Cancellation List (SCL) decoders, providing a considerable improvement in the performance. A novel approach to identify and flip multiple erroneous bits in each decoding attempt has been aimed in this paper. Moreover, a faster version of the proposed decoder is also presented, which provides better performance throughout the entire decoding range. The performance of the proposed decoders have been evaluated with respect to frame error correction rate along with average normalized complexity and then compared with some of the existing works for validating the outperformance.
By adopting successive cancellation list decoding (SCL), polar codes demonstrate competitive error correction performance over LDPC and Turbo codes. However, SCL decoding suffers from high computational complexity and long decoding latency, especially when the list size is very large. Successive cancellation flip (SCF), as another decoding algorithm that can achieve high error correction performance, has a complexity that is close to that of successive cancellation (SC) decoding. With the observation that SCL and SCF decoding are similar at giving more chances to inspect possible codewords simultaneously or sequentially, a novel hybrid decoder is proposed in this paper, which essentially combines the ideas of SCF and SCL decoders. Moreover, in order to compensate for the degradation of performance caused by the reduction of path splitting and further reduce the decoding latency, the convolutional polar codes are adopted with a designed bit-flipping set. Simulation results demonstrate that the proposed decoder achieves the reduction of decoding latency while attaining better performance than conventional CRC-aided SCL decoder.
The Successive Cancellation decoder cannot provide satisfactory error correcting performance for finite length polar codes. The error performance can be improved by using Successive Cancellation Flip decoders at the expense of higher complexity. In line with this, a novel decoding approach has been developed in this paper, where distributed parity bits are used to divide the codeword into multiple segments having equal probability of error occurrence, allowing early termination. The proposed Segmented Parity Successive Cancellation Flip (SP-SC Flip) Decoder achieves lower normalized complexity and average decoding latency compared to some related existing decoders, without degrading the error correcting performance. Further improvement in decoder performance is observed when code words are divided into a greater number of segments.
In this paper, two decoding algorithms based on Successive-Cancellation (SC) are proposed to improve the error-correction performance of cyclic redundancy check (CRC)-aided polar codes while aiming for a low-complexity implementation. Comparisons with Dynamic SC Flip (DSCF) and SC Perturbation (SCP) are carried out since the proposed DSCF and Perturbation (DSCFP) and Perturbed DSCF (PDSCF) algorithms combine both methods. The analysis includes comparisons with several code lengthsNNNand various number of decoding attemptsTmaxT_{max}Tmax​. ForN=1024N=1024N=1024and the coding rateR=1/2R= 1/2R=1/2, the DSCF and the SCP algorithms withTmax⁡=17T_{\max}= 17Tmax​=17are bested by approximately 0.1 dB at block-error rate (BLER) of 0.001. At BLER = 10−6and forTmax=64T_{max}= 64Tmax​=64, the gain is of 0.375 dB and > 0.5 dB with respect to DSCF and SCP, respectively. At high signal-to-noise ratio, the average computational complexity of the proposed algorithms is virtually equivalent to that of SC.