## 4 FFT Implementation Issues  
The DFT required in OFDM environments is implemented efficiently using Decimation In Time (DIT) FFT as was proposed in the mid-sixties by [PERSON] and [PERSON] [17]. Instead of performing all the calculations dictated by Equation 3 the DFT can be estimated from two or more elementary DFTs avoiding the calculation of the same parameters multiple times. For example, in a radix-2 FFT an _N_-point FFT is performed by combining a pair of _N_/2 point FFTs. One of these FFTs accepts as input the odd inputs of the _N_-point FFT and the other one the even inputs. Each one of these _N_/2 point FFTs is also implemented by a pair of _N_/4-point FFTs and so forth until 2 point FFTs are defined. In this way the _N_\({}^{2}\) operations required by the initial _N_-point FFT are reduced to _Nlog\({}_{2}\)N_. This architecture is shown for the case of an 8-point radix-2 FFT in Figure 4 [18]. The inputs are bit reversed while the outputs are in normal order. The _N_/4 point FFT which for the case of Figure 4 is actually a 2-point FFT defines the butterfly operation between its two inputs \(x_{i0}\) and \(x_{iI}\):  
\[ \begin{split} X_{o0}=&\ x_{i0}+w_{N}^{r}x_{i1}\\ X_{o1}=&\ x_{i0}-w_{N}^{r}x_{i1}\end{split}  \tag{13}\]  
The twiddle factors \(w\), multiply the input symbol \(x_{n}\) that corresponds to the diagonal arrow in a butterfly and their product is added to the complex symbol value assigned to the horizontal line that meets the end of the diagonal arrow. For simplicity reasons, the twiddle factors were not displayed in Figure 4.  
Generally an _r_-radix FFT is defined as [19]:  
\[X_{k}=\sum_{n=0}^{N-1}x_{m}w_{N}^{rkn}+\sum_{n=0}^{N-1}x_{m+1}w_{N}^{(rn+1)k}+...+\sum_{n=0}^{N-1}x_{m+r-1}w_{N}^{(rn+r-1)k} \tag{14}\]  
Each of the terms in Equation 14 represents one of the \(r\) elementary _N_/_r_ point FFTs that are combined to implement an _r_-radix FFT. The overall arithmetic operations required by an _N_-point FFT decrease when \(r\) is high but the complexity of each butterfly increases since (a) a higher number of complex arithmetic operations is required, (b) the number of butterfly inputs is high, (c) the  
Figure 4: Implementation of an 8-point DFT as a radix-2 DIT FFT (the red arrows indicate zero butterfly outputs). connectivity is more complicated, and (d) the critical path delay in the butterfly is also high. High radix FFTs are not very popular as their VLSI implementation is more difficult. Their advantage though, is that the number of multiplications and the number of stages (corresponding to global communication and memory accesses to execute FFTs) decreases [20]. Although, some alternatives of the proposed undersampling technique may cooperate more efficiently with high-radix FFTs we will focus on the affect of the proposed scheme to the implementation of a radix-2 FFT like the one shown in Figure 4.  
The \(x_{n}\) pairs in the 2-point FFTs that are grouped in the \(N\)/2-point FFT with the odd positioned values are the pairs: \(x_{2p+1}\) and \(x_{2p+1+N2}\) that are expected to be equal (denoted by the same type of dashed lines in Figure 4) as described in the previous section. The result of a DFT with equal \(x_{n}\) symbols (\(x_{n}=x_{c}\)) is zero (the dotted red lines in Figure 4):  
\[X_{k}=\sum\limits_{n=0}^{N-1}xw_{N}^{kn}=x\sum\limits_{n=0}^{N-1}w_{N}^{kn}=0 \tag{15}\]  
As can be shown from Figure 4, all the \(N\)-point FFT outputs in this case are determined by only the outputs of the \(N\)/2-point FFT with the odd positioned input symbols. These, will be half of the outputs of the \(N\)-point FFT while the rest will be determined by the same \(N\)/2-point FFT outputs multiplied by the appropriate twiddle factor. In other words, the \(N\)/2-point FFT with the odd positioned input symbols can be completely removed. However, as we will see in the next section, if 25% of the \(x_{n}\) symbols at the receiver are substituted by the value of other available samples, a non-negligible error floor is posed.