Understanding the Fast Fourier Transform (快速傅里叶变换)

The FFT is the most important numerical algorithm of our lifetime.

— Gilbert Strang [1]

Introduction

The Discrete Fourier Transform (DFT)See Smith [2] for an excellent introduction aimed at engineers. is one of the most important tools in computational mathematics and signal processing. It converts a sequence of $𝑁$ complex numbers into another sequence of $𝑁$ complex numbers, revealing the frequency content of the original signal.

然而，直接计算 DFT 需要 $𝑂\left({𝑁}^2\right)$ 次运算，对于大规模数据来说效率太低。DFT 的直接算法复杂度很高——对 $𝑁={10}^6$ 的信号需要约 ${10}^{\left\{12\right\}}$ 次运算。 1965年，Cooley 和 Tukey 发表了快速傅里叶变换（FFT）算法，将复杂度降低到 $𝑂\left(𝑁log𝑁\right)$，使得频谱分析在实际工程中变得可行。FFT 是信号处理领域的革命性突破，被誉为“20世纪最重要的算法之一”。

You can also use a numbered note: This note has a superscript number marker in the text and margin.

This article walks through the mathematical foundation of the DFT, derives the radix-2 Cooley–Tukey FFT algorithm, and provides a Python implementation.

The Discrete Fourier Transform

Formally, we write ${𝜔}_{𝑁}={𝑒}^{-2𝜋𝑖/𝑁}$ for the primitive $𝑁$-th root of unity, so the transform becomes:

The inverse DFT recovers the original sequence, as shown in Equation 2:

Key Properties

The DFT satisfies several important properties:

• Linearity: $\mathrm{D}\mathrm{F}\mathrm{T}\left(𝛼𝑥+𝛽𝑦\right)=𝛼\mathrm{D}\mathrm{F}\mathrm{T}\left(𝑥\right)+𝛽\mathrm{D}\mathrm{F}\mathrm{T}\left(𝑦\right)$
• Parseval’s theoremParseval’s theorem tells us that the DFT preserves energy — the total power is the same whether computed in the time or frequency domain.: ${\sum }_{𝑛}|{𝑥}_{𝑛}{|}^2=\frac{1}{𝑁}{\sum }_{𝑘}|{𝑋}_{𝑘}{|}^2$

• Convolution theorem: pointwise multiplication in the frequency domain corresponds to circular convolution in the time domain:

  $$\mathrm{D}\mathrm{F}\mathrm{T}\left(𝑥\ast 𝑦\right)=\mathrm{D}\mathrm{F}\mathrm{T}\left(𝑥\right)\cdot \mathrm{D}\mathrm{F}\mathrm{T}\left(𝑦\right)$$

  (3)

• Shift property: 时域中的移位对应频域中的相位旋转。若 ${𝑦}_{𝑛}={𝑥}_{𝑛-𝑚}$，则 ${𝑌}_{𝑘}={𝜔}_{𝑁}^{𝑚𝑘}{𝑋}_{𝑘}$。

A Visual Intuition

Below is a margin figure showing the magnitude spectrum of a simple signal:

As Figure 1 shows, the FFT clearly separates the two frequency components.

The Cooley–Tukey FFT Algorithm

The key insight of the FFT is to exploit the symmetry and periodicity of ${𝜔}_{𝑁}$. By splitting the DFT into even and odd indices:

This gives us the butterfly operation, which is the computational core of the FFT:

Figure 2 visualizes this butterfly structure — each pair of inputs $\left({𝐸}_{𝑘},{𝑂}_{𝑘}\right)$ produces two outputs via addition and subtraction of the twiddle factor ${𝜔}_{𝑁}^{𝑘}$:

Since ${𝐸}_{𝑘}$ and ${𝑂}_{𝑘}$ are periodic with period $𝑁/2$, we only need to compute them for $𝑘=0,1,\dots ,𝑁/2-1$.

通过递归地应用这一分解，我们可以将 $𝑁$ 点 DFT 的计算分解为 ${log}_2𝑁$ 层蝶形运算，每层包含 $𝑁/2$ 次蝶形操作。

Complexity Analysis

For a concrete example, consider $𝑁=2^{20}\approx {10}^6$:

• Naive DFT: $\sim {10}^{12}$ operations
• FFT: $\sim {10}^7$ operations
• Speedup factor: $\sim {10}^5$That’s roughly 100,000× faster — the difference between a computation finishing in seconds vs. taking all day.

Python Implementation

Below is a recursive radix-2 FFT implementation. Note the elegant correspondence to the mathematical derivation above.

import numpy as np

def fft(x):
    """Compute the FFT of sequence x (length must be a power of 2)."""
    N = len(x)
    if N == 1:
        return x

    # Split into even and odd indices
    even = fft(x[0::2])
    odd  = fft(x[1::2])

    # Twiddle factors: ω_N^k for k = 0, ..., N/2 - 1
    T = np.exp(-2j * np.pi * np.arange(N // 2) / N)

    # Butterfly: combine E_k and O_k
    return np.concatenate([
        even + T * odd,   # X_k       = E_k + ω^k · O_k
        even - T * odd    # X_{k+N/2} = E_k - ω^k · O_k
    ])

# Verify against NumPy's FFT
if __name__ == "__main__":
    x = np.random.random(1024)
    assert np.allclose(fft(x), np.fft.fft(x))
    print("FFT implementation verified!")

Performance note: this recursive version is clear but not optimal. Production FFT libraries (like FFTW [3]) use iterative approaches with carefully tuned memory access patterns, achieving near-peak hardware performance.

What the FFT Reveals

Figure 3 shows a typical FFT output: a time-domain signal containing two sine waves (50 Hz and 120 Hz) is transformed into a frequency-domain representation with clear peaks at those exact frequencies.

Applications

Signal processing. The most common application — spectral analysis, filtering, and compression (MP3, JPEG, etc.) all rely on the FFT.

Other important applications include:

1. Polynomial multiplication: multiplying two degree-$𝑛$ polynomials in $𝑂\left(𝑛log𝑛\right)$ instead of $𝑂\left({𝑛}^2\right)$
2. Large integer multiplication: the Schönhage–Strassen algorithm uses FFT to multiply $𝑛$-digit integers in $𝑂\left(𝑛log𝑛loglog𝑛\right)$
3. Partial differential equations: 谱方法利用 FFT 在频域中高效求解偏微分方程，在流体力学和量子力学模拟中广泛使用
4. Convolution: fast computation of convolutions via the convolution theorem, used in deep learning (CNNs)

FFT in the Real World

A wide figure showing a more detailed visualization:

As Figure 4 demonstrates, even a visually complex signal is just a sum of simple sinusoids — the FFT tells us exactly which ones.

Conclusion

The FFT is one of the most beautiful and practical algorithms in all of computational mathematics. It reduces the complexity of the DFT from $𝑂\left({𝑁}^2\right)$ to $𝑂\left(𝑁log𝑁\right)$, making large-scale spectral analysis feasible.

The central idea — divide and conquer via the symmetry of roots of unity — is both mathematically elegant and practically powerful. Understanding the FFT provides deep insight into the interplay between the time domain and the frequency domain, a duality that lies at the heart of much of applied mathematics.