The Scientist and Engineer's Guide to
Digital Signal Processing
By Steven W. Smith, Ph.D.

• Home
• The Book by Chapters
• About the Book
  • Copyright and permissible use
  • What is DSP?
  • 8 good reasons for learning DSP
  • Comments by reviewers
  • Errata
  • Free Software and Teaching Aids
  • Differences Between Editions
• Steven W. Smith
• Blog
• Contact

When the DFT is calculated by correlation (as in Table 12-2), the program uses two nested loops, each running through N points. This means that the total number of operations is proportional to N times N. The time to complete the program is thus given by:

where N is the number of points in the DFT and k_DFT is a constant of proportionality. If the sine and cosine values are calculated within the nested loops, k_DFT is equal to about 25 microseconds on a Pentium at 100 MHz. If you precalculate the sine and cosine values and store them in a look-up-table, k_DFT drops to about 7 microseconds. For example, a 1024 point DFT will require about 25 seconds, or nearly 25 milliseconds per point. That's slow!

Using this same strategy we can derive the execution time for the FFT. The time required for the bit reversal is negligible. In each of the Log₂N stages there are N/2 butterfly computations. This means the execution time for the program is approximated by:

The value of k_FFT is about 10 microseconds on a 100 MHz Pentium system. A 1024 point FFT requires about 70 milliseconds to execute, or 70 microseconds per point. This is more than 300 times faster than the DFT calculated by correlation!

Not only is NLog₂N less than N², it increases much more slowly as N becomes larger. For example, a 32 point FFT is about ten times faster than the correlation method. However, a 4096 point FFT is one-thousand times faster. For small values of N (say, 32 to 128), the FFT is important. For large values of N (1024 and above), the FFT is absolutely critical. Figure 12-8 compares the execution times of the two algorithms in a graphical form.

The FFT has another advantage besides raw speed. The FFT is calculated more precisely because the fewer number of calculations results in less round-off error. This can be demonstrated by taking the FFT of an arbitrary signal, and then running the frequency spectrum through an Inverse FFT. This reconstructs the original time domain signal, except for the addition of round-off noise from the calculations. A single number characterizing this noise can be obtained by calculating the standard deviation of the difference between the two signals. For comparison, this same procedure can be repeated using a DFT calculated by correlation, and a corresponding Inverse DFT. How does the round-off noise of the FFT compare to the DFT by correlation? See for yourself in Fig. 12-9.