Jump back to chapter selection.

Table of Contents

10.1 From DTFT to DFT
10.2 DFT Properties
10.3 Circular and Linear Convolution
10.4 Spectral Leakage and Windowing
10.5 Fast Fourier Transform
10.6 Short-Time Fourier Analysis

10 Discrete Fourier Transform and FFT

The DTFT is the natural Fourier representation for infinite-length discrete-time signals, but it is still a continuous function of frequency. Computers need finite lists of numbers. The discrete Fourier transform (DFT) turns a finite sequence into a finite list of frequency samples, and the fast Fourier transform (FFT) computes that list efficiently.

This chapter is therefore the bridge from transform theory to numerical signal processing.

10.1 From DTFT to DFT

For a length- $N$ sequence $x [n]$ , defined for $0 \leq n \leq N - 1$ , the DFT is

X [k] = \sum_{n = 0}^{N - 1} x [n] e^{- j 2 π k n / N}, k = 0, 1, \dots, N - 1.

The inverse DFT is

x [n] = \frac{1}{N} \sum_{k = 0}^{N - 1} X [k] e^{j 2 π k n / N}, n = 0, 1, \dots, N - 1.

The DFT basis functions are sampled complex exponentials. The frequency represented by bin $k$ is

ω_{k} = \frac{2 π k}{N} .

Because discrete-time frequency is periodic with period $2 π$ , bins near $N$ correspond to negative frequencies:

ω_{N - r} = 2 π - \frac{2 π r}{N} \equiv - \frac{2 π r}{N} .

The DFT can be understood in two equivalent ways:

as the Fourier series coefficients of a periodic sequence with period $N$ ;
as samples of the DTFT of a finite-duration sequence at $ω_{k} = 2 π k / N$ .

If $x [n]$ is finite duration and zero outside $0 \leq n < N$ , its DTFT is

X (e^{j ω}) = \sum_{n = 0}^{N - 1} x [n] e^{- j ω n} .

The DFT samples this at equally spaced frequencies:

X [k] = X (e^{j ω}) |_{ω = 2 π k / N} .

This distinction matters. The DFT itself always assumes periodicity in both domains:

x [n + N] = x [n], X [k + N] = X [k] .

When using the DFT to analyse a finite segment of a longer signal, we are implicitly windowing the signal and periodically extending that windowed segment.

10.2 DFT Properties

The DFT has properties analogous to the DTFT, but all indexing is modulo $N$ .

x [n] \leftrightarrow X [k], y [n] \leftrightarrow Y [k],

then:

Property	Time domain	DFT domain
Linearity	$a x [n] + b y [n]$	$a X [k] + b Y [k]$
Circular time shift	$x [(n - n_{0})_{N}]$	$e^{- j 2 π k n_{0} / N} X [k]$
Frequency shift	$e^{j 2 π k_{0} n / N} x [n]$	$X [(k - k_{0})_{N}]$
Time reversal	$x [(- n)_{N}]$	$X [(- k)_{N}]$
Circular convolution	$x [n] ⊛_{N} y [n]$	$X [k] Y [k]$
Multiplication	$x [n] y [n]$	$\frac{1}{N} X [k] ⊛_{N} Y [k]$

For real-valued $x [n]$ , the DFT has conjugate symmetry:

X [N - k] = X^{*} [k] .

The bins $k = 0$ and, for even $N$ , $k = N / 2$ are purely real. This symmetry is used heavily in real-valued FFT implementations.

Parseval's relation for the DFT is

\sum_{n = 0}^{N - 1} | x [n] |^{2} = \frac{1}{N} \sum_{k = 0}^{N - 1} | X [k] |^{2} .

Energy is preserved up to the normalization convention.

10.3 Circular and Linear Convolution

The DFT converts circular convolution into multiplication:

y [n] = x [n] ⊛_{N} h [n] ⟺ Y [k] = X [k] H [k] .

The $N$ -point circular convolution is

y [n] = \sum_{m = 0}^{N - 1} x [m] h [(n - m)_{N}] .

Circular convolution wraps around modulo $N$ . Linear convolution does not.

If $x [n]$ has length $L_{x}$ and $h [n]$ has length $L_{h}$ , their linear convolution has length

L_{y} = L_{x} + L_{h} - 1.

To compute linear convolution using the DFT, choose

