Fast Fourier Transform

Gawtham Senthilvelan•November 2025

1. Introduction

"If you wish to make an apple pie from scratch, you must first invent the universe."

That will be the overarching philosophy behind understanding the Fast Fourier Transform (FFT). The FFT is an algorithm that exploits symmetry in the complex domain to reduce the time complexity of transforming a signal from the time domain to the frequency domain from O(N^2) to O(N \log N).

This blog will explain everything from the beginning of signals to the development of the FFT algorithm. Any resource I see online talks about how understanding the math behind FFT is extremely complicated and so they tend to gloss over many of the fundamental details by saying that its simply an algorithm that does the Fourier transform faster. I want to explain everything from its first principles.

2. The Ingredients of Reality

If you blend a banana, a strawberry, and some yogurt, you get a smoothie, and once everything is mixed, there's no way to separate it back into the original fruits. The FFT, remarkably, does the mathematical equivalent of exactly that. It takes a "blended" signal and uncovers the precise ingredients that created it. To understand how this algorithm reshaped modern computing, we first need to understand the recipe of reality itself.

Any type of message that someone tries to send, needs to be done via some sort of signal. The most basic type of signal is a simple sine wave, like we have below.

This sine wave repeats a periodic pattern in a specified amount of time, called its frequency. In this case, it's 5kHz, meaning it repeats that pattern 5000 times within a single second. Let's call this signal bananas. Now imagine, I have another signal, but this one has a frequency of 7kHz instead, and I'll also make the signal stronger by increasing its amplitude. Let's call this signal strawberries.

Now I'll add a 10kHz signal as well to make it look even more complicated. I'll call this signal yogurt. Say now that I add these 3 signals together, how would the new signal look like? Well we would just add the amplitudes together at each point and get what we have below.

The resulting signal is the smoothie. It's the result after adding signals of many different frequencies together. I said before that if we had a smoothie, it is not possible to get the banana, the strawberry, and the yogurt back, but Joseph Fourier would disagree.

3. The Fourier Series

Basically, Joseph Fourier ended up developing a formula to take the resulting signal and break it down to the individual components that make up that signal.

x(t) = \sum_{n=-\infty}^{\infty} c_n e^{j n \omega_0 t}c_n = \frac{1}{T} \int_{T} x(t) e^{-j n \omega_0 t} \, dt

Basically, the first equation tells us that the resulting signal we have is an infinite sum of some certain weight c_n multiplied by a complex exponential. The weights c_n are given by the integral of the signal multiplied by more complex exponentials.

At first this seems complex, but it boils down nicely intuitively. Notice that the complex exponential contains \omega_0which is just a way of representing a frequency. From Euler's formula, we have the following:

e^{j\theta} = \cos(\theta) + j\sin(\theta)

Now it might be easier to see where the first equation comes from. The resulting signal (the smoothie) x(t) is just a sum of a bunch of cosine waves and sine waves at different frequencies.

Key Insight

To find if a specific frequency exists in the signal, we multiply the signal by that frequency and see if it resonates. If you multiply two signals that are the same, you get a huge positive number (Constructive Interference). If they are different, they cancel out to zero (Destructive Interference).

You'll see that idea be used over again throughout the blog, since it's so fundamental in helping us figure out which frequencies are involved. Fourier's idea was basically this—try the smoothie and try a banana—if they taste really familiar then the banana is most likely in the smoothie. Additionally, if they taste really similar, then we know a lot of bananas were used, but if it just tasted slightly similar, then maybe we only added a slice or two.

Notice that when using the second equation, we figure out which fruits are involved in the smoothie. Specifically c_n will be 0 at frequencies that are not in the smoothie. We should think about this as taking the signal in the time domain (the sine wave earlier) to the frequency domain, shown below. The amplitude of the lines just signify the weight of how much that frequency contributes to the resulting signal.

In effect, we took the smoothie and got the banana, apple, and yogurt back.

4. The Fourier Transform

We should note that the above formulas only work when we are working with a signal that is periodic. What if the signal isn't periodic? That issue is also solved by the formula below:

X(\omega) = \int_{-\infty}^{\infty} x(t) e^{-j\omega t} \, dt

We see that we can take the signal we want to deconstruct and multiply it with a complex exponential to sift and find which frequencies make up that signal.

The important thing to consider is that when we have a periodic signal, the Fourier equations show that we can directly represent that as a sum of sines and cosines at discrete frequencies. But if the signal is not periodic, we would effectively need an infinite number of sines and cosines at different frequencies to make up that signal, so in the frequency domain, it would be continuous.

