DFT and FFT Algorithms: Complete Beginner's Guide Guide.

The Discrete Fourier Transform, or DFT, converts a finite list of N sampled signal values into N numbers showing how much of each frequency the signal contains. If the samples are the heights of a sound wave from a microphone, the DFT reveals which musical notes hide inside it and how loud each one is.

This matters because nearly every device handling sound, images or radio needs frequency information. Audio compression, mobile signals, medical scanners and Wi-Fi all move signals between time and frequency domains. The Fast Fourier Transform, or FFT, computes exactly the same DFT result but hundreds of times faster, which made all these applications practical.

Key Concepts

• X[k]: the k-th DFT output, a complex number whose magnitude is the strength and whose angle is the phase of the k-th frequency component.
• Frequency bins: the N outputs sit at frequencies k·fs/N, where fs is the sampling rate in Hz.
• Twiddle factor: W_N = e^(−j2π/N), the unit-magnitude complex rotation used in every DFT sum.
• Nyquist limit: for real signals only bins up to N/2 are unique; bin N/2 sits at fs/2, the highest representable frequency.
• Spectral leakage: if the block holds a non-integer number of cycles, energy smears across neighbouring bins instead of landing in one.
• Complexity: direct DFT needs about N² operations; the FFT needs about N·log2(N).

Formulas

• DFT: X[k] = sum of x[n]·e^(−j2πkn/N) for n = 0 to N−1. Each bin is a weighted sum of all samples with rotating complex weights.
• Inverse DFT: x[n] = (1/N) times the sum of X[k]·e^(+j2πkn/N) for k = 0 to N−1.
• FFT saving: the work ratio is roughly N/log2(N); for N = 1024 the FFT needs about 10,240 operations instead of 1,048,576, around 100 times fewer.
• Assumption: the math treats the finite block as repeating forever, which is exactly why leakage appears for non-integer cycle counts.

Worked Example

Compute the 4-point DFT of x = [1, 2, 3, 4]. Bin 0 is the sum: X[0] = 10. For bin 1, the twiddle powers are e^(−jπ/2) = −j, e^(−jπ) = −1, e^(−j3π/2) = +j, so X[1] = 1 + 2(−j) + 3(−1) + 4(j) = −2 + 2j, with magnitude √(4+4) ≈ 2.83.

Bin 2: X[2] = 1 − 2 + 3 − 4 = −2, purely real at the Nyquist frequency. Bin 3 is the conjugate of bin 1: X[3] = −2 − 2j, which always holds for real inputs. The symmetry between bins 1 and 3 confirms the hand calculation.

Common Misconceptions

• The FFT gives a different result than the DFT. It does not. The FFT is only a faster algorithm returning the same N values.
• Zero-padding improves true resolution. Padding interpolates the spectrum smoothly but cannot separate tones the original samples could not separate. Longer recordings give real resolution.
• The DFT shows a continuous spectrum. It shows exactly N discrete bins; content between bins is invisible.

Real-World Applications

• MP3/AAC compression uses a DFT cousin to discard frequencies the ear cannot hear.
• Wi-Fi and 4G/5G build their OFDM subcarriers with an inverse FFT in every transmitter.
• MRI scanners reconstruct images from frequency data using the inverse FFT.

The DFT bridges what a signal looks like over time and what it is made of in frequency. The FFT made that bridge cheap enough to cross billions of times per second inside everyday devices.