N \geq L_{x} + L_{h} - 1,

zero-pad both sequences to length $N$ , multiply their DFTs, and take the inverse DFT. With enough zero-padding, the circular wraparound happens only in zeros and therefore matches linear convolution.

For long signals, filtering with one giant FFT is inefficient or impossible due to memory. Practical block methods include:

overlap-add: split the input into blocks, zero-pad each block, convolve by FFT, and add overlapping output tails;
overlap-save: process overlapping input blocks and discard the corrupted samples caused by circular wraparound.

Both methods implement ordinary LTI filtering while using FFTs internally.

10.4 Spectral Leakage and Windowing

When a finite segment is analysed with a DFT, the signal is multiplied by a window $w [n]$ :

x_{w} [n] = x [n] w [n] .

Multiplication in time corresponds to convolution in frequency. Thus the measured spectrum is the true spectrum blurred by the window spectrum:

X_{w} (e^{j ω}) = \frac{1}{2 π} X (e^{j ω}) * W (e^{j ω}) .

For a rectangular window, the window transform has narrow main lobe but large side lobes. If a sinusoid does not land exactly on a DFT bin, its energy spreads into many bins. This is spectral leakage.

Other windows trade main-lobe width against side-lobe level:

rectangular: best frequency resolution, worst leakage;
Hann/Hamming: reduced side lobes, wider main lobe;
Blackman: stronger side-lobe suppression, even wider main lobe;
Kaiser: adjustable tradeoff through a parameter.

Zero-padding does not improve the true frequency resolution. It samples the same windowed DTFT more densely, which can make peaks easier to locate visually or numerically. The actual ability to separate two close frequencies is set mainly by the observation length and window shape.

10.5 Fast Fourier Transform

Direct computation of the DFT requires $N^{2}$ complex multiplications. The FFT exploits symmetry and periodicity of the twiddle factors

W_{N} = e^{- j 2 π / N}

to reduce the complexity to order

O (N \log_{2} N)

for radix-2 lengths.

For $N$ even, split the DFT into even and odd time samples:

X [k] = \sum_{n = 0}^{N - 1} x [n] W_{N}^{k n} .

Write $n = 2 r$ and $n = 2 r + 1$ :

X [k] = \sum_{r = 0}^{N / 2 - 1} x [2 r] W_{N / 2}^{k r} + W_{N}^{k} \sum_{r = 0}^{N / 2 - 1} x [2 r + 1] W_{N / 2}^{k r} .

Define

E [k] = \sum_{r = 0}^{N / 2 - 1} x [2 r] W_{N / 2}^{k r}, O [k] = \sum_{r = 0}^{N / 2 - 1} x [2 r + 1] W_{N / 2}^{k r} .

Then

X [k] = E [k] + W_{N}^{k} O [k],

and

X [k + N / 2] = E [k] - W_{N}^{k} O [k],

for $k = 0, \dots, N / 2 - 1$ . This is the decimation-in-time FFT butterfly.

Repeating this decomposition recursively gives the FFT. Decimation-in-frequency uses the complementary idea: split the output frequencies first rather than the input time indices. Both lead to the same complexity class.

Important implementation details are:

bit-reversed ordering or equivalent index permutations;
in-place butterflies to reduce memory;
precomputed or recursively generated twiddle factors;
scaling conventions for the inverse transform;
numerical round-off, especially for fixed-point implementations.

10.6 Short-Time Fourier Analysis

The DFT assumes the analysed segment is the object of interest. For signals whose spectrum changes with time, one uses a sliding window:

X [m, k] = \sum_{n = - \infty}^{\infty} x [n] w [n - m R] e^{- j 2 π k n / N},

where $m$ indexes the frame and $R$ is the hop size. This is the short-time Fourier transform (STFT).

The STFT gives a time-frequency representation. The window length controls the tradeoff:

a long window gives good frequency resolution but poor time localization;
a short window gives good time localization but poor frequency resolution.

There is no way around this tradeoff for Fourier windows. It is the signal-processing version of a time-bandwidth limitation. Speech, radar, music, vibration analysis, and spectroscopy all use variants of this idea.

For reconstruction, neighbouring windows must overlap in a way that allows the windowed segments to add back to the original signal. This is the basis of overlap-add reconstruction and many modern time-frequency processing algorithms.