# Area-Efficient Early-Termination Technique for Belief-Propagation Polar Decoders
## 3 Proposed Method  
For BP decoders, an internal LLR value is computed as \(LLR^{t}_{i,s}=\text{log}\big{(}\text{Pr}(\hat{u}^{t}_{i,s}=0)/\text{Pr}(\hat{ u}^{t}_{i,s}=1)\big{)}\), which represents a statistical inference at each node [8]. It is natural that the larger the absolute LLR values, the more reliable are the estimations expected. Using this LLR property, the previous threshold-based method presents a termination criterion to check whether all the magnitudes of \(LLR^{t}_{i,s}=L^{t}_{i,s}+R^{t}_{i,s}\) at the left-most nodes are larger than the predetermined threshold [15]. As the comparison for each LLR value leads to \(N\) comparisons, the threshold-based method first finds the minimum value, and then the minimum value is compared with the threshold value [15]. Although the previous criterion [15] succeeded in presenting an early-termination technique in a BP [8] decoder for the first time, it needs optimization in terms of the hardware complexity. Especially, as the previous threshold-based method [15] considers LLR values for every bit to check the early-termination criterion, the threshold-based method [15] has a high hardware complexity. We first present two propositions to simplify the previous threshold-based early-termination technique [15], and next describe a structure for the proposed early-termination technique. Lastly, we emphasize the advantages of the proposed technique by comparing it with information-BER-based [16] and frozen-BER-based [17], early-termination methods. **Proposition 1**: \(\min_{i\in A}\left(\left|L_{i,1}^{t}+R_{i,1}^{t}\right|\right)\leq\min_{i\in A^{c }}\left(\left|L_{i,1}^{t}+R_{i,1}^{t}\right|\right)\)_._  
According to (1) and (2), the right-LLR \(R_{i,1}^{t}\) for the information set and frozen set at the left-most nodes are initialized as zero and infinity, respectively. Since the initial values of \(R_{i,1}^{t}\) of the frozen set at the left-most nodes are infinity, the magnitude of \(LLR_{i}^{t}=L_{i}^{t}+R_{i}^{t}\) in information set \(A\) is always less than the magnitude of \(LLR_{i}^{t}=L_{i}^{t}+R_{i}^{t}\) in frozen set \(A^{c}\). As the minimum LLR value is important to check the termination condition, comparisons of the frozen set are no longer necessary. **Proposition 2**: \(\min_{i\in A}\left(\left|L_{i,1}^{t}+R_{i,1}^{t}\right|\right)=\min_{i\in A} \left(\left|L_{i,1}^{t}\right|\right)\)_._  
According to Equation (1), the right-LLR \(R_{i,1}^{t}\) for information set \(A\) at the left-most nodes are initialized as zeroes so that \(LLR_{i}^{t}=L_{i}^{t}+R_{i}^{t}\) directly becomes \(LLR_{i}^{t}=L_{i}^{t}\). Instead of finding the minimum among \(LLR_{i}^{t}=L_{i}^{t}+R_{i}^{t}\) in information set \(A\), the proposed method tries to find the minimum among \(LLR_{i}^{t}=L_{i}^{t}\) demanding no additions. After finding the minimum value of left-LLR \(L_{i,1}^{t}\) among the information set values, the minimum value can be compared to the pre-determined threshold value \(\beta\). Based on Propositions 1 and 2, we modified the threshold-based method [15], resulting in the proposed early-termination algorithm as shown in Algorithm 4. The proposed early termination checks the condition if all the left-LLR \(L_{i,1}^{t}\) values for information set \(A\) at the left-most nodes are larger than the threshold value. Note that no degradation is introduced compared to the threshold-based method [15], as the same frame-error-rate performances are guaranteed according to Propositions 1 and 2 with the same number of decoding iterations compared with the threshold-based method [15]. For instance, Figure 6 represents the hardware architecture of the proposed early-termination technique for (8, 4) polar codes, where the dotted lines indicate the eliminated circuits from the previous threshold-based method [15]. In Figure 6, the proposed method requires a total of 4 absolute operators and 4 comparators, and the proposed method for (\(N\), \(K\)) polar codes requires \(K\) absolute operators and \(K\) comparators.