Radix 2 FFT(Fast Fourier Transform)
As we know that, the discrete Fourier transform (DFT) plays an important role in many applications of digital signal processing, including linear filtering, correlation analysis, and spectrum analysis. A major reason for its importance is the existence of efficient algorithms for computing the DFT. The main topic of this article is the description of computationally efficient algorithms for evaluating the DFT. Two different approaches are used for calculating FFT. One is a divideandconquer approach in which a DFT of size N, where N is a composite number, is reduced to the computation of smaller DFTs from which the larger DFT is computed. In particular, we present important computational algorithms, called fast Fourier transform (FFT) algorithms, for computing the DFT.
Let us consider the computation of the
N = 2^{v} point DFT by the divideandconquer approach. We split the Npoint data sequence into two N/2point data sequences
f_{1}(n) and
f_{2}(n), corresponding to the evennumbered and oddnumbered samples of x(n), respectively, that is,
Thus
f_{1}(n) and
f_{2}(n) are obtained by decimating x(n) by a factor of 2, and hence the resulting FFT(Fast Fourier Transform) algorithm is called a
decimationintime algorithm.
TAG: View Matlab code for Radix2 decimation in Frequency
Now the Npoint DFT can be expressed in terms of the DFT's of the decimated sequences as follows:
But W_{N}^{2} = W_{N/2}. With this substitution, the equation can be expressed as
where
F_{1}(k) and
F_{2}(k) are the N/2point DFT
s of the sequences
f_{1}(m) and
f_{2}(m), respectively. Since
F_{1}(k) and
F_{2}(k) are periodic, with period N/2, we have
F_{1}(k+N/2) = F_{1}(k) and
F_{2}(k+N/2) = F_{2}(k). In addition, the factor
W_{N}^{k+N/2} = W_{N}^{k}. Hence the equation may be expressed as
We observe that the direct computation of
F_{1}(k) requires
(N/2)^{2} complex multiplications. The same applies to the computation of
F_{2}(k). Furthermore, there are N/2 additional complex multiplications required to compute
W_{N}^{k}F_{2}(k). Hence the computation of
X(k) requires
2(N/2)^{2} + N/2 = N ^{2}/2 + N/2 complex multiplications. This first step results in a reduction of the number of multiplications from
N^{ 2 }to N ^{2}/2 + N/2, which is about a factor of 2 for N large.

Figure TC.3.1 First step in the decimationintime algorithm 
By computing N/4point DFTs, we would obtain the N/2point DFTs F_{1}(k) and F_{2}(k) from the relations
The decimation of the data sequence can be repeated again and again until the resulting sequences are reduced to onepoint sequences. For
N = 2^{v}, this decimation can be performed
v = log_{2}N times. Thus the total number of complex multiplications is reduced to
(N/2)log_{2}N. The number of complex additions is
Nlog_{2}N.
For illustrative purposes, Figure TC.3.2 depicts the computation of
N = 8 point DFT. We observe that the computation is performed in three stages, beginning with the computations of four twopoint DFT
s, then two fourpoint DFT
s, and finally, one eightpoint DFT. The combination for the smaller DFT
s to form the larger DFT is illustrated in Figure TC.3.3 for
N = 8.

Figure TC.3.2 Three stages in the computation of an N = 8point DFT 

Figure TC.3.3 Eightpoint decimationintime Fast Fourier Transform algorithm 

Figure TC.3.4 Basic butterfly computation in the decimationintime FFT algorithm 
An important observation is concerned with the order of the input data sequence after it is decimated
(v1) times. For example, if we consider the case where
N = 8, we know that the first decimation yields the sequence
x(0), x(2), x(4), x(6), x(1), x(3), x(5), x(7), and the second decimation results in the sequence
x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7). This shuffling of the input data sequence has a welldefined order as can be ascertained from observing Figure TC.3.5, which illustrates the decimation of the eightpoint sequence.

Figure TC.3.5 Shuffling of the data and bit reversal 
Decimation in frequency FFT algorithm
Another important radix2 FFT algorithm, called the
decimationinfrequency algorithm, is obtained by using the divideandconquer approach. To derive the algorithm, we begin by splitting the DFT formula into two summations, one of which involves the sum over the first N/2 data points and the second sum involves the last N/2 data points. Thus we obtain
Now, let us split (decimate) X(k) into the even and oddnumbered samples. Thus we obtain
where we have used the fact that
W_{N}^{2} = W_{N/2}
The computational procedure above can be repeated through the decimation of the
N/2point DFT
s X(2k) and
X(2k+1). The entire process involves
v = log_{2}N stages of decimation, where each stage involves
N/2 butterflies of the type shown in Figure TC.3.7. Consequently, the computation of the Npoint DFT via the decimationinfrequency FFT requires
(N/2)log_{2}N complex multiplications and
Nlog_{2}N complex additions, just as in the decimationintime algorithm. For illustrative purposes, the eightpoint decimationinfrequency algorithm is given in Figure TC.3.8.

Figure TC.3.6 First stage of the decimationinfrequency FFT algorithm 

Figure TC.3.7 Basic butterfly computation in the decimationinfrequency. 

Figure TC.3.8 N = 8point decimationinfrequency FFT algorithm 
We observe from Figure TC.3.8 that the input data x(n) occurs in natural order, but the output DFT occurs in bitreversed order. We also note that the computations are performed in place. However, it is possible to reconfigure the decimationinfrequency algorithm so that the input sequence occurs in bitreversed order while the output DFT occurs in normal order. Furthermore, if we abandon the requirement that the computations be done in place, it is also possible to have both the input data and the output DFT in normal order. That what all about Radix 2 FFT algorithm.
Reference Book: Digital Signal Processing Fourth Edition by John G. Proakis and Dimitris G. Manolakis
If you like this post then don't forget to Share with your friends