An Interactive Guide To The Fourier Transform

Hi Kalid,

This is absolutely fantastic, as always. Thank you so much for this article!

I had a question about how the Fourier Transform works when there are several different time spikes of different amplitudes, e.g. (0 6 0 2 8 0). I noticed that if you plug something like that into your Fourier program (which is awesome, by the way!), the “recipe” that it outputs is a bit more complicated - each simple wave has a slightly different amplitude, so it seems like you’re not using the “tentative recipe” anymore. How do you work out what these individual amplitudes are?

Thanks, and sorry if I misunderstood anything!

Hi Ming, glad you enjoyed it!

So, the recipe for each time spike has to be scaled by the size of the spike. Let’s say we just want (1 0 0 0) as a time spike. This would be equal strengths from each possible frequency, or

[1/4 1/4 1/4 1/4] 

In this case, there’s no phase offset needed. Now, let’s say we have the spike of (0 2 0 0). We still need equal strengths, except this time it’s double, since we want to sum to 2.0 and not 1.0:

[1/2 1/2 1/2 1/2]

Whoops! We need to add in the phase offsets. It should be:

[1/2 1/2:-90 1/2:-180 1/2:-270]

since each Hz component needs to line up at t=1, not t=0. If we were to combine the signals (1 2 0 0) we would have:

[1/4 1/4 1/4 1/4] + [1/2 1/2:-90 1/2:-180 1/2:-270] = ?

The first term [0Hz component] can combine easily, to get 3/4. But the other terms have to be added like they are vectors:

1/4 pointing at 0 degrees + 1/2 pointing at -90 degrees is, with some trig:

Amplitude: sqrt[ (1/4)^2 + (1/2)^2 ] = .559
Angle: atan( -(1/2) / (1/4)) = -63.43 degrees

If you plug in (1 2 0 0) into the simulator, you get

[0.75 0.56:-63.4 0.25:180 0.56:63.4]

which are the first two terms. The others can be computed similarly. Of course, it’s a pain to do all this trig – we typically keep the components (amplitude + angle) as complex numbers (a + bi) so we can simply add them up to combine them. The simulator shows the phase offset as an actual angle to help visualize them. But the Fourier Transform formula only deals with complex numbers.

Phew – hope that helps!

Brilliant and easy-to-understand description of what the Fourier Transform does. Thanks.

Good description thanks. Miniscule criticism: SI units please! :slight_smile:

Thanks a lot. Many sites simply gives us the formula and explain in a very abstract way. I had understood that Fourier transform has a lot of application, but, couldn’t understand what exactly it is trying to do.

But, you have made it very clear now, by giving enough analogies and visualization.

Thanks a lot!!!

Thanks, it helped me a lot! Great job with the article.

Thanks for this article - especially the leadups expaining the mathematics of complex numbers, euler’s identity, etc., those were really helpful. The rotation analogy makes it all much more intuitive. I was excited to read the Fourier article here, feeling like there was a pot of gold at the end that would finally tell me how the smoothie filters worked, but I must admit I left it a little confused still. I’ve long understood WHAT the Fourier transform does and what it’s useful for, and thanks to your explanations I can do the equations now and understand roughly how the different parts work in a complex-rotational context. But I’m still totally baffled as to WHY this works. Why is it that integer-frequency’d sinusoids happen to be able to add up in such a way that they magically cancel each other out at the right places and can represent any possible sampled time-domain function? Maybe I just need to meditate on the math more? I’ll probably check out Stephen’s “AC Signal Processing” link above, sounds like he gets into the why a little more. But if you get time to dig into the why a little more at some point I’d love to read it, your explanation style is really clear and fun to read.

Hi Luke, great question. (Btw, this confused mathematicians in Fourier’s time as well.)

Why it works is a deep question, What is an intuitive way of explaining how the Fourier transform works? - Quora has more details (see the first answer). I also like this analogy (“a fly in the room”):

Here’s my 2 cents:

Projection (the dot product) is how we find how much of “x is in y”, essentially giving a readout. If we pick a point in the x/y plane, we might say its coordinates are (1,1). It means that the coordinate is 1 when projected onto the x-axis, and 1 when projected onto the y-axis.

Our choice of axes can change: if we use the “NorthEast, SouthWest” axes, then that same point is (1.414, 0). [sqrt(2) at a 45-degree angle].

The Fourier Transform basically says “Every possible sinusoid is the set of axes that you can project your function onto. You’ll get a listing of how much of each sinusoid is present in your signal.”

The reason why these sinusoids are enough is fairly intricate, but in short: we have an infinity of distinct sinusoids to use. It’s a pretty big lego box, and likely that some combination adds up to our signal. (And we can see it happening in small portions if we handle one instant at a time.)

