Reference topics: MIT 6.341 · independent study notes, not affiliated

Digital Signal Processing

Discrete-time signals, DFT/FFT, digital filters (FIR/IIR), sampling, quantization, and applications.

5Lectures
1Assignments
1Exams
40hDuration
1

Discrete-Time Signals and Systems

The Digital Signal Processing Revolution DSP changed everything. Before DSP, filters were analog circuits: op-amps, resistors, capacitors. Now they're algorithms: multiply, add, store. Why does...

⏱ 50 min read

The Digital Signal Processing Revolution

DSP changed everything. Before DSP, filters were analog circuits: op-amps, resistors, capacitors. Now they're algorithms: multiply, add, store. Why does this matter?

  • Reproducibility: a digital filter gives the same result every time
  • Flexibility: change the coefficients, change the filter
  • Complexity: implement filters that are impossible in analog
  • Storage: record and replay exact signals
  • Compression: reduce data before transmission

DSP powers your phone, your music player, your Wi-Fi router, your camera, medical imaging, radar.

Discrete-Time Signals

A discrete-time signal x[n] is defined for integer n only. Between samples, nothing exists (mathematically). In practice, we reconstruct continuous signals via interpolation.

Common signals:

  • Unit impulse δ[n]: 1 at n=0, 0 elsewhere
  • Unit step u[n]: 1 for n≥0, 0 for n<0
  • Exponential: x[n] = a^n
  • Sinusoid: x[n] = A cos(Ωn + φ)
  • Complex exponential: x[n] = e^(jΩn)

The Key Difference: Frequency is Periodic

For continuous sinusoids, cos(ωt) has a unique frequency ω ∈ [0, ∞). For discrete sinusoids, cos(Ωn) is periodic in Ω with period 2π:

cos((Ω + 2π)n) = cos(Ωn + 2πn) = cos(Ωn)

So Ω and Ω+2πk describe the same signal. Only Ω ∈ [0, π] is unique. The range [π, 2π] is symmetric with [0, π].

This is a fundamental difference. It leads to aliasing and the Nyquist limit.

Basic Operations

Time shift: y[n] = x[n - n0]. Delays the signal.

Time reversal: y[n] = x[-n].

Scaling: y[n] = A × x[n].

Addition: y[n] = x1[n] + x2[n].

Multiplication: y[n] = x1[n] × x2[n]. This is important in modulation.

LTI Systems and Convolution

A system is Linear and Time-Invariant (LTI) if:

  • Superposition holds
  • Behavior doesn't change with time

LTI systems are fully described by their impulse response h[n].

Output for any input x[n]:

y[n] = x[n] * h[n] = Σ_{k=-∞}^{∞} x[k] h[n-k]

Convolution. This is the fundamental operation of DSP.

Stability and Causality

Causal: h[n] = 0 for n < 0. Cannot respond to future inputs.

BIBO stable: Bounded input → Bounded output. Condition: Σ|h[n]| < ∞.

Causal + BIBO stable is the standard for real-time DSP.

Difference Equations

LTI systems are described by difference equations:

y[n] = -a1 y[n-1] - a2 y[n-2] + b0 x[n] + b1 x[n-1] + b2 x[n-2]

This is the general IIR (Infinite Impulse Response) form. If all a's are zero, it's FIR (Finite Impulse Response).

FIR vs IIR

FIR: h[n] has finite length. Always stable. Can have exact linear phase. More computation.

IIR: h[n] infinite (feedback). Can be unstable. Nonlinear phase usually. Less computation for sharp filters.

FIR for audio, IIR for control.

Example: Moving Average

y[n] = (x[n] + x[n-1] + x[n-2] + x[n-3]) / 4

FIR filter with h = [0.25, 0.25, 0.25, 0.25]. Low-pass, simple smoothing.

Length L moving average: cutoff at approximately fs/L.

Example: One-Pole IIR

y[n] = α × x[n] + (1 - α) × y[n-1]

Alpha close to 1: slow smoothing. Alpha close to 0: fast smoothing.

This is an exponential moving average. Simple, efficient low-pass filter.

Key Takeaways

  • Discrete signals defined for integer n only
  • Frequency is periodic with period 2π
  • LTI systems described by impulse response
  • Convolution: y = x * h
  • Difference equations describe LTI systems
  • FIR (finite) vs IIR (feedback)
  • DSP gives reproducibility, flexibility, complexity
2

The Z-Transform and Transfer Functions

Why the Z-Transform? Just as the Laplace transform handles continuous-time systems, the Z-transform handles discrete-time systems. It converts difference equations into algebraic equations, making...

