Fourier Analysis

History

Jean Baptiste Joseph, Baron de Fourier, theorized that “arbitrarily complicated periodic signals could be represented as a sum of many simultaneous simple signals … of different amplitudes, frequencies, and phases” (Roads 1075-1076) now called a Fourier series. In 1807, he presented his work on heat propagation to the Institut de France, showing the usefulness of his mathematical theory in representing temperature distributions. Joseph Louis Lagrange was in attendance at Fourier’s presentation, and contested that Fourier’s approach could not be used to represent waves with corners, such as square waves. Even though a theory analogous to Fourier’s had been developed by the Swiss mathematician Leonard Euler as early as the late 1770s and a method similar to the modern-day FFT had been developed by the German mathematician Karl Friedrich Gauss in 1805 (Roads 1076), the Institut de France so relied on Lagrange’s credibility and prestige that Fourier was not able to publish his work until after Lagrange’s death 15 years later in 1822 (Smith 8.1).

Determining a Fourier series for a given waveform, its decomposition from a complex periodic waveform to a series of simple functions, is called a Fourier transform. When Fourier’s work was published, the method required so many calculations that it was impractical for a mathematician to calculate by hand. However, the advent of the computer allowed for practical applications of Fourier’s work.

Following the development of stored-program computers in the 1940s, programmers created the first digital implementations of the Fourier transform (FT), but these consumed enormous amounts of computer time – a scarce commodity in that era. Finally, in the mid-1960s, the voluminous calculations required for Fourier analysis were greatly reduced by a set of algorithms known as the fast Fourier transform or FFT, described by James Cooley at Princeton University and John Tukey at Bell Telephone Laboratories (Roads 1076).

In 1972, some 165 years after his 1807 lecture, Grattan-Guinness published Fourier’s original text (Roads 1075), calling his work “an anticipation of linear programming” (Grattan-Guinness). Today, Fourier analysis has many uses, from touch-tone dialing to determining sunspot activity (Moler).

Types of Fourier transforms

Signals can be analyzed using different types of Fourier transforms. Each kind of Fourier transform has a real version, which uses real, ordinary numbers, and a complex version, which uses both real and imaginary numbers (Moler). Rather than using Cartesian numbers on a linear diagram with rectangular coordinates, a complex Fourier transform uses real and imaginary numbers represented on a polar diagram with polar coordinates (Roads 1086). A Fourier transform removes the signal from the time domain, therefore resulting in a linear diagram where y is amplitude and x is frequency (Roads 1086).

Since “[a] signal can be either continuous or discrete, and … either periodic or aperiodic[,] [t]he combination of these two features generates … four categories” (Smith 8.1). Continuous and discrete signals use different math, similar to the differences between analog and digital.

These four classes of signals all extend to positive and negative infinity. [There is no] version of the Fourier Transform that uses finite length signals[.].. Sine and cosine waves are defined as extending from negative infinity to positive infinity. You cannot use a group of infinitely long signals to synthesize something finite in length. The way around this dilemma is to make the finite data look like an infinite length signal. This is done by imagining that the signal has an infinite number of samples on the left and right of the actual points. If all these imaginary samples have a value of zero, the signal looks discrete and aperiodic, and the Discrete Time Fourier Transform applies. As an alternative, the imaginary samples can be a duplication of the actual 1024 points. In this case, the signal looks discrete and periodic, with a period of 1024 samples. This calls for the Discrete Fourier Transform to be used…. As it turns out, an infinite number of sinusoids are required to synthesize a signal that is aperiodic. This makes it impossible to calculate the Discrete Time Fourier Transform in a computer algorithm. By elimination, the only type of Fourier transform that can be used in DSP is the DFT. In other words, digital computers can only work with information that is discrete and finite in length (Smith 8.1).

FFTs and Their Use

