What is the FFT Algorithm

The FFT algorithm was developed to answer the problem of real-time time-to-frequency conversion of sampled sequenced. Currently, the discrete fourier transform was used for this. The DFT uses N-1 complex summations and N complex multiplications for each frequency point. Since there are N frequency points to calculate, this means that there will be N*N complex multiplications and N(N-1) complex summations. Counting two real sums for every complex one, and four real multiplications plus two real summations for every complex multiplication, gives a total of 4n*n-2n real summations and 4N*N real multiplications.

For a N=1024 data sequence, the number of multiplications is 4,194,304. For a DSP 56001/2 with a 27 Mhz clock, it takes .31 seconds to execute. Since the DFT needs to be completed before the next number of sampled sequences are introduced, we are then limited to a sample rate of 3.3KHz. The limited sampling rate can be calculated by taking the inverse of the time it takes to execute the algorithm for one point of the N points. Maximum Sampling Rate = 1 / ((seconds/number of points) / number of points) = 1 / (.31 / 1024 ) = 3.3KHz. Because the sampling rate is lower than 8 Khz, the minimum sampling rate for voice, this algorithm isn't useful for real-time applications.

The FFT algorithm is an algorithm which computes the Discrete Fourier Transform faster than the normal usage of the DFT. In general, the FFT breaks the group of discrete sequences into groups of dfts with a sequence length of 2. For example, for 8 sampled sequences, we will break this group down into 4 dfts where the length of each dft is 2 (N=2). The advantage of this is because the number of multiplications used to compute the dft's length is proportional to the square of the dft's length. If we replaced the N point dft with two dfts of N/2 length, we can thus reduce the magnitude of the computation by a factor of .5 (.25+.25).

The FFT algorithm can be represented in term of its frequency points and time sampled points. because of this there are two types of FFT, the decimation in frequency FFT and decimation in time FFT.

The Decimation in Time FFT employs the breakdown of a N point time sampled sequence sequence into groups of 2 point dfts. The formula for the two point dft is listed below.

We see that the even and odd grouped sequences can be decomposed into further decompositions listed below.

If N in an integer power of 2, this process can be repeated until a simple, two-point dft is obtained. The decomposition of the dft can be represented as a butterfly diagram showing how the decomposition exposes the redundancy within the FFT algorithm. This redundancy is also what makes the algorithm faster than the original dft.

The Decimation in Frequency FFT is a decomposition of the sampled points in the frequency domain. The equation for the DIF FFT is listed below.

Example

References

  1. Title: Digital Signal Processing A Practical Approach
  2. Implementation of Fast Fourier transforms on Motorola's Digital Signal Processors App. Note