The FFT has a fairly easy algorithm to implement, and it is shown step
by step in the list below. This version of the FFT is the Decimation
in Time Method
The process of decimating the signal in the time domain has caused the INPUT samples to be re-ordered. For an 8 point signal the original order of the samples is
What has happened is that the bit patterns representing the sample number has been reversed. This new sequence is the order that the samples enter the FFT.
So far we have not mentioned anything about how the samples are recombined to produce the result. This is covered in the next section.
On to FFT Butterfly or back to Mathematics of Time Decimation
or back to FFT Contents or back to Main Contents