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