Summary of The Fast Fourier Transform (FFT)

The Fast Fourier Transform (FFT) Explained for Students

SummaryKnowledge testFlashcardsPodcastMindmap

Introduction

The Fast Fourier Transform (FFT) is an efficient algorithm to compute the Discrete Fourier Transform (DFT) and its inverse. While the DFT and FFT produce identical results, the FFT reduces computational cost dramatically for sequences whose length is a power of two. FFT is fundamental in signal processing, communications, image processing, and many scientific computations.

Definition: The Discrete Fourier Transform (DFT) of a sequence $x[n]$ of length $N$ is the sequence $X[k]$ given by $$X[k]=\sum_{n=0}^{N-1} x[n],e^{-j,2\pi,\frac{kn}{N}},\quad k=0,1,\dots,N-1.$$

Why FFT matters

  • Direct computation of the DFT requires $O(N^2)$ complex multiplications for $N$ samples.
  • The FFT reduces this to $O\left(\frac{N}{2}\log_2 N\right)$ complex multiplications for the classic radix-2 Cooley–Tukey algorithm, yielding a speed-up factor around $\frac{2N}{\log_2 N}$ for large $N$.
💡 Věděli jste?Fun fact: FFT algorithms enabled many modern digital signal processing applications because they lowered computational barriers when fast general-purpose processors became available.

Key concepts and building blocks

DFT phasor and W-matrix

  • The basic DFT phasor (twiddle factor) is $$W_N = e^{-j,\frac{2\pi}{N}}.$$
  • All DFT computations use powers of this phasor, $W_N^{kn}$.

Definition: The DFT matrix $\mathbf{W}_N$ is the $N\times N$ matrix with entries $[\mathbf{W}N]{k,n}=W_N^{kn}$ so that $\mathbf{X}=\mathbf{W}_N\mathbf{x}$.

Matrix view and precomputation

  • The DFT can be written as matrix multiplication $\mathbf{X}=\mathbf{W}_N\mathbf{x}$.
  • Because $\mathbf{W}_N$ has only $N$ distinct powers, it can be precomputed or cached to save repeated evaluations when multiple transforms of the same length are required.

Cooley–Tukey decomposition (radix-2)

  • If $N$ is a power of two, the DFT of length $N$ can be recursively split into two DFTs of length $N/2$ (even and odd indexed samples). Repeating this decomposition yields the radix-2 FFT.
  • Example for $N=8$: an 8-point DFT splits into two 4-point DFTs, each 4-point DFT splits into two 2-point DFTs, etc.

Butterfly block

  • A basic computational unit of radix-2 FFT is the butterfly combining two complex values $a$ and $b$ to produce $$A=a+b\quad\text{and}\quad B=a+b,W_N^r,$$ where $W_N^r$ is an appropriate twiddle factor.

Definition: A butterfly is the elementary operation that combines pairwise values in the FFT stages.

Bit-reversal permutation

  • The natural order of outputs from in-place radix-2 FFT implementations typically appears in bit-reversed index order. Reordering to natural order requires applying a bit-reversal permutation to indices.
  • Example for $N=8$: index $3$ (binary $011$) maps to spectrum position with reversed bits $110$ which equals $6$.

Practical computation in MATLAB and Python

  • In MATLAB: use X = fft(x) or X = fft(x,N); inverse with x = ifft(X).
  • In NumPy: X = numpy.fft.fft(x) or X = numpy.fft.fft(x, N); inverse with x = numpy.fft.ifft(X).
  • If the input length is a power of two, implementations apply FFT algorithm. Otherwise, some libraries may compute DFT directly or use mixed-radix algorithms.
  • Padding/truncation rules: if you request length $N$ and input is shorter, the signal is zero-padded; if longer, it is truncated from the end.

FFT normalization variants (NumPy)

  • NumPy supports three normalization modes via the norm argument:
    • norm="backward" (default): forward FFT unnormalized, inverse scaled by $1/N$.
    • norm="forward": forward scaled by $1/N$, inverse unnormalized.
    • norm="ortho": symmetric orthonormal scaling by $1/\sqrt{N}$ for both directions.

Definition: The orthonormal DFT pair uses normalization factors so that the transform is unitary and preserves energy.

SciPy FFT alternatives

  • SciPy offers scipy.fftpack (legacy) and scipy.fft (newer). The newer scipy.fft is a superset of NumPy FFT, offers more algorithms, better multidimensional suppor
Zaregistruj se pro celé shrnutí
FlashcardsKnowledge testSummaryPodcastMindmap
Start for free

Already have an account? Sign in

Fast Fourier Transform

