# Area-Efficient Early-Termination Technique for Belief-Propagation Polar Decoders
## 2 Belief-Propagation (BP) Decoder and Previous Early-Termination Techniques  
The BP algorithm is one of the most efficient algorithms to decode polar codes, which iteratively propagates reliabilities over a factor graph [8]. An \(n\)-stage (\(n=\log_{2}\!N\)) factor graph is necessary for (\(N,K\)) polar codes, in which each stage consists of \(N/2\) processing elements (PEs). For instance, Figure 1 depicts the factor graph of (8, 4) polar codes with three decoding stages. Given received messages \(y_{i}\) (\(1\leq i\leq N\)), the BP decoder computes estimated messages \(\hat{u}_{i}\) (\(1\leq i\leq N\)). More precisely, one PE depicted in Figure 2 passes LLRs using four left-LLRs (\(L_{i,s}^{t}\)) and four right-LLRs (\(R_{i,s}^{t}\)) along the right-to-left and left-to-right directions, respectively, where \(i\), \(s\), and \(t\) respectively denote the node index (\(1\leq i\leq N\)), stage index (\(1\leq s\leq n+1\)), and iteration index (\(1\leq t\leq T\)). As the BP algorithm iteratively propagates such LLR values, the initialization in a BP decoder is important to decode polar codes successfully [8]. The right-most nodes at \(s=n+1\) are initialized as \(L_{i,n+1}^{0}=\log(\Pr(y_{i}\!\left|\!x_{i}=0\right. )/\Pr(y_{i}\!\left|\!x_{i} =1)\right. )\) and \(R_{i,n+1}^{0}=0\) based on the LLRs of the received messages. In addition, the left-most nodes at \(s=1\) are initialized depending on the type of bit channels. For the information bit channels, the left-most nodes in set \(A\) are initialized as  
\[L_{i,1}^{0}=0,\ R_{i,1}^{0}=0,\ \text{for}\ i\in A, \tag{1}\]  
and for the frozen bit channels, the left-most nodes in set \(A^{c}\) are initialized as  
\[L_{i,1}^{0}=0,\ R_{i,1}^{0}=\infty,\ \text{for}\ i\in A^{c}, \tag{2}\]  
The other nodes are initialized as zeros as there are no prior probabilities. After the initialization, all left-LLRs and right-LLRs are updated until the maximum number of iterations is reached as follows:  
Figure 1: Factor graph of polar belief-propagation (BP) decoder for (8, 4) polar code. \[L^{t}_{i,s}=f\Big{(}L^{t-1}_{i,s+1}\,,\,L^{t-1}_{i+2^{m-s},s+1}+R^{t}_{i+2^{m-s},s} \Big{)}\,L^{t}_{i+2^{m-s},s}=f\Big{(}L^{t-1}_{i,s+1}\,,\,R^{t}_{i+2^{m-s},s}\Big{)} +L^{t-1}_{i+2^{m-s},s+1^{\prime}} \tag{3}\]  
\[R^{t}_{i,s+1}=f\Big{(}R^{t}_{i,s}\,\,,\,\,L^{t-1}_{i+2^{m-s},s+1}+R^{t}_{i+2^{m- s},s}\Big{)},R^{t}_{i+2^{m-s},s+1}=f\Big{(}R^{t}_{i,s}\,\,,\,\,L^{t-1}_{i,s+1} \Big{)}+R^{t}_{i+2^{m-s},s}, \tag{4}\]  
where \(f(a,b)\) is the classical min-sum approximation calculated as \(f(a,b)=\text{sign}(a)\cdot\text{sign}(b)\cdot\text{min}(|a|,\,|b|)\). After reaching the max iteration, the conventional BP decoder finally estimates the decoding result \(\hat{n}_{i}\) by making a hard decision as sign (\(L^{t}_{i,1}+R^{t}_{i,1}\)) at the left-most node \(s=1\). Although the conventional BP decoder continues decoding iterations until the predetermined max iteration \(T\), the reliable estimations can in fact be obtained before the max iteration \(T\), especially for a high signal-to-noise ratio (SNR) channel condition. The early-termination method for BP polar decoders was first proposed in Reference [15], which compares all the LLR values at the left-most nodes with a threshold value. When all the LLR values at the left-most nodes are larger than the predetermined threshold value, the decoding iteration is terminated even when the iteration number is less than \(T\). In the threshold-based method, decoding can be improved, but high additional hardware complexity is inevitable [15]. The overall procedure of the threshold-based early-termination method [15] is explained in Algorithm 1, and Figure 3 depicts the hardware architecture of the threshold-based early-termination method for (8, 4) polar codes. Note that the number inside the box represents the bit-width of the arithmetical operators. In Figure 3, the threshold-based early-termination method requires 4-bit 8 adders, 8 abstractors, and 8 comparators for (8, 4) polar codes [15].