Contents

Introduction

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 [1].
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 [2] 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 [3].
As a result the “hypothesis

” formulated by Kolmogorov to assess
complexity of

valued multiplication was disproved.
Today the development principle of fast algorithms bears the name
“divide and conquer” [4] 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

,

with

signal samples

,

(in general a complex one).
To calculate one spectrum sample

operations of
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
to two

point DFT as it is shown in Figure 1.

Figure 1. Replacement of the

point DFT with Two

point DFT

Replacement of one

point DFT with two

point DFT
will lead to halving the number of operations, but operations of
halving the sequence and association of two

point DFT
into one

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

point DFT.
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

times.
For

(

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

where

is a complex conjugate operator.

It is easy to show that the following equation is correct for
two complex numbers

and

:

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.

Conclusions

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.

Reference

[1]
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

[2]
James W. Cooley and John W. Tukey
An Algorithm for the Machine Calculation of Complex Fourier Series.
Mathematics of Computation, 1965 p. 297–301.

[3]
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

[4]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
Data structures and algorithms.
Menlo, Addison-Wesley, 1983 .

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

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

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