Fast Fourier Transform Formula:

The Fast Fourier Transform Formula is a computational tool which facilitates signal analysis, such as power spectrum analysis and filter simulation using digital computers.

In digital analysis of signals, the continuous waveform to be analysed is first sampled and then converted to digits that represent the amplitude of the samples. The digital analyser operates on this number sequence and produces another number sequence as digital processing. If the resulting sequence repre­sents the samples of a time sequence, it can be converted to analog form by the use of D/A converter, to farm a continuous waveform in the time domain. In the case of an FFT of the number sequence, the result of the digital process is a number sequence, which represents in the frequency domain the characteristics of the continuous waveform that formed the basis for the input number sequence.

The Fourier transform of a number sequence is referred to as the Discrete Fourier Transforms (DFT) and is analogous to the Fourier series and the Fourier intergral transform of continuous and transient time signals.

The DFT defines the spectrum of a time series. The convolution of a two time series is equivalent to the multiplication of the DFTs of the two time.

The FFT is a highly efficient procedure for computing the DFT of a time series. The calculation of the DFT of a time series have N = 2ⁿ samples involves N² arithmetic operations; the same can be done by a FFT with only 2Nn = 2N log₂ N arithmetic operations.

In a computer that takes about half an hour to do the DFT calculation in the conventional way for N = 8192 samples, the calculation time required using FFT is only about five seconds.