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

arXiv:1501.03235 · IEEE International Symposium on Circuits and Systems proceedings

Successive cancellation decoding of polar codes using stochastic computing

Bo Yuan, Keshab K. Parhi

Published May 1, 2015• 32 citations
arXivHTMLPDF

Abstract

Polar codes have emerged as the most favorable channel codes for their unique capacity-achieving property. To date, numerous approaches for efficient decoding of polar codes have been reported. However, these prior efforts focused on design of polar decoders via deterministic computation, while the behavior of stochastic polar decoder, which can have potential advantages such as low complexity and strong error-resilience, has not been studied in existing literatures. This paper, for the first time, investigates polar decoding using stochastic logic. Specifically, the commonly-used successive cancellation (SC) algorithm is reformulated into the stochastic form. Several methods that can potentially improve decoding performance are discussed and analyzed. Simulation results show that a stochastic SC decoder can achieve similar error-correcting performance as its deterministic counterpart. This work can pave the way for future hardware design of stochastic polar codes decoders.

DOI
10.1109/iscas.2015.7169328

Related papers

Efficient stochastic list successive cancellation decoder for polar codes

Xiao Liang, Chuan Zhang, Menghui Xu +2 more

Representing continuous values by streams of random binary bits, stochastic decoding has shown advantages in both hardware efficiency and fault tolerance, therefore has been widely adopted by iterative decoding of error correction codes such as low-density parity-check (LDPC) codes and so on. Recently, polar codes, the first codes that can provably achieve the capacity of symmetric binary-input discrete memoryless channels (B-DMCs), have drawn a lot of attentions from both academia and industry. Although, polar codes with list successive cancellation (SC) decoding can outperform several best-known LDPC codes even within high error-rate regions, the linearly increasing hardware complexity makes its efficient implementation difficult. To this end, the stochastic list SC polar decoding algorithm is proposed in this paper to provide a good tradeoff between performance and complexity. In order to increase the decoding performance of stochastic list SC polar decoder, doubling probability approach is presented. The corresponding hardware architecture is also given. The approximate doubling approach is employed to facilitate the efficient implementation. Implementation results have shown that the proposed stochastic list SC polar decoder can achieve a good trade-off between performance and complexity.

IEEE International System-on-Chip Conference (SOCC)•Sep 1, 2015•12 citations

SUCCESSIVE CANCELLATION DECODER OF POLAR CODES FOR 5G COMMUNICATION

Mrs. Sowmya Jyothi, B. SRI SAI KAVYA, G. TEJASRI

Polar codes have emerged as a promising error correction coding scheme for the next generation communication systems, particularly in the context of 5G technology. This Project architectures for polar code decoders using stochastic computing. Prior efforts were focused on design of polar decoders via deterministic computation, while the behaviour of stochastic polar decoder, which can have potential advantages such as low complexity and strong error-resilience, was not been studied. We design implement 8-bit stochastic polar SC decoder and verify the functionality.

Biomedical and Pharmacological Literature Archives•Nov 21, 2025•0 citations

Successive cancellation decoders of polar codes based on stochastic computation

Zhenglei Xu, Kai Niu

Polar codes are a class of codes discovered recently, which are proved to have capacity-achieving performance. The hardware implementations of successive cancellation (SC) decoding and List SC decoding are increasing dramatically now. However, throughput of these hardware structures remain to be improved on the one hand. On the other hand, stochastic computation is now wildly used because it uses simple structures to implement complicated mathematical operations and thus improves the throughput. This paper extends the application of stochastic computation to the decoding of polar codes. A family of SC decoders based on stochastic computation are proposed, including decoders based on bipolar stochastic computation(BSC-SC), low bits stochastic computation(LBSC-SC) and improved stochastic computation(ISC-SC). These methods have high generality and improve the throughput over SC decoder while having 0.5dB loss in decoding performance. The proposed 32-bit ISC-SC decoder has a better decoding accuracy and improves throughput over BSC-SC. It also reduces the hardware cost and latency compared to LBSC-SC decoder.

IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)•Sep 1, 2014•5 citations

Insertion/Deletion/Substitution Error Correction by a Modified Successive Cancellation Decoding of Polar Code

Hikari Koremura, Haruhiko Kaneko

This paper presents a successive cancellation (SC) decoding of polar codes modified for insertion/deletion/substitution (IDS) error channels, in which insertions and deletions are described by drift values. The recursive calculation of the original SC decoding is modified to include the drift values as stochastic variables. The computational complexity of the modified SC decoding is O (D3) with respect to the maximum drift value D, and O (N log N) with respect to the code length N. The symmetric capacity of polar bit channel is estimated by computer simulations, and frozen bits are determined according to the estimated symmetric capacity. Simulation results show that the decoded error rate of polar code with the modified SC list decoding is lower than that of existing IDS error correction codes, such as marker-based code and spatially-coupled code.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Mar 31, 2020•6 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

Threshold Successive Cancellation Flip Decoding Algorithm for Polar Codes: Design and Performance

Zhicheng Liu, Liuquan Yao, Shuai Yuan +3 more

