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 Journal on Selected Areas in Communications

Low-Complexity Soft-Output Decoding of Polar Codes

Ubaid U. Fayyaz, John R. Barry

Published Apr 24, 2014• 166 citations
Publisher

Abstract

The state-of-the-art soft-output decoder for polar codes is a message-passing algorithm based on belief propagation, which performs well at the cost of high processing and storage requirements. In this paper, we propose a low-complexity alternative for soft-output decoding of polar codes that offers better performance but with significantly reduced processing and storage requirements. In particular we show that the complexity of the proposed decoder is only 4% of the total complexity of the belief propagation decoder for a rate one-half polar code of dimension 4096 in the dicode channel, while achieving comparable error-rate performance. Furthermore, we show that the proposed decoder requires about 39% of the memory required by the belief propagation decoder for a block length of 32768.

DOI
10.1109/jsac.2014.140515

Related papers

A low-complexity soft-output decoder for polar codes

Ubaid U. Fayyaz, John R. Barry

A widely used soft-output decoder for polar codes is a message-passing algorithm based on belief propagation, which performs well at the cost of high processing and storage requirements. In this paper we propose a low-complexity alternative for soft-output decoding of polar codes that offers comparable performance but with significantly reduced processing and storage requirements. In particular we show that the complexity of the proposed decoder is about 5% of the total complexity of the belief propagation decoder for the dicode channel, while achieving comparable error-rate performance. Furthermore, we show that the proposed decoder requires about 39% of the memory required by the belief propagation decoder for a block length of 32768.

Globecom•Dec 1, 2013•6 citations

A high throughput belief propagation decoder architecture for polar codes

Jun Ting Lin, Jin Sha, Li Li +3 more

The belief propagation (BP) decoding algorithm not only is an alternative to the successive cancelation (SC) decoders of polar codes, but also provides soft outputs that are necessary for joint detection and decoding. The BP decoders with the flooding schedule achieve high throughput with excessive hardware cost especially when the block length is large. The soft-cancelation (SCAN) decoders for polar codes have reduced memory complexity compared to the BP decoders based on the flooding schedule. The simplified SC aided reduced complexity soft-cancelation (S-RCSC) decoders further reduce the computational and memory complexity of the SCAN decoders at the cost of negligible error performance degradation. Both the SCAN and S-RCSC decoders have limited throughput due to their serial decoding schedules. In this paper, we first propose an improved S-RCSC (IS-RCSC) decoding algorithm and then present a high throughput decoder architecture based on our IS-RCSC algorithm. Our IS-RCSC decoding algorithm performs the message passing on a binary tree representation of a polar code. Compared to the S-RCSC decoding algorithm, our IS-RCSC decoding algorithm accelerates the computing of the returned soft messages when certain types of nodes are activated. The corresponding hardware architecture of our IS-RCSC decoder is also proposed. In terms of area efficiency, the hardware implementation results demonstrate that our IS-RCSC decoders are 19% to 43% better than decoders in the literature.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2016•5 citations

Efficient Soft Cancelation Decoder Architectures for Polar Codes

Jun Ting Lin, Zhiyuan Yan, Zhongfeng Wang

The flooding belief propagation (FO-BP) and the soft-cancelation (SCAN) algorithms are the two most popular soft-output BP algorithms for the decoding of capacity-achieving polar codes. The FO-BP algorithm has high throughput at the cost of performance degradation in high signal-to-noise ratio (SNR) region or with large block length. The SCAN algorithm has much better decoding performance while suffering from long decoding latency and low throughput. In this paper, an improved BP algorithm, named reduced complexity soft-cancelation (RCSC) algorithm, is proposed. Compared with the SCAN algorithm, the number of memory entries required by the RCSC algorithm is reduced by more than 50% in general, while achieving comparable or even better (e.g., when block size N = 215) decoding performance. When block size is large (e.g., N ≥ 215), the proposed RCSC algorithm reduces the required memory entries by more than 23% compared with the state-of-the-art FO-BP algorithm. The numerical results show that the error performance improvement of the RCSC algorithm is more significant when the SNR increases. For a different tradeoff, a reduced latency soft-cancelation (RLSC) algorithm is proposed to reduce the decoding latency and increase the throughput of the RCSC algorithm while slightly sacrificing decoding performance. Finally, the optimized VLSI architectures are presented for the RCSC and RLSC algorithms, respectively. The synthesis results demonstrate the efficiency of the proposed algorithms and architectures.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems•Jul 12, 2016•12 citations

