Ferkans — Interactive Telecom Tutor

Why the FFT Changed Everything

The Fast Fourier Transform (FFT) is arguably the most important numerical algorithm of the 20th century. It converts a signal from the time domain to the frequency domain in $O(N \log N)$ operations, enabling everything from audio compression (MP3) to medical imaging (MRI) to wireless communications (OFDM). Without the FFT, a 1024-point DFT would require $\sim 10^6$ complex multiplications; with the FFT, it takes $\sim 5000$ .

Definition:
The Discrete Fourier Transform (DFT)

For a signal $x[n]$ of length $N$ , the DFT is defined as:

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

The inverse DFT (IDFT) recovers the original signal:

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

In NumPy:

X = np.fft.fft(x)       # forward DFT
x = np.fft.ifft(X)      # inverse DFT

The DFT assumes the signal is periodic with period $N$ . This implicit periodicity causes spectral leakage when the signal does not contain an integer number of cycles in the analysis window.

Definition:
DFT as a Matrix-Vector Product

The DFT can be written as $\mathbf{X} = \mathbf{F}_N \mathbf{x}$ , where the DFT matrix $\mathbf{F}_N$ has entries:

$[\mathbf{F}_N]_{kn} = e^{-j 2\pi k n / N} = W_N^{kn}$

with $W_N = e^{-j 2\pi / N}$ the $N$ -th root of unity. The matrix $\frac{1}{\sqrt{N}}\mathbf{F}_N$ is unitary: $\mathbf{F}_N^H \mathbf{F}_N = N\,\mathbf{I}$ .

N = len(x)
n = np.arange(N)
k = n.reshape(-1, 1)
F = np.exp(-2j * np.pi * k * n / N)
X_matrix = F @ x   # same as np.fft.fft(x)

The FFT algorithm exploits the symmetry and periodicity of $W_N^{kn}$ to reduce the $O(N^2)$ matrix-vector product to $O(N \log N)$ operations via divide-and-conquer.

Definition:
Frequency Axis with fftfreq

The function np.fft.fftfreq(N, d) returns the frequency bins corresponding to each DFT index, where $d = 1/f_s$ is the sample spacing:

$f_k = \frac{k}{N \cdot d} = \frac{k \cdot f_s}{N}$

For $k > N/2$ , the frequencies wrap to negative values. Use np.fft.fftshift to rearrange the output so that zero frequency is at the center:

freqs = np.fft.fftfreq(N, d=1/fs)
X_shifted = np.fft.fftshift(X)
f_shifted = np.fft.fftshift(freqs)

Definition:
FFT Normalization Conventions

NumPy supports three normalization modes via the norm parameter:

Mode	Forward ( $\mathbf{F}$ )	Inverse ( $\mathbf{F}^{-1}$ )
`None` (default)	No scaling	Divide by $N$
`"ortho"`	Divide by $\sqrt{N}$	Divide by $\sqrt{N}$
`"forward"`	Divide by $N$	No scaling

X = np.fft.fft(x, norm="ortho")   # unitary DFT

The "ortho" convention makes the DFT a unitary transform, preserving energy: $\|\mathbf{X}\|^2 = \|\mathbf{x}\|^2$ (Parseval's theorem).

Definition:
2D and N-Dimensional DFT

The 2D DFT of an image $x[m, n]$ of size $M \times N$ is:

$X[k, l] = \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} x[m,n]\, e^{-j2\pi(km/M + ln/N)}$

Since the 2D DFT is separable, it can be computed as row-wise 1D FFTs followed by column-wise 1D FFTs:

X2d = np.fft.fft2(x_2d)             # 2D FFT
x_2d = np.fft.ifft2(X2d)            # 2D inverse FFT
Xnd = np.fft.fftn(x_nd)             # N-dimensional FFT

Definition:
Zero-Padding for Frequency Interpolation

Appending zeros to a signal before computing the DFT increases the number of frequency bins, providing a smoother spectral representation. Zero-padding to length $M > N$ interpolates the spectrum but does not improve spectral resolution (which is determined by the observation duration $T = N/f_s$ ):

X_padded = np.fft.fft(x, n=4*N)  # 4x zero-padding

The frequency resolution remains $\Delta f = f_s / N$ , but zero-padding reveals the shape of the underlying spectral peaks more clearly.

Zero-padding is equivalent to sinc interpolation of the spectrum. It is essential for applications like radar range profiling where you need to locate spectral peaks between DFT bins.

