Riguz Lee 2025-12-01
PDF
The Discrete Fourier Transform1Understanding the Fast Fourier Transform (快速傅里叶变换)Riguz Lee · 2025-12-01 · math, algorithms, signal-processingAn introduction to the Fast Fourier Transform (FFT) — from the DFT definition to the Cooley–Tukey algorithm, with Python code and complexity analysis.ContentsIntroduction .......................................................................... 1The Discrete Fourier Transform ..................................................... 1Key Properties .............................................................................. 2A Visual Intuition ........................................................................... 2The Cooley–Tukey FFT Algorithm .................................................. 2Complexity Analysis ......................................................................... 2Python Implementation .............................................................. 3What the FFT Reveals ...................................................................... 3Applications .......................................................................... 4FFT in the Real World ...................................................................... 4Conclusion ............................................................................ 4Bibliography .......................................................................... 5The FFT is the most important numerical algorithm of our lifetime.— Gilbert Strang [1]IntroductionThe 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 需要 𝑂(𝑁2) 次运算，对于大规模数据来说效率太低。DFT 的直接算法复杂度很高——对 𝑁=106 的信号需要约 10{12} 次运算。 1965年，Cooley 和 Tukey 发表了快速傅里叶变换（FFT）算法，将复杂度降低到 𝑂(𝑁log𝑁)，使得频谱分析在实际工程中变得可行。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 TransformFormally, we write 𝜔𝑁=𝑒−2𝜋𝑖/𝑁 for the primitive 𝑁-th root of unity, so the transform becomes:𝑋𝑘=∑𝑁−1𝑛=0𝑥𝑛𝜔𝑘𝑛𝑁(1)The inverse DFT recovers the original sequence, as shown in Equation 2:𝑥𝑛=1𝑁∑𝑁−1𝑘=0𝑋𝑘𝜔−𝑘𝑛𝑁(2)1 The Cooley–Tukey FFT Algorithm2Key PropertiesThe DFT satisfies several important properties:•Linearity: DFT(𝛼𝑥+𝛽𝑦)=𝛼DFT(𝑥)+𝛽DFT(𝑦)•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.: ∑𝑛|𝑥𝑛|2=1𝑁∑𝑘|𝑋𝑘|2•Convolution theorem: pointwise multiplication in the frequency domain corresponds to circular convolution in the time domain:DFT(𝑥∗𝑦)=DFT(𝑥)⋅DFT(𝑦)(3)•Shift property: 时域中的移位对应频域中的相位旋转。若 𝑦𝑛=𝑥𝑛−𝑚，则 𝑌𝑘=𝜔𝑚𝑘𝑁𝑋𝑘。A Visual IntuitionBelow is a margin figure showing the magnitude spectrum of a simple signal:0123456Frequency bin 𝑘Figure 1: Magnitude spectrum of a two-tone signal (50 Hz + 120 Hz). The two peaks correspond to the two frequency components.As Figure 1 shows, the FFT clearly separates the two frequency components.The Cooley–Tukey FFT AlgorithmThe key insight of the FFT is to exploit the symmetry and periodicity of 𝜔𝑁. By splitting the DFT into even and odd indices:𝑋𝑘=∑𝑁/2−1𝑚=0𝑥2𝑚𝜔𝑚𝑘𝑁/2⏟⏟⏟⏟⏟⏟⏟𝐸𝑘+𝜔𝑘𝑁∑𝑁/2−1𝑚=0𝑥2𝑚+1𝜔𝑚𝑘𝑁/2⏟⏟⏟⏟⏟⏟⏟𝑂𝑘(4)This gives us the butterfly operation, which is the computational core of the FFT:𝑋𝑘=𝐸𝑘+𝜔𝑘𝑁𝑂𝑘𝑋𝑘+𝑁/2=𝐸𝑘−𝜔𝑘𝑁𝑂𝑘(5)Figure 2 visualizes this butterfly structure — each pair of inputs (𝐸𝑘,𝑂𝑘) produces two outputs via addition and subtraction of the twiddle factor 𝜔𝑘𝑁:Figure 2: The butterfly operation. Each pair of inputs produces two outputs via addition/subtraction of the twiddle factor.Since 𝐸𝑘 and 𝑂𝑘 are periodic with period 𝑁/2, we only need to compute them for 𝑘=0,1,…,𝑁/2−1.通过递归地应用这一分解，我们可以将 𝑁 点 DFT 的计算分解为 log2𝑁 层蝶形运算，每层包含 𝑁/2 次蝶形操作。Complexity AnalysisTable 1: Comparison of DFT and FFT computational complexity.AlgorithmMultiplicationsAdditionsTotalNaive DFT𝑁2𝑁(𝑁−1)𝑂(𝑁2)Radix-2 FFT𝑁2log2𝑁𝑁log2𝑁𝑂(𝑁log𝑁)For a concrete example, consider 𝑁=220≈106:•Naive DFT: ∼1012 operations•FFT: ∼107 operations•Speedup factor: ∼105That’s roughly 100,000× faster — the difference between a computation finishing in seconds vs. taking all day.2 Python Implementation3Python ImplementationBelow is a recursive radix-2 FFT implementation. Note the elegant correspondence to the mathematical derivation above.import numpy as npdef 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 FFTif __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 RevealsFigure 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.3 Conclusion4Figure 3: FFT spectrum of a two-tone signal. The peaks at 50 Hz and 120 Hz correspond to the two frequency components in the original signal.ApplicationsSignal processing. The most common application — spectral analysis, filtering, and compression (MP3, JPEG, etc.) all rely on the FFT.The FFT reduced the operation count for an 𝑁-point transform from 𝑁2 to 𝑁log𝑁. For 𝑁=106, that’s a factor of nearly 100,000. This single algorithm change made real-time digital signal processing possible.— Press et al. [4]Other important applications include:1.Polynomial multiplication: multiplying two degree-𝑛 polynomials in 𝑂(𝑛log𝑛) instead of 𝑂(𝑛2)2.Large integer multiplication: the Schönhage–Strassen algorithm uses FFT to multiply 𝑛-digit integers in 𝑂(𝑛log𝑛loglog𝑛)3.Partial differential equations: 谱方法利用 FFT 在频域中高效求解偏微分方程，在流体力学和量子力学模拟中广泛使用4.Convolution: fast computation of convolutions via the convolution theorem, used in deep learning (CNNs)FFT in the Real WorldA wide figure showing a more detailed visualization:Figure 4: A time-domain signal containing multiple frequency components. The FFT decomposes this into its constituent frequencies.Time → · A noisy composite signal with multiple frequency componentsAs Figure 4 demonstrates, even a visually complex signal is just a sum of simple sinusoids — the FFT tells us exactly which ones.ConclusionThe FFT is one of the most beautiful and practical algorithms in all of computational mathematics. It reduces the complexity of the DFT from 𝑂(𝑁2) to 𝑂(𝑁log𝑁), making large-scale spectral analysis feasible.4 Bibliography5The 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.Bibliography[1]G. Strang, Introduction to Applied Mathematics. Wellesley-Cambridge Press, 1994.[2]S. W. Smith, The Scientist and Engineer's Guide to Digital Signal Processing. California Technical Publishing, 1997. [Online]. Available: https://www.dspguide.com/[3]M. Frigo and S. G. Johnson, “The Design and Implementation of FFTW3,” Proceedings of the IEEE, vol. 93, no. 2, pp. 216–231, 2005.[4]W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes: The Art of Scientific Computing, 3rd ed. Cambridge University Press, 2007.5

HTML view coming soon.

Download PDF for the full formatted version.