# An Enhanced Belief Propagation Flipping Decoder for Polar Codes with Stepping Strategy
## 1 Introduction  
Polar code is the first error-correcting code [1] which has achieved the Shannon limit. It has been adopted as the fifth generation (5G) wireless communications standard [2]. Not only does it have a strong error correction capability, but its encoding and decoding complexity is also affordable compared with the Low Density Parity Check (LDPC) [3] and Turbo codes [4]. The Successive Cancellation (SC) algorithm, which was proposed by [PERSON] [5], is one of the most common decoding methods for polar codes and has attracted widespread attention. The original SC algorithm has been optimized by the relevant scholars, producing optimizations such as the SC list (SCL) [6], SC flip (SCF) [7] and dynamic SC flipping (DSCF) [8] algorithms. The Cyclic redundancy check (CRC)-aided SC list (CA-SCL) [9] decoder was introduced to improve the BLER of polar codes and has become a baseline algorithm used in the standardization process. Compared with the SC and its other optimized algorithms, the Belief Propagation (BP) algorithm [10] with parallel decoding has great advantages in terms of its throughput and decoding latency. In addition, BP decoding is expected to support polar codes of 5G standard in practical applications with a set of hardware units. However, the BP decoder will not terminate until the maximum number, the termination scheme suffers from lack of flexibility, and introduces great computational complexity. Moreover, the BLER performance of BP is uncompetitive. To improve the original BP decoding performance, many methods to improve the BP-based algorithm have been proposed--for example, the BP list (BPL) [11] decoder. When using the standard polar code decoding factor graph (DFG), the original BP algorithm may generate incorrect decoding results because the transmission process of the messages ismodified. However, the BPL decoder uses the permuted version of the standard graph and can produce the correct estimation result. A permuted factor graph is introduced in [12; 13] based on the BPL decoder. The guessing algorithm [14] was first proposed in the LDPC codes and then introduced to the BP decoding, which guesses the oscillating bits by assigning the priority log-likelihood ratios (LLRs), the maximum LLR magnitude, and repeating the original BP decoding to achieve good decoding results. The BP Bit-Flip (BPF) [15] algorithm, which is different from other BP-based evolutionary algorithms, utilizes the information in the decoding process to make it more targeted to the codeword being decoded. BP flipping algorithms identify and then flip error-prone positions to improve decoding performance. For polar codes, bit-flipping strategies have been applied to both SC and BP decoding. However, the principles of flipping strategies on SC and BP decoding are different due to their different decoding schedules. The key to the BP flipping algorithm is to construct a flip set (FS), which consists of the error-prone bits. FS can accurately indicate the error bits, thus flipping the bits within FS can narrow the search space. Initially, the FS was constructed in SC [7], which proposed a progressive multi-bit-flipping algorithm. Under the Gaussian approximation (GA) construction, it was generated according to the Rate-1 nodes called the critical set (CS). The bits identified in the CS may exhibit a high possibility of error in the BP decoding. Thus, the CS is introduced to BP and the constructed CS with order \(T\) (CS-\(T\)) [15], where \(T\) denotes the size of the CS. By analyzing the behavior of the incorrect decoding results of the bit-flipping BP decoder with CS, a BP decoder with multiple bit-flipping sets (BFSs) and stopping criteria (BP-MF-MC) was proposed [16]. The CS is relatively static and the multiple BPSs have more complexity, so the Generalized BP Bit-flipping (GBPF) Decoder [17] with a redefinition of BP bit-flipping was proposed. The error-prone bits in the FS consist of the unfrozen bits with small LLR magnitudes from the outputs, which contribute to a better performance.