So, I was binge-watching Veritasium's YouTube the other day. During this binge-watch session, I stumbled upon a very interesting video about Fast Fourier Transforms. (I've always loved watching Veritasium videos. They have such a unique way of balancing science, history and of course, entertainment.) It was a fascinating watch, explaining how any signal can be broken down into sine waves. FFT was nothing new for me. I've had a mandatory major in my college years. TBH, I was not very thrilled about it but it was mandatory so I had to take it. In that, I had learned about Fourier Transforms and it's cousin - FFT. At that time, it felt a burden, but after re-watching this gem of a video from Veritasium, my curiosity sparked. So I dug deeper.

The Video referred another one of my favourite YouTuber's video for Fourier Transform - 3Blue1Brown. I had already seen that video on Fourier Transform, but this time, it was different. I was curious and willing to learn more from it. His visualizations are just incredible - the way he animates concepts that seemed so abstract before. I spent hours watching it, rewinding, trying to truly understand every bit of it.

Then, I thought let me read some papers, articles about this. So I did that for a week or so, finding anything and everything that would make it easy for me to understand the concept intuitively. And it worked! The more I learned, the more I realized how fundamental this concept is. It's everywhere - in the music we stream, the images we share, the medical scans that save lives. I was in awe.

But then came the realization. I have tendency to forget things and I knew I was going to forget it all if I don't write it down. But I just didn't want to write it down. It's never the same when you try to read it back or give it to someone else to read. So, as I did with Merkle Trees , I tried building the understanding into an interactive article. One other reason was, wanting to create something like those beautiful illustrations that Grant Sanderson had made in his video - interactive, visual, intuitive. So, I've tried my best to do that here (of course, with the help of agents!). This will be a bit longer article than the previous one, but hope you enjoy it as much as I did while researching and writing it.

A little bit of History

