Radix-2 Decimation in Frequency FFT Algorithm

Contents
Introduction
Consider one more method of divide and conquer which is called decimation in frequency.
Decimation in Frequency FFT Algorithm
Let samples of the input signal , be, at the same time is the whole degree of two .
In FFT algorithm with decimation in time there was dividing of the input signal according to the bit reversal. Thus, we received the first and second half of discrete Fourier transform (DFT).
In the decimation in frequency algorithm the input , , is halved, i.e. and , .
Then the DFT signal can be written in the form:
(1)
(1)
Consider (1) for spectral samples , , with even indexes:
(2)
(2)
Take into account in (2) that , and also , then we get:
(3)
(3)
Thus, spectral samples , , with even indexes are point DFT of the signal .
Similarly consider (1) for spectral samples , , with odd indexes:
(4)
(4)
Take into account in (4) that , and also that . Then (4) can be presented in the form:
(5)
(5)
Spectral samples , , with odd indexes are point DFT of the signal .
Thus, the divide procedure includes calculating signals of half duration and , . Then it is possible to replace point DFT with two points DFT of signals and .
Decimation in Frequency FFT Algorithm Butterfly Diagram
The procedure of calculating signals of half duration
(6)
(6)
can be presented in the form of the butterfly diagram as it is shown in Figure 1.
Figure 1. Butterfly Diagram of Decimation in Frequency FFT Algorithm
Difference of the butterfly diagram of the decimation in frequency FFT algorithm from a similar diagram for the decimation in time FFT algorithm is that multiplication by the twiddle factor is performed after subtracting places. In the butterfly diagram of the decimation in time FFT algorithm multiplication by the twiddle factor was performed before subtracting places.
Complete Diagram of Decimation in Frequency FFT Algorithm
We replaced calculating points DFT with two points. As a result the diagram of decimation in frequency FFT algorithm for is given in Figure 2.
Figure 2. Diagram of Decimation in Frequency FFT Algorithm for
At the same time each of points DFT can be also calculated using the decimation in frequency FFT algorithm. As a result we will receive the complete diagram of decimation in frequency FFT algorithm as it is shown in Figure 3.
Figure 3. Complete Diagram of Decimation in Frequency FFT Algorithm for
At the first stage we receive and according to (6):
(7)
(7)
To calculate 4-points DFT of signals and , , we use the decimation in frequency FFT algorithm again. Then we receive signals:
(8)
(8)
After calculating two-points DFT at the last level of dividing we receive the spectral samples:
(9)
(9)
which we have to subject to the bit reversal in the same way as this procedure in the algorithm with decimation in time is performed.
Conclusions
In this section we considered radix-2 decimation in frequency FFT algorithm. In the following section we will consider computing efficiency of radix-2 FFT algorithms and some questions of program implementing FFT algorithms.
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.