## 4 Efficient FFT Algorithms
### Transform Decomposition  
The index used in FFT pruning algorithms shows irregularity because of the irregular position of zero inputs/outputs. This irregularity makes the hardware implementation of FFT pruning difficult. [PERSON] _et al_. proposed an efficient algorithm called transform decomposition (TD) in [69]. It was shown that, transform decomposition is more efficient and flexible than FFT pruning in the view point of hardware implementation. Transform decomposition is considered as a modified Cooley-Tukey FFT, where the DFT is decomposed into two smaller DFTs.  
Figure 9: An example FFT butterfly structure with pruning.  
In the TD method, the \(N\)-point DFT with \(L\) nonzero outputs is decomposed into two parts: \(N_{2}\) number of \(N_{1}\)-point DFTs and the multiplications with twiddle factors and recombination of the products. Since only \(L\) output values are nonzero, only \(L\) twiddle factors are multiplied with each of the \(N_{1}\)-point DFTs. The total number of multiplications for TD method is given by  
\[MUL_{TD}=\frac{N}{2}\times\ log_{2}(N_{1})+\ L\ \times\ (N_{2}-1) \tag{5}\]  
Thus, there is a reduction of number of multiplications and the computational complexity. In a similar way, the transform decomposition algorithm can be applied for zero inputs. The advantage of transform decomposition is that, it does not need conditional statements to choose the butterfly for calculations as opposed to FFT pruning. Transform decomposition method exhibits considerable regularity which facilitates its hardware implementation.  
[PERSON] _et al._[PERSON] et al. (2010) proposed a computational structure of the transform decomposition algorithm for cognitive radio systems. In this method, efficient computation of the power-of-two FFT is considered for OFDM systems with only a subset of subcarriers being active. If there are \(L\) active subcarriers, then there will be \(L\) non-zero inputs/outputs for the IFFT/FFT blocks. Considering \(N\) point FFT computation, \(N_{1}\) is chosen to be the nearest power-of-two integer larger than \(L\) and as a factor of \(N\). As in [PERSON] et al. (2011), the computation is divided into two stages where, in the first stage \(N_{1}\) point FFTs are computed and in the second stage multiplication with twiddle factors and recombination are performed. The computational structure shows a considerable regularity in memory addressing. Using simulation results it was shown that, the algorithm is more efficient for small number of non-zero output values (\(L\)) and the complexity increases with the number of non-zero values.  
[PERSON] _et al._[PERSON] et al. (2010) proposed an efficient multi-resolution spectrum sensing method based on transform decomposition. The TD algorithm can be used to perform spectral analysis with finer resolutions in the frequency bands of interest, at low computational cost. [PERSON] _et al._[PERSON] et al. (2010) proposed a computationally efficient method for sparse input points DFT based on TD method and the method was shown to be more efficient than the conventional TD.  
In [PERSON] et al. (2011), the authors have proposed a transform decomposition scheme based on two dimensional (2-D) systolic arrays for IDFT/DFT and IDCT/DCT, in order to achieve an efficient computation for OFDM in Cognitive Radio system. The authors have also developed a fast hybrid DFT and DCT architecture for OFDM systems.