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₂ (N) stages, the approx number of complex multiplications is

N log₂ (N)

This means that this decimation approach has reduced the number of complex multiplications from N squared (N²) to N log₂ (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