Thanks Kalid - I read the links you mentioned a couple times, think I’m at least getting a sense of it. The orthogonal basis vectors analogy is useful - like in linear algebra you could potentially define a space with many different choices of basis vectors, as long as they’re at least partially orthogonal to each other (i.e. stretch into every dimension of the space at least a little). And I guess the integer-frequency sinusoids are analogous to perfectly orthogonal basis vectors? Not sure I have that right but the general idea makes some sense.

I saw it mentioned in a few places (e.g. https://www.youtube.com/watch?v=h6QJLx22zrE ) that the Fourier transform is essentially performing a correlation for each component sinusoid, directly comparing them by multiplying and summing. That was helpful - it’s checking in a simple brute-force way how much a given time signal correlates with different frequencies, rather than taking the signal apart in some more “magical” way.

So I understand how the smoothie filters work :). Why the particular fruits 0 to N-1 Hz are all that’s needed for every possible N-ingredient smoothie is still a little mysterious, but if I get time I’ll brush up on some of the math involved and check out some of the other links people mentioned and hopefully understand it better. Thanks for the elaborations!

Excellent work and really helping way and material. Great work done.

So many good explanations here!
However, I think I have a new perspective here, got some 80 votes on Quora in one week:
https://www.quora.com/What-does-Fourier-Transform-physically-mean/answer/Job-Bouwman
Cheers!

  1. I don’t understand why there is a 1/N in inverse fourier transform rather than fourier transform. I know I am wrong, cuz a lot of equations say that. But my calculation tells me the 1/N should be in the fourier transform. Try [1 3 6 5] in the frequency domain, which is (15 -5 -1 -5) in the time domain,( here N is 4). For example, in 0Hz if you follow the equation, then the the value of the first time spike should be (1 + 3 + 6 + 5) / 4 = 15 / 4, which is different from the result.

  2. When we do the inverse Fourier Transform, the result xn (value of the signal at time n) is real number, so actually we should only take the real part of the complex result on the right, is that correct?

This was pretty neat https://84c67cd8f568acc648fb74bc321df20db70c2600.googledrive.com/host/0B3p9nx7jwyf9MjFtY3d1aXVBMjA/fourier.gif

Hi Kalid,

Excellent article! Great work! I loved mathematics, and have understood lot of concepts intuitively and have liked it learning that way. I never understood Fourier transforms till today.

I was able to memorize and theoretically understood the formulas and get very good grades during my Engineering studies, which was about 20 years ago, but this is the best article on Fourier transforms.

Sreeni

Great article Kalid! I thought I understood Fourier transform during college, but your article has enhanced and refined my understanding.

If you can, please do try to follow up with more topics of college engineering maths - laplace transform, z transform etc. Thanks!

-Bhavya

@Sreeni and @Syed: Thank you!

@Joe: Great question. For the 1/N term, we just need that factor to be applied when doing the transform and then doing the inverse. So, we could have 1/N on the forward transform, or 1/N on the inverse, or 1/sqrt(N) on each part. It’s a convention about where we apply that factor.

When we do the inverse transform, we get our original signal back. If our original signal was purely real, then we’ll get that back. The “ingredient list” (i.e., the result of the forward transform) can have real and imaginary parts since it must track the phase & amplitude of each frequency. Doing the inverse transform means all the imaginary components cancel, leaving us with our original (real) signal. [If we had put in a complex signal in the beginning, the inverse transform would return that complex signal.]

This comment seems misplaced in comparing the smoothie analogy with real world signals. I would say the components that make up the “smoothie” are also whole in their own domain. How did Amit arrive at his differences in comparison ?
Anyone else care to comment ? I would like to see this misconception cleared up.

I would love to see this too. For myself, I started working 14 years ago on a project that employs Signal Processing at its very core and having just touched on SP in college, the real world applications and results that I see still amaze me. I think Fourier’s work would be one of the greatest contributions to real world applications of mathematics and certainly a mixed layman/mathematician history of his life and his discovery would be great. Just like Simon Singh described Cryptography in his book, someone should author one about Fourier.

Hi,
I suppose, that’s a stupid question, but I found no answer…

How on earth did you sum the offsets? Because, if I just sum those with a value that isn’t 0 before up, and put it into your Simulation, I get stupid results… That’s also the case, if I summed all the offsets or took the average… So I’d love to see an explanation, that is as good as the rest of this article about my problem :grinning:
Carl Sagan said “There is no such thing as a stupid question”, so I think my question has a right to be here :relaxed:

TeEmZe

Hi, Kalid.

I found this page when searching for resources relevant to the Discrete Fourier Transform (DFT). I have been reading any and all material I can find on the topic, as well as on the topic of Fourier Transforms in general. The more perspectives I get on the subject, the better. It helps me with my own work.

I do some computer programming and one of the programs I recently wrote was to perform the Fast Fourier Transform (FFT) on a sequence of data points. In addition to verifying results with commercial products when possible, I like to confirm the background material with resources like your site. Having a tutorial like this one available is one more opportunity to learn from another person’s perspective.

Thank-you for taking the time to provide this convenient resource.