Theorem: Parseval's Theorem

For a signal $x[n]$ and its DFT $X[k]$ , the total energy is preserved:

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

With the "ortho" normalization: $\sum |x[n]|^2 = \sum |X[k]|^2$ .

The DFT is a rotation in $N$ -dimensional space. Rotations preserve lengths (norms), so the total energy measured in the time domain equals the total energy measured in the frequency domain.

Proof

Expand the frequency-domain sum

$\sum_{k=0}^{N-1}|X[k]|^2 = \sum_k X[k] X^*[k] = \sum_k \left(\sum_n x[n] W_N^{kn}\right)\left(\sum_m x^*[m] W_N^{-km}\right)$ $

Interchange summation order

$= \sum_n \sum_m x[n] x^*[m] \underbrace{\sum_{k=0}^{N-1} W_N^{k(n-m)}}_{= N\,\delta[n-m]}$ $

Apply orthogonality

$= N \sum_n |x[n]|^2$ $Dividing both sides by$ N$ gives the result.

Theorem: Convolution Theorem

Circular convolution in the time domain corresponds to pointwise multiplication in the frequency domain:

$\mathrm{DFT}\{x \circledast h\} = X[k] \cdot H[k]$

where $\circledast$ denotes circular (periodic) convolution. For linear convolution, zero-pad both sequences to length $\ge N + M - 1$ before applying the DFT.

The DFT diagonalizes circulant matrices. Convolution by $h$ is multiplication by a circulant matrix built from $h$ , so in the DFT basis it becomes a diagonal (pointwise) operation.

Theorem: Nyquist-Shannon Sampling Theorem

A bandlimited signal $x(t)$ with maximum frequency $f_\max$ can be perfectly reconstructed from its samples $x[n] = x(n/f_s)$ if and only if:

$f_s > 2 f_\max$

The minimum sampling rate $f_s = 2 f_\max$ is called the Nyquist rate. Sampling below this rate causes aliasing — high-frequency components fold back into the baseband and cannot be separated.

Each sample provides one equation. A bandlimited signal has $2 f_\max T$ degrees of freedom in time $T$ , so you need at least that many samples per second to capture all the information.

Example: FFT of a Multi-Tone Signal

Create a signal $x(t) = \sin(2\pi \cdot 50\,t) + 0.5\sin(2\pi \cdot 120\,t)$ sampled at $f_s = 1000\,\text{Hz}$ for 0.5 seconds. Compute its FFT and plot the magnitude spectrum.

Solution

Generate the signal and compute the FFT

import numpy as np
import matplotlib.pyplot as plt

fs = 1000
T = 0.5
t = np.arange(0, T, 1/fs)
x = np.sin(2*np.pi*50*t) + 0.5*np.sin(2*np.pi*120*t)

X = np.fft.fft(x)
freqs = np.fft.fftfreq(len(x), d=1/fs)

# Plot only positive frequencies
mask = freqs >= 0
plt.stem(freqs[mask], 2*np.abs(X[mask])/len(x))
plt.xlabel("Frequency (Hz)")
plt.ylabel("Amplitude")

The magnitude spectrum shows peaks at 50 Hz (amplitude 1.0) and 120 Hz (amplitude 0.5), matching the original signal components.

Example: Verifying the DFT Matrix

For $N = 8$ , construct the DFT matrix $\mathbf{F}_8$ explicitly and verify that $\mathbf{F}_8 \mathbf{x}$ matches np.fft.fft(x). Also verify that $\frac{1}{\sqrt{8}}\mathbf{F}_8$ is unitary.

Solution

Build the DFT matrix

N = 8
n = np.arange(N)
k = n.reshape(-1, 1)
F = np.exp(-2j * np.pi * k * n / N)

x = np.random.randn(N)
X_matrix = F @ x
X_fft = np.fft.fft(x)
print(f"Match: {np.allclose(X_matrix, X_fft)}")  # True

Check unitarity

F_normed = F / np.sqrt(N)
print(np.allclose(F_normed.conj().T @ F_normed, np.eye(N)))  # True

The normalized DFT matrix is unitary, confirming that the DFT is an orthonormal change of basis.

Example: Zero-Padding Reveals Spectral Shape

A signal contains two closely-spaced sinusoids at 100 Hz and 105 Hz, sampled at $f_s = 1000$ Hz for 0.1 seconds (100 samples). Show how zero-padding to 1024 points reveals the peak structure without improving the true resolution of $\Delta f = 10$ Hz.

