IEEE Communications Letters

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

Chengguan Chen, Xiaojun Zhang, Yimeng Liu, Weike Wang, Qingtian Zeng

Published Jan 27, 2022• 13 citations

Abstract

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.

DOI: 10.1109/lcomm.2022.3146876

Related papers

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

Siyu Zhang, Behnam Shahrrava

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.

IEEE Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON)Oct 1, 20196 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

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

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

An Enhanced Belief Propagation Decoder for Polar Codes

Meng Zhang, Zhuo Li, Lijuan Xing

Belief propagation (BP) has attracted increasing attention due to its high parallelism. In this letter, a correction method is proposed to improve the block error rate (BLER) performance of the BP decoder for polar codes so that it is comparable to that of the successive cancellation list (SCL) decoder. Compared with BP flipping (BPF) decoding, the proposed decoder focuses on prior knowledge of the code bits in the factor graph. Two strategies have been proposed to construct the correction set. The simulation results show that the BPC decoder exhibits a BLER similar to that of BPF decoder while reducing the average latency and complexity by half. In addition, the BLER of the BPC decoder can approach that of the cyclic redundancy check (CRC)-aided SCL (CA-SCL) decoder in regions with low and medium signal-to-noise ratios (SNRs).

IEEE Communications LettersAug 11, 202116 citations

Higher-Order Belief Propagation Correction Decoder for Polar Codes

Meng Zhang, Zhuo Li, Lijuan Xing +1 more

Belief propagation (BP) decoding for polar codes has been extensively studied because of its inherent parallelism. However, its performance remains inferior to that of successive cancellation list decoding (SCL) due to the structure of the decoding graph. To improve the block error rate (BLER) performance, the BP correction (BPC) decoding, a post-processing scheme that corrects prior knowledge of the identified code bit, improves convergence by executing additional iterations on the failed BP decoder. Moreover, the BPC decoder demonstrates a better decoding performance than the BP-based bit-flipping decoder. Nevertheless, the additional decoding attempts lead to increased latency. In this article, a modified BPC decoder is proposed to reduce the number of decoding attempts by redefining the correction rules. A new metric is designed to effectively identify the corrected location. Numerical results show that the proposed modified BPC decoder achieves a slight improvement in BLER compared with the original BPC, with a dramatic reduction in average complexity. Furthermore, a higher-order version, named MBPC-Ω, is extended to further improve the performance, where the Ω is the maximum correction order. Numerical results show that the higher-order modified BPC achieves a similar BLER performance to existing multiple bit-flipping BP decoders but has around half the latency overhead. In addition, the proposed MBPC-2 decoder performs better than the cyclic redundancy check-aided SCL (CA-SCL) decoder with list size 4 and is slightly worse than the CA-SCL with list size 8 in high signal-to-noise ratio (SNR) regions but with significant decoding latency reduction.

EntropyApr 11, 20222 citations