Home >Science  >  FFT: Fourier Analysis

Fourier Analysis

A Fourier transform is a special case of a wavelet transform with basis vectors defined by trigonometric functions--sine and cosine. What's so special about trigonometric functions? If you've gone through the harmonic oscillator digression, you might have a pretty good idea. When things oscillate, their displacements are governed by trigonometric functions.

Resonance

When a sound wave interacts with an oscillator, it may excite it or not. When it excites it, the oscillator starts oscillating with its own characteristic frequency. What does it tell you about the sound wave? It tells you that this particular sound wave contains this particular frequency. It could be a complicated wave, not even resembling a sine wave, but somehow it does have in itself a component of a given frequency. Since it causes the oscillator to resonate, it must continually pass some of its energy to it. So, on average, when the oscillator is moving one way (the first half of its period) there is more "pushing" by the sound wave, and when it is moving the other way (the second half of its period) there is more "pulling" from the sound wave. The wave "swings" the oscillator.

We can test a given sound mathematically to find out whether it contains a certain frequency (whether it will swing the oscillator with this particular characteristic frequency). We just have to add up (accumulate) the consecutive sound samples multiplied by special weights. We'll make the weights positive when the oscillator is in the first half of its period and negative when its in the second half of its period. Since the energy transfer is best when the oscillator is in the middle of its swing, we'll make the weight highest there. Taking all this into account, the best weighing function will be, you guessed it, a sine. To test for a particular frequency, we'll use the sine wave of that frequency.
Weighted sum of samples

Fig. Summing samples (blue) with appropriate weights (red)

The accumulated sum will be close to zero if the sound doesn't contain a given frequency. Positive samples will, on average, cancel negative samples. But if there is a correlation between the sound and the weighing function, the contributions will accumulate and the result will possibly be a large number.

If we were to physically analyze a sound, we could create a set of oscillators, each tuned to a slightly different frequency, and let the sound swing them. Whatever frequencies were contained in the sound would excite the corresponding oscillators. This is essentially what happens in our ear.

Alternatively, instead of building a set of oscillators, we could analyze the sound wave mathematically, to find out which oscillators would be excited. Each oscillator corresponds to a sinusoidal weight function of specific frequency. If the sound is digitized, we would multiply its samples by the corresponding weights and add them all up (without digitizing we would have to multiply the sound wave by the sine function and then integrate it). The resulting number tells us how much of a given frequency there is in this particular sound wave. A set of such numbers, corresponding to various frequencies, is called a Fourier transform (more precisely, a Digital Fourier Transform, DFT) or a frequency spectrum of the sound.

What does the Fourier transform have to do with the wavelet transform? Look at the weights we use in our analysis. These are nothing else but some very particular basis vectors. They just happen to follow the shape of a sine function (compare it with the Haar basis).

Trigonometric wavelets

Fig. Wavelet base vectors corresponding to a Digital Fourier Transform


Notice that it's not enough to use the sine-shaped functions. For completeness, we have to add the cosine-shaped functions as well. Even though they correspond to the same frequencies as the sine-shaped ones, they describe the out-of-phase swings of the oscillators. As you can see, the Fourier basis can be obtained by sampling sine and cosine waves.

Fourier Synthesis

It so happens that the Fourier wavelets form an orthogonal system--if you take a scalar product of any two of them, you'll get zero. Also, with proper normalization, you can make the squares of these vectors equal to one. N of these vectors form a perfect orthonormal basis in N-dimensional space. In other words, any buffer with N samples can be projected onto these N vectors giving N numbers (which are called Fourier coefficients). These numbers form the digital Fourier transform of the buffer.

Conversely, given those numbers we can reconstitute the original buffer. It is enough to multiply each basis vector by its corresponding Fourier coefficient and add them all up to obtain one N-dimensional vector exactly equal to the original sample buffer. The process of reconstructing the sound wave from its Fourier coefficients is called Fourier synthesis. Since each basis vector is a sampled sine (cosine) wave of a given frequency, you see that by adding up these waves with appropriate coefficients you can re-create any sound wave. In this sense a sound wave is the sum of the pure frequencies contained in it.

We now know (theoretically) how to extract these frequencies (Fourier analysis) as well as synthesize arbitrary sounds from them (Fourier synthesis). It's time for some practical algorithms. But before we get to it, we have to learn some complex numbers.


Next ImageNext: Complex numbers