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

39

The Fourier transform is a mathematical process that can transform audio data from the

time to the frequency domain. Sometimes it's more convenient to represent sound data one way

as opposed to another because it's easier to manipulate it in a certain domain. For example, in

the time domain we can easily change the amplitude of the sound by multiplying each amplitude

by a number. On the other hand, it may be easier to eliminate certain frequencies or change the

relative magnitudes of frequencies if we have the data represented in the frequency domain.

2.3.7 The Discrete Fourier Transfer and its Inverse

The discrete Fourier transform is a version of the Fourier transform that can be applied to

digitized sound. The algorithm is given in Algorithm 2.1.

/*Input:

f, an array of digitized audio samples

N, the number of samples in the array

Note:

√

Output:

F, an array of complex numbers which give the amplitudes of the

frequency components of the sound given by f */

for ( )

(∑ )

Algorithm 2.1 Discrete Fourier transform

Each time through the loop, the

nth

frequency components is computed, . Each is a

complex number with a cosine and sine term, the sine term having the factor i in it.

We assume that you're familiar with complex numbers, but if not, a short introduction

should be enough so that you can work with the Fourier algorithm.

A complex number takes the form , where √ . Thus,

( )

is a complex number. In this case, a is replaced with and b with ( ).

Handling the complex numbers in an implementation of the Fourier transform is not difficult.

Although i is an imaginary number,

√

, and you might wonder how you‟re supposed to do

computation with it, you really don‟t have to do anything with it at all except assume it‟s there.

The summation in the formula can be replaced by a loop that goes from 0 through N-1. Each

time through that loop, you add another term from the summation into an accumulating total.

You can do this separately for the cosine and sine parts, setting aside i. This is explained in more

detail in the exercise associated with this section. Also, in object-oriented programming

languages, you may have a Complex number class to do complex number calculations for you.

The result of the Fourier transform is a list of complex numbers , each of the form

, where the magnitude of the frequency component is equal to

√

.

The inverse Fourier transform transforms audio data from the frequency domain to the

time domain. The inverse discrete Fourier transform is given in Algorithm 6.2.