Improved Soft Cancellation Decoding of Polar Codes

Mingyue You, Zhifeng Ma

The soft cancellation decoding of polar codes achieves a better performance than the belief propagation decoding with lower computational time and space complexities. However, because the soft cancellation decoding is based on the successive cancellation decoding, the decoding efficiency and performance with finite-length blocks can be further improved. Exploiting the idea of the successive cancellation list decoding, the soft cancellation decoding can be improved in two aspects: one is by adding branch decoding to the error-prone information bits to increase the accuracy of the soft information, and the other is through using partial iterative decoding to reduce the time and computational complexities. Compared with the original method, the improved soft cancellation decoding makes progress in the error correction performance, increasing the decoding efficiency and reducing the computational complexity, at the cost of a small increase of space complexity.

Journal of Beijing Institute of Technology•Sep 30, 2020•0 citations

Computational Complexity Reduced Belief Propagation Algorithm for Polar Code Decoders

Arvid B. van den Brink, Marco J.G. Bekooij

The belief propagation algorithm is desirable for a polar code based decoder, because of the potentially low latency and the ability of integration in digital signal processing units or other multi-core processor systems to parallelize the computations. Although belief propagation polar code decoder algorithms have the ability for a highly parallelized imple-mentation, the algorithms require many iterations to achieve a comparable frame error rate and bit error rate with respect to a successive cancellation polar code algorithm. The iterative nature of the belief propagation algorithms also result in a higher computational complexity, i.e. O(IN(2log_{2} N-1)) compared to the computational complexity O(Nlog_{2}N) of the successive cancellation decoder algorithm. In this paper we propose several simplifications for a simplified belief propagation algorithm for polar code decoders, where the arithmetic complexity of the nodes is reduced. The proposed belief propagation algorithm shows preliminary results of a net reduction of the arithmetic complexity of ≈ 13%. This reduction is a result of the reduced number of arithmetic operations, i.e., additions, compares, and multiplications, without a lost in error-correcting performance.

•Feb 3, 2021•0 citations

Simplified Early Stopping Criterion for Polar Codes

Jianming Cui, Jun Li, Yanfei Dong +2 more

Belief propagation (BP) algorithm of polar codes suffers from very high computational complexity when the iteration number becomes larger. In this paper, an early stopping criterion is proposed to avoid unnecessary iterations efficiently. The proposed only needs to detect whether the proportion of unchanged soft-output messages in a detection space exceeds a threshold. The proposed iteration can achieve a desired trade-off between complexity and decoding performance. Simulation results have shown that when the maximum iteration number is 40, the flooding BP (FO-BP) decoder with the proposed criterion can reduce 82.17% of iterations at 3.5dB compared with the FO-BP decoder without early stopping criterion. The proposed criterion costs Nl32 additions and Nl32 comparisons, where N indicates the code length, which effectively reduces the computational complexity.

