Week 13 — Transforms and DSP: Laplace, z-Transform, Filters, and the FFT

Overview

This week generalizes the Fourier transform to the complex plane (Laplace for continuous time, the z-transform for discrete) where poles and zeros encode stability and system behavior, then turns to practical digital signal processing: designing FIR and IIR filters, the discrete Fourier transform and circular convolution, and the fast Fourier transform that makes spectral computation cheap. This is where the theory becomes the algorithm you actually run.

Readings

OWN Ch 9 — Laplace transform. Region of convergence, poles/zeros, stability, LTI analysis.
OWN Ch 10 — z-transform. ROC, poles/zeros, difference equations, discrete-time stability.
O&S Ch 4 — Sampling of continuous-time signals (review and depth).
O&S Ch 7 — Filter design. FIR/IIR, window and frequency-sampling methods.
O&S Ch 8 — DFT. Definition, circular convolution, properties.
O&S Ch 9 — Computation of the DFT. FFT algorithms and complexity.
O&S Ch 10 — Fourier analysis using the DFT. Windowing, spectral leakage, the STFT.

Key Concepts

Laplace and z-transforms

The Laplace transform \(X(s) = \int_0^\infty x(t)e^{-st}\,dt\) generalizes the Fourier transform to complex \(s = \sigma + j\omega\); the z-transform \(X(z) = \sum_n x[n]z^{-n}\) does the same for discrete time. The region of convergence matters as much as the formula. A rational transform is described by its poles and zeros, and stability is read off pole locations:

Continuous-time LTI is stable iff all poles lie in the left half-plane (\(\operatorname{Re}(s) < 0\)).
Discrete-time LTI is stable iff all poles lie inside the unit circle (\(|z| < 1\)).

Difference equations \(\sum_k a_k y[n-k] = \sum_k b_k x[n-k]\) transform into the rational system function \(H(z) = B(z)/A(z)\) — the algebra of designing and analyzing filters.

Filter design

A filter shapes a signal’s spectrum (low-pass, high-pass, band-pass). FIR filters have finite impulse response, are always stable, and can have exactly linear phase; they are designed by windowing an ideal response or by frequency sampling, trading transition width against length. IIR filters use feedback (poles), achieving sharp responses with fewer coefficients but risking instability and nonlinear phase; they are often designed from analog prototypes (Butterworth, Chebyshev) via the bilinear transform.

DFT and circular convolution

The discrete Fourier transform samples the spectrum of a length-\(N\) sequence:

\[X[k] = \sum_{n=0}^{N-1} x[n]\,e^{-j 2\pi k n / N}, \qquad k = 0,\dots,N-1.\]

The DFT implements circular (not linear) convolution; linear convolution is recovered by zero-padding to avoid time-domain wraparound. The DFT is the practical, finite, computable version of the transforms in Week 12.

The FFT

The fast Fourier transform computes the DFT in \(O(N\log N)\) instead of \(O(N^2)\) by recursively splitting the sum (radix-2 decimation-in-time/frequency exploits the divide-and-conquer structure of Week 14). This single algorithmic improvement is what makes real-time spectral processing, fast convolution, and polynomial multiplication feasible.

Windowing and the STFT

Analyzing a finite chunk of a signal multiplies it by a window, which convolves the spectrum with the window’s transform and causes spectral leakage; window choice (Hann, Hamming, Blackman) trades main-lobe width against side-lobe height. The short-time Fourier transform slides a window to produce a time–frequency spectrogram — the front end of audio and speech pipelines.

Connections

Backward: the region of convergence, poles/zeros, and Laurent expansions used here are exactly the complex analysis of Week 11.
Forward: pole/zero stability and the FFT recur in performance work and the algorithmic complexity of Week 14; spectral/Fourier methods reappear in optics (Week 18).
Across courses: digital filtering and state estimation front ends (Course 1), spectrogram/MFCC features for speech (Course 3), DSP and performance kernels (Course 4).