# An Enhanced Belief Propagation Flipping Decoder for Polar Codes with Stepping Strategy
## 2 Preliminary
### BP Flipping Decoding Algorithm  
The bit-flipping strategy is a feasible method with which to improve the performance of BP-based algorithms. Due to the parallelism of BP decoding, there may be more than one bit that could correct the error frame by flipping it. Not only can the real error bits correct the error frames, but there are still other bits that can correct the error frames in the process of the iterative computation of the DFG [18]. However, there exist more bits that provide no assistance in error frame correction, and the invalid flipping of these will cause much latency. Therefore, the study of the strategy used for locating the flipping bits which can effectively correct the error frames is essential. Initially, the CS is used to identify unreliable bits in the SC flipping decoder, which is composed of the first bit index of each Rate-1 node [15]. As shown in Figure 3, blue nodes are referred to as Rate-1 nodes because all the leaf nodes are information bits, white node means that all its leaf nodes are frozen bits and grey node denotes that its leaf nodes include both information and frozen bits. In Figure 3, CS = [8,10,11,13] is shown as striped blue nodes. It can be noticed that the size and elements of CS are fixed for a certain polar code, which means that CS is static in decoding. Because of this characteristic, no latency will be caused by FS construction. The BPF algorithm [15] employs CS in bit-flipping and the flipping operation is as follows  
\[R_{i,0}=\left\{ \begin{array}{ll}+\infty,&\quad i\in CS\text{ and }\hat{u}_{i}=0,\\ -\infty,&\quad i\in CS\text{ and }\hat{u}_{i}=1.\end{array} \right. \tag{11}\]  
For the GBPF decoding [17,18] algorithm, the FS is constructed dynamically with the smallest LLR magnitude. A sorting network is required to select information bits to constitute the FS, \(\mathbf{F}_{1}^{\Gamma}\)=\(\{F_{1},F_{2},\ldots,F_{\Gamma}\}\), where \(\Gamma\) denotes the length of the FS. Before the next-round of BP decoding attempts, the FS is generated by the smallest LLR magnitude and the bit-flipping operation is performed with the FS. The rule used to generate the FS is defined by  
\[FS\gets j\in\mathcal{A}\text{ and smallest }|\mathcal{L}_{n}^{(j)}|. \tag{12}\]  
Figure 2: Fundamental PE. Specifically, the GBPF flipping operation can be written as  
\[R_{0,i}=\left\{ \begin{array}{ll}+\infty,&\quad i\in FS\text{ and }\hat{u}_{i}=1,\\ -\infty,&\quad i\in FS\text{ and }\hat{u}_{i}=0,\\ 0,&\quad i\in\mathcal{A}/FS.\end{array} \right. \tag{13}\]  
The oracle-assisted BP (OA-BP) decoder [18] knows which bit estimates make the frame mistakes after the original BP decoding and then re-decodes the incorrect frame by flipping the erroneous bit in turn into the correct value. The incorrect codeword set can be expressed as \(\mathbf{A}_{1}^{\intercal}=\{A_{1},A_{2},\ldots,A_{\tau}\}\), where \(\tau\) is the count of erroneous bits. The differences between BPF algorithms are how to choose the flipping set. The BPF algorithm generates CS before decoding with Rate-1 nodes and stays static in decoding. The GBPF algorithm generates FS dynamically in decoding, which will lead to extra costs of sorting the LLR magnitude in generating FS. However, the GBPF algorithm also provides greater possibility of error-correction by setting larger sizes of FS. The generalized procedure for BPF-1 algorithm [15] and GBPF-1 algorithm [17] can be summarized as Algorithm 1. ```
1:Input:\(y_{1}^{N}\), \(\Gamma\), \(\rho_{1}\)
2:Output:\(\hat{u}_{11}^{N}\)
3:\(\{\hat{u}_{1}^{N}\}\leftarrow\) BP (\(y_{1}^{N}\));
4:if CRC(\(\hat{u}_{1}^{N}\)) fail
5:for\(\rho_{1}\gets 1\) to \(\Gamma\)do
6:\(\{\hat{u}_{1}^{N}\}\leftarrow\) BP (\(y_{1}^{N}\),\(\rho_{1}\));
7:if CRC (\(\hat{u}_{1}^{N}\)) succeed
8:break;
9:endif
10:endfor
11:endif
12:return\(\hat{u}_{1}^{N}\)
```  
**Algorithm 1** BP flipping algorithm. The bits needing to be flipped by the BP flipping algorithms are listed in Table 1. The BPF algorithm has a significantly higher number of flipping bits than the GBPF algorithm.