Digital Sound & Music: Concepts, Applications, & Science, Chapter 2, last updated 6/25/2013
F, an array of complex numbers representing audio data
in the frequency domain, the elements represented by the coefficients
of their real and imaginary parts, a and b respectively
N, the number of samples in the array
Output: f, an array of audio samples in the time domain*/
for ( )
∑ ( )
Algorithm 2.2 Inverse discrete Fourier transform
2.3.8 The Fast Fourier Transform (FFT)
If you know how to program, it's not difficult to write your own discrete Fourier transform and
its inverse through a literal implementation of the equations above. We include this as an
exercise in this section. However, the "literal" implementation of the transform is
computationally expensive. The equation in Algorithm 2.1 has to be applied N times, where N is
the number of audio samples. The equation itself has a summation that goes over N elements.
Thus, the discrete Fourier transform takes on the order of operations.
The fast Fourier transform (FFT) is a more efficient implementation of the Fourier
transform that does on the order of operations. The algorithm is made more efficient
by eliminating duplicate mathematical operations. The FFT is the version of the Fourier
transform that you'll often see in audio software and applications. For example, Adobe Audition
uses the FFT to generate its frequency analysis view, as shown in Figure 2.41.