⏱ 50 min read

Why the Z-Transform?

Just as the Laplace transform handles continuous-time systems, the Z-transform handles discrete-time systems. It converts difference equations into algebraic equations, making analysis and design much easier.

Definition

For a discrete-time signal x[n]:

X(z) = Σ_{n=-∞}^{∞} x[n] z^(-n)

where z is a complex variable. The set of z values for which the sum converges is the Region of Convergence (ROC).

Common Transforms

| x[n] | X(z) |
|------|------|
| δ[n] | 1 |
| u[n] | z/(z-1) |
| a^n u[n] | z/(z-a) |
| n a^n u[n] | az/(z-a)² |
| cos(Ω0 n) u[n] | (z² - z cos Ω0) / (z² - 2z cos Ω0 + 1) |

Properties

Linearity: a x1[n] + b x2[n] ↔ a X1(z) + b X2(z)

Time shift: x[n - n0] ↔ z^(-n0) X(z)

Scaling in z: a^n x[n] ↔ X(z/a)

Time reversal: x[-n] ↔ X(1/z)

Convolution: x[n] * h[n] ↔ X(z) × H(z)

Initial value: x[0] = lim(z→∞) X(z)

The convolution property is the most important. It turns convolution into multiplication.

Transfer Function

For an LTI system with input x[n] and output y[n]:

H(z) = Y(z) / X(z)

For a difference equation:

y[n] = Σ b_k x[n-k] - Σ a_k y[n-k]

The transfer function is:

H(z) = (Σ b_k z^(-k)) / (1 + Σ a_k z^(-k))

The numerator gives the zeros, the denominator gives the poles.

Poles and Stability

For a causal system, it's BIBO stable if all poles are inside the unit circle (|z| < 1).

This is the discrete-time analog of "poles in the left half-plane" for continuous systems.

Poles on the unit circle: marginally stable (oscillates forever).
Poles outside the unit circle: unstable (exponential growth).

Example: One-Pole System

y[n] = α x[n] + (1-α) y[n-1]

Taking Z-transform:

Y(z) = α X(z) + (1-α) z^(-1) Y(z)

H(z) = α / (1 - (1-α) z^(-1))

Pole at z = 1 - α. For 0 < α < 1, pole is inside unit circle → stable.

For α = 0.1, pole at 0.9. Slow decay.
For α = 0.9, pole at 0.1. Fast decay.

Frequency Response

Evaluate H(z) on the unit circle (z = e^(jΩ)):

H(e^(jΩ)) = H(z) |_{z = e^(jΩ)}

This gives the frequency response — the gain and phase for each digital frequency Ω.

|H(e^(jΩ))| is the magnitude response.
∠H(e^(jΩ)) is the phase response.

Plot vs Ω from 0 to π (higher frequencies are symmetric).

Geometric Interpretation

The frequency response is the product of distances from e^(jΩ) to each zero, divided by distances to each pole.

Zeros near the unit circle → dips in magnitude response.
Poles near the unit circle → peaks in magnitude response.

Stability Condition Revisited

For an IIR filter, stability requires all poles inside the unit circle. If even one pole is outside, the filter is unstable and useless.

In practice, design with margins — poles 0.99 or less.

Key Takeaways

  • Z-transform converts difference equations to algebra
  • Transfer function H(z) = Y(z)/X(z)
  • Poles and zeros determine frequency response
  • Stable iff all poles inside unit circle
  • Frequency response: H(e^(jΩ))
  • Geometric interpretation: distances from poles and zeros
  • Design with pole margins for robustness
3

The Discrete Fourier Transform and FFT

From Continuous to Discrete Frequency We&#39;ve seen the Fourier series for periodic signals, the Fourier transform for aperiodic, and the DTFT for discrete signals. Now: the DFT, which is what...

⏱ 50 min read

From Continuous to Discrete Frequency

We've seen the Fourier series for periodic signals, the Fourier transform for aperiodic, and the DTFT for discrete signals. Now: the DFT, which is what computers actually compute.

The Discrete Fourier Transform

For a length-N sequence x[0..N-1]:

X[k] = Σ_{n=0}^{N-1} x[n] e^(-j 2π k n / N), k = 0, 1, ..., N-1

The inverse:

x[n] = (1/N) Σ_{k=0}^{N-1} X[k] e^(j 2π k n / N)

The DFT transforms N time samples into N frequency samples.

Why N Samples?

The DFT assumes x[n] is periodic with period N. The frequency resolution is fs/N Hz. The maximum frequency represented is fs(N-1)/N ≈ fs/2 (Nyquist).

