Fourier Analysis and Fast Fourier Transform Cheat Sheet

Updated 2026-05-21

Next Topic: Game Theory for Computer Science Cheat Sheet

🧠Study flashcards on this topic113 cards · spaced repetition→

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, 113 flashcards. 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

Quick IndexSubscribe to unlock

A jump-to index of every table row in this cheat sheet.

Mind MapSubscribe to unlock

An interactive map of every table and concept in this topic.

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.
Gibbs phenomenon	Truncated square-wave Fourier series overshoots ≈ 8.9% of the jump at each discontinuity regardless of $N$	• Overshoot near a discontinuity that persists as the number of terms → ∞ • the overshoot does not vanish but narrows • reduced in practice by windowing or Fejér summation
Parseval's theorem (Fourier series)	$\frac{1}{T}\int_0^T \lvert x(t)\rvert^2,dt = \sum_{n=-\infty}^{\infty}\lvert c_n\rvert^2$	• Signal energy (or power) is conserved between time and frequency domains • the sum of squared coefficients equals the mean power of the signal
Convergence at discontinuities	Square wave at $t=0$: series converges to $\frac{x(0^+)+x(0^-)}{2}$	At a jump discontinuity the Fourier series converges to the average of the left and right limits, not to either value.

Table 2: Continuous-Time Fourier Transform (CTFT) Properties

The CTFT extends Fourier analysis from periodic signals to aperiodic continuous-time signals, yielding a continuous spectrum. These properties — linearity, shifting, scaling, convolution, duality — are the core algebraic toolkit that every signal processing practitioner applies daily.

Property	Example	Description
Fourier transform definition	$X(\omega) = \int_{-\infty}^{\infty} x(t),e^{-j\omega t},dt$ $x(t) = \frac{1}{2\pi}\int_{-\infty}^{\infty} X(\omega),e^{j\omega t},d\omega$	• Decomposes an aperiodic signal into a continuous spectrum $X(\omega)$ • the inverse recovers the signal • the spectrum is generally complex-valued

The rest of this section is part of the full cheat sheet

Table 3: Discrete Fourier Transform (DFT) Properties

The DFT is the computable, finite-length counterpart of the CTFT, operating on $N$ sampled values and yielding $N$ complex frequency bins. Its circular (rather than linear) shift behavior, periodicity assumption, and bit-reversal structure are key distinctions from the continuous-time transform.

Property	Example	Description
DFT definition	$X[k] = \sum_{n=0}^{N-1} x[n],e^{-j2\pi kn/N},\quad k=0,\ldots,N-1$	• Transforms an $N$-point sequence to $N$ complex frequency bins spaced $f_s/N$ Hz apart • frequency bin $k$ represents frequency $k,f_s/N$.

The rest of this section is part of the full cheat sheet

Table 4: FFT Algorithms

These are the algorithmic techniques that reduce DFT computation from $O(N^2)$ to $O(N\log N)$ or better. The Cooley–Tukey family dominates practice, but understanding Bluestein, Rader, and mixed-radix variants matters when input lengths are prime, arbitrary, or when operating in finite fields.

Algorithm	Example	Description
Cooley–Tukey radix-2 DIT (Decimation-In-Time)	$N=8$: split $x[n]$ into even/odd, recursively; $\frac{N}{2}\log_2 N=12$ butterfly ops	• Most common FFT variant • splits input into even/odd samples recursively • requires $N=2^k$ • input arrives in bit-reversed order, output in natural order • each stage uses twiddle factors $W_N^k = e^{-j2\pi k/N}$.

The rest of this section is part of the full cheat sheet

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.
Gibbs phenomenon	Truncated square-wave Fourier series overshoots ≈ 8.9% of the jump at each discontinuity regardless of $N$	• Overshoot near a discontinuity that persists as the number of terms → ∞ • the overshoot does not vanish but narrows • reduced in practice by windowing or Fejér summation
Parseval's theorem (Fourier series)	$\frac{1}{T}\int_0^T \lvert x(t)\rvert^2,dt = \sum_{n=-\infty}^{\infty}\lvert c_n\rvert^2$	• Signal energy (or power) is conserved between time and frequency domains • the sum of squared coefficients equals the mean power of the signal
Convergence at discontinuities	Square wave at $t=0$: series converges to $\frac{x(0^+)+x(0^-)}{2}$	At a jump discontinuity the Fourier series converges to the average of the left and right limits, not to either value.

Table 2: Continuous-Time Fourier Transform (CTFT) Properties

Property	Example	Description
Fourier transform definition	$X(\omega) = \int_{-\infty}^{\infty} x(t),e^{-j\omega t},dt$ $x(t) = \frac{1}{2\pi}\int_{-\infty}^{\infty} X(\omega),e^{j\omega t},d\omega$	• Decomposes an aperiodic signal into a continuous spectrum $X(\omega)$ • the inverse recovers the signal • the spectrum is generally complex-valued

Table 3: Discrete Fourier Transform (DFT) Properties

Property	Example	Description
DFT definition	$X[k] = \sum_{n=0}^{N-1} x[n],e^{-j2\pi kn/N},\quad k=0,\ldots,N-1$	• Transforms an $N$-point sequence to $N$ complex frequency bins spaced $f_s/N$ Hz apart • frequency bin $k$ represents frequency $k,f_s/N$.

Table 4: FFT Algorithms

Algorithm	Example	Description
Cooley–Tukey radix-2 DIT (Decimation-In-Time)	$N=8$: split $x[n]$ into even/odd, recursively; $\frac{N}{2}\log_2 N=12$ butterfly ops	• Most common FFT variant • splits input into even/odd samples recursively • requires $N=2^k$ • input arrives in bit-reversed order, output in natural order • each stage uses twiddle factors $W_N^k = e^{-j2\pi k/N}$.