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.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, 20186 citations

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.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 ProcessingJan 1, 20233 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.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 SystemsOct 1, 201614 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.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 proceedingsMay 1, 20165 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.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, 20250 citations

Belief Propagation List Decoding of Polar Codes

Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer +1 more

We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size L. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are the lower decoding latency than the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size L. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are the lower decoding latency than the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.

arXiv:1806.10503IEEE Communications LettersJun 26, 2018161 citations

2.8\times

and

2.7\times

, respectively.