This includes some math

What is Fourier Transform?

A good analogy would be, it can tell you the ingredients of a cocktail when you feed this algorithm with the cocktail.

A more accurate definition would be, it allows us to decompose a complex signal into it’s components.

But it’s not only that! There is a faster version, which is Fast-Fourier-Transform (FFT). Because, yes, Fourier Transform takes too much time to compute. Whereas FFT takes a very little time to compute the very same thing.

FFT might be the algorithm that has the most diverse application areas. For example:

• image processing/compressing (for example WhatsApp uses Fourier Transform for compressing the video/image you send)
• signal processing (the whole electric engineering industry and more specifically, nearly the whole audio industry)
• noise reduction in both images and signals
• much much faster multiplication (used in advanced cryptography). I want to emphasize this. Imagine how hard it is to improve something so essential and primitive. We are talking about the multiplication operation itself here.
• You probably heard about quantum computing, and as a defense mechanism, post-quantum-cryptography. FFT plays a very important role in post-quantum-cryptography area.
• and probably in many more fields that I don’t even know…

A tool that is useful in both decomposing waves, and also performs faster multiplication, is like a magic. So I’ve decided to understand the intuitions behind as best as I can. On the internet, you may find abundant amount of resources related to FFT, Fourier Transform, and Fourier Series.

However, it took me watching around 20 videos, and reading many blog posts, and asking a few questions on reddit myself to fully understand the intuitions behind FFT. And some of these intuitions, I’ve discovered them myself, so I’m not even sure if they are available on the internet as direct as I will explain here.

In this post, I’ll try to communicate all my intuitions. My aim is: anybody reading this post, should be able to answer every possible why question on the FFT (especially its relation with signal decomposing and faster multiplication).

Fun fact (actually sad fact):

If FFT was invented a couple of years before, probably no country would have nuclear weapons in their arsenal. The reason is, back then, the scientist were able to detect nuclear tests executed in the water or air, but they couldn’t separate the nuclear tests executed deep in earth from earthquakes. This was a huge gap for banning nuclear weapons, because a country could test their hidden nuclear weapons under the ground, and claim that these were just earthquakes.

With FFT however, the scientist would be able to separate the nuclear tests from earthquakes. Recall that, FFT allows efficient signal decomposition, and that would allow scientist the distinguish that complex signals from earthquake and nuclear weapon testings in a reasonable time. And ultimately, a global ban on the testing nuclear weapons would be successful.

Since the discovery of FFT was late, several countries already tested nuclear weapons and employed them in their arsenal. And nuclear weapons became stable. So it’s too late now.

GG WP…

Another fun fact:

• Gauss did find FFT in 1805. Gauss was studying the newly found asteroids (Pallas, Ceres and Juno). To determine the orbit of Juno, Gauss devised a novel approach to harmonic analysis. And he noted it down but later used a different method. And he never thought of publishing that first insight (FFT).

This is pure tragicomedy! FFT was just a couple of years late to prevent nuclear arming, but in fact, it was available 1.5 century earlier! LOL

That was probably the worst introduction ever, since I made you hate FFT.

Below are the chapters, I recommend reading them in order if you are unfamiliar with them.

How does Fourier Transform decompose signals

Deriving the formula

How does Fourier Transform Multiply Numbers?

FFT and NTT