# Turbo Decoder Design based on an LUT-Normalized Log-MAP Algorithm
## 5 Complexity Analysis of the Proposed Algorithm  
In the improved Log-MAP algorithm, the main part of improvement is the \(\log(1+e^{-|\mathbf{a}-\mathbf{b}|})\) of the function max*, so that different algorithms have different complexities of the max* function. The complexity analysis of this section starts with one decoded bit (or a trellis transition), then we calculate the complexity of the Log-MAP algorithm and the complexity of the function max* using different approximation algorithms [22; 23]. First of all, for the rule of an eight-state trellis transition of the TD-LTE turbo codes, there are 16 branch metrics, which means that there are 16 message transmission paths. The complexity calculation of the Log-MAP algorithm is as follows:  
Step 1: The calculation of the branch metric by Equation (2) requires a total of \(8\times 2\times\mathbf{n}\) addition operations and \(8\times 2\times\mathbf{n}\) multiplication operations. Step 2: In Equation (4), the calculation of forward-state metrics requires a total of eight additions, which correspond to the forward-state metrics of the eight sides in Figure 12, and this requires eight max* calculations. Step 3: Calculation of backward-state metrics using Equation (5) is the same as in Step 2. Step 4: In Equation (6), the calculation of external information needs \(8\times 4\) additions and one subtraction operation; it also requires a total of \(8+4+2\) max* calculations in hardware implementation. The logic addition is same as subtraction. Step 5: The calculation of posteriori information only requires \(8\times 2\) additions in Equation (7). The complexity analysis of the Log-MAP algorithm is summarized in Table 4. As can be seen, the total complexity of the Log-MAP algorithm is \(95+32\times\mathbf{n}\), which consists of \(65+16\times\mathbf{n}\) additions or subtractions, \(16\times\mathbf{n}\) multiplications, and \(30\) max* operations. Next, the different complexities of approximation algorithms of the function max* are analyzed as follows. As can be seen in Figure 10, only two additions and one comparison are performed for Max-Log-MAP algorithm, due to the omission of the \(\log(1+e^{-|\mathbf{a}-\mathbf{b}|})\) of the function max*. For the LUT-Log-MAP algorithm, two additions are made at first, followed by a comparison and a subtraction, then the LUT equivalent to four comparators. Finally, the results of the lookup table make an addition with the comparison results of the function max. As can be seen in Figure 11, for the Nor-Log-MAP algorithm, two additions are performed at first, then the results go through a normalization operation after the function max comparison; for the selected normalized factor in Equation (14), every datum needs to be shifted three times. Finally, an addition operation is used to sum. In addition to considering the complexity of the LUT-Log-MAP and Nor-Log-MAP algorithms, the LUT-Nor-Log-MAP algorithm requires a mode comparison to choose between LUT-Log-MAP decoding and Nor-Log-MAP decoding. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Algorithm** & **ADD/SUB** & **Multiplication** & **Max*** \\ \hline Step1 (\(\gamma_{k}\)) & \(8\times 2\times\mathbf{n}\) & \(8^{*2}\)*n & 0 \\ Step2 (\(\alpha_{k}(s_{k})\)) & 8 & 0 & 8 \\ Step3 (\(\beta_{k}(s_{k})\)) & 8 & 0 & 8 \\ Step4 (\(\lambda_{e}(u_{k})\)) & \(8\times 2\times 2+1\) & 0 & \(8+4+2\) \\ Step5 (\(\alpha_{o}(u_{k})\)) & \(8^{*2}\) & 0 & 0 \\ all & 65 + 16 *n & 16 *n & 30 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Complexity analysis of the Log-MAP algorithm. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Algorithm** & **LUT-Log-MAP** & **Max-Log-MAP** & **Nor-Log-MAP** & **LUT-Nor-Log-MAP** \\ \hline Decoder Gate Count(K) & \(76.1\) K & \(68.7\) K & \(71.8\) K & \(74.5\) K \\ SISO Gate Count(K) & \(4.44\) K & \(3.65\) K & \(4.02\) K & \(4.32\) K \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Simulation results of logic resource consumption.