For a 1024-point DFT at 44.1 kHz:

  • Frequency resolution: 43 Hz
  • Frequency range: 0 to ~22 kHz

DFT as Matrix Multiplication

X = W × x

where W is the N×N DFT matrix with entries W[k][n] = e^(-j 2π k n / N).

Computing this naively takes O(N²) operations.

The FFT

The Fast Fourier Transform (Cooley-Tukey, 1965) computes the DFT in O(N log N).

For N = 1,048,576:

  • Naive DFT: 10¹² operations
  • FFT: 2 × 10⁷ operations

A 50,000x speedup. This is why FFT made DSP practical.

The FFT Algorithm (Radix-2)

Split length-N sequence into even and odd indices:

X[k] = Σ x[2m] e^(-j 2π k (2m) / N) + Σ x[2m+1] e^(-j 2π k (2m+1) / N)
= E[k] + e^(-j 2π k / N) O[k]

where E is the DFT of the even-indexed subsequence and O of the odd.

Recursively split until length-1. Combine results. Total complexity O(N log N).

Requires N to be a power of 2 (or a product of small primes).

Properties

Linearity: DFT of ax + by is aX + bY.

Parseval: Σ|x[n]|² = (1/N) Σ|X[k]|². Energy preserved.

Convolution: Circular convolution in time = multiplication in frequency.

This is used for fast convolution (multiply in frequency, IFFT back).

Circular vs Linear Convolution

DFT computes circular convolution, not linear. For linear convolution via FFT, zero-pad to at least length(x) + length(h) - 1.

This is the standard technique for fast FIR filtering.

Windowing

The DFT assumes the signal is periodic. If you chop a longer signal into blocks, discontinuities at block edges cause spectral leakage.

Apply a window (Hamming, Hann, Blackman) before the DFT to reduce leakage. Trade-off: narrower main lobe vs lower side lobes.

Applications

  • Spectrum analysis: identify frequencies in a signal
  • Fast convolution: for FIR filters
  • OFDM: modulation for Wi-Fi, 4G/5G
  • Audio processing: pitch shifting, time stretching
  • Image processing: JPEG uses 2D DCT (related to DFT)
  • Radar: matched filtering
  • Astronomy: pulsar detection
  • Medical: CT reconstruction

The FFT in Practice

Libraries: FFTW, KissFFT, CMSIS-DSP (ARM), Intel MKL.

On an MCU (Cortex-M4 with FPU): 1024-point FFT in ~1 ms.

For real-time audio: 1024-point FFT at 44.1 kHz, block rate ~43 Hz.

Key Takeaways

  • DFT: N samples → N frequency samples
  • O(N²) naive, O(N log N) with FFT
  • FFT is what makes DSP practical
  • Circular convolution via DFT; zero-pad for linear
  • Windowing reduces spectral leakage
  • FFT is universal: audio, image, radar, communications
  • Libraries handle the implementation; you focus on the application
4

FIR Filter Design

What is an FIR Filter? Finite Impulse Response: h[n] is nonzero only for a finite range. y[n] = Σ_{k=0}^{M-1} h[k] × x[n-k] M is the filter length. Output is a weighted sum of the last M inputs. FIR...

⏱ 50 min read

What is an FIR Filter?

Finite Impulse Response: h[n] is nonzero only for a finite range.

y[n] = Σ_{k=0}^{M-1} h[k] × x[n-k]

M is the filter length. Output is a weighted sum of the last M inputs.

FIR filters are always stable (no feedback) and can have exactly linear phase.

The Ideal Low-Pass Filter

In frequency domain, ideal low-pass:

H(e^(jΩ)) = 1 for |Ω| < Ωc
0 for Ωc < |Ω| < π

Taking the inverse DTFT gives an infinite sinc impulse response:

h[n] = sin(Ωc n) / (π n)

Truncate to length M for a real FIR filter. Truncation causes ripples (Gibbs phenomenon).

Windowing Method

Multiply the ideal impulse response by a window w[n]:

h_windowed[n] = h_ideal[n] × w[n]

Common windows:

  • Rectangular: sharp cutoff, big ripples
  • Hamming: good compromise, 43 dB side lobe
  • Hann: smoother, 31 dB side lobe
  • Blackman: best side lobes, widest main lobe

Trade-off: narrower main lobe (sharper transition) means higher side lobes (worse stopband).

Example Design

Design a low-pass FIR with:

  • Cutoff: 1 kHz
  • Sample rate: 8 kHz
  • Length: 65 taps
  • Window: Hamming

Normalized cutoff: Ωc = 2π × 1000/8000 = π/4.