5. The Discrete Fourier Transform

Here's the issue with everything we've talked about so far. We use the Fourier transform to take a signal that represents some message, and convert it to the frequency domain so we can interpret what's really going on. This is usually done by a computer.

The problem lies in the fact that a computer can't actually perform integration since it's a continuous operation; it can only work with lists of numbers. This is why we have to sample our signal in order for the computer to work with the numbers we have, which effectively makes the integration become a summation. This is the birth of the Discrete Fourier Transform.

X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j\frac{2\pi}{N}kn}

The above is the formula for the discrete Fourier transform, a Fourier transform that the computer can actually understand. Imagine instead of working with the entire smoothie all together, we work with many smaller pieces to figure out what fruits were used.

Breaking down the formula in a more intuitive way, the complex exponential once again appears since it helps us figure out which frequencies are in our signal. Since this complex exponential shows up so much, why don't we just call it something else to make it look scary? That's where the Twiddle Factor comes in.

W_{N} = e^{-j\frac{2\pi}{N}}

This is just a nicer way to represent these complex exponentials so we don't have to keep writing them over and over again.

You might ask what does the N represent? Imagine in the time domain we have some continuous signal, but we can only have discrete lists of values, so we take a snapshot of the signal, and take a sample every so often. N represents the number of samples we are using. If you think about it, N is like a knob for our frequency resolution.

Let's think about how many computations we would actually need to perform if we wanted to do DFT. We would need to multiplyN samples by N different "frequency bins", resulting in N^2 computations.

But if we think about this a little more carefully, we notice something interesting. The twiddle factor is just a complex exponential, and complex exponentials have some interesting properties. Especially with symmetry.

6. The Fast Fourier Transform

As mentioned before, the Fast Fourier Transform exploits symmetry and properties of the twiddle factor in order to use fewer computations. Basically, it allows us to use some twiddle factor multiple times so we don't have to waste precious compute power to recalculate every time.

Well firstly, we need to understand the symmetry properties of the twiddle factor.

W_{N}^{k+N/2} = -W_{N}^{k}

W_{N}^{k+N} = W_{N}^{k}

To convince yourself these statements are true, all we need to do is write it as the complex exponential and expand out the terms. For example:

W_{N}^{k+N/2} = (e^{-j\frac{2\pi}{N}})^{k+\frac{N}{2}} = e^{-j\frac{2\pi}{N}k} \cdot e^{-j\frac{2\pi}{N}\cdot\frac{N}{2}}

↓

= W_{N}^{k} \cdot e^{-j\pi} = W_{N}^{k} \cdot (-1) = -W_{N}^{k}

In the complex plane, an angle of \pi (or 180°) points exactly to the left. It is equal to -1.

Divide and Conquer

Remember when we first introduced the idea of breaking down something into smaller pieces earlier? We can try breaking down the N-DFT into 2 smaller N/2-DFTs and then just combine the results.

We can split the summation into two separate piles: the indices that are even numbers (n=0, 2, 4...) and the indices that are odd numbers (n=1, 3, 5...).

X[k] = \sum_{\text{even}} x[n]W_{N}^{kn} + \sum_{\text{odd}} x[n]W_{N}^{kn}

With a little bit of algebra (using exponent rules), we can simplify these terms. The "Even" part looks exactly like a DFT of size N/2. The "Odd" part also looks like a DFT of size N/2, just multiplied by a twiddle factor out front.

X[k] = DFT_{even}[k] + W_{N}^{k} \cdot DFT_{odd}[k]

But what about the second half of the frequencies? What happens when we look at index k + N/2? This is where the geometry of the universe saves us work.

Since the Even and Odd parts are smaller DFTs, they are periodic. They repeat themselves every N/2 steps. The only thing that changes is the Twiddle Factor.

Because the rotation factor turns into a -1 (as we proved earlier), the equation for the second half becomes:

X[k + N/2] = DFT_{even}[k] - W_{N}^{k} \cdot DFT_{odd}[k]

The Butterfly Effect

From just two calculated values (Even and Odd), we can generate two output frequencies:

Top Output: A + WB
Bottom Output: A - WB

We get two outputs for the price of one multiplication. This is the secret to the speed of the FFT.

So how many computations are we doing now? We would be splitting up the DFT into 2 smaller DFTs each time, and the number of times we split is equal to \log_2 N. In each stage we do N computations. So we would have N \log_2 N total computations.

So in summary, we've not only figured out what fruits made up the smoothie, not only did we do it in a way that a computer can do it for us, we designed an algorithm to compute it significantly faster than how we would normally do it.