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
contains samples with even indexes,
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
and also to take into account that
then (4) will be transformed to the form:
points DFT of decimated sequences
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
is of the “odd” sequence
by twiddle factors
Now analyze the second DFT half
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:
Equation (12) combines two
of decimated signals of half duration
in the resulting
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
, by means of two
of even and odd decimated sequences
The same procedure can be applied to calculate each of
it is possible to perform
division step into “even” and “odd” and after that to conquer
the spectrum with
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.
has an index in the decimal number system
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
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
is rewritten from right to left, then all the same
will save its place, similarly
It is important to note that this renumbering method has to be applied
upon putting the number into the binary system consisting from
In the given example
, so 3 bits of binary number were used,
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
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:
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
James W. Cooley and John W. Tukey
An Algorithm for the Machine Calculation of Complex Fourier Series.
Mathematics of Computation, 1965 p. 297–301.
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.