Digital Signal Processing
Discrete-time signals, DFT/FFT, digital filters (FIR/IIR), sampling, quantization, and applications.
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...
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
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...
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
The Discrete Fourier Transform and FFT
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...
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
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...
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
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...
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.