IEEE International Conference on Signal Processing, Communications and Computing (ICSPCC)•Sep 1, 2018•4 citations
The state-of-the-art soft-output decoder for polar codes is a message-passing algorithm based on belief propagation, which performs well at the cost of high processing and storage requirements. In this paper, we propose a low-complexity alternative for soft-output decoding of polar codes that offers better performance but with significantly reduced processing and storage requirements. In particular we show that the complexity of the proposed decoder is only 4% of the total complexity of the belief propagation decoder for a rate one-half polar code of dimension 4096 in the dicode channel, while achieving comparable error-rate performance. Furthermore, we show that the proposed decoder requires about 39% of the memory required by the belief propagation decoder for a block length of 32768.
A widely used soft-output decoder for polar codes is a message-passing algorithm based on belief propagation, which performs well at the cost of high processing and storage requirements. In this paper we propose a low-complexity alternative for soft-output decoding of polar codes that offers comparable performance but with significantly reduced processing and storage requirements. In particular we show that the complexity of the proposed decoder is about 5% of the total complexity of the belief propagation decoder for the dicode channel, while achieving comparable error-rate performance. Furthermore, we show that the proposed decoder requires about 39% of the memory required by the belief propagation decoder for a block length of 32768.
The belief propagation (BP) decoding algorithm not only is an alternative to the successive cancelation (SC) decoders of polar codes, but also provides soft outputs that are necessary for joint detection and decoding. The BP decoders with the flooding schedule achieve high throughput with excessive hardware cost especially when the block length is large. The soft-cancelation (SCAN) decoders for polar codes have reduced memory complexity compared to the BP decoders based on the flooding schedule. The simplified SC aided reduced complexity soft-cancelation (S-RCSC) decoders further reduce the computational and memory complexity of the SCAN decoders at the cost of negligible error performance degradation. Both the SCAN and S-RCSC decoders have limited throughput due to their serial decoding schedules. In this paper, we first propose an improved S-RCSC (IS-RCSC) decoding algorithm and then present a high throughput decoder architecture based on our IS-RCSC algorithm. Our IS-RCSC decoding algorithm performs the message passing on a binary tree representation of a polar code. Compared to the S-RCSC decoding algorithm, our IS-RCSC decoding algorithm accelerates the computing of the returned soft messages when certain types of nodes are activated. The corresponding hardware architecture of our IS-RCSC decoder is also proposed. In terms of area efficiency, the hardware implementation results demonstrate that our IS-RCSC decoders are 19% to 43% better than decoders in the literature.
The flooding belief propagation (FO-BP) and the soft-cancelation (SCAN) algorithms are the two most popular soft-output BP algorithms for the decoding of capacity-achieving polar codes. The FO-BP algorithm has high throughput at the cost of performance degradation in high signal-to-noise ratio (SNR) region or with large block length. The SCAN algorithm has much better decoding performance while suffering from long decoding latency and low throughput. In this paper, an improved BP algorithm, named reduced complexity soft-cancelation (RCSC) algorithm, is proposed. Compared with the SCAN algorithm, the number of memory entries required by the RCSC algorithm is reduced by more than 50% in general, while achieving comparable or even better (e.g., when block size N = 215) decoding performance. When block size is large (e.g., N ≥ 215), the proposed RCSC algorithm reduces the required memory entries by more than 23% compared with the state-of-the-art FO-BP algorithm. The numerical results show that the error performance improvement of the RCSC algorithm is more significant when the SNR increases. For a different tradeoff, a reduced latency soft-cancelation (RLSC) algorithm is proposed to reduce the decoding latency and increase the throughput of the RCSC algorithm while slightly sacrificing decoding performance. Finally, the optimized VLSI architectures are presented for the RCSC and RLSC algorithms, respectively. The synthesis results demonstrate the efficiency of the proposed algorithms and architectures.
The soft cancellation decoding of polar codes achieves a better performance than the belief propagation decoding with lower computational time and space complexities. However, because the soft cancellation decoding is based on the successive cancellation decoding, the decoding efficiency and performance with finite-length blocks can be further improved. Exploiting the idea of the successive cancellation list decoding, the soft cancellation decoding can be improved in two aspects: one is by adding branch decoding to the error-prone information bits to increase the accuracy of the soft information, and the other is through using partial iterative decoding to reduce the time and computational complexities. Compared with the original method, the improved soft cancellation decoding makes progress in the error correction performance, increasing the decoding efficiency and reducing the computational complexity, at the cost of a small increase of space complexity.
The belief propagation algorithm is desirable for a polar code based decoder, because of the potentially low latency and the ability of integration in digital signal processing units or other multi-core processor systems to parallelize the computations. Although belief propagation polar code decoder algorithms have the ability for a highly parallelized imple-mentation, the algorithms require many iterations to achieve a comparable frame error rate and bit error rate with respect to a successive cancellation polar code algorithm. The iterative nature of the belief propagation algorithms also result in a higher computational complexity, i.e. O(IN(2log_{2} N-1)) compared to the computational complexity O(Nlog_{2}N) of the successive cancellation decoder algorithm. In this paper we propose several simplifications for a simplified belief propagation algorithm for polar code decoders, where the arithmetic complexity of the nodes is reduced. The proposed belief propagation algorithm shows preliminary results of a net reduction of the arithmetic complexity of ≈ 13%. This reduction is a result of the reduced number of arithmetic operations, i.e., additions, compares, and multiplications, without a lost in error-correcting performance.
Belief propagation (BP) algorithm of polar codes suffers from very high computational complexity when the iteration number becomes larger. In this paper, an early stopping criterion is proposed to avoid unnecessary iterations efficiently. The proposed only needs to detect whether the proportion of unchanged soft-output messages in a detection space exceeds a threshold. The proposed iteration can achieve a desired trade-off between complexity and decoding performance. Simulation results have shown that when the maximum iteration number is 40, the flooding BP (FO-BP) decoder with the proposed criterion can reduce 82.17% of iterations at 3.5dB compared with the FO-BP decoder without early stopping criterion. The proposed criterion costs Nl32 additions and Nl32 comparisons, where N indicates the code length, which effectively reduces the computational complexity.