The Fast Fourier Transform

There are several ways to calculate the Discrete Fourier Transform (DFT), such as solving
simultaneous linear equations or the correlation method described in Chapter 8. The Fast
Fourier Transform (FFT) is another method for calculating the DFT. While it produces the same
result as the other approaches, it is incredibly more efficient, often reducing the computation time
by hundreds. This is the same improvement as flying in a jet aircraft versus walking! If the
FFT were not available, many of the techniques described in this book would not be practical.
While the FFT only requires a few dozen lines of code, it is one of the most complicated
algorithms in DSP. But don't despair! You can easily use published FFT routines without fully
understanding the internal workings.
CHAPTER
The Fast Fourier Transform
12

There are several ways to calculate the Discrete Fourier Transform (DFT), such as solving
simultaneous linear equations or the correlation method described in Chapter 8. The Fast
Fourier Transform (FFT) is another method for calculating the DFT. While it produces the same
result as the other approaches, it is incredibly more efficient, often reducing the computation time
by hundreds . This is the same improvement as flying in a jet aircraft versus walking! If the
FFT were not available, many of the techniques described in this book would not be practical.
While the FFT only requires a few dozen lines of code, it is one of the most complicated
algorithms in DSP. But don't despair! You can easily use published FFT rou