{"id":276,"date":"2015-05-29T06:38:48","date_gmt":"2015-05-29T05:38:48","guid":{"rendered":"http:\/\/www.billconnelly.net\/?p=276"},"modified":"2025-07-05T04:15:10","modified_gmt":"2025-07-05T03:15:10","slug":"visualizing-how-ffts-work","status":"publish","type":"post","link":"https:\/\/www.billconnelly.net\/?p=276","title":{"rendered":"Visualizing how FFTs work."},"content":{"rendered":"

A lot of scientists have performed Fast Fourier Transforms at some point, and those that haven’t, probably are going to in future, or at the very least, have read a paper using it. I’d used them for years before I ever began to think about how they algorithm actually worked. However, if you’ve ever looked it up, unless math is your first language, the explanation probably didn’t help you a lot. Normally you either get an explanation along the lines of “FFTs convert the signal from the time domain to the frequency domain” or you just get this:<\/p>\n

$latex X_{(k)}\\ = \\sum_{n=0}^{N-1} x_{(n)} \\cdot e^{-2 \\pi i k n \/ N} &s=2$<\/div>\n

However, the other day I came across an amazing explanation of the algorithm, and I really wanted to share it. While I might not be able to get you to the point that you completely understand the FFT, I think think it might seriously enhance your understanding.
\n<\/p>\n

So the first thing, I kind of lied to you. I’m not going to show you how the F<\/strong>FT algorithm works. I’m going to show you how discrete Fourier Transforms works. The FFT is just a fast way of computing the DFT.<\/p>\n

So the beautiful explanation I read came from here<\/a>. They color code the equation to show you how the various parts work.<\/p>\n

\"DFT\"<\/a><\/p>\n

A lot of that may not be immediately obvious, though realizing that $latex e^{2 \\pi i x} $ carves out a circle in the imaginary plane is a great start. The real beauty comes from the following textual explanation:<\/p>\n

Imagine an enormous speaker, mounted on a pole, playing a repeating sound. The speaker is so large, you can see the cone move back and forth with the sound. Mark a point on the cone, and now rotate the pole. Trace the point from an above-ground view, if the resulting squiggly curve is off-center, then there is frequency corresponding the pole’s rotational frequency is represented in the sound. <\/p><\/blockquote>\n

There is an animation demonstrating that on the above page, but I felt a full interactive version might be helpful.<\/p>\n

Enter in some details for two sine waves that will be summed to make your signal (graph to the left). The script will then play this waveform into our “rotating speaker” (graph to the right) which will rotate at increasing frequencies. After the waveform is played in, a red line will show up, representing a vector for the mean position of our “speaker”. The length of this vector represents the magnitude of our signal at that frequency and the angle represents the phase. The magnitude of the signal is then presented on the bottom graph, which is our DFT. Note how if you change the amplitude of your input sine waves, the length of the vector gets longer, if you change the phase, the vector points in a different direction and if you change the frequency, the vector only has a significant length when then “speaker” is rotating at that frequency. The cool thing is, while there is a lot of unnecessary graphics, the meat of this function performs a real DFT, albeit incredible slowly.
\n