Solution

Compare FFT with and without zero-padding

fs = 1000
t = np.arange(0, 0.1, 1/fs)
x = np.sin(2*np.pi*100*t) + np.sin(2*np.pi*105*t)

X_100 = np.fft.fft(x)           # 100 points
X_1024 = np.fft.fft(x, n=1024)  # zero-padded to 1024

f_100 = np.fft.fftfreq(100, 1/fs)
f_1024 = np.fft.fftfreq(1024, 1/fs)

With 100 points ( $\Delta f = 10$ Hz), the two tones merge into one peak. With 1024 points, the spectral envelope is smoother but still shows a single broad peak. True resolution requires a longer observation window, not more zero-padding.

FFT Explorer: Frequency and Time Domain

Adjust signal parameters and observe how the FFT magnitude spectrum changes. Try adding multiple frequency components and varying the number of samples to see spectral leakage.

Parameters

DFT Matrix Visualizer

Visualize the real and imaginary parts of the DFT matrix for different sizes $N$ . Notice the harmonic structure of the rows and the symmetry.

Parameters

Aliasing When Sampling Below Nyquist

Watch what happens as the sampling rate drops below the Nyquist rate. The animation shows how an undersampled sinusoid appears as a lower-frequency alias.

Parameters

FFT Butterfly Diagram (N = 8) — The radix-2 Cooley-Tukey FFT decomposes an $N$ -point DFT into $\log_2 N$ stages of butterfly operations. Each butterfly computes $a + W_N^k b$ and $a - W_N^k b$ using one complex multiplication and two additions.

Fourier Transform Recipes

python

Complete examples: 1D/2D FFT, fftfreq, fftshift, zero-padding, normalization modes, and the DFT matrix product.

# Code from: ch07/python/fourier_transforms.py
# Load from backend supplements endpoint

Quick Check

What is the computational complexity of the radix-2 FFT algorithm for an $N$ -point DFT?

$O(N^2)$

$O(N \log N)$

$O(N)$

$O(N^2 \log N)$

Correction:

O(N \log N)

The FFT recursively splits the DFT into two $N/2$ -point DFTs at each of $\log_2 N$ levels.

Quick Check

Zero-padding a signal from $N$ to $4N$ points before computing the FFT:

Improves frequency resolution by a factor of 4

Interpolates the spectrum for a smoother visualization

Reduces spectral leakage

Doubles the signal bandwidth

Correction:

Interpolates the spectrum for a smoother visualization

Zero-padding is equivalent to sinc interpolation of the underlying DTFT.

Common Mistake: Forgetting fftshift for Centered Spectra

Mistake:

Plotting the raw FFT output directly: the negative frequencies appear at the right side of the array, not centered at zero.

Correction:

Use np.fft.fftshift on both the FFT output and the frequency axis:

X_centered = np.fft.fftshift(np.fft.fft(x))
f_centered = np.fft.fftshift(np.fft.fftfreq(N, 1/fs))

Common Mistake: Normalization Mismatch Between Forward and Inverse

Mistake:

Computing the forward FFT with norm="ortho" and then the inverse FFT with the default norm=None, producing a result scaled by $1/\sqrt{N}$ .

Correction:

Always use the same norm argument for both fft and ifft:

X = np.fft.fft(x, norm="ortho")
x_back = np.fft.ifft(X, norm="ortho")  # matches!

Key Takeaway

The FFT computes the DFT in $O(N \log N)$ operations instead of $O(N^2)$ . Use np.fft.fftfreq for the frequency axis and np.fft.fftshift for centered spectra. Zero-padding interpolates the spectrum but does not improve resolution. Always match the norm argument between forward and inverse transforms.

Key Takeaway

The DFT is a matrix-vector product $\mathbf{X} = \mathbf{F}_N \mathbf{x}$ . Understanding this linear algebra perspective is essential for grasping OFDM, where subcarriers are the rows of the DFT matrix, and the inverse FFT is the modulator.

Why This Matters: OFDM: The FFT as a Modulation Scheme

Orthogonal Frequency-Division Multiplexing (OFDM) — used in WiFi, 4G LTE, and 5G NR — transmits data on orthogonal subcarriers. The transmitter applies an inverse FFT to map frequency-domain symbols to a time-domain waveform, and the receiver applies a forward FFT to recover them. The entire OFDM transceiver is essentially two FFT operations sandwiching a wireless channel.