Klíčové pojmy: FFT computes DFT efficiently reducing complexity from $O(N^2)$ to $O(N\log N)$, DFT uses twiddle factor $W_N=e^{-j\,2\pi/N}$ and powers $W_N^{kn}$, Cooley–Tukey radix-2 splits length $N$ into two $N/2$ DFTs recursively, Butterfly is the elementary pairwise FFT operation combining $a$ and $b$, FFT output from in-place radix-2 often needs bit-reversal reordering, NumPy/MATLAB provide fft/ifft; specify length $N$ to pad or truncate input, NumPy `norm` options: backward, forward, ortho affect scaling, SciPy `scipy.fft` can offer FFTW-based optimizations and multidimensional routines, Use power-of-two lengths for simplest and often fastest transforms, FFT enables fast convolution by transforming to frequency domain and multiplying

## Introduction The **Fast Fourier Transform (FFT)** is an efficient algorithm to compute the Discrete Fourier Transform (DFT) and its inverse. While the DFT and FFT produce identical results, the FFT reduces computational cost dramatically for sequences whose length is a power of two. FFT is fundamental in signal processing, communications, image processing, and many scientific computations. > Definition: The Discrete Fourier Transform (DFT) of a sequence $x[n]$ of length $N$ is the sequence $X[k]$ given by > $$X[k]=\sum_{n=0}^{N-1} x[n]\,e^{-j\,2\pi\,\frac{kn}{N}},\quad k=0,1,\dots,N-1.$$ ## Why FFT matters - Direct computation of the DFT requires $O(N^2)$ complex multiplications for $N$ samples. - The FFT reduces this to $O\left(\frac{N}{2}\log_2 N\right)$ complex multiplications for the classic radix-2 Cooley–Tukey algorithm, yielding a speed-up factor around $\frac{2N}{\log_2 N}$ for large $N$. Fun fact: FFT algorithms enabled many modern digital signal processing applications because they lowered computational barriers when fast general-purpose processors became available. ## Key concepts and building blocks ### DFT phasor and W-matrix - The basic DFT phasor (twiddle factor) is $$W_N = e^{-j\,\frac{2\pi}{N}}.$$ - All DFT computations use powers of this phasor, $W_N^{kn}$. > Definition: The DFT matrix $\mathbf{W}_N$ is the $N\times N$ matrix with entries $[\mathbf{W}_N]_{k,n}=W_N^{kn}$ so that $\mathbf{X}=\mathbf{W}_N\mathbf{x}$. ### Matrix view and precomputation - The DFT can be written as matrix multiplication $\mathbf{X}=\mathbf{W}_N\mathbf{x}$. - Because $\mathbf{W}_N$ has only $N$ distinct powers, it can be precomputed or cached to save repeated evaluations when multiple transforms of the same length are required. ### Cooley–Tukey decomposition (radix-2) - If $N$ is a power of two, the DFT of length $N$ can be recursively split into two DFTs of length $N/2$ (even and odd indexed samples). Repeating this decomposition yields the radix-2 FFT. - Example for $N=8$: an 8-point DFT splits into two 4-point DFTs, each 4-point DFT splits into two 2-point DFTs, etc. ### Butterfly block - A basic computational unit of radix-2 FFT is the butterfly combining two complex values $a$ and $b$ to produce $$A=a+b\quad\text{and}\quad B=a+b\,W_N^r\,$$ where $W_N^r$ is an appropriate twiddle factor. > Definition: A butterfly is the elementary operation that combines pairwise values in the FFT stages. ### Bit-reversal permutation - The natural order of outputs from in-place radix-2 FFT implementations typically appears in bit-reversed index order. Reordering to natural order requires applying a bit-reversal permutation to indices. - Example for $N=8$: index $3$ (binary $011$) maps to spectrum position with reversed bits $110$ which equals $6$. ## Practical computation in MATLAB and Python - In MATLAB: use `X = fft(x)` or `X = fft(x,N)`; inverse with `x = ifft(X)`. - In NumPy: `X = numpy.fft.fft(x)` or `X = numpy.fft.fft(x, N)`; inverse with `x = numpy.fft.ifft(X)`. - If the input length is a power of two, implementations apply FFT algorithm. Otherwise, some libraries may compute DFT directly or use mixed-radix algorithms. - Padding/truncation rules: if you request length $N$ and input is shorter, the signal is zero-padded; if longer, it is truncated from the end. ### FFT normalization variants (NumPy) - NumPy supports three normalization modes via the `norm` argument: - `norm="backward"` (default): forward FFT unnormalized, inverse scaled by $1/N$. - `norm="forward"`: forward scaled by $1/N$, inverse unnormalized. - `norm="ortho"`: symmetric orthonormal scaling by $1/\sqrt{N}$ for both directions. > Definition: The orthonormal DFT pair uses normalization factors so that the transform is unitary and preserves energy. ## SciPy FFT alternatives - SciPy offers `scipy.fftpack` (legacy) and `scipy.fft` (newer). The newer `scipy.fft` is a superset of NumPy FFT, offers more algorithms, better multidimensional suppor