DFT Definition and Interpretation | DSP-101

The DFT Formula

The Discrete Fourier Transform (DFT) is the computational workhorse of spectral analysis. Given an N-point sequence x[n], the DFT produces N complex numbers X[k], each encoding the amplitude and phase of a sinusoidal component at a specific discrete frequency. The DFT is defined as:

DFT Definition

X[k] = \sum_{n=0}^{N-1} x[n]\,e^{-j2\pi kn/N}, \quad k = 0, 1, \ldots, N-1

X[k] is the DFT of the N-point sequence x[n]. The index k runs from 0 to N−1, corresponding to N equally spaced frequencies around the unit circle. Each bin k represents frequency f_k = k·f_s/N Hz (or ω_k = 2πk/N rad/sample).

The inverse DFT (IDFT) recovers x[n] exactly from X[k]:

Inverse DFT (IDFT)

x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k]\,e^{j2\pi kn/N}, \quad n = 0, 1, \ldots, N-1

The 1/N normalization ensures that applying the IDFT after the DFT recovers x[n] exactly. Together the DFT and IDFT form a lossless, invertible transform pair over N-point sequences.

What Each Bin Contains

X[k] is a complex number. Its magnitude |X[k]| gives the amplitude of the sinusoidal component at frequency k·f_s/N, and its angle ∠X[k] gives the phase. For real-valued x[n], the DFT has conjugate symmetry: X[N−k] = X*[k], so only bins 0 through N/2 carry independent information.

|X[k]| = amplitude at f = k·f_s/N — ∠X[k] = phase at that frequency

Interpreting Frequency Bins

Each DFT bin k corresponds to a physical frequency. If the signal was sampled at rate f_s and the DFT size is N, then bin k corresponds to frequency f_k = k·f_s/N. The frequency spacing between adjacent bins — the bin spacing, often loosely called the frequency resolution — is therefore:

Frequency Resolution

\Delta f = \frac{f_s}{N}

Bin spacing equals the sampling rate divided by the DFT length N. Halving Δf means doubling N — but only acquiring more samples improves true frequency resolution. Zero-padding to a larger N shrinks the bin spacing without resolving anything new.

Bin 0

DC Component

X[0] = sum of all x[n]. This is the DC level — the average value of the signal scaled by N.

Bin N/2

Nyquist Frequency

For even N, bin N/2 corresponds to the Nyquist frequency f_s/2 — the highest unambiguous frequency.

Bins N/2+1 … N−1

Negative Frequencies

These bins represent negative frequencies (−f_s/2 up to just below 0). For real signals they mirror bins 1 … N/2−1 by conjugate symmetry.

Bin k

f = k·f_s/N Hz

General mapping: multiply bin index by the frequency resolution Δf = f_s/N to get the physical frequency in Hz.

The DFT as a Matrix Operation

The DFT is a linear transformation. We can write it compactly as matrix–vector multiplication: X = W_N x, where W_N is the N×N DFT matrix. The (k, n) entry of W_N is the twiddle factor W_N^kn:

Twiddle Factor

W_N = e^{-j2\pi/N} \quad \Rightarrow \quad [\mathbf{W}_N]_{k,n} = W_N^{kn} = e^{-j2\pi kn/N}

W_N is the primitive N-th root of unity. It lives on the unit circle at angle −2π/N. Raising it to the kn-th power rotates to the kn-th equally spaced point on the unit circle.

The DFT matrix is symmetric and unitary (up to the 1/√N normalization). This means its inverse is simply its conjugate transpose: W_N⁻¹ = (1/N)W_N^*. The matrix view makes clear that the DFT is just a change of basis — from the standard time-sample basis to the complex exponential (frequency) basis.

Direct DFT is O(N²)

Computing X = W_N x naively requires N multiplications per output bin and N output bins — a total of N² complex multiplications. For N = 1024 this is over one million operations. The Fast Fourier Transform (FFT) reduces this to O(N log N) using the structure of the twiddle factors.

The Circular (Periodic) Nature of the DFT

A subtle but crucial property: the DFT implicitly treats x[n] as one period of an infinitely periodic signal with period N. This means that from the DFT's perspective, the sample after x[N−1] wraps around to x[0]. Arithmetic on DFT indices is always modulo N.

This periodicity has direct consequences for convolution. Multiplying two DFT spectra X[k] and H[k] and taking the IDFT does not give the linear convolution x[n] ∗ h[n] — it gives the circular convolution x[n] ⊛ h[n], computed modulo N. To use the DFT for linear convolution (as needed in filtering), the sequence length must be padded to avoid time-domain aliasing.

Circular Convolution

y[n] = \mathrm{IDFT}\{X[k]\cdot H[k]\} = \sum_{m=0}^{N-1} x[m]\,h[(n-m)_{\bmod N}]

IDFT{X[k]·H[k]} gives circular convolution, not linear convolution. To recover linear convolution from the DFT, zero-pad both sequences to length ≥ L_x + L_h − 1 before computing the DFT.

Zero-Padding Rule

If x[n] has length L_x and h[n] has length L_h, choose DFT size N ≥ L_x + L_h − 1. Pad both sequences with zeros to length N, compute their DFTs, multiply pointwise, and take the IDFT. The result is the exact linear convolution.

Frequency Resolution and Zero-Padding

The DFT's bin spacing is Δf = f_s/N, and there are two ways to shrink it — but only one of them improves true frequency resolution. Acquiring more samples does: a longer observation window genuinely increases the time-bandwidth product. Appending zeros to the existing sequence does not. Zero-padding interpolates the spectrum — it evaluates the DTFT at more points, producing a smoother plot — but it adds no new spectral information. Two closely spaced sinusoids that cannot be resolved with L samples cannot be separated by zero-padding; they can only be separated by recording more data.

A practical rule: if you need to distinguish two sinusoids separated by Δf Hz, you need at least T = 1/Δf seconds of data (L ≥ f_s/Δf samples). Zero-padding beyond that makes the spectrum look smoother but does not reveal new peaks.

The next lesson explores frequency resolution and windowing — how the observation window shape affects spectral leakage and what window functions do to minimize it.

Key Takeaways

The DFT maps an N-point sequence x[n] to N complex spectral values X[k] = Σ x[n] e^−j2πkn/N; the IDFT inverts it exactly with a 1/N factor.
Bin k represents frequency f_k = k·f_s/N Hz; the bin spacing is Δf = f_s/N.
|X[k]| is amplitude and ∠X[k] is phase at frequency k·f_s/N; for real x[n], the upper half of the DFT mirrors the lower half by conjugate symmetry.
The DFT is a matrix multiplication X = W_N x, where W_N has entries W_N^{kn} = e^{−j2πkn/N}; direct computation costs O(N²).
The DFT implicitly assumes x[n] is periodic with period N — all DFT index arithmetic is modulo N.
Multiplying DFT spectra and inverting gives circular convolution; zero-pad to length ≥ L_x + L_h − 1 to obtain linear convolution.
Zero-padding interpolates the spectrum (smoother plot) but does not improve true frequency resolution — that requires more data samples.