#
Decimation in Time

##
Visual Representaion of Time Decimation.

Decimation is the process of breaking down something into it's constituent
parts. Decimation in time involves breaking down a signal in the time domain
into smaller signals, each of which is easier to handle.
If the input (time domain) signal, of N points, is x(n) then the
frequency response *X(k)* can be calculated by using the DFT

We start by taking this signal and breaking it down into two equal parts,
made up of the odd and even numbered samples.

This process of decimating the signal can easily be visualised.
The first breakup into two *N/2* point DFT can be shown as:

The *Recombine Algebra* mentioned in the diagram is just used to
combine the samples again in the correct order. *How* this is done
is covered in more detail in the Butterfly section.
You do not need to understand it just yet, the main point here is that
you understand the process of breaking down the samples for the FFT.

The decimation process is taken another stage by breaking down the *N/2*
point DFTs into *N/4* point DFTs.

This is repeated again and again until you reach a series of two
point DFTs e.g. For an 8 sample signal:

Since the recombination algebra takes N complex multiplications and there
are *log*_{2} *(N)* stages, the approx number of complex
multiplications is

This means that this decimation approach has reduced the number of complex
multiplications from *N* squared (*N*^{2}) to *N log*_{2}
*(N).* At high values of *N* (i.e., large signals) this is a
massive saving.
The question still remains: What is the recombination algebra ?

The recombination uses flow graph notation and is called a butterfly
network. This is fully explained in a moment, but first the math
that back this up.

On to *Mathematics of Time Decimation*
or back to *History of the FFT*

or back to *FFT Contents* or back
to *Main Contents*