# An Enhanced Belief Propagation Flipping Decoder for Polar Codes with Stepping Strategy
## 3 The Proposed BPSF Algorithm
### Proposed BPSF Algorithm  
A flipping set of FS-\(T\) can be expressed as \(\varepsilon_{T}=\){\(\omega_{1},\cdots,\omega_{T}\)} and \(\omega_{q}\) (\(1\leq q\leq T\)) indicates the \(q\)-th flipping position. \(\hat{u}[\omega_{q}]_{j}\) denotes the hard decision estimate of the bit \(u_{j}\) after flipping the \(\omega_{q}\)-th bit. Let \(P(\omega_{q})\) be the probability of \(\omega_{q}\) correcting the trajectory of BP decoding, where  
\[P\big{(}\omega_{q}\big{)}=\Pr\big{(}\hat{u}[\omega_{q}]_{1}^{N}=u_{1}^{N}| \textbf{y}\big{)} \tag{14}\]  
Experiments show that only a few bits in the FS-\(T\) can correct the error frames, and flipping the rest will not facilitate successful decoding. Thus, this paper proposes a stepping  
\begin{table}
\begin{tabular}{c c c c} \hline \(\boldsymbol{M}\) & \(\boldsymbol{M\leq 9}\) & \(\boldsymbol{10\leq M\leq 19}\) & \(\boldsymbol{20\leq M\leq 39}\) \\ \hline BPF-1 & 87.9\% & 11.7\% & 0.4\% \\ GBPF-1 & 79.3\% & 17.6\% & 3.1\% \\ \hline \(\boldsymbol{M}\) & \(\boldsymbol{M\leq 99}\) & \(\boldsymbol{100\leq M\leq 399}\) & \(\boldsymbol{400\leq M\leq 780}\) \\ \hline BPF-2 & 79.1\% & 17.7\% & 3.2\% \\ GBPF-2 & 78.3\% & 18.1\% & 3.6\% \\ \hline \end{tabular}
\end{table}
Table 2: Statistics for the number of successful BP-flipping decoding attempts in 10,000 error frames at \(N=256\), \(E_{b}/N_{0}=2\) dB.  
Figure 5: The number of successful BP flipping decoding attempts by the BPF-1 [15] ([PERSON]; [PERSON]; [PERSON]; [PERSON] 2019), GBPF-1 algorithms [17] ([PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] 2020) at 2 dB. (**a**) The number of successful BP flipping decoding attempts with \(N=256\). (**b**) The number of successful BP flipping decoding attempts with \(N=1024\).  
scheme to step the flipping bits with low \(P(\omega_{q})\). Let \(L_{j,0}^{(\omega_{q})}\) denote the LLR of the bit \(u_{j}\) after flipping the \(\omega_{q}\)-th bit. The LLR magnitude can be intuitively used as a metric of the reliability [21]. If the \(L_{\omega_{q},0}^{(\omega_{q})}\) magnitude is smaller, the bit is considered as an unreliable bit and then the \(P(\omega_{q})\) of the bit is deemed to be higher. Thus, if the \(L_{\omega_{q},0}^{(\omega_{q})}\) magnitude is smaller than the \(L_{\omega_{q}+1,0}^{(\omega_{q})}\) magnitude, \(P(\omega_{q})\) is deemed to be higher than \(P(\omega_{q+1})\) and there is no need to perform a useless flipping for the reliable \(\omega_{q+1}\) bit. Let \(\rho\)={\(\rho_{1}\),\(\rho_{2}\),\(\cdots\),\(\rho_{T}\)} denote the index of FS. We assume one decoding trial of flipping \(\omega_{\rho_{i}}\) has failed. Additionally, we obtain the new LLR of \(L_{\omega_{\rho_{i}},0}^{(\omega_{\rho_{i}})}\) and \(L_{\omega_{\rho_{i}},0}^{(\omega_{\rho_{i}})}\), \(i<k\leq T\). The stepping decision is as (15). Using the stepping decision, the flipping sequence of the original BPF is modified, as shown in Figure 6.  
\[\rho_{k}\text{ is skipped, }\qquad\text{if }|L_{\omega_{\rho_{i}},0}^{(\omega_{ \rho_{i}})}|<|L_{\omega_{\rho_{i}},0}^{(\omega_{\rho_{i}})}|\enspace. \tag{15}\]  
The original flipping strategy used in BPF [15] is to flip bits within CS-\(T\) in turn. We propose the use of the stepping decision in the BPSF algorithm to decide which bit can be skipped. The flipping operation in the proposed algorithm is as (16), which flips the left message \(L_{j,n+1}\) of the rightmost nodes.  
\[L_{j,n+1}=\left\{\begin{array}{ll}-\infty,&\text{if }\mathcal{L}_{n}^{(j)} \geq 0,\\ +\infty,&\text{if }\mathcal{L}_{n}^{(j)}<0.\end{array}\right. \tag{16}\]  
Similarly, inspired by the GBPF-\(\Omega\) algorithm [17; 18], we design a generalized bit step-flipping (GBPSF-\(\Omega\)) algorithm. There are two differences between the GBPF-\(\Omega\) and GBPSF-\(\Omega\). Firstly, GBPSF-\(\Omega\) flips the left message of the rightmost nodes according to (16). Secondly, the stepping decision is used to step over bits, as shown in Figure 6, after the construction of FS.