Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT)

Why it matters

The DFT represents a finite record by discrete frequency bins. FFT algorithms compute the same transform efficiently; they are not a different physical transform.

Definitions

For N samples indexed n = 0,…,N−1, use X[k] = Σ x[n] exp(−j2πkn/N), k = 0,…,N−1. The inverse is x[n] = (1/N)Σ X[k] exp(j2πkn/N). State the normalization because software conventions can differ. For samples at f_s, bin spacing is Δf = f_s/N. Bins above the Nyquist limit represent negative frequencies in the usual ordering. The transform implicitly treats the record as one period of a periodic sequence.

Worked example

Let x = [1, 0, −1, 0], N = 4, f_s = 1000 Hz. X[0] = 1−1 = 0. X[1] = 1 + (−1)exp(−jπ) = 2. X[2] = 1 + (−1)exp(−j2π) = 0. X[3] = 2. Therefore X = [0, 2, 0, 2]. The bins represent 0, +250, ±500 and −250 Hz. This sequence is one period of a unit-amplitude 250 Hz cosine, whose two-sided coefficients are X/N = [0, 0.5, 0, 0.5].

FFT, leakage and convolution

A direct DFT uses O(N²) arithmetic; common FFTs use O(N log N). Radix-2 FFT needs a power-of-two length, but FFT algorithms exist for other lengths. A finite record can cause spectral leakage when periodic extension creates a discontinuity. Windowing changes the sidelobe/main-lobe tradeoff and amplitude calibration. Zero-padding gives denser frequency samples but does not add information or improve the underlying ability to resolve nearby tones. Multiplication of N-point DFTs corresponds to N-point circular convolution. To obtain linear convolution of lengths L and M, pad both to at least L+M−1 before transforming.

Quick check

1. N = 1000 and f_s = 8000 Hz: what is bin spacing? 8 Hz.
2. Does an FFT approximate a different transform? No; it efficiently computes the DFT, subject to numerical roundoff.
3. What length avoids circular wraparound for records of lengths 5 and 4? At least 8.