IEEE Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON)

Stopping Criterion for Belief Propagation Polar Code Decoders based on Bits Difference Ratio

Siyu Zhang, Behnam Shahrrava

Published Oct 1, 2019• 6 citations

Abstract

In this paper, a novel stopping criterion for Belief Propagation (BP) decoding of polar codes is proposed. The proposed stopping criterion is based on the Bit Difference Ratio (BDR). The BDR stopping method is implemented by monitoring the fluctuation of BDR along with the number of iterations, to decide if the BP decoding process can be terminated. Simulation results indicate that the proposed criterion can provide superiority in iteration reduction compared with the current stopping criteria. Hence, the proposed BDR stopping criterion can effectively reduce the energy waste and decoding latency in systems. Moreover, by loosing the constraint, the proposed stopping criterion can achieve more iteration reduction at the cost of Bit Error Rate (BER) degradation.

DOI: 10.1109/iemcon.2019.8936303

Related papers

An Ultra-Low Complexity Early Stopping Criterion for Belief Propagation Polar Code Decoder

Chengguan Chen, Xiaojun Zhang, Yimeng Liu +2 more

In order to reduce the decoding latency, a new early stopping criterion is proposed for belief propagation (BP) decoding. A kind of special processing elements (PEs) of BP decoder called frozen and information PE (FIPE) is selected to predict whether decoding is successful or not. Statistics indicate that FIPE can be considered reliable when the frozen bit is decoded successfully. The proposed criterion is based on the fact that the number of reliable FIPE increase along with iterations and the variation trend is approximate to the ratio of correct information bits. In the term of hardware complexity, the proposed method has a linear correlation with the number of FIPE. This criterion consumes only ‘xor’ and ‘or’ gates to check stopping condition. Simulation results show that the proposed criterion achieves lower latency than Worst Information Bits (WIB) and Frozen Bit Error Rate (FBER) without BLER degradation compared with fixed and G-matrix. Compared with WIB, FBER, Best Frozen Bits (BFB) criterion, the proposed criterion has the lowest hardware complexity.

IEEE Communications LettersJan 27, 202213 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, 20184 citations

Belief Propagation Bit-Flip Decoder for Polar Codes

Yongrun Yu, Zhiwen Pan, Nan Liu +1 more

The bit-flip method has been successfully applied to the successive cancellation (SC) decoder to improve the block error rate (BLER) performance for polar codes in the finite code length region. However, due to the sequential decoding, the SC decoder inherently suffers from longer decoding latency than that of the belief propagation (BP) decoder with efficient early stopping criterion. It is natural to ask how to perform bit-flip in a polar BP decoder. In this paper, bit-flip is introduced into the BP decoder for polar codes. The idea of critical set (CS), that is, originally proposed by Zhang et al. for identifying unreliable bits in a SC bit-flip decoder, is extended to the BP decoder here. After revealing the relationship between CS and the incorrect BP decoding results, critical set with order ω (CS-ω) is constructed to identify unreliable bit decisions in polar BP decoding. The simulation results demonstrate that compared with the conventional BP decoder, the BLER of the proposed bit-flip decoder can achieve significant signal-to-noise ratio (SNR) gain which is comparable to that of a cyclic redundancy check-aided SC list decoder with a moderate list size. In addition, the decoding latency of the proposed BP bit-flip decoder is only slightly higher than that of the conventional BP decoder in the medium and high SNR regions.

IEEE AccessJan 1, 201967 citations

Parity-check and G-matrix based intelligent early stopping criterion for belief propagation decoder for polar codes

Qasim Jan, Shahid Hussain, Zhiwen Pan +4 more

The error correction performance of Belief Propagation (BP) decoding for polar codes is satisfactory compared with the Successive Cancellation (SC) decoding. Nevertheless, it has to complete a fixed number of iterations, which results in high computational complexity. This necessitates an intelligent identification of successful BP decoding for early termination of the decoding process to avoid unnecessary iterations and minimize the computational complexity of BP decoding. This paper proposes a hybrid technique that combines the “parity-check” with the “G-matrix” to reduce the computational complexity of BP decoder for polar codes. The proposed hybrid technique takes advantage of the parity-check to intelligently identify the valid codeword at an early stage and terminate the BP decoding process, which minimizes the overhead of the G-matrix and reduces the computational complexity of BP decoding. We explore a detailed mechanism incorporating the parity bits as outer code and prove that the proposed hybrid technique minimizes the computational complexity while preserving the BP error correction performance. Moreover, mathematical formulation for the proposed hybrid technique that minimizes the computation cost of the G-matrix is elaborated. The performance of the proposed hybrid technique is validated by comparing it with the state-of-the-art early stopping criteria for BP decoding. Simulation results show that the proposed hybrid technique reduces the iterations by about 90% of BP decoding in a high Signal-to-Noise Ratio (SNR) (i.e., 3.5 ∼ 4 dB), and approaches the error correction performance of G-matrix and conventional BP decoder for polar codes.

Digital Communications and NetworksDec 15, 20221 citation

Improved Belief Propagation List Decoding for Polar Codes

Huan Li, Jingxuan Huang, Ce Sun

Polar codes have become the channel coding scheme for control channel of enhanced mobile broadband in the 5G communication systems. Belief propagation (BP) decoding of polar codes has advantages of low decoding latency and high parallelism but achieves worse bit error ratio (BER) performance compared with the successive cancellation list (SCL) decoding scheme. In this paper, an improved BP list (IBPL) decoding algorithm is proposed with comparable BER performance to SCL algoritm. Firstly, the optimal permuted factor graph is analyzed for polar codes, which improves the performance of the BP decoder without path extension. Furthermore, based on the optimal graph, the bit metric and decoding path metric are proposed to extend and prune the decoding path. The proposed IBPL decoder is focused on not only the permutation of polar codes but also the reliabilities of decoded codewords during each iteration of BP decoding, which has a more accurate decoding path list. The simulation results show that the proposed IBPL decoder improves the BER performance compared with the original BP decoder significantly, and can approach the performance of the SCL decoder at low signal to noise ratio regions.

ElectronicsAug 7, 20227 citations

Low Complexity Early Stopping Belief Propagation Decoder for Polar Codes

Chungsu Lee, Chansoo Park, Sungyeol Back +1 more

Belief propagation is one of low latency decoding algorithms for polar codes but it requires relatively high decoding complexity due to its inherent iterative decoding nature. To remedy the problem, early stopping belief propagation algorithm was proposed. Unfortunately, it requires additional complexity to test stopping criterion at each end of decoder iterations. In this paper, we propose a low complexity early stopping belief propagation decoder for polar codes which requires lower complexities not only for stopping criterion test but also for decoding by reducing the number of message updates within the decoder without any performance loss.

IEEE AccessJan 1, 20244 citations