Radix-2 Decimation in Time FFT Algorithm

Contents
Introduction
In the previous sections we considered DFT and its properties and also showed the Fast Fourier Transform (FFT) principle on the basis of the divide and conquer procedure.
In this section we will consider one of the most widespread FFT algorithms: radix-2 decimation in time FFT [1-4].
Let’s give the DFT equation once again:
 (1)
(1)
The divide and conquer procedure was considered in the previous section.
We will operate on twiddle factors:
 (2)
(2)
as we already did upon considering DFT properties. Then (1) taking into account (2) takes the more simplified form:
 (3)
(3)
Decimation in time consists of dividing the input sequence , , into two sequences of half duration and , , therefore, , and . The sequence contains samples with even indexes, and with odd ones. Decimation in time for is visually presented in Figure 1.

Figure 1. Decimation in Time for
Divide and Conquer Procedure
Consider DFT of the signal which is decimated in time:
 (4)
(4)
If we consider only the first DFT half for indexes , and also to take into account that
 (5)
(5)
then (4) will be transformed to the form:
 (6)
(6)
where
 (7)
(7)
points DFT of decimated sequences and , respectively.
Thus, decimation in time can be considered as an algorithm of dividing the sequence into two sequences of half duration. The first DFT half is the DFT sum of the “even” sequence and DFT is of the “odd” sequence multiplied by twiddle factors .
Now analyze the second DFT half for :
 (8)
(8)
Consider twiddle factors in more detail:
 (9)
(9)
It is possible to simplify in a similar way:
 (10)
(10)
Then (8) taking into account (9) and (10) takes the form:
 (11)
(11)
Using the equation for the first (6) and the second half of DFT (11), it is definitely possible to write "the conquer procedure" as:
 (12)
(12)
Butterfly Diagram
Equation (12) combines two points DFT and , , of decimated signals of half duration and , , in the resulting points DFT , , of a input signal.
Graphically the divide and conquer process is presented in Figure 2.

Figure 2. Butterfly Diagram
Because of a specific diagram form it takes the name “butterfly”. This divide and conquer procedure is the main one upon creating radix-2 FFT algorithms.
In Figure 3 the FFT algorithm diagram according to (12) is presented for .

Figure 3. Decimation in Time FFT Algorithm Diagram for
Full Diagram of Decimation in Time FFT Algorithm. Bit Reversal
Equation (12) presents the conquer procedure to calculate points DFT , , by means of two points DFT and , of even and odd decimated sequences and , .
The same procedure can be applied to calculate each of points DFT and by means of two points DFT. Then for it is possible to perform sequence division step into “even” and “odd” and after that to conquer the spectrum with steps. As a result we will get the full FFT algorithm diagram. As an example a full decimation in time FFT diagram for is given in Figure 4.

Figure 4. Decimation in Time FFT Algorithm Diagram for
At the first step input signal samples are interchanged and the initial sequence is divided into “even” and “odd” sequences. Then “even” and “odd” sequences, in their turn, are divided into “even” and “odd” sequences again.
This procedure is called bit reversal, in such a way it is possible to renumber samples having rewritten the sample number in the binary system in the reversed direction.
For example, has an index in the decimal number system . If is rewritten from right to left, then we will get , that is after division into “even-odd” before the first operation the “butterfly” will take the place of the sample which in its turn will take the place .
In a similar way all samples will be interchanged, at the same time some of them will save their places, in particular because if is rewritten from right to left, then all the same will save its place, similarly , and .
It is important to note that this renumbering method has to be applied upon putting the number into the binary system consisting from bits. In the given example , so 3 bits of binary number were used, but if were equal to 16, then it would be necessary to write down the number upon using 4 bits. In this case and after reversal we will get that is when , the sample will not save its place, and will be interchange with .
After the bit reversal we get four 2-points DFT:
 (13)
(13)
Two 4-points DFT are formed on the basis of four 2-points DFT:
 (14)
(14)
And the full input signal DFT is formed at the last level:
 (15)
(15)
Conclusions
In this section we considered one of the most widespread fast Fourier transform algorithms: an algorithm with decimation in time.
The divide procedure by decimation in time is shown and the divide and conquer procedure on the basis of the Butterfly Diagram according to (12) is given.
The complete FFT diagram with decimation in time was given for .
In the following section we will consider one more radix-2 FFT algorithm: decimation in frequency FFT algorithm.
Reference
[1] James W. Cooley and John W. Tukey An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 1965 p. 297–301.

[2] Richard E. Blahut Fast Algorithms for Signal Processing. Cambridge University Press, 2010.

[3] Nussbaumer Henri J. Fast Fourier Transform and Convolution Algorithms. Second Corrected and Updated Edition. Springer-Verlag, 1982.

[4] Oppenheim Alan V. and Schafer Ronald W. Discrete-Time Signal Processing Second Edition. Prentice-Hall, New Jersey, 1999.