# Higher-Order Belief Propagation Correction Decoder for Polar Codes
## 3 Design of Higher-Order Belief Propagation Correction Decoder
### Higher-Order Belief Propagation Correction Decoder  
In this section, we generalize the MBPC decoder to a higher-order version, called MBPC-\(\Omega\). When the conventional BP fails to pass the CRC, the decoder executes MBPC-\(\Omega\) in increasing order consecutively. Similar to the SCF-\(\Omega\) decoder defined in [26], the proposed MBPC-\(\Omega\) decoding is performed on nested correction sets, each of which contains \(T_{k}\) elements, denoted as \(\mathcal{S}_{k}\), \(1\leq k\leq\Omega\). Each element consists of \(k\) code bits. The nested rule is designed to construct the set. Concretely, the set \(\mathcal{S}_{k}\) is established based on the preorder set \(\mathcal{S}_{k-1}\) and its corresponding decoding results. In other words, each element in \(\mathcal{S}_{k}\) contains the element in \(\mathcal{S}_{k-1}\) and an additional code bit, which was selected based on the metric of the decoding result in the decoding attempt by \(\mathcal{S}_{k-1}\). Denoting the \(r\)-th element in \(S_{k-1}\) by \(S_{k-1,r}\), we redefine \(M(j)^{k,r}\) as the metric of each code bit in the decoding result of a decoding attempt with \(S_{k-1,r}\). \[M(j)^{k,r}=\alpha\cdot|\mathcal{L}(j)^{k-1,r}|+\beta\cdot(n+1)\cdot(1/ST(j)), \tag{6}\]where \(\mathcal{L}(j)^{k-1,r}\) represents the reliability of code bits corresponding to the decoding result by \(S_{k-1,r}\) and \(\mathcal{L}(j)^{0,r}\) represents the initial message \(\mathrm{LLR}(y_{j})\). For limited computational complexity, we extract \(T_{k,k-1}\) elements from \(S_{k-1}\), each of which selects \(T_{k,k}\) code bits with the smallest metric based on Equation (6) as the \(k\)-th identified bit. Thus, the size of set \(\mathcal{S}_{k}\) is \(T_{k}=T_{k,k-1}\times T_{k,k}\), and the maximum number of decoding attempts of order-\(k\) is \(2^{k}\times T_{k}\). The rule to generate the correction set can be summarized as \(generate\_S_{k}\), described in Algorithm 3. The MBPC-\(\Omega\) decoder is presented in Algorithm 4. For the convenience of description, we describe the enhanced correction operation in the procedure as \(correction\_operation(\mathcal{S}_{k,r})\) in Algorithm 5. For each attempt, \(k\) identified code bits are corrected simultaneously. The \"flag\" indicates the avoidable decoding attempt. The maximum number of decoding attempts is \(T=\sum_{k=1}^{\Omega}2^{k}\times T_{k}\). Note that, in the case of \(|\mathcal{L}(j_{l})|\geq\mathcal{V}\), if the decoding attempts of both sides fail the CRC, the element to which \(j_{l}\) belongs is repeatedly recorded in the next order of the correction set. If none of the decoding attempts meet the requirements of the CRC until the order exceeds \(\Omega\), the decoder declares a failure. ```
1:for\(r=1\) to \(T_{k,k-1}\)do
2:\(\mathcal{S}_{tmp}\gets T_{k,k}\) bits with smallest \(M(j)^{k,r}\). 3:// generate a size-\(T_{k,k}\) set of \(k\)-th corrected bit
4:for\(j=1\) to \(T_{k,k}\)do
5:\(\mathcal{S}_{k,(r-1)\cdot T_{k,k-1}+j}\leftarrow\mathcal{S}_{k-1,r}\cup \mathcal{S}_{tmp},j\). 6:endfor
7:endfor
```  
**Algorithm 3** The procedure of \(generate\_S_{k}\). ```
1:\(\mathrm{LLR}(y_{1}^{N})\), \(I_{max}\), \(\mathcal{L}\), \(T\), \(\Omega\). 2:Initial \(\mathbf{L}\) and \(\mathbf{R}\) by Equations (3) and (4). 3:Perform the original BP decoder with CRC termination. 4:if\(a_{1}^{N}\) passes the CRC then
5:return\(\hat{a}_{1}^{N}\). 6:else
7:Generate the set \(\mathcal{S}_{1}\) of size \(T_{1}\). 8:for\(k=1\) to \(\Omega\)do
9:for\(r=1\) to \(T_{k}\)do
10:// each code bit in \(r\)-th element expressed by \(j_{l}\): \((j_{1},j_{2},...j_{k})\). 11:\(a=0\), \(\mathrm{flag}=0\). 12:while\(a<2^{k}\)do
13:Initialize \(\mathbf{L}\) and \(\mathbf{R}\) by Equations (3) and (4). 14: Perform the \(correction\_operation(\mathcal{S}_{k,r},a,\mathrm{flag})\); \(a++\). 15:if\(\mathrm{flag}=1\)then
16:continue. 17:endif
18:\(\hat{a}_{1}^{N}\leftarrow\) conventional BP decoding with CRC termination. 19:if CRC(\(\hat{a}_{1}^{N}\)) = true then
20:return\(\hat{a}_{1}^{N}\).