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:

Consider (1) for spectral samples

,

, with even indexes:

Take into account in (2) that

,
and also

, then we get:

Thus, spectral samples

,

,
with even indexes are

point DFT of the signal

.

Similarly consider (1) for spectral samples

,

, with odd indexes:

Take into account in (4) that

,
and also that

. Then (4) can be presented in the form:

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

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):

To calculate 4-points DFT of signals

and

,

, we use the decimation in frequency FFT algorithm again.
Then we receive signals:

After calculating two-points DFT at the last level
of dividing we receive the spectral samples:

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

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.