The Discrete Fourier Transform (DFT)
today is one of widespread analysis tools which is used in all branches
of science and engineering.
However before emergence of computers the DFT was seldom used as the DFT
calculation of 32 samples requires 1024 operations of
complex multiplication and summing.
The first mention of the function expansion algorithm in a trigonometric
series where periodicity properties of trigonometric functions for the accelerated
analysis were used refers to Gauss’s work .
Nobody had paid attention to this work until the fast Fourier
transform algorithms were widely adopted.
The first program realization of the FFT algorithm was carried out
in the early sixties of the XXth century by James Cooley in the computer
IBM center under the supervision of John Tukey, and in 1965 they published
the article  devoted to the fast Fourier transform algorithm.
From that point the real FFT-mania has begun.
Many works devoted to the FFT algorithm are being published,
monographs are being issued one by one, programmers are competing
in efficiency of the algorithm realization.
The FFT becomes the main tool of the spectrum signal analysis.
It is necessary to note that the development principle of fast algorithms
by means of recursive reducing to smaller problems was used by the Soviet
mathematician Anatoly Karatsuba to implement the fast algorithm of
number multiplication (the Karatsuba multiplication) for the first time .
As a result the “hypothesis
” formulated by Kolmogorov to assess
valued multiplication was disproved.
Today the development principle of fast algorithms bears the name
“divide and conquer”  and it is used for a wide range of tasks:
FFT, instant search, fast matrix multiplication and others.
FFT Algorithm Development Principle
Consider the equation for the discrete Fourier transform:
The DFT associates
complex spectrum samples
(in general a complex one).
To calculate one spectrum sample
complex multiplication and summing are required.
Thus, computational complexity of the DFT algorithm consists of
complex multiplication and summing.
As the algorithm complexity grows in a quadratic correlation
concerning the size of an input signal, it is possible to reach essential
calculation acceleration if we manage to reduce the
point DFT calculation
point DFT as it is shown in Figure 1.
Figure 1. Replacement of the
point DFT with Two
Replacement of one
point DFT with two
will lead to halving the number of operations, but operations of
halving the sequence and association of two
point are additionally required.
At the same time each of the
point DFT can also be
calculated by replacement the
point DFT with two
point which in their turn can be calculated by means of the
This recursion can be continued, so far it is possible
to divide the input sequence into two.
In our case if
is a positive integer,
we can halve the sequence
) such dividing is presented in Figure 2.
Figure 2. Dividing and Conquering of the Sequence for
The FFT algorithms which use selections with the length
are called “radix-2 FFT algorithms”. These algorithms have gained
the greatest distribution because of their efficiency and the relative
simplicity of the program realization.
We will consider two ways of dividing and conquering:
decimation in time and decimation in frequency.
Inverse Fast Fourier Transform
The efficient direct FFT calculation algorithm can
be used for the inverse transform too.
Pay attention that complex exponents in the equations for the
direct and inverse DFT are complex conjugated:
is a complex conjugate operator.
It is easy to show that the following equation is correct for
two complex numbers
In connection with the IDFT equation it is possible to write down:
Thus, take the complex conjugated spectrum
the direct DFT is carried out and the result is exposed
to complex conjugate.
The IDFT calculation when using the DFT is given in Figure 3.
Figure 3. Calculation of the Inverse FFT
If instead of the DFT we use the FFT, we will get the invers
fast Fourier transform (IFFT).
At that, for carrying out complex conjugate it is necessary
only to change a sign before an imaginary spectrum part before
the FFT function call and the result after the FFT.
Thus, we considered an acceleration way of calculations upon calculating the DFT,
and also converted the IFFT to the direct one.
Now it is necessary to consider ways of dividing and conquering
providing essential reduction of calculations.
In the following sections we will consider FFT algorithms
in detail on grounds of two
decimation in time
and decimation in frequency
M. Heideman, D. Johnson, C. Burrus
Gauss and the history of the fast fourier transform.
IEEE ASSP Magazine, Vol. 1, Issue 4, October 1984, p. 14-21
James W. Cooley and John W. Tukey
An Algorithm for the Machine Calculation of Complex Fourier Series.
Mathematics of Computation, 1965 p. 297–301.
A. Karatsuba and Yu. Ofman
Multiplication of Many-Digital Numbers by Automatic Computers.
Proceedings of the USSR Academy of Sciences. Vol. 145, p.293–294
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
Data structures and algorithms.
Menlo, Addison-Wesley, 1983 .
Richard E. Blahut
Fast Algorithms for Signal Processing.
Cambridge University Press, 2010.
Nussbaumer Henri J.
Fast Fourier Transform and Convolution Algorithms.
Second Corrected and Updated Edition.
Oppenheim Alan V. and Schafer Ronald W.
Discrete-Time Signal Processing
Prentice-Hall, New Jersey, 1999.