Fourier Analysis and Fast Fourier Transform Cheat Sheet

Updated 2026-05-21

Next Topic: Game Theory for Computer Science Cheat Sheet

Fourier analysis is the mathematical framework for decomposing signals into sums of sinusoids, bridging the time domain and the frequency domain. Its computational workhorse — the Fast Fourier Transform (FFT) — reduces an O(N²) discrete Fourier transform to O(N log N), making it the engine behind audio codecs, image compression, wireless communications, radar, and deep-learning architectures. The critical mental model to internalize is that every FFT is merely an algebraic refactoring of the DFT: the math is identical, only the order of operations changes — yet this reordering yields orders-of-magnitude speedups that Gilbert Strang called "the most important numerical algorithm of our lifetime."

What This Cheat Sheet Covers

This topic spans 24 focused tables and 260 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Fourier Series FundamentalsTable 2: Continuous-Time Fourier Transform (CTFT) PropertiesTable 3: Discrete Fourier Transform (DFT) PropertiesTable 4: FFT AlgorithmsTable 5: Real-Input FFT and Hermitian SymmetryTable 6: Inverse FFT and Normalization ConventionsTable 7: Convolution Theorem and Fast Polynomial MultiplicationTable 8: Windowing FunctionsTable 9: Sampling, Aliasing, and Frequency ResolutionTable 10: Short-Time Fourier Transform (STFT) and SpectrogramsTable 11: 2D FFT for Image ProcessingTable 12: FFT Libraries and ToolkitsTable 13: Number-Theoretic Transform (NTT)Table 14: FFT Pitfalls and Common MistakesTable 15: Fourier Analysis ApplicationsReferencesReferencesReferencesReferencesReferencesReferencesReferencesReferencesReferences

Table 1: Fourier Series Fundamentals

The Fourier series expresses any periodic function as an infinite sum of harmonically related sinusoids, grounding all of Fourier analysis in its most concrete form. Understanding the trigonometric and complex exponential forms, the role of Dirichlet conditions, and the Gibbs phenomenon is essential before moving to the continuous-time Fourier transform.

Concept	Example	Description
Fourier series (trigonometric form)	$x(t) = \frac{a_0}{2} + \sum_{n=1}^{\infty}\left(a_n\cos\frac{2\pi n t}{T} + b_n\sin\frac{2\pi n t}{T}\right)$	Represents a periodic signal of period $T$ as a weighted sum of cosines and sines at integer multiples of the fundamental frequency $f_0 = 1/T$ .
Fourier series (complex exponential form)	$x(t) = \sum_{n=-\infty}^{\infty} c_n\, e^{j 2\pi n t / T}$ $c_n = \frac{1}{T}\int_0^T x(t)\,e^{-j 2\pi n t / T}\,dt$	• Compact form using Euler's formula $e^{j\theta}=\cos\theta+j\sin\theta$ • complex coefficients $c_n$ encode both amplitude and phase of each harmonic
Fundamental frequency and harmonics	Signal period $T=0.01\text{ s}$ → $f_0=100\text{ Hz}$ ; harmonics at $200, 300, \ldots\text{ Hz}$	• The fundamental frequency $f_0=1/T$ is the lowest; harmonics are integer multiples $n f_0$ . • All energy is confined to discrete spectral lines separated by $f_0$ .
Dirichlet conditions	A square wave: finite discontinuities per period, bounded, absolutely integrable	Sufficient (not necessary) conditions for Fourier series convergence: finite number of discontinuities and extrema per period, signal is absolutely integrable over one period.

Table 1: Fourier Series Fundamentals

Concept	Example	Description
Fourier series (trigonometric form)	$x(t) = \frac{a_0}{2} + \sum_{n=1}^{\infty}\left(a_n\cos\frac{2\pi n t}{T} + b_n\sin\frac{2\pi n t}{T}\right)$	Represents a periodic signal of period $T$ as a weighted sum of cosines and sines at integer multiples of the fundamental frequency $f_0 = 1/T$ .
Fourier series (complex exponential form)	$x(t) = \sum_{n=-\infty}^{\infty} c_n\, e^{j 2\pi n t / T}$ $c_n = \frac{1}{T}\int_0^T x(t)\,e^{-j 2\pi n t / T}\,dt$	• Compact form using Euler's formula $e^{j\theta}=\cos\theta+j\sin\theta$ • complex coefficients $c_n$ encode both amplitude and phase of each harmonic
Fundamental frequency and harmonics	Signal period $T=0.01\text{ s}$ → $f_0=100\text{ Hz}$ ; harmonics at $200, 300, \ldots\text{ Hz}$	• The fundamental frequency $f_0=1/T$ is the lowest; harmonics are integer multiples $n f_0$ . • All energy is confined to discrete spectral lines separated by $f_0$ .
Dirichlet conditions	A square wave: finite discontinuities per period, bounded, absolutely integrable	Sufficient (not necessary) conditions for Fourier series convergence: finite number of discontinuities and extrema per period, signal is absolutely integrable over one period.