#
Decimation in Time

##
Mathematical Represenation 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 take this *N* point DFT, & break it down into two
*N/2*
point DFT's by splitting the input signal into odd & even numbered
samples to get:

If we assume that the input signal has been divided by *1/N*
(normalised) and we let

we get

But If you look at the equation you will see that the two twiddle
factors are not the same between the ODD and EVEN parts of the signal,
so to simplify the equation, we pull part of the twiddle factor out of
the sumation.

(Remember that from the Definition of the DFT)

We now have two *N/2* point DFTs which take less time to work out
than one *N* point DFT.

This process of decimating each DFT is continued until we reach
a series of two point DFts (ie only two input samples.)

Now that you know roughly whats going on (at least I hope you
do!), lets look at the algorithm used for the FFT
which takes all the maths & ideas and puts them into easy to follow
A-B-C
steps.

On to *The FFT Algorithm*

or back to *Visual Representation of
Time Decimation*

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