Ideal: h_ideal[n] = sin(π n/4) / (π n), truncated to 65 taps (centered at n = 32).

Apply Hamming window. Result: sharp transition at 1 kHz, stopband attenuation ~53 dB.

Parks-McClellan Algorithm

Optimal equiripple FIR design. Gives the best possible filter for a given length and tolerance.

Instead of settling for window side lobes, distribute the error uniformly across the band.

Requires an iterative optimization (Remez exchange).

Available in MATLAB (firpm), Python (scipy.signal.remez), and other tools.

Linear Phase FIR

If h[n] is symmetric (h[n] = h[M-1-n]) or antisymmetric, the filter has exactly linear phase.

Linear phase = constant group delay = no phase distortion.

Critical for audio, image processing, communications.

Linear phase requires FIR (IIR cannot have exactly linear phase).

Types of Linear Phase FIR

Four types based on symmetry and length:

  • Type I: even length, symmetric — good for lowpass
  • Type II: even length, antisymmetric — good for highpass
  • Type III: odd length, symmetric — good for bandpass
  • Type IV: odd length, antisymmetric — good for differentiators

Moving Average Filter

Simplest FIR: h[n] = 1/M for n = 0..M-1.

Low-pass with cutoff ~fs/M. Poor transition but simple and efficient.

Useful for smoothing noisy sensors.

Bandpass and Highpass

Design a lowpass prototype, then frequency-shift:

h_bp[n] = 2 h_lp[n] cos(Ω0 n)

For highpass:

h_hp[n] = δ[n] - h_lp[n]

Modular design — build from lowpass prototype.

Implementation

Direct form:

y[n] = h[0] x[n] + h[1] x[n-1] + ... + h[M-1] x[n-M+1]

Use a circular buffer for x[]:

x[head] = new_input;
head = (head + 1) % M;
sum = 0;
for (int i = 0; i < M; i++) {
sum += h[i] * x[(head - i + M) % M];
}

For high-performance, use SIMD or a DSP with dedicated MAC units.

Fixed-Point vs Floating-Point

DSPs often use fixed-point for speed and cost.

  • Q15: 1 sign bit + 15 fractional bits, range [-1, 1)
  • Q31: 32-bit fixed-point

Careful with scaling to avoid overflow. Coefficient quantization affects the response slightly.

Key Takeaways

  • FIR: finite, always stable, can be linear phase
  • Design by windowing or Parks-McClellan
  • Linear phase requires symmetric h[n]
  • Moving average: simplest FIR
  • Build bandpass/highpass from lowpass prototype
  • Circular buffer for streaming
  • Fixed-point for embedded, float for desktop
  • Linear phase essential for audio and images
5

Adaptive Filters and Applications

What Are Adaptive Filters? A filter whose coefficients change over time to optimize some performance criterion. Used when the signal statistics are unknown or time-varying. Examples: Echo...

⏱ 50 min read

What Are Adaptive Filters?

A filter whose coefficients change over time to optimize some performance criterion. Used when the signal statistics are unknown or time-varying.

Examples:

  • Echo cancellation in phones
  • Channel equalization in modems
  • Noise cancellation in headphones
  • System identification
  • Beamforming in radar
  • Active vibration control

The General Structure

Input x[n], desired signal d[n]. Filter produces y[n] = w^T x[n]. Error e[n] = d[n] - y[n]. Update weights to minimize E[e²[n]].

The LMS Algorithm

Least Mean Squares: simplest adaptive filter.

For each sample:

y[n] = w^T x[n]
e[n] = d[n] - y[n]
w[n+1] = w[n] + μ e[n] x[n]

μ is the step size. Small μ: slow but stable. Large μ: fast but may diverge.

Stability: μ < 2 / (M × P_x), where P_x is the input power.

Example: Noise Cancellation

Reference microphone captures noise. Main microphone captures signal + noise. Adaptive filter estimates noise from reference and subtracts.

Classic application: Bose noise-canceling headphones.

Echo Cancellation

In a phone call, the far-end signal echoes back through the local speaker-microphone path. An adaptive filter estimates the echo path and subtracts it.

Long echo paths (100+ ms) require 1000+ taps. Uses NLMS (normalized LMS) for faster convergence.

Channel Equalization

In a communication channel, the received signal is distorted. Adaptive filter inverts the channel to recover the transmitted data.

Used in modems, DSL, wireless.

Training phase: send known sequence, adapt filter to match. Data phase: use adapted filter to equalize.

Recursive Least Squares (RLS)

Converges faster than LMS. Uses the inverse of the autocorrelation matrix.

w[n+1] = w[n] + k[n] e[n]

