# An Enhanced Belief Propagation Flipping Decoder for Polar Codes with Stepping Strategy
## 3 The Proposed BPSF Algorithm
### Enhanced BPSF Algorithm  
The BPSF-\(\Omega\) algorithm can significantly decrease the average number of iterations, but some flipping bits that could correct the frame in FS are skipped when their LLR magnitude is small, which will cause performance degradation. In Figure 7a,c, the \"blue line\" denotes the LLR magnitude of \(\omega_{j}\) (\(1\leq j\leq M\)), which cannot correct the error frame after one BP decoding attempt. The \"Purple line\" denotes the LLR magnitude of \(\omega_{k}\) (\(j<k\leq M\)), which is the first bit after \(\omega_{k}\) that can correct the error frame. The LLR magnitude gap between \(\omega_{k}\) and \(\omega_{j}\), called \(\beta\), is shown in Figure 7b,d. It indicates that \(\omega_{k}\) can still be an unreliable bit even if it satisfies (15).  
Figure 6: The flipping sequence of original BPF and BPF with stepping strategy.  
Table 3 illustrates that the \(\beta\) value mostly concentrates on the range [1 2] and [0 2]. Using the \(\beta\), the stepping decision of (15) is modified to (17) to skip the unreliable bits more accurately. Then, the enhanced BPSF-\(\Omega\) algorithm (EBPSF-\(\Omega\)) and the enhanced GBPSF-\(\Omega\) algorithm (EGBPSF-\(\Omega\)) with the threshold \(\beta\) are developed, whose stepping decision is the same as (17). \(\beta\) can be determined by a Monte-Carlo simulation. We detail the EBPSF-2 algorithm in Algorithm 2, and the EBPSF-\(\Omega\) algorithm is also similar to it when \(\Omega>2\).  
\[\rho_{k}\;is\;skipped,\qquad\text{if}\;|L_{\omega_{p_{i}};0}^{(\omega_{p_{i}} )}|-\beta<|L_{\omega_{p_{k}};0}^{(\omega_{p_{i}})}|\;\;. \tag{17}\]  
Figure 7: The LLR magnitude and the gap \(\beta\) between the error bits and the correct bits at 2 dB. (**a**) The LLR magnitude for \(P\)(512, 256). (**b**) The gap \(\beta\) between the error bits and the correct bits for \(P\)(512, 256). (**c**) The LLR magnitude for \(P\)(1024, 512). (**d**) The gap \(\beta\) between the error bits and the correct bits for \(P\)(1024, 512).  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline \(N\) = 512 & **0–1** & **1–2** & **2–4** & **>4** \\ \hline The distribution of \(\beta\) & 26.9\% & 46.9\% & 19.7\% & 6.2\% \\ \hline \(N\) = 1024 & **0–2** & **2–4** & **4–6** & **>6** \\ \hline The distribution of \(\beta\) & 48.1\% & 31.9\% & 11.7\% & 8.3\% \\ \hline \hline \end{tabular}
\end{table}
Table 3: Statistics for the distribution of \(\beta\) when \(N=512\) and \(N=1024\).  
```
1:Input:\(y_{1}^{N}\), \(\omega_{\rho}\), \(\beta\), \(T\)
2:Output:\(\hat{n}_{1}^{N}\)
3:\(\{\hat{n}_{1}^{N}\}\leftarrow\mathrm{BP}\;(y_{1}^{N})\);
4:if CRC(\(\hat{n}_{1}^{N}\)) fail
5:while\(\rho_{1}<\mathrm{T}\)do
6: flip (\(\mathcal{L}_{n_{\rho_{1}}}^{(\omega_{\rho_{1}})}\)) based (16);
7:\(\{\hat{n}_{1}^{N}\}\leftarrow\mathrm{BP}\;(y_{1}^{N})\);
8:if CRC (\(\hat{n}_{1}^{N}\)) fail
9: update \(\rho_{1}\) according to (17);
10:else
11:break;
12:endif
13:endwhile
14:if CRC (\(\hat{u}_{1}^{N}\)) fail
15:\(\rho_{2}=\rho_{1}+1\);
16:while\(\rho_{1}<\mathrm{T}\)do
17:while\(\rho_{2}<\mathrm{T}\)do
18: flip (\(\mathcal{L}_{n}^{(\omega_{\rho_{1}})},\mathcal{L}_{n}^{(\omega_{\rho_{2}})}\)) based (16);
19:\(\{\hat{n}_{1}^{N}\}\leftarrow\mathrm{BP}\;(y_{1}^{N})\);
20:if CRC (\(\hat{u}_{1}^{N}\)) fail
21: update \(\rho_{1}\) according to (17);
22: update \(\rho_{2}\) according to (17);
23:else
24:break;
25:endif
26:endwhile
27:if CRC (\(\hat{u}_{1}^{N}\)) succeed
28:break;
29:endif
30:endif
31:endif
32:endif
33:return\(\hat{n}_{1}^{N}\)
```  
**Algorithm 2** EBPSF-2 decoding.