The story of the Fourier Transform begins in 1807, when a French mathematician (it's almost always a french dude!) named Jean-Baptiste Joseph Fourier presented a paper to the French Academy of Sciences. He made a bold claim: any periodic function, no matter how complicated or irregular, could be expressed as a sum of simple sine and cosine waves. The Academy was skeptical, as one would expect. The idea just seemed too good to be true.

Two centuries later, however, Fourier's insight has become one of the most consequential ideas in all of science and engineering. Every time you listen to an MP3 or make a phone call or look at a JPEG image or use voice recognition, you're relying on Fourier's decomposition. MRI machines, seismographs, radio telescopes, quantum computers - all depend on it. Its impact is quite astonishing.

Yet despite its ubiquity, the Fourier transform remains mysterious. Maybe because of the math. It can be intimidating at times - complex exponentials, integrals to infinity, abstract function spaces. But the core idea is beautifully intuitive (as you'll see). Okay, so let's build that intuition from the ground up, with my honest attempt at making these interactive visualizations at every step.

Signals and the Language of Signal Processing

Before we dive into Fourier's idea, we need to talk about what signals are. In the most general sense, a signal is just a quantity that varies over time (or space, or any other dimension). The voltage coming out of a microphone as you speak is a signal. The air pressure oscillations of a musical note is a signal. Your heartbeat over a minute is a signal. The daily temperature over a year is a signal. The stock price over a decade is a signal.

We encounter signals constantly in our everyday life, but we rarelyconsciously think about them in a structured way. Keyword here is consciously because subconsciously (or unconsciously - don't know which one) we do perceive them in the time domain. When you hear a sound, your brain does something remarkable: it separates the sound into its component frequencies. You can distinguish a piano from a guitar playing the same note because they have different frequency content - different combinations of harmonics. Your ear is identifying signal and performing a kind of Fourier transform in real-time.

The demo above shows a few common signal patterns. Notice how different they look in the time view - the raw signal plotted over time. A heartbeat has sharp spikes. Speech-like signals look complex and uneven. A musical tone looks more regular. Yet each of these can be broken into simple sine waves, each with its own frequency, amplitude, and phase. That's the core idea behind Fourier analysis.

One quick note: this demo uses relative frequency bins to build intuition, not exact real-world units like Hz.

Sine Waves: The Building Blocks

The sine wave is the fundamental building block of Fourier analysis. Why sine waves specifically? Because they're the simplest possible periodic motion - the projection of uniform circular motion onto a line. When you swing a pendulum, bounce on a spring, or pluck a guitar string, the resulting motion is a sine wave (or a combination of sine waves).

A sine wave (or any periodic wave, for that matter) is completely characterized by three parameters:

• Frequency - How fast it oscillates. Measured in Hertz (Hz), meaning cycles per second. A 440 Hz wave completes 440 full cycles every second.
• Amplitude - How tall the wave is. This determines loudness in sound, or brightness in light. It's the "strength" of that frequency component.
• Phase - Where in its cycle the wave starts. Two waves can have the same frequency and amplitude but be shifted relative to each other. Phase is usually measured in degrees or radians.

Combining all these, we get a periodic wave. As everything else, we can represent it mathematically as a wave function. It's quite simple:

where A is amplitude, f is frequency, t is time, and φ (phi) is phase.

Play with the sliders above. Notice how frequency squeezes the wave horizontally. Amplitude controls the vertical extent. Phase shifts the entire wave left or right. These three parameters give us complete control over any sine wave.

Superposition: Combining Waves

Here's where things get interesting. What happens when we add multiple sine waves together? The answer is superposition: we simply add the values at each point in time. If wave A has value 0.5 at time t=1, and wave B has value 0.3 at t=1, the combined wave has value 0.8 at t=1.

This simple addition creates remarkable complexity. Two sine waves of different frequencies create a beating pattern. Three waves create even more intricate shapes. With enough sine waves of carefully chosen frequencies and amplitudes, you can create any shape you want. That's Fourier's revolutionary claim.

The demo shows individual sine waves and their sum. Try adjusting the frequencies to be related by simple ratios (like 1:2:3) - you'll get a clear repeating pattern. Then try larger or mixed ratios and watch the shape become more intricate before it repeats. This is why even simple sine waves can combine into rich, complex signals.

Fourier's Big Idea: Decomposition

We've seen that adding sine waves creates complex shapes, but Fourier's insight was the reverse: any signal can be decomposed into sine waves. Given any periodic function, there exists a unique set of frequencies, amplitudes, and phases that sum together to recreate it perfectly.

Think about what this means. A square wave - that sharp, discontinuous shape used in digital circuits - is actually an infinite sum of smooth sine waves. A triangle wave, a sawtooth wave, your voice saying "hello", the Wi-Fi signal carrying this webpage to your device - all of them are just collections of sine waves in disguise. Amazing, right!

This decomposition gives us a completely different way of thinking about signals. Instead of asking "what's the value at each moment in time?" (the time domain), we can ask "how much of each frequency is present?" (the frequency domain). Both representations contain exactly the same information, but different operations become easier in each domain.

Draw any wave you like in the demo above, then watch as it's decomposed into its frequency components. The bar chart shows the spectrum - the amplitude of each frequency present in your drawing. Simple shapes have simple spectra; complex shapes have rich, detailed spectra.

Fourier Series: Building Familiar Shapes

For periodic signals, the decomposition takes a special form called the Fourier series. The frequencies involved aren't arbitrary - they're all integer multiples of a fundamental frequency. These integer multiples are called harmonics. The 2nd harmonic has twice the frequency of the fundamental, the 3rd harmonic has three times, and so on.

Let's see this concretely with a square wave. A perfect square wave jumps instantly between +1 and -1. Its Fourier series turns out to contain only odd harmonics (1, 3, 5, 7...) with amplitudes that decrease as 1/n:

The more terms we include, the closer we get to a perfect square wave. With just 10 terms, it's recognizably square. With 100 terms, it's nearly indistinguishable. With infinite terms, it's exact.

Use the slider to add more harmonic terms. Watch how each new sine wave refines the shape. The individual components are shown below, each contributing its part to the whole. This is the essence of Fourier synthesis.

The Gibbs Phenomenon

In the above examples, you must have noticed one thing - the spikes in the Fourier series when there is sudden change in the amplitude. it's an overshoot of around ~9% that always happens - no matter how many terms we add to our series. This is the Gibbs phenomenon, discovered in 1899. It's not a flaw in Fourier's theory - it's a fundamental limitation we face when representing discontinuities with smooth waves. Adding more terms to the series makes the overshoot narrower, but never smaller in amplitude.

Notice the "ringing" near the edges. This same phenomenon appears in real-world signal processing. It causes artifacts in images (ringing near sharp edges) and audio (pre-echo before transients). Engineers have developed various window functions and filtering techniques to minimize it.

Sampling and the Nyquist Theorem

In the mathematical world, signals are continuous - defined at every instant of time. But as you port it into digital realm (computers live in a discrete world), We can only store a finite number of values, sampled at specific moments. So, how do we bridge this gap?

The answer is sampling. So, we measure the signal at regular intervals - say, 44,100 times per second for CD-quality audio. The critical insight from the Nyquist-Shannon sampling theorem is that if we sample at more than twice the highest frequency of the signal, we can perfectly reconstruct the original continuous signal.

For audio, human hearing extends to about 20 kHz, so we need to sample at more than 40 kHz. CD audio uses 44.1 kHz, providing some margin. The Nyquist frequency is half the sampling rate: 22.05 kHz for CD audio.

What happens if we sample too slowly? We get aliasing. High frequencies masquerade as lower ones. You've seen this in old movies where wagon wheels appear to spin backwards - the film's frame rate isn't high enough to capture the true rotation speed.

The demo shows a continuous wave and its sampled version. Reduce the sampling rate below the Nyquist limit and watch aliasing occur - the reconstructed wave shows a completely different frequency than the original. This is why CD players, digital cameras, and other devices include "anti-aliasing" filters before sampling.

The Discrete Fourier Transform

With sampled signals, we need a discrete version of the Fourier transform. Enter the Discrete Fourier Transform (DFT). Given N samples of a signal, the DFT produces N frequency components. But how does it actually work?

The intuition is beautiful: to find how much of a particular frequency is in the signal, we correlate the signal with a sine wave of that frequency. Multiply sample by sample, then sum. If the signal contains that frequency, the products will mostly have the same sign, giving a large sum. If it doesn't, positive and negative products will cancel out, giving a small sum.

We do this for N different frequencies:

The e^(-i2πkn/N) is just a compact way of writing a sine and cosine wave (via Euler's formula). The result X[k] is a complex number whose magnitude tells us the amplitude of frequency k, and whose angle tells us the phase.

Step through the DFT computation above. Watch how each frequency bin is computed by correlating the signal with a reference sine wave. High correlation (bright bar) means that frequency is present; low correlation means it's absent. Toggle "Show Phase" to see the phase information for each frequency component-magnitude tells us "how much" of a frequency is present, while phase tells us "when" it occurs in the cycle.

Real Signals and Conjugate Symmetry

Most signals we encounter-audio, images, sensor data-are real-valued(not complex). This creates a special symmetry in the DFT output called conjugate symmetry: the spectrum for positive frequencies is the mirror image of the negative frequencies, with complex conjugate phase.

Practically, this means we only need to look at the first N/2+1 frequency bins for real signals. The second half contains no new information-it's completely determined by the first half. This is why audio spectrum analyzers only show 0 Hz to Nyquist frequency, even though the full DFT produces N complex values.

Frequency Resolution

The DFT divides the frequency range into N equally-spaced "bins". More samples means more bins, which means finer frequency resolution. But there's a fundamental tradeoff: more samples also means a longer time window, which reduces time resolution. You can know precisely what frequencies are present, or precisely when they occur, but not both at once.

Adjust the number of samples and watch how the frequency bins change. Fewer samples = fewer, wider bins. More samples = more, narrower bins. This tradeoff is fundamental and leads to the uncertainty principle we'll discuss later.

Spectral Leakage and Windowing

Here's something surprising: even a pure sine wave might not appear as a single spike in the DFT. If the signal's frequency doesn't align perfectly with one of the DFT bins, its energy "leaks" into nearby bins, creating a broad spectrum instead of a sharp peak.

This happens because the DFT assumes the signal repeats periodically. When the frequency doesn't align, there's a discontinuity where the end of the window tries to connect to the beginning-like trying to join two mismatched puzzle pieces.

The solution is windowing: multiply the signal by a function that smoothly tapers it to zero at the edges. This reduces the discontinuity at the cost of slightly reduced frequency resolution. Common windows include Hann, Hamming, and Blackman.

Try setting the frequency to a non-integer value (like 5.5 Hz) with "No Window" selected-watch how the spectrum spreads across multiple bins. Then switch to "Hann Window" and see how the leakage is reduced, though the peak becomes slightly wider.

Zero Padding and Interpolation

Here's a subtle point about the DFT: adding zeros to the end of your signal (called zero padding) increases the number of frequency bins in the output, but it doesn't actually improve frequency resolution. It just interpolates between the existing frequency samples, giving you a smoother-looking spectrum.

Think of it this way: frequency resolution is determined by the length of time you observe the signal (the "time window"). A longer observation gives better frequency resolution because you can distinguish slower oscillations. Zero padding doesn't extend your observation time-it just adds computed samples between the frequencies you could already measure.

Zero padding is still useful for visualizing spectra (smoother curves) and for making the signal length a power of 2 (required for efficient FFT). Just remember: you can't create information that wasn't in the original signal by adding zeros!

Reading the Spectrum

The output of a Fourier transform is called the spectrum. It shows the frequency content of a signal - which frequencies are present and how strong each one is. Learning to read spectra is essential for audio engineering, signal processing, and many areas of science.

A pure sine wave has a spectrum with a single spike at its frequency. A square wave has spikes at odd harmonics (1×, 3×, 5×...) with decreasing amplitudes. Speech and music have rich, continuously varying spectra.

Real-time spectrum analyzers show how a signal's frequency content evolves over time. They're ubiquitous in audio production software, radio equipment, and scientific instruments. Let's build one.

This spectrum analyzer processes audio in real-time. If you allow microphone access, try whistling - you'll see a peak move up and down as you change pitch. Speak and watch the complex pattern of formants that make up your voice. The "waterfall" view shows how the spectrum evolves over time.

The Computational Complexity of DFT

There's a problem with the DFT as we've described it. For each of the N frequency bins, we need to compute a sum over N samples. That's N × N = N² operations. For audio processing with 44,100 samples per second, that's almost 2 billion multiplications every second. Modern CPUs can handle this, but barely - and real-time processing with margin to spare would be impossible.

The computational complexity is O(N²), meaning doubling the signal length quadruples the computation time. For large signals, this quickly becomes prohibitive.

Watch the O(N²) growth in action. Each dot represents a multiplication. Even going from 8 to 32 samples increases the work dramatically. Now imagine millions of samples. We need something faster.

The Fast Fourier Transform

In 1965, Cooley and Tukey published what's been called the most important algorithm of the 20th century: the Fast Fourier Transform (FFT). It computes the exact same result as the DFT, but in O(N log N) time instead of O(N²). For a million samples, that's about 50,000 times faster.

Interestingly, the algorithm wasn't truly new. Carl Friedrich Gauss had discovered the same method in 1805-predating even Fourier's work!- but never published it. It was rediscovered by Danielson and Lanczos in 1942, then again by Cooley and Tukey when the digital computer age made fast computation essential.

The key insight is divide and conquer. The DFT of N points can be split into two DFTs of N/2 points - one for even-indexed samples, one for odd. These can be combined with just N operations. Apply this recursively: each N/2-point DFT splits into two N/4-point DFTs, and so on, until we reach trivial 1-point DFTs.

The combination step is called the butterfly operation, named for the shape of its data flow diagram. Each butterfly combines two values to produce two new values, using a "twiddle factor" (a complex exponential that depends on the position).

The diagram shows how data flows through the FFT. Notice the recursive structure: at each stage, we combine pairs of results from the previous stage. The total number of operations is N × log₂(N) instead of N².

The Speedup in Practice

How much faster is the FFT? Let's race them.

At small sizes, the difference is modest. But watch what happens as N grows. By the time we hit 1024 samples, the FFT is an order of magnitude faster. At 65,536 samples (about 1.5 seconds of CD audio), the FFT takes microseconds while the DFT would take seconds. This speedup is what makes real-time audio processing, video compression, and countless other applications possible.

Audio Processing Applications

Audio is perhaps the most intuitive domain for understanding Fourier transforms. We perceive sound as combinations of frequencies - that's literally what pitch is. The Fourier transform lets us manipulate these frequencies individually.

Equalization

An equalizer (EQ) boosts or cuts specific frequency ranges. Want more bass? Boost the low frequencies. Want to reduce vocal sibilance? Cut around 5-8 kHz. In the frequency domain, this is just multiplication - multiply each frequency bin by a gain factor.

Drag the sliders to shape the frequency response. This is exactly how the EQ in your music player works. The FFT converts audio to frequency domain, applies the gains, and the inverse FFT converts back to audio you can hear.

Noise Reduction

Many noise reduction algorithms work in the frequency domain. If noise is confined to certain frequencies (like a 60 Hz power line hum), we can simply remove those frequencies. More sophisticated algorithms estimate the noise spectrum and subtract it from the signal spectrum.

The demo adds noise to a clean signal, then filters it in the frequency domain. Adjust the filter cutoff to see how different settings affect noise removal vs. signal preservation. This tradeoff - removing noise while keeping the signal - is the core challenge of all noise reduction.

Image Processing Applications

The Fourier transform works in two dimensions as well as one. For images, we transform both horizontally and vertically, revealing spatial frequencies instead of temporal ones. Low spatial frequencies correspond to gradual variations (like smooth color gradients), while high frequencies correspond to sharp edges and fine details.

The 2D spectrum shows frequency content in all directions. The center represents low frequencies (slow variations), while the edges represent high frequencies (rapid variations). Patterns in the image - like stripes or textures - appear as corresponding patterns in the spectrum.

Image Filtering

Just as we filter audio by modifying frequency components, we can filter images by modifying spatial frequency components. A low-pass filter keeps low frequencies and removes high ones - this blurs the image. A high-pass filter does the opposite - it extracts edges and fine details. These operations are fundamental to image compression, enhancement, and analysis.

The JPEG image format uses a variant of the Fourier transform (the Discrete Cosine Transform) to achieve compression. High-frequency components - which the eye is less sensitive to - are quantized aggressively or discarded entirely. This is why highly compressed JPEGs look "blocky" - they've lost their high-frequency detail.

Beyond Media: Convolution and More

One of the most powerful applications of the FFT is computing convolutions. Direct convolution is O(N²), but thanks to the convolution theorem, we can compute it in O(N log N) by using FFTs: convolution in the time domain equals multiplication in the frequency domain.

The demo shows convolution computed both ways - directly and via FFT. The results are identical, but the FFT method is dramatically faster for large inputs. This technique is used everywhere: reverb simulation in audio, blur effects in graphics, pattern matching in signal processing.

Beyond Media: Where Else is FFT Used?

The applications extend far beyond media processing:

• Wireless communications - OFDM, the modulation scheme used by WiFi and 4G/5G, is basically a massive FFT/IFFT system
• Medical imaging - MRI machines use the FFT to reconstruct images from raw signal data
• Spectroscopy - Analyzing the chemical composition of materials from their absorption spectra
• Seismology - Processing earthquake data to understand Earth's structure
• Astronomy - Radio telescopes use FFT-based aperture synthesis to create images
• Quantum computing - The quantum Fourier transform is central to Shor's factoring algorithm
• Polynomial multiplication - Surprisingly, FFT is the fastest known way to multiply large polynomials (and by extension, large integers)

The Uncertainty Principle

We've mentioned the tradeoff between time and frequency resolution. This isn't just a practical limitation - it's a fundamental mathematical fact known as the Gabor limit, named after Dennis Gabor (who also invented holography).

The uncertainty principle states: you cannot simultaneously have precise knowledge of both when a frequency occurs and exactly what that frequency is. Short analysis windows give good time resolution but poor frequency resolution (wide frequency bins). Long windows give the opposite.

This is mathematically analogous to Heisenberg's uncertainty principle in quantum mechanics (position vs. momentum). In both cases, the fundamental issue is that the quantities are related by Fourier transforms, and narrow signals in one domain necessarily spread out in the other.

Adjust the "pulse width" parameter. A short pulse is well-localized in time but has a broad spectrum (many frequencies). A long pulse has a narrow spectrum (nearly a single frequency) but is spread out in time. The product of the spreads is constant - this is the uncertainty principle in action.

Conclusion

Fourier's insight - that complex signals can be built from simple sine waves - is one of those ideas that seems obvious in hindsight but took genius to discover. It gives us a completely different way to understand signals, revealing patterns and structure that are invisible in the raw data.

The FFT algorithm made this insight practical, turning a mathematically beautiful idea into a computationally tractable one. Without it, real-time audio processing, digital communication, and modern signal processing would be impossible.

What I find most remarkable is the universality. The same mathematics that describes vibrating violin strings describes radio waves, medical images, and quantum states. The same algorithm that compresses your music can multiply billion-digit numbers. Nature seems to speak in frequencies, and Fourier gave us the dictionary.

Next time you listen to a compressed audio file, look at a JPEG image, or use WiFi, remember: somewhere in the silicon, billions of butterflies are dancing through the data, transforming it from the chaos of raw samples into the elegant clarity of frequency space and back again. It's one of humanity's greatest intellectual achievements, hidden in plain sight in every pocket and every home.

References