The circular convolution property of the DFT is what makes OFDM work: adding a cyclic prefix converts the linear channel convolution into circular convolution, enabling simple per-subcarrier equalization via division in the frequency domain.

See full treatment in Chapter 15

Historical Note: Cooley and Tukey (1965): Rediscovering the FFT

1965

James Cooley and John Tukey published their FFT algorithm in 1965, reducing the DFT from $O(N^2)$ to $O(N \log N)$ . The algorithm was actually discovered earlier by Gauss around 1805 for interpolating asteroid orbits, but his work went unnoticed. Cooley-Tukey's paper ignited a revolution in digital signal processing, making real-time spectral analysis computationally feasible for the first time.

Historical Note: Joseph Fourier and the Theory of Heat

1807

Joseph Fourier introduced his transform in 1807 while studying heat conduction. His radical claim that any periodic function could be decomposed into a sum of sines and cosines was met with skepticism by Lagrange and Laplace. Two centuries later, the Fourier transform is the cornerstone of signal processing, physics, and engineering.

DFT (Discrete Fourier Transform)

A transform that converts a finite sequence of $N$ samples into $N$ complex coefficients representing the signal's frequency content.

FFT (Fast Fourier Transform)

An efficient algorithm for computing the DFT in $O(N \log N)$ operations instead of the naive $O(N^2)$ .

Aliasing

The phenomenon where high-frequency signal components are misrepresented as lower frequencies when the sampling rate is below the Nyquist rate ( $f_s < 2 f_\max$ ).

Spectral Leakage

The spreading of a signal's energy across multiple frequency bins when the observation window does not contain an integer number of signal cycles, caused by the implicit rectangular windowing of the DFT.

Zero-Padding

Appending zeros to a signal before computing the DFT to increase the number of frequency bins (spectral interpolation) without improving the underlying frequency resolution.

FFT Normalization Conventions

Convention	Forward Scale	Inverse Scale	Parseval	Use Case
Default (None)	1	1/N	$\sum\|X\|^2 = N\sum\|x\|^2$	Standard DSP, most textbooks
Ortho	$1/\sqrt{N}$	$1/\sqrt{N}$	$\sum\|X\|^2 = \sum\|x\|^2$	Unitary DFT, energy preservation
Forward	1/N	1	$\sum\|X\|^2 = \sum\|x\|^2/N$	Physics convention

Fourier Transforms

Why the FFT Changed Everything

Definition: The Discrete Fourier Transform (DFT)

Definition: DFT as a Matrix-Vector Product

Definition: Frequency Axis with fftfreq

Definition: FFT Normalization Conventions

Definition: 2D and N-Dimensional DFT

Definition: Zero-Padding for Frequency Interpolation

Theorem: Parseval's Theorem

Expand the frequency-domain sum

Interchange summation order

Apply orthogonality

Theorem: Convolution Theorem

Theorem: Nyquist-Shannon Sampling Theorem

Example: FFT of a Multi-Tone Signal

Generate the signal and compute the FFT

Example: Verifying the DFT Matrix

Build the DFT matrix

Check unitarity

Example: Zero-Padding Reveals Spectral Shape

Compare FFT with and without zero-padding

FFT Explorer: Frequency and Time Domain

Parameters

DFT Matrix Visualizer

Parameters

Aliasing When Sampling Below Nyquist

Parameters

FFT Butterfly Diagram (N = 8)

Fourier Transform Recipes

Quick Check

Quick Check

Common Mistake: Forgetting fftshift for Centered Spectra

Common Mistake: Normalization Mismatch Between Forward and Inverse

Key Takeaway

Key Takeaway

Why This Matters: OFDM: The FFT as a Modulation Scheme

Historical Note: Cooley and Tukey (1965): Rediscovering the FFT

Historical Note: Joseph Fourier and the Theory of Heat

DFT (Discrete Fourier Transform)

FFT (Fast Fourier Transform)

Aliasing

Spectral Leakage

Zero-Padding

FFT Normalization Conventions

Definition:
The Discrete Fourier Transform (DFT)

Definition:
DFT as a Matrix-Vector Product

Definition:
Frequency Axis with fftfreq

Definition:
FFT Normalization Conventions

Definition:
2D and N-Dimensional DFT

Definition:
Zero-Padding for Frequency Interpolation