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

Electronics

Novel Low Complexity BP Decoding Algorithms for Polar Codes: Simplifying on Non-Linear Operations

Yuhuan Wang, Jianguo Li, Neng Ye, Xiangyuan Bu

Published Dec 28, 2021• 3 citations
Publisher

Abstract

The parallel nature of the belief propagation (BP) decoding algorithm for polar codes opens up a real possibility of high throughput and low decoding latency during hardware implementation. To address the problem that the BP decoding algorithm introduces high-complexity non-linear operations in the iterative messages update process, this paper proposes to simplify these operations and develops two novel low complexity BP decoding algorithms, namely, exponential BP (Exp-BP) decoding algorithm and quantization function BP (QF-BP) decoding algorithm. The proposed algorithms simplify the compound hyperbolic tangent function by using probability distribution fitting techniques. Specifically, the Exp-BP algorithm simplifies two types of non-linear operations into single non-linear operation using the piece-wise exponential model function, which can approximate the hyperbolic tangent function in the updating formula. The QF-BP algorithm eliminates non-linear operations using the non-uniform quantization in the updating formula, which is effective in reducing computational complexity. According to the simulation results, the proposed algorithms can reduce the computational complexity up to 50% in each iteration with a loss of less than 0.1 dB compared with the BP decoding algorithm, which can facilitate the hardware implementation.

DOI
10.3390/electronics11010093

Related papers

Dual-Bit-Wise Stochastic Decoding for Polar Codes

Suwen Song, Lu Liu, Zhongfeng Wang +1 more

Polar codes, being the first class of codes with provable capacity-achieving property, have aroused extensive attention. The belief propagation (BP) algorithm, which is one of the popular decoding approaches for polar codes, possesses inherent high parallelism but also high computational complexity. With low complexity and high fault tolerance, stochastic computing has been well studied and applied to BP decoding for polar codes. However, existing stochastic BP decoders suffer from high decoding latency. In this paper, firstly, a novel dual-bit-wise iterative message update method is proposed for stochastic BP, reducing the decoding latency by more than half. Based on the dual-bit-wise decoding, more special nodes in the factor graph are investigated and then fully exploited to pursue lower decoding complexity than prior arts. Moreover, a well-optimized architecture is developed for the proposed stochastic decoder, where the random number generator (RNG), tracking forecast memory (TFM), and hard decision unit are intelligently designed for reduced hardware cost. Experimental results demonstrate that the presented decoder can exhibit 61.7% lower decoding latency than the state-of-the-art works. Besides, the throughput and hardware efficiency can be improved by nearly$2.8\times$and$2.7\times$, respectively.

IEEE Transactions on Signal Processing•Jan 1, 2023•3 citations

Software Implementation and Performance of a Computational Complexity Reduced Belief Propagation Polar Code Decoder

Arvid B. van den Brink, Oğuz Meteer, Marco J.G. Bekooij

The belief propagation algorithm is one of the preferred algorithms for a polar code based decoder that can potentially achieve the lowest latency. Although belief propagation polar code algorithms have the ability for a highly parallelized implementation, they require more iterations to achieve a comparable frame error rate and bit error rate compared to the successive cancellation polar code algorithm. The iterative nature of the belief propagation algorithms also results in a higher computational complexity, i.e. O(N(2log2N-1)) compared to the computational complexity O(Nlog2N) of the successive cancellation decoder algorithm. In this paper we propose several software implementations of belief propagation polar code decoders using the computational complexity reduced belief propagation algorithm and the enhanced loop-weakened belief propagation algorithm, to increase the number of decoded codes per second. Compared to a baseline belief propagation implementation, our proposed radix-2 and radix-4 implementations increase the throughput by approximately 15.4% and 22.04% respectively. This gain is the result of a reduction of arithmetic operations, i.e., additions, compares, and multiplications, which is obtained without a loss in error-correcting performance.

International Conference on Electrical, Computer, Communications and Mechatronics Engineering (ICECCME)•Jul 19, 2023•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

Bit-Wise Iterative Decoding of Polar Codes using Stochastic Computing

Kaining Han, Junchao Wang, Warren J. Gross

