DFT & FFT Basics

What the DFT Does

In Lesson 1 we learned that any signal can be decomposed into sinusoids. The Discrete Fourier Transform (DFT) is the mathematical tool that performs this decomposition on a discrete (sampled) signal.

Given N samples of a signal in the time domain, the DFT produces N complex numbers in the frequency domain. Each complex number tells you two things about one specific frequency: how strong that frequency is (magnitude), and where in its cycle it starts (phase).

Think of the DFT as a prism that splits white light into its rainbow of constituent colors — except instead of light, it splits a signal into its constituent frequencies.

The DFT Formula

The DFT of a sequence x[0], x[1], \ldots, x[N-1] is defined as:

Let's unpack this piece by piece:

• x[n] — The input: your time-domain samples (the signal you recorded or generated).
• X[k] — The output: a complex number for frequency bin k.
• N — The total number of samples (also the total number of frequency bins).
• e^{-j\,2\pi\, k\, n / N} — A complex sinusoid at frequency k. This is the "test tone" being compared against the signal. (Recall Euler's formula from Lesson 1.)
• \sum — We multiply each sample by the test tone and sum the results. This is essentially a correlation — measuring how much the signal resembles that frequency.

The DFT computes this for every value of k from 0 to N-1, giving you a complete frequency-domain picture.

Frequency Bins and Resolution

Each index k in the DFT output corresponds to a specific frequency, called a frequency bin. If your sampling rate is f_s Hz and you have N samples, then:

The spacing between bins — the frequency resolution — is:

This tells you something important: to get finer frequency resolution, you need more samples. For example, at a 1000 Hz sampling rate with 1000 samples, each bin is 1 Hz wide. With only 100 samples at the same rate, each bin is 10 Hz wide — you can't distinguish frequencies less than 10 Hz apart.

Also note that only the first N/2 + 1 bins contain unique frequency information for real-valued signals. The remaining bins are mirror images (complex conjugates). This is why FFT plots typically show only the "positive" half of the spectrum.

Interpreting the Output: Magnitude & Phase

Each DFT output X[k] is a complex number a + jb. We extract two useful quantities from it:

• Magnitude |X[k]| = \sqrt{a^2 + b^2} — How strong frequency k is in the signal. A tall bar in the spectrum means that frequency is prominent.
• Phase \angle X[k] = \text{atan2}(b, a) — The starting angle (shift) of that frequency component. Phase is critical for reconstructing the original signal but is often less intuitive to interpret visually.

Most spectrum visualizations show the magnitude spectrum — a bar or line chart of |X[k]| vs. frequency. Try computing one yourself in our FFT Calculator.

What Is the FFT?

The Fast Fourier Transform (FFT) is not a different transform — it computes exactly the same result as the DFT. The difference is speed.

A naïve implementation of the DFT formula requires O(N^2) operations. The FFT (discovered by Cooley and Tukey in 1965, though the idea dates back to Gauss) cleverly reuses partial results to reduce this to O(N \log N).

How big is the difference? For N = 1{,}048{,}576 (about 1 million samples — roughly 24 seconds of CD audio):

• Naïve DFT: ~1 trillion operations
• FFT: ~20 million operations

That's roughly 50,000× faster. The FFT made real-time spectrum analysis, MP3 encoding, MRI imaging, radar, and countless other technologies practical. It's been called one of the most important algorithms of the 20th century.

Practical Tips

• Use power-of-2 sizes (256, 512, 1024, …). Most FFT implementations are fastest when N is a power of 2. Pad your signal with zeros if needed.
• Apply a window function before the FFT to reduce spectral leakage (energy smearing across bins). Common windows: Hann, Hamming, Blackman.
• Normalize if comparing spectra. Divide magnitudes by N (or N/2 for single-sided spectra) to get amplitude-correct values.