In this paper, we propose the threshold successive cancellation flip (Th-SCF) decoding algorithm for polar codes, which enhances the performance of the SC decoder while maintaining low complexity. Theoretical analysis reveals that Th-SCF asymptotically delays the first error position (FEP, the first part where the SC decoder fails) with probability 1, ensuring high decoding performance. Simulation results show that the Th-SCF algorithm achieves performance comparable to the dynamic SC flip (D-SCF) algorithm, but with a reduction in complexity by eliminating the need for sorting operations. A key contribution of this work is the rigorous theoretical framework supporting the Th-SCF algorithm, distinguishing it from existing SC flip (SCF) decoding methods. This theoretical foundation not only explains the performance improvements but also provides insights into the underlying mechanisms of flipping. The proposed Th-SCF algorithm demonstrates strong performance across a wide range of code lengths and rates, and its performance remains stable within a certain threshold range, indicating its practical applicability in real-world communication systems. These results offer valuable perspectives for the design of efficient flip decoding strategies in 5G and future networks.

Entropy•Jun 12, 2025•1 citation
Polar codes have emerged as the most favorable channel codes for their unique capacity-achieving property. To date, numerous approaches for efficient decoding of polar codes have been reported. However, these prior efforts focused on design of polar decoders via deterministic computation, while the behavior of stochastic polar decoder, which can have potential advantages such as low complexity and strong error-resilience, has not been studied in existing literatures. This paper, for the first time, investigates polar decoding using stochastic logic. Specifically, the commonly-used successive cancellation (SC) algorithm is reformulated into the stochastic form. Several methods that can potentially improve decoding performance are discussed and analyzed. Simulation results show that a stochastic SC decoder can achieve similar error-correcting performance as its deterministic counterpart. This work can pave the way for future hardware design of stochastic polar codes decoders.
Representing continuous values by streams of random binary bits, stochastic decoding has shown advantages in both hardware efficiency and fault tolerance, therefore has been widely adopted by iterative decoding of error correction codes such as low-density parity-check (LDPC) codes and so on. Recently, polar codes, the first codes that can provably achieve the capacity of symmetric binary-input discrete memoryless channels (B-DMCs), have drawn a lot of attentions from both academia and industry. Although, polar codes with list successive cancellation (SC) decoding can outperform several best-known LDPC codes even within high error-rate regions, the linearly increasing hardware complexity makes its efficient implementation difficult. To this end, the stochastic list SC polar decoding algorithm is proposed in this paper to provide a good tradeoff between performance and complexity. In order to increase the decoding performance of stochastic list SC polar decoder, doubling probability approach is presented. The corresponding hardware architecture is also given. The approximate doubling approach is employed to facilitate the efficient implementation. Implementation results have shown that the proposed stochastic list SC polar decoder can achieve a good trade-off between performance and complexity.
Polar codes have emerged as a promising error correction coding scheme for the next generation communication systems, particularly in the context of 5G technology. This Project architectures for polar code decoders using stochastic computing. Prior efforts were focused on design of polar decoders via deterministic computation, while the behaviour of stochastic polar decoder, which can have potential advantages such as low complexity and strong error-resilience, was not been studied. We design implement 8-bit stochastic polar SC decoder and verify the functionality.
Polar codes are a class of codes discovered recently, which are proved to have capacity-achieving performance. The hardware implementations of successive cancellation (SC) decoding and List SC decoding are increasing dramatically now. However, throughput of these hardware structures remain to be improved on the one hand. On the other hand, stochastic computation is now wildly used because it uses simple structures to implement complicated mathematical operations and thus improves the throughput. This paper extends the application of stochastic computation to the decoding of polar codes. A family of SC decoders based on stochastic computation are proposed, including decoders based on bipolar stochastic computation(BSC-SC), low bits stochastic computation(LBSC-SC) and improved stochastic computation(ISC-SC). These methods have high generality and improve the throughput over SC decoder while having 0.5dB loss in decoding performance. The proposed 32-bit ISC-SC decoder has a better decoding accuracy and improves throughput over BSC-SC. It also reduces the hardware cost and latency compared to LBSC-SC decoder.
This paper presents a successive cancellation (SC) decoding of polar codes modified for insertion/deletion/substitution (IDS) error channels, in which insertions and deletions are described by drift values. The recursive calculation of the original SC decoding is modified to include the drift values as stochastic variables. The computational complexity of the modified SC decoding is O (D3) with respect to the maximum drift value D, and O (N log N) with respect to the code length N. The symmetric capacity of polar bit channel is estimated by computer simulations, and frozen bits are determined according to the estimated symmetric capacity. Simulation results show that the decoded error rate of polar code with the modified SC list decoding is lower than that of existing IDS error correction codes, such as marker-based code and spatially-coupled code.
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.
In this paper, we propose the threshold successive cancellation flip (Th-SCF) decoding algorithm for polar codes, which enhances the performance of the SC decoder while maintaining low complexity. Theoretical analysis reveals that Th-SCF asymptotically delays the first error position (FEP, the first part where the SC decoder fails) with probability 1, ensuring high decoding performance. Simulation results show that the Th-SCF algorithm achieves performance comparable to the dynamic SC flip (D-SCF) algorithm, but with a reduction in complexity by eliminating the need for sorting operations. A key contribution of this work is the rigorous theoretical framework supporting the Th-SCF algorithm, distinguishing it from existing SC flip (SCF) decoding methods. This theoretical foundation not only explains the performance improvements but also provides insights into the underlying mechanisms of flipping. The proposed Th-SCF algorithm demonstrates strong performance across a wide range of code lengths and rates, and its performance remains stable within a certain threshold range, indicating its practical applicability in real-world communication systems. These results offer valuable perspectives for the design of efficient flip decoding strategies in 5G and future networks.