Polar codes have received recent attention due to their potential to be applied in advanced wireless communication protocols such as the fifth generation mobile communication system (5G). Among the existing decoding algorithms, Belief Propagation (BP) exhibits high-throughput, low-latency and soft output with a high hardware cost. A form of approximate computing called stochastic computing provides a low-cost implementation solution for the BP algorithm. However, existing stochastic BP decoders suffer from a relatively long decoding latency resulting in low hardware efficiency. In this paper, a novel bit-wise iterative stochastic decoding architecture for the BP algorithm is proposed to improve the throughput and hardware efficiency. Multiple methods at the algorithm and architecture levels are presented to further speed up convergence and hardware efficiency.

ACM Great Lakes Symposium on VLSI (GLSVLSI)•May 30, 2018•6 citations

A Non-uniform Quantization-based Hardware Architecture for BP Decoding of Polar Codes

Xinyi Gu, Mohammad Rowshan, Yixuan Xie +1 more

Belief propagation (BP) decoding of polar codes benefits from the high parallelism in hardware implementation and consequently provides high throughput compared to successive cancellation-based decoding algorithms. As the evolved log-likelihood ratios (LLRs) in the decoding process have a wide dynamic range, the quantization error can degrade the error correction performance of the BP decoder. To reduce the quantization error in a uniform quantization scheme, we may need to use more bits for each LLR value which is not desirable due to the required memory space. In this paper, we design an efficient hardware architecture for non-uniformly quantized LLR messages in BP decoding where the arithmetic operations on logarithmically compressed messages are replaced with the mapping to precomputed results in lookup tables. By employing 5-bit non-uniform quantization, the designed BP decoder architecture reduces the required memory space by 37.5 percent compared to 8-bit uniform quantization while additionally improving the block error rate (BLER) by more than 0.1 dB in high SNR regimes. Compared to uniform quantization, the BLER improvement of the designed architecture is up to 0.4 dB when both quantization schemes use 5 bits for LLRs.

International Symposium on Communications and Information Technologies•Oct 16, 2023•3 citations

Stochastic Bit-Wise Iterative Decoding of Polar Codes

Kaining Han, Junchao Wang, Warren J. Gross +1 more

Polar codes have received recent attention due to their potential to be applied in advanced wireless communication protocols such as the fifth generation mobile communication system (5G). Among the existing decoding algorithms, Belief Propagation (BP) exhibits high-throughput, low-latency, and soft output with a high hardware cost. Stochastic computing, as a form of approximate computing, provides a potential low-cost implementation solution for the BP algorithm. However, existing stochastic BP decoders suffer from a relatively long decoding latency resulting in low hardware efficiency. In this paper, a novel bit-wise iterative stochastic decoding architecture for the BP algorithm is proposed to improve the throughput and hardware efficiency. By utilizing the frozen bits of polar codes and stochastic computing, multiple novel optimization methods are presented to further speed up convergence and increase the hardware efficiency.