where k[n] = R^(-1)[n] x[n].

Complexity: O(M²) per sample vs O(M) for LMS. Faster convergence but more computation.

Applications

Active Noise Cancellation (ANC):

  • Feedforward: reference mic + error mic
  • Feedback: only error mic
  • Hybrid: both

Used in headphones, cars, HVAC ducts.

Adaptive Beamforming:

  • Multiple antennas
  • Adaptive weights to steer null toward interference
  • Used in radar, sonar, 5G massive MIMO

Adaptive Predistortion:

  • Compensate for nonlinear power amplifier
  • Used in 5G base stations

Adaptive Control:

  • Self-tuning regulators
  • Model Reference Adaptive Control (MRAC)

Convergence and Misadjustment

LMS converges when input is stationary. The final error has two parts:

  • Minimum mean-square error (unavoidable)
  • Misadjustment (from gradient noise)

Trade-off: larger μ → faster convergence, higher misadjustment.

Rule of thumb: μ ≈ 0.01 / (M × P_x) for reasonable balance.

Modern Extensions

  • NLMS: normalized step size, more robust
  • AP (Affine Projection): between LMS and RLS
  • Kalman filter: optimal for linear Gaussian systems
  • Deep learning: replace adaptive filters with neural networks for very complex problems

DSP in Practice

Real-time DSP requires:

  • Efficient algorithms (LMS, FFT, convolution)
  • Fixed-point or SIMD optimized code
  • Interrupt-driven I/O (ADC, DAC, DMA)
  • Ring buffers for streaming
  • Careful attention to latency

An ESP32 can run 48 kHz stereo audio filters. A dedicated DSP (TI C6000) runs GHz-rate processing. GPU tensors handle AI.

Key Takeaways

  • Adaptive filters optimize coefficients online
  • LMS: simple, O(M) per sample, μ controls trade-off
  • RLS: fast convergence, O(M²) per sample
  • Applications: noise cancel, echo cancel, equalization
  • ANC uses adaptive filters for anti-noise
  • Beamforming steers nulls toward interference
  • Modern deep learning complements classic DSP
  • Real-time DSP needs efficient implementation

📝 Problem Set 1: Discrete-Time Signals, Z-Transform, DFT

Q1. Compute the Z-transform of x[n] = (0.5)^n u[n]. Find poles and ROC.

Show Solution

X(z) = Σ (0.5)^n z^-n = 1/(1 - 0.5z^-1) = z/(z-0.5), |z| > 0.5. Pole at z = 0.5. ROC: |z| > 0.5.

Q2. Design a 5-tap moving average FIR filter. Find its frequency response and -3dB cutoff.

Show Solution

H(ω) = (1/5)(1 + e^-jω + e^-2jω + e^-3jω + e^-4jω). |H(0)| = 1, |H(π)| = 0. Using Dirichlet kernel: |H(ω)| = |sin(5ω/2)/(5sin(ω/2))|. -3dB at ω ≈ 0.72 rad/sample (f ≈ 0.115 fs).

Q3. Compute the 4-point DFT of x = [1, 2, 3, 4].

Show Solution

X[0] = 1+2+3+4 = 10. X[1] = 1 + 2(-j) + 3(-1) + 4(j) = -2 + 2j. X[2] = 1 - 2 + 3 - 4 = -2. X[3] = 1 + 2(j) + 3(-1) + 4(-j) = -2 - 2j.

🎯 Midterm 1: Signals, Z-Transform, DFT

Q1. Is the system y[n] = x[n] - x[n-1] linear? Causal? Stable?

Show Solution

Linear: y = (ax1+bx2)[n] - (ax1+bx2)[n-1] = a(x1[n]-x1[n-1]) + b(x2[n]-x2[n-1]) ✓. Causal ✓. Impulse response h[n] = {1,-1} — finite length, so BIBO stable ✓.

Q2. Design a first-order IIR low-pass filter with cutoff at 0.1·fs. Find the difference equation.

Show Solution

Use y[n] = α·x[n] + (1-α)·y[n-1]. For -3dB at f_c: α = 1 - exp(-2π·f_c/fs) ≈ 2π·f_c/fs for f_c << fs. With f_c/fs = 0.1: α ≈ 0.47. y[n] = 0.47x[n] + 0.53y[n-1].

Q3. An 8-point FFT requires how many complex multiplications? Compare with direct DFT.

Show Solution

Direct DFT: N² = 64 multiplications. FFT (radix-2): (N/2)·log₂N = 4 × 3 = 12 multiplications. Speedup: 5.3×. For large N, speedup grows as N/log₂N.