Contents

Introduction

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:

We will operate on twiddle factors:

as we already did upon considering DFT properties.
Then (1) taking into account (2) takes the more simplified form:

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:

If we consider only the first DFT half

for indexes

,
and also to take into account that

then (4) will be transformed to the form:

where

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

:

Consider twiddle factors

in more detail:

It is possible to simplify

in a similar way:

Then (8) taking into account (9) and (10) takes the form:

Using the equation for the first (6) and the second half of DFT (11),
it is definitely possible to write "the conquer procedure" as:

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:

Two 4-points DFT are formed on the basis of four 2-points DFT:

And the full input signal DFT is formed at the last level:

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

.

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.