IEEE Transactions on Signal Processing•Jan 15, 2019•31 citations
The parallel nature of the belief propagation (BP) decoding algorithm for polar codes opens up a real possibility of high throughput and low decoding latency during hardware implementation. To address the problem that the BP decoding algorithm introduces high-complexity non-linear operations in the iterative messages update process, this paper proposes to simplify these operations and develops two novel low complexity BP decoding algorithms, namely, exponential BP (Exp-BP) decoding algorithm and quantization function BP (QF-BP) decoding algorithm. The proposed algorithms simplify the compound hyperbolic tangent function by using probability distribution fitting techniques. Specifically, the Exp-BP algorithm simplifies two types of non-linear operations into single non-linear operation using the piece-wise exponential model function, which can approximate the hyperbolic tangent function in the updating formula. The QF-BP algorithm eliminates non-linear operations using the non-uniform quantization in the updating formula, which is effective in reducing computational complexity. According to the simulation results, the proposed algorithms can reduce the computational complexity up to 50% in each iteration with a loss of less than 0.1 dB compared with the BP decoding algorithm, which can facilitate the hardware implementation.
Polar codes, being the first class of codes with provable capacity-achieving property, have aroused extensive attention. The belief propagation (BP) algorithm, which is one of the popular decoding approaches for polar codes, possesses inherent high parallelism but also high computational complexity. With low complexity and high fault tolerance, stochastic computing has been well studied and applied to BP decoding for polar codes. However, existing stochastic BP decoders suffer from high decoding latency. In this paper, firstly, a novel dual-bit-wise iterative message update method is proposed for stochastic BP, reducing the decoding latency by more than half. Based on the dual-bit-wise decoding, more special nodes in the factor graph are investigated and then fully exploited to pursue lower decoding complexity than prior arts. Moreover, a well-optimized architecture is developed for the proposed stochastic decoder, where the random number generator (RNG), tracking forecast memory (TFM), and hard decision unit are intelligently designed for reduced hardware cost. Experimental results demonstrate that the presented decoder can exhibit 61.7% lower decoding latency than the state-of-the-art works. Besides, the throughput and hardware efficiency can be improved by nearly2.8×2.8\times2.8×and2.7×2.7\times2.7×, respectively.
The belief propagation algorithm is one of the preferred algorithms for a polar code based decoder that can potentially achieve the lowest latency. Although belief propagation polar code algorithms have the ability for a highly parallelized implementation, they require more iterations to achieve a comparable frame error rate and bit error rate compared to the successive cancellation polar code algorithm. The iterative nature of the belief propagation algorithms also results in a higher computational complexity, i.e. O(N(2log2N-1)) compared to the computational complexity O(Nlog2N) of the successive cancellation decoder algorithm. In this paper we propose several software implementations of belief propagation polar code decoders using the computational complexity reduced belief propagation algorithm and the enhanced loop-weakened belief propagation algorithm, to increase the number of decoded codes per second. Compared to a baseline belief propagation implementation, our proposed radix-2 and radix-4 implementations increase the throughput by approximately 15.4% and 22.04% respectively. This gain is the result of a reduction of arithmetic operations, i.e., additions, compares, and multiplications, which is obtained without a loss in error-correcting performance.
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.
Polar codes have received recent attention due to their potential to be applied in advanced wireless communication protocols such as the fifth generation mobile communication system (5G). Among the existing decoding algorithms, Belief Propagation (BP) exhibits high-throughput, low-latency and soft output with a high hardware cost. A form of approximate computing called stochastic computing provides a low-cost implementation solution for the BP algorithm. However, existing stochastic BP decoders suffer from a relatively long decoding latency resulting in low hardware efficiency. In this paper, a novel bit-wise iterative stochastic decoding architecture for the BP algorithm is proposed to improve the throughput and hardware efficiency. Multiple methods at the algorithm and architecture levels are presented to further speed up convergence and hardware efficiency.
Belief propagation (BP) decoding of polar codes benefits from the high parallelism in hardware implementation and consequently provides high throughput compared to successive cancellation-based decoding algorithms. As the evolved log-likelihood ratios (LLRs) in the decoding process have a wide dynamic range, the quantization error can degrade the error correction performance of the BP decoder. To reduce the quantization error in a uniform quantization scheme, we may need to use more bits for each LLR value which is not desirable due to the required memory space. In this paper, we design an efficient hardware architecture for non-uniformly quantized LLR messages in BP decoding where the arithmetic operations on logarithmically compressed messages are replaced with the mapping to precomputed results in lookup tables. By employing 5-bit non-uniform quantization, the designed BP decoder architecture reduces the required memory space by 37.5 percent compared to 8-bit uniform quantization while additionally improving the block error rate (BLER) by more than 0.1 dB in high SNR regimes. Compared to uniform quantization, the BLER improvement of the designed architecture is up to 0.4 dB when both quantization schemes use 5 bits for LLRs.
Polar codes have received recent attention due to their potential to be applied in advanced wireless communication protocols such as the fifth generation mobile communication system (5G). Among the existing decoding algorithms, Belief Propagation (BP) exhibits high-throughput, low-latency, and soft output with a high hardware cost. Stochastic computing, as a form of approximate computing, provides a potential low-cost implementation solution for the BP algorithm. However, existing stochastic BP decoders suffer from a relatively long decoding latency resulting in low hardware efficiency. In this paper, a novel bit-wise iterative stochastic decoding architecture for the BP algorithm is proposed to improve the throughput and hardware efficiency. By utilizing the frozen bits of polar codes and stochastic computing, multiple novel optimization methods are presented to further speed up convergence and increase the hardware efficiency.