Digital Sound & Music: Concepts, Applications, & Science, Chapter 2, last updated 6/25/2013

40

/*Input:

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

Note: √

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.