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:
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