The two most common types of Fourier transforms are the Discrete Fourier Transform and the Fast Fourier Transform. The Discrete Fourier Transform (DFT) can be used on consecutive segments of time (ideally the length of one full cycle of the waveform) to determine the frequency, phase, and amplitude of each sinusoidal wave making up the larger complex wave, and the Fast Fourier Transform (FFT) is a much quicker calculation that can be used on waveforms if the number of digital samples in the specified time segment is a power of two (MSP Tutorial 25). The FFT is “incredibly more efficient, often reducing the computation time by hundreds. This is the same improvement as flying in a jet aircraft versus walking!” (Smith 12) While the DFT requires N^2 operations, Cooley and Tukey demonstrated in 1965 that this formula was redundant and that the FFT required only N x log2(N) operations, greatly speeding up the process (Roads 1108).

The input sequence [of an FFT must be] a power of two in length … The central idea of the FFT is to divide the original N-point input sequence into two shorter sequences of length N/2, the DFTs of which can be combined to give the DFT of the original N-point sequence. One sequence derives from the even-numbered points of the original N, the other from the odd-numbered points. The bifurcation of the stream of input samples, which is the source of the term “decimation-in-time,” reduces the number of complex multiplications by half. The bifurcation can be repeated recursively, reducing sequences of length N/2 to sequences of length N/4, and so on, until one is left with a 2-point DFT (Roads 1109).

The FFT is a method for calculating the complex DFT, and thus uses both real and imaginary numbers (Smith 12.1). It is important to remember that while these complex number data can be used for spectral processing, they must be converted back into Cartesian coordinates before they can be used to create sound. “[C]hanging from rectangular to polar coordinates [means] we are switching from a real and imaginary description to a magnitude and phase description, where ‘phase’ here means angular position in time” (Roads 1098).

One method to check that an FFT is working properly is to put in “some arbitrary time domain signal, such as from a random number generator, and run it through the FFT. Next, run the resultant frequency spectrum through the Inverse FFT and compare the result with the original signal. They should be identical, except round-off noise (a few parts-per-million for single precision)” (Smith 12.3)

Considerations When Using Fourier Transforms

Fourier analysis is designed to work with signals that are infinite, which real-world signals are obviously not. In order to get around this problem, Fourier transforms require windows to limit their duration. Window length has a direct influence on frequency resolution, in that “the frequencies are spaced at integer multiples (harmonics) of sampling frequency / window length N in samples” (Roads 1099). For most sound transformations, bell-shaped curves such as Kaiser and Gaussian windows are the best musical shape (Roads 1103). Windows can cause rippling in the spectrum due to the truncation of the window at the beginning and end. This can cause clicking to be heard in resynthesis (Roads 1101).

Another consideration is phase wrapping and unwrapping. Phase values can be converted to frequency values by “measuring the difference in phase values between successive samples and divide by the time interval between them. Hence the instantaneous frequency can be defined as the difference between two successive phase values divided by the sample period” (Roads 1098) Phase wrapping forces all values to fall between π and –π (Smith 10.2), making subtraction difficult when 345 degrees is followed by 0 degrees instead of 360 degrees. Phase unwrapping does not constrain the information in this way.

Overall, Fourier analysis can be a useful tool for spectral processing. While the theory and math behind the equations are complex, the user does not have to completely understand every aspect of Fourier theory to develop an appreciation for their use or implement them effectively. Their uses in the audio world are as varied as shifting pitch to finding the spectral average of a pop song.

Bibliography
1. Grattan-Guinness, I. “Joseph Fourier's Anticipation of Linear Programming.”
Operational Research Quarterly (1970-1977), Vol. 21, No. 3 (Sep., 1970), pp. 361-364 < http://www.jstor.org/stable/3008492>
2. Moler, Cleve. Numerical Computing with MATLAB. Society for Industrial and Applied Mathematics, 2004. Digital. Chapter 8, “Fourier Analysis.” <http://www.mathworks.com/moler/fourier.pdf>
2. MSP Tutorial 25, “Using the FFT.”
2. Roads, ed. 1996. The computer music tutorial. Cambridge, Mass: MIT Press.
2. Smith, Steven W. The Scientist and Engineer's Guide to Digital Signal Processing. 1st ed. California Technical Pub., 1997. Digital. <http://www.dspguide.com/>

1505 words

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License