Bit flipping was first used to improve the decoding performance of successive cancellation (SC) decoder. Since SC decoding process is serial, so the first bit that goes wrong in the decoding process will cause several subsequent bits to go wrong, which will suffer from higher decoding delay than belief propagation (BP) parallel decoding. In order to meet the performance of 5G low latency and high reliability, BP decoding algorithm have received a lot of attention. However, at medium and high signal-to-noise ratios (SNR), BP decoding does not perform as well as the SC list (SCL) decoding algorithm. Hence, BP decoding algorithm borrows bit-flip strategies from SC bit flip (SCF) decoder to improve the performance. The performance of BP bit flip (BPF) decoding depends on whether the construction of the flip set is correct, so this letter proposes a flip set construction approach based on the standard deviation of the log-likelihood ratio (LLR) and the reliability weight of polarized channels, which is comparable to the existing BPF decoding, the improved algorithm can identify the error-prone bits more efficiently and improve the decoding performance.
Bit flipping was first used to improve the decoding performance of successive cancellation (SC) decoder. Since SC decoding process is serial, so the first bit that goes wrong in the decoding process will cause several subsequent bits to go wrong, which will suffer from higher decoding delay than belief propagation (BP) parallel decoding. In order to meet the performance of 5G low latency and high reliability, BP decoding algorithm have received a lot of attention. However, at medium and high signal-to-noise ratios (SNR), BP decoding does not perform as well as the SC list (SCL) decoding algorithm. Hence, BP decoding algorithm borrows bit-flip strategies from SC bit flip (SCF) decoder to improve the performance. The performance of BP bit flip (BPF) decoding depends on whether the construction of the flip set is correct, so this letter proposes a flip set construction approach based on the standard deviation of the log-likelihood ratio (LLR) and the reliability weight of polarized channels, which is comparable to the existing BPF decoding, the improved algorithm can identify the error-prone bits more efficiently and improve the decoding performance.
Polar codes is the only coding scheme in the world that has been proved that the Shannon threshold is reachable. Because of the high time delay caused by the serial characteristic of Successive Cancellation (SC) decoding, the Belief Propagation (BP) decoding has received more attention because of its higher throughput. However, because its decoding performance is not as good as SC decoding, Bit-Flip (BF) decoding is used in BP. Aiming at the inaccurate construction of flip set in current bit flipping decoding, this paper proposes a new bit error rate BP BF (BPF) decoding algorithm, which is used to construct flip set. We also propose rough flip set and fine flip set Concept of flip set. The rough flip set is constructed by the variance of the characteristics of data stability. The range of the flip set is reduced by the difference in bit error rate, that is, the fine flip set. The research results show that the algorithm proposed in this paper is superior to the current best decoding algorithms such as BP, Enhanced BPF (EBPF) and Log Likelihood Ratio BPF (BPF-LLR). At the same time, the number of iterations of the algorithm is significantly reduced compared with other bit-flipping decoding algorithms.
Since the inherent serial nature of successive cancellation list (SCL) decoding results in a long latency, belief propagation (BP) decoding for polar codes has drawn attention for high-throughput applications. However, its error correction performance is inferior to that of SCL decoding. Therefore, the bit-flipping strategy has been recently applied to BP decoding, which can approach the SCL decoding performance through multiple additional decoding attempts. The original BP flip (BPF) decoding suffers from an inaccurate identification of erroneous bits by a fixed flip set (FS), which has been improved by the generalized BPF (GBPF) decoding. In this article, the GBPF decoding is extended to support multiple bits being flipped in one decoding attempt. In addition, for two types of decoding errors: detected errors and undetected errors, we propose two novel methods to more effectively identify erroneous bits. For detected errors, the concept of loop sets is defined and a loopbased identification method is introduced based on the study of error patterns of BP decoding. On the other hand, a method to generate a more accurate fixed FS is proposed for undetected errors, which considers the bit error distribution under BP decoding. Combining the two methods, the GBPF with merged sets (GBPF-MS) decoding can achieve the SCL-8 performance and outperforms the state-of-the-art BPF, BP list, and SC flip (SCF) decoding, for polar codes with length 1024 and information rate 1/2. Implemented by 40nm CMOS technology, the proposed GBPF-MS decoder with ten flips exhibits an average throughput of 4.19 Gbps at 2.5 dB, which is 1.6× and 1.72× faster than the state-of-the-art SCL-4 and SCF decoders, respectively.
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.
Due to the design principle of parallel processing, belief propagation (BP) decoding is attractive, and it provides good error-correction performance compared with successive cancellation (SC) decoding. However, its error-correction performance is still inferior to that of successive cancellation list (SCL) decoding. Consequently, this paper proposes a novel flip-list- (FL)-enabled belief propagation (BP) method to improve the error-correction performance of BP decoding for polar codes with low computational complexity. The proposed technique identifies the vulnerable channel log-likelihood ratio (LLR) that deteriorates the BP decoding result. The FL is utilized to efficiently identify the erroneous channel LLRs and correct them for the next BP decoding attempt. The preprocessed channel LLR through FL improves the error-correction performance with minimal flipping attempts and reduces the computational complexity. The proposed technique was compared with the state-of-the-art BP, i.e., BP bit-flip (BP-BF), generalized BP-flip (GBPF), cyclic redundancy check (CRC)-aided (CA-SCL) decoding, and ordered statistic decoding (OSD), algorithms. Simulation results showed that the FL-BP had an excellent block error rate (BLER) performance gain up to 0.7 dB compared with BP, BP-BF, and GBPF decoder. Besides, the computational complexity was reduced considerably in the high signal-to-noise ratio (SNR) regime compared with the BP-BF and GBPF decoding methods.
Recently, belief propagation list (BPL) decoding has been proposed to achieve the excellent parallel decoding performance of polar codes with high throughput and low latency. However, the performance gap between BPL decoding and state-of-the-art successive cancellation list (SCL) decoding is still significant at practical SNRs. In this letter, we propose an efficient BPL flip (EBPLF) decoding algorithm for filling this gap. Firstly, an efficient bit-flipping strategy under BPL decoding is proposed to allow multiple bits being flipped more efficiently than the existing bit-flipping strategy. Then, by exploiting the decoding diversity and reliability of each bit over the multiple factor graphs within BPL decoding, an enhanced flip set is constructed to identify the error-prone patterns in an efficient way. Extensive simulation results show that EBPLF decoding outperforms the existing BPLF scheme and approaches the performance of adaptive SCL decoding at practical SNRs with much lower average latency.
The belief propagation (BP) algorithm for polar codes has attracted significant attention due to its soft-output property and high parallelism. However, the BP algorithm is not comparable with the successive cancellation list (SCL) algorithm in terms of the error-correction performance. In this paper, we propose a high-stage BP flip (HSBPF) algorithm to further improve the error-correction performance of the BP algorithm by analyzing the distribution of log-likelihood ratio (LLR) values. Simulation results show that the decoding latency can be reduced by 30% with the proposed algorithm. Moreover, benefiting from the simplified message passing of the factor graph, the computational complexity of the proposed algorithm is also significantly reduced compared with the existing algorithms.