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 Transactions on Signal Processing

Dual-Bit-Wise Stochastic Decoding for Polar Codes

Suwen Song, Lu Liu, Zhongfeng Wang, Juyan Xu

Published Jan 1, 2023• 3 citations
Publisher

Abstract

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.

DOI
10.1109/tsp.2023.3247140

Related papers

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

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

Stochastic BP Polar Decoding and Architecture with Efficient Re-Randomization and Directive Register

Menghui Xu, Xiao Liang, Chuan Zhang +2 more

Recently, polar codes have gained their popularity because of its capacity achieving property. On the other hand, representing continuous values by unary bit streams, stochastic decoding shows its advantages in both hardware efficiency and error resilience. Therefore, this paper devotes itself in combining both together to offer a stochastic belief propagation (BP) polar decoder, which is suitable for applications requiring low complexity, high fault tolerance, but not sensitive to processing speed. In this paper, several approaches such as bit length increasing and efficient re-randomization are proposed and carefully analyzed to improve the decoding performance. Numerical results have shown that for N = 64 and N = 256, the proposed stochastic BP decoder can achieve comparable decoding performance as the deterministic one. Hardware architecture employing directive register is also proposed in detail for efficient implementation of the proposed stochastic decoder.

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Oct 1, 2016•14 citations

Randomly Penalized-Aided Belief Propagation Flipping Decoding of Polar Codes

WenFan Wang, Jie Shen, Guiping Li

Belief Propagation(BP) decoders of Polar Codes can run in parallel and have a remarkable throughput achievement at a cost of performance degradation, when compared with other decoding algorithms of polar codes. The existing improved algorithms still have a gap to be optimized in performance, complexity or latency. This paper proposes a modified BP flipping algorithm by introducing random penalty items into the reliability metrics of bits to correct un-converged errors under the type of noise with Gaussian distributions considered. Simulation results illustrate that the proposed penalizing method can exhibit significant performance gains over the original BP and other three existing BP flipping decoding algorithms with different blocks in the additive white Gaussian noise channel(AWGN) under a lower decoding latency. This shows the proposed scheme identifies the error-prone bits more efficiently.

•Mar 25, 2025•0 citations

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

Yuhuan Wang, Jianguo Li, Neng Ye +1 more

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.

Electronics•Dec 28, 2021•3 citations

High-Throughput Flexible Belief Propagation List Decoder for Polar Codes

Yuqing Ren, Yifei Shen, Leyu Zhang +4 more

Owing to its high parallelism, belief propagation (BP) decoding is highly amenable to high-throughput implementations and thus represents a promising solution for meeting the ultra-high peak data rate of future communication systems. However, for polar codes, the error-correcting performance of BP decoding is far inferior to that of the widely used CRC-aided successive cancellation list (SCL) decoding algorithm. To close the performance gap to SCL, BP list (BPL) decoding expands the exploration of candidate codewords through multiple permuted factor graphs (PFGs). From an implementation perspective, designing a unified and flexible hardware architecture for BPL decoding that supports various PFGs and code configurations presents a big challenge. In this paper, we propose the first hardware implementation of a BPL decoder for polar codes and overcome the implementation challenge by applying a hardware-friendly algorithm that generates flexible permutations on-the-fly. First, we derive the graph selection gain and provide a sequential generation (SG) algorithm to obtain a near-optimal PFG set. We further prove that any permutation can be decomposed into a combination of multiple fixed routings, and we design a low-complexity permutation network to satisfy the decoding schedule. Our BPL decoder not only has a low decoding latency by executing the decoding and permutation generation in parallel, but also supports an arbitrary list size without any area overhead. Experimental results show that, for length-1024 polar codes with a code rate of one-half, our BPL decoder with 32 PFGs has a similar error-correcting performance to SCL with a list size of 4 and achieves a throughput of 25.63 Gbps and an area efficiency of 29.46 Gbps/mm$^{2}$ at SNR=4.0dB, which is 1.82$\times$ and 4.33$\times$ faster than the state-of-the-art BP flip and SCL decoders,~respectively

arXiv:2210.13887•Oct 25, 2022•4 citations
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.
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.
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.
Recently, polar codes have gained their popularity because of its capacity achieving property. On the other hand, representing continuous values by unary bit streams, stochastic decoding shows its advantages in both hardware efficiency and error resilience. Therefore, this paper devotes itself in combining both together to offer a stochastic belief propagation (BP) polar decoder, which is suitable for applications requiring low complexity, high fault tolerance, but not sensitive to processing speed. In this paper, several approaches such as bit length increasing and efficient re-randomization are proposed and carefully analyzed to improve the decoding performance. Numerical results have shown that for N = 64 and N = 256, the proposed stochastic BP decoder can achieve comparable decoding performance as the deterministic one. Hardware architecture employing directive register is also proposed in detail for efficient implementation of the proposed stochastic decoder.
Belief Propagation(BP) decoders of Polar Codes can run in parallel and have a remarkable throughput achievement at a cost of performance degradation, when compared with other decoding algorithms of polar codes. The existing improved algorithms still have a gap to be optimized in performance, complexity or latency. This paper proposes a modified BP flipping algorithm by introducing random penalty items into the reliability metrics of bits to correct un-converged errors under the type of noise with Gaussian distributions considered. Simulation results illustrate that the proposed penalizing method can exhibit significant performance gains over the original BP and other three existing BP flipping decoding algorithms with different blocks in the additive white Gaussian noise channel(AWGN) under a lower decoding latency. This shows the proposed scheme identifies the error-prone bits more efficiently.
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.
Owing to its high parallelism, belief propagation (BP) decoding is highly amenable to high-throughput implementations and thus represents a promising solution for meeting the ultra-high peak data rate of future communication systems. However, for polar codes, the error-correcting performance of BP decoding is far inferior to that of the widely used CRC-aided successive cancellation list (SCL) decoding algorithm. To close the performance gap to SCL, BP list (BPL) decoding expands the exploration of candidate codewords through multiple permuted factor graphs (PFGs). From an implementation perspective, designing a unified and flexible hardware architecture for BPL decoding that supports various PFGs and code configurations presents a big challenge. In this paper, we propose the first hardware implementation of a BPL decoder for polar codes and overcome the implementation challenge by applying a hardware-friendly algorithm that generates flexible permutations on-the-fly. First, we derive the graph selection gain and provide a sequential generation (SG) algorithm to obtain a near-optimal PFG set. We further prove that any permutation can be decomposed into a combination of multiple fixed routings, and we design a low-complexity permutation network to satisfy the decoding schedule. Our BPL decoder not only has a low decoding latency by executing the decoding and permutation generation in parallel, but also supports an arbitrary list size without any area overhead. Experimental results show that, for length-1024 polar codes with a code rate of one-half, our BPL decoder with 32 PFGs has a similar error-correcting performance to SCL with a list size of 4 and achieves a throughput of 25.63 Gbps and an area efficiency of 29.46 Gbps/mm2^{2}2 at SNR=4.0dB, which is 1.82×\times× and 4.33×\times× faster than the state-of-the-art BP flip and SCL decoders,~respectively