# Higher-Order Belief Propagation Correction Decoder for Polar Codes
## 3 Design of Higher-Order Belief Propagation Correction Decoder
### The Modified BPC Decoder  
In the BPC decoder, the correction operation assigns \(\pm\infty\) to the selected code bits separately and performs decoding attempts, bringing numerous latencies overhead. Since the code bits contain prior information, the correction operation is reconsidered by the parameter \(\mathcal{V}\), a threshold for the magnitude of \(\mathcal{L}(j)\), which is set to identify the current state of \(x_{j}\). When \(|\mathcal{L}(j)|\geq\mathcal{V}\), the code bit is considered reliable so that both positive and negative assignments were executed. Otherwise, the node is corrected with its opposite side based on the sign of \(\mathcal{L}(j)\).  
The modified BPC decoder based on the proposed metric and refined correction, abbreviated as MBPC, is detailed in Algorithm 2. The function \(\text{sign}(x)\) marks the sign of  
Figure 2: Normal realization of the encoding graph for \(N=8\). An example of the stopping tree rooted at \(u_{7}\) is shown in the black nodes.  
\(x\), \(\text{sign}(x)=\begin{cases}1&x\geq 0\\ -1&x<0\end{cases}\). As shown in Algorithm 2, the enhanced correction operation in lines 9-14 avoids unnecessary attempts to reduce the complexity and latency overhead. Additionally, in lines 10 and 14, a predefined finite value \(\tau\) is set, rather than \(\infty\), which can mitigate the impact caused by a false assignment. Here, the value of \(\tau\) is set to 8. Note that, in Algorithm 1, the store operation in line 6 and refresh operation in line 9 ensure that the correction is post-processed on the conventional BP and avoid error propagation caused by previous false attempts. Based on the empirical fact that it converges quickly if the input is valid in the BP decoder, we modify the refresh operation, where the \(\mathbf{L}\) and \(\mathbf{R}\) messages are reset to the initial state before each attempt, as shown in Algorithm 2 line 8, resulting in avoiding complexity and memory consumption. Moreover, the modified refresh operation enables the post-processing scheme to operate in \(T\) independent factor graphs in parallel.  
```
0:\(\text{LLR}(y_{1}^{N})\), \(I_{max}\), \(\mathcal{I}\), \(T\).
1: Initial \(\mathbf{L}\) and \(\mathbf{R}\) by Equations (3) and (4).
2:\(\hat{u}_{1}^{N}\leftarrow\text{conventional BP decoding with CRC termination and }I_{max}\).
3:if\(\text{CRC}(\hat{u}_{1}^{N})=\text{true}\)then
4:return\(\hat{u}_{1}^{N}\).
5:else
6: Construct the set \(\mathcal{S}=\{j_{1},j_{2},...,j_{T}\}\) based on \(M(j)\) in Equation (5).
7:for\(k=1\) to \(T\)do
8: Initial \(\mathbf{L}\) and \(\mathbf{R}\) by Equations (3) and (4).
9:if\(|\mathcal{L}(j_{k})|<\mathcal{V}\)then
10:\(L_{n+1,j_{k}}=-\text{sign}(L_{n+1,j_{k}})\times\tau\)
11:\(\hat{u}_{1}^{N}\leftarrow\text{conventional BP decoding with CRC termination.}\)
12:else
13:for\(a=0:1\)do
14:\(L_{n+1,j_{k}}=(1-2a)\times\tau\).
15:\(\hat{u}_{1}^{N}\leftarrow\text{conventional BP decoding with CRC termination.}\)
16:endfor
17:endif
18:if\(\text{CRC}(\hat{u}_{1}^{N})=\text{true}\)then
19:return\(\hat{u}_{1}^{N}\).
20:endif
21:endfor
22:endif
23:Output:\(\hat{u}_{1}^{N}\)
```  
**Algorithm 2** Modified BPC decoding algorithm.