Equation of the Day #20: The Fourier Transform
Autobots roll out and Fourier transform Equation of the Day
A wave, in general, is any function that obeys the wave equation. To simplify things, though, let’s look at repeating wave patterns.
The image above depicts a sine wave. This is the shape of string and air vibration at a pure frequency; as such, sinusoidal waveforms are also known as “pure tones.” If you want to hear what a pure tone sounds like, YouTube is happy to oblige. But sine waves are not the only shapes that a vibrating string could make. For instance, I could make a repeating pattern of triangles (a triangle wave),
or rectangles (a square wave),
Now, making a string take on these shapes may seem rather difficult, but synthesizing these shapes to be played on speakers is not. In fact, old computers and video game systems had synthesizers that could produce these waveforms, among others. But let’s say you only know how to produce pure tones. How would you go about making a square wave? It seems ridiculous; pure tones are curvy sine waves, and square waves are choppy with sharp corners. And yet a square wave does produce a tone when synthesized, and that tone has a pitch that corresponds to how tightly its pattern repeats — its frequency — just like sine waves.
As it turns out, you can produce a complex waveform by adding only pure tones. This was discovered by Jean-Baptiste Joseph Fourier, an 18th century scientist. What he discovered was that sine waves form a complete basis of functions, or a set of functions that can be used to construct other well-behaved, arbitrary functions. However, these sine waves are special. The frequencies of these sine waves must be harmonics of the lowest frequency sine wave.
The image above shows a harmonic series of a string with two ends fixed (like those of a guitar or violin). Each frequency is an integer multiple of the lowest frequency (that of the top string, which I will call ν1 = 1/T, where ν is the Greek letter "nu."), which means that the wavelength of each harmonic is an integer fraction of the longest wavelength. The lowest frequency sine wave, or the fundamental, is given by the frequency of the arbitrary wave that’s being synthesized, and all other sine waves that contribute to the model will have harmonic frequencies of the fundamental. So, the tone of a trumpet playing the note A4 (440 Hz frequency) will be composed of pure tones whose lowest frequency is 440 Hz, with all other pure tones being integer multiples of 440 Hz (880, 1320, 1760, 2200, etc.). As an example, here’s a cool animation showing the pure tones that make up a square wave:
As you can see in the animation, these sine waves will not add up equally; typically, instrument tones have louder low frequency contributions than high frequency ones, so the amplitude of each sine wave will be different. How do we determine the strengths of these individual frequencies? This is what Fourier was trying to determine, albeit for a slightly different problem. I mentioned earlier that sine waves form a complete basis of functions to describe any arbitrary function (in this case, periodic waveforms). This means that, when you integrate the product of two sine waves within a harmonic series over the period corresponding to the fundamental frequency (T = 1/ν1), the integral will be zero unless the two sine waves are the same. More specifically,
Because of this trick, we can extract the amplitudes of each sine wave contributing to an arbitrary waveform. Calling the arbitrary waveform f(t) and the fundamental frequency 1/T,
This is how we extract the amplitudes of each pure tone that makes up the tone we want to synthesize. The trick was subtle, so I’ll describe what happened there line by line. The first line shows that we’re breaking up the arbitrary periodic waveform f(t) into pure tones, a sum over sine waves with frequencies m/T, with m running over the natural numbers. The second line multiplies both sides of line one by a sine wave with frequency n/T, with n being a particular natural number, and integrating over one period of the fundamental frequency, T. It’s important to be clear that we’re only summing over m and not n; m is an index that takes on multiple values, but n is one specific value! The third line is just swapping the order of taking the sum vs. taking the integral, which is allowed since integration is a linear operator. The fourth line is where the magic happens; because we’ve integrated the product of two sine waves, we get a whole bunch of integrals on the right hand side of the equation that are zero, since m and n are different for all terms in the sum except when m = n. This integration trick has effectively selected out one term in the sum, in doing so giving us the formula to calculate the amplitude of a given harmonic in the pure tone sum resulting in f(t).
This formula that I’ve shown here is how synthesizers reproduce instrument sounds without having to record the instrument first. If you know all the amplitudes bn for a given instrument, you can store that information on the synthesizer and produce pure tones that, when combined, sound like that instrument. To be completely general, though, this sequence of pure tones, also known as a Fourier series, also includes cosine waves as well. This allows the function to be displaced by any arbitrary amount, or, to put it another way, accounts for phase shifts in the waveform. In general,
or, using Euler’s identity,
The collection of these coefficients is known as the waveform’s frequency spectrum. To show this in practice, here’s a waveform I recorded of me playing an A (440 Hz) on my trumpet and its Fourier series amplitudes,
Each bar in the cn graph is a harmonic of 440 Hz, and the amplitudes are on the same scale for the waveform and its frequency spectrum. For a trumpet, all harmonics are present (even if they’re really weak). I admittedly did clean up the Fourier spectrum to get rid of noise around the main peaks to simplify the image a little bit, but know that for real waveforms the Fourier spectrum does have “leakage” outside of the harmonics (though the contribution is much smaller than the main peaks). The first peak is the fundamental, or 440 Hz, followed by an 880 Hz peak, then a 1320 Hz peak, a 1760 Hz peak, and so on. The majority of the spectrum is concentrated in these four harmonics, with the higher harmonics barely contributing. I also made images of the Fourier series of a square wave and a triangle wave for the curious. Note the difference in these spectra from each other and from the trumpet series. The square wave and triangle wave only possess odd harmonics, which is why their spectra look more sparse.
One of the best analogies I’ve seen for the Fourier series is that it is a recipe, and the "meal" that it helps you cook up is the waveform you want to produce. The ingredients are pure tones — sine waves — and the instructions are to do the integrals shown above. More importantly, the Fourier coefficients give us a means to extract the recipe from the meal, something that, in the realm of food, is rather difficult to do, but in signal processing is quite elegant. This is one of the coolest mathematical operations I’ve ever learned about, and I keep revisiting it over and over again because it’s so enticing!
Now, this is all awesome math that has wide applications to many areas of physics and engineering, but it has all been a setup for what I really wanted to showcase. Suppose I have a function that isn’t periodic. I want to produce that function, but I still can only produce pure tones. How do we achieve that goal?
Let’s say we’re trying to produce a square pulse.
One thing we could do is start with a square wave, but make the valleys larger to space out the peaks.
As we do this, the peaks become more isolated, but we still have a repeating waveform, so our Fourier series trick still works. Effectively, we’re lengthening the period T of the waveform without stretching it. Lengthening T causes the fundamental frequency ν1 to approach 0, which adds more harmonics to the Fourier series. We don’t want ν1 to be zero, though, because then nν1 will always be zero, and our Fourier series will no longer work. What we want is to take the limit as T approaches infinity and look at what happens to our Fourier series equations. To make things a bit less complicated, let’s look at what happens to the cn treatment. Let’s reassign some values,
Here, νn are the harmonic frequencies in our Fourier series, and Δν is the spacing between harmonics, which is equal for the whole series. Substituting the integral definition of cn into the sum for f(t) yields
The reason for the t' variable is to distinguish the dummy integration variable from the time variable in f(t). Now all that’s left to do is take the limit of the two expressions as T goes to infinity. In this limit, the νn smear into a continuum of frequencies rather than a discrete set of harmonics, the sum over frequencies becomes an integral, and Δν becomes an infinitesimal, dν . Putting this together, we arrive at the equations
These equations are the Fourier transform and its inverse. The first takes a waveform in the time domain and breaks it down into a continuum of frequencies, and the second returns us to the time domain from the frequency spectrum. Giving the square pulse a width equal to a, a height of unity, and plugging it into the Fourier transform, we find that
This is one of the first Fourier transform pairs that students encounter, since the integral is both doable and relatively straightforward (if you’re comfortable with complex functions). This pair is quite important in signal processing since, if you reverse the domains of each function, the square pulse represents a low pass frequency filter. Thus, you want an electrical component whose output voltage reflects the sinc function on the right. (I swapped them here for the purposes of doing the easier transform first, but the process is perfectly reversible).
Let’s look at the triangular pulse and its Fourier transform,
If you think the frequency domain looks similar to that of the square pulse, you’re on the right track! The frequency spectrum of the triangular pulse is actually the sinc function squared, but the integral is not so straightforward to do.
And now, for probably the most enlightening example, the Gaussian bell-shaped curve,
The Fourier transform of a Gaussian function is itself, albeit with a different width and height. In fact, the Gaussian function is part of a family of functions which have themselves as their Fourier transform. But that’s not the coolest thing here. What is shown above is that a broad Gaussian function has a narrow range of frequencies composing it. The inverse is also true; a narrow Gaussian peak is made up of a broad range of frequencies. This has applications to laser operation, the limit of Internet download speeds, and even instrument tuning, and is also true of the other Fourier transform pairs I’ve shown here. More importantly, though, this relationship is connected to a much deeper aspect of physics. That a localized signal has a broad frequency makeup and vice versa is at the heart of the Uncertainty Principle, which I’ve discussed previously. As I mentioned before, the Uncertainty Principle is, at its core, a consequence of wave physics, so it should be no surprise that it shows up here as well. However, this made the Uncertainty Principle visceral for me; it’s built into the Fourier transform relations! It also turns out that, in the same way that time and frequency are domains related by the Fourier transform, so too are position and momentum:
Here, ψ(x) is the spatial wavefunction, and ϕ(p) is the momentum-domain wavefunction.
Whew! That was a long one, but I hope I’ve done justice to one of the coolest — and my personal favorite — equations in mathematics.
P.S. I wanted to announce that Equation of the Day has its own website! Hop on over to eqnoftheday.com and check it out! All the entries over there are also over here on BZPower, but I figured I'd make a site where non-LEGO fans might more likely frequent. Let me know what you think of the layout/formatting/whatever!