Common Digital Signal Processing Algorithms

Why This Matters

Digital signal processing algorithms form the computational backbone of everything from streaming audio to medical imaging. In this course, you're being tested on more than just knowing what each algorithm does—you need to understand why we choose one approach over another, how transforms relate to each other mathematically, and what trade-offs engineers face when processing real-world signals. These algorithms demonstrate core principles like time-frequency duality, computational efficiency, filter stability, and multi-resolution analysis.

The algorithms below aren't just isolated techniques; they're interconnected tools that build on Fourier theory. The FFT makes the DFT practical, convolution connects filtering to frequency response, and wavelets extend Fourier analysis to handle signals that change over time. Don't just memorize definitions—know what problem each algorithm solves and when you'd reach for one tool instead of another.

---

Frequency-Domain Transforms

These algorithms convert signals from the time domain to the frequency domain, revealing spectral content that's hidden in raw samples. The core principle: any signal can be decomposed into sinusoidal components, and working in the frequency domain often simplifies analysis and processing.

Discrete Fourier Transform (DFT)

• Converts time-domain samples to frequency-domain representation—the mathematical foundation for spectral analysis of discrete signals
• Periodicity assumption means the DFT treats your signal as if it repeats infinitely, which can cause aliasing and spectral leakage if not addressed
• Computational complexity of $O(N^2)$ makes direct computation impractical for large datasets, motivating the need for faster algorithms

Fast Fourier Transform (FFT)

• Reduces DFT complexity from $O(N^2)$ to $O(N \log N)$—this efficiency gain is what makes real-time spectral analysis possible
• Divide-and-conquer strategy recursively breaks the DFT into smaller transforms, typically using radix-2 or radix-4 decomposition
• Ubiquitous in applications including audio processing, radar systems, medical imaging, and telecommunications—if you're doing frequency analysis, you're using FFT

Discrete Cosine Transform (DCT)

• Uses only cosine basis functions—ideal for real-valued signals because it produces real coefficients with strong energy compaction
• Powers JPEG and MPEG compression by concentrating most signal energy into a few low-frequency coefficients that can be efficiently encoded
• Avoids boundary discontinuities better than DFT because cosines naturally handle symmetric extensions of finite signals

---

Digital Filtering Architectures

Filters modify signals by attenuating or amplifying specific frequency components. The key distinction: how the filter uses past outputs (feedback) determines its impulse response length, stability, and phase characteristics.

Finite Impulse Response (FIR) Filtering

• Impulse response has finite duration—output depends only on current and past inputs, with no feedback, guaranteeing stability
• Achieves exactly linear phase when coefficients are symmetric, preserving waveform shape—critical for audio and communications
• Higher computational cost than IIR for equivalent frequency selectivity, requiring more coefficients to achieve sharp cutoffs

Infinite Impulse Response (IIR) Filtering

• Uses feedback from past outputs—the impulse response theoretically extends forever, enabling efficient sharp frequency responses
• Computationally efficient compared to FIR for similar magnitude response, often requiring far fewer coefficients
• Introduces phase distortion due to nonlinear phase response, and requires careful design to ensure stability (poles must be inside unit circle)

---

Fundamental Signal Operations

These operations are the building blocks that connect time-domain processing to frequency-domain analysis. Understanding convolution and correlation is essential because they underpin filtering, system analysis, and signal detection.

Convolution

• Combines input signal with impulse response to produce output—this is how filtering actually works mathematically: $y[n] = x[n] * h[n]$
• Convolution in time equals multiplication in frequency—this duality lets us perform filtering efficiently using FFT: compute in frequency domain, then inverse transform
• Computational shortcut via FFT reduces convolution from $O(N^2)$ to $O(N \log N)$ for long signals, making real-time processing feasible

Correlation

• Measures similarity between signals as a function of time lag—mathematically similar to convolution but without time-reversing one signal
• Cross-correlation finds time delays between related signals, essential for radar ranging, GPS, and synchronization systems
• Auto-correlation reveals periodicity and is used in pitch detection, signal characterization, and power spectral estimation

---

Spectral Analysis Techniques

Real-world signals are finite, and how we handle their boundaries dramatically affects frequency analysis. Windowing addresses the fundamental tension between frequency resolution and spectral leakage.

Windowing

• Reduces spectral leakage by tapering signal edges before computing the DFT—without windowing, abrupt signal boundaries create artificial high-frequency content
• Trade-off between main lobe width and side lobe level—narrow main lobes give better frequency resolution, but higher side lobes can mask weak signals
• Common windows include Hamming, Hanning, and Blackman—each offers different compromises; Blackman has lowest side lobes, rectangular has narrowest main lobe

---

Sample Rate Conversion

Changing the sampling rate of a digital signal requires careful handling to avoid aliasing or artifacts. These operations are essential for interfacing systems with different sample rates and for efficient multi-rate processing.

Decimation and Interpolation

• Decimation (downsampling) reduces sample rate by keeping every $M$-th sample—must apply anti-aliasing lowpass filter first to prevent frequency folding
• Interpolation (upsampling) increases sample rate by inserting zeros between samples, then lowpass filtering to smooth the result
• Multi-rate processing combines both operations for efficient filter implementation and sample rate conversion between systems (e.g., 44.1 kHz to 48 kHz audio)

---

Multi-Resolution Analysis

When signals have frequency content that changes over time, fixed-resolution Fourier analysis falls short. Wavelets provide adaptive time-frequency resolution, trading off temporal and spectral precision based on frequency.

Wavelet Transform

• Provides time-frequency representation with adaptive resolution—high frequencies get fine time resolution, low frequencies get fine frequency resolution
• Ideal for non-stationary signals where frequency content evolves, such as speech, music transients, ECG signals, and seismic data
• Enables efficient compression and denoising by representing signals sparsely—most energy concentrates in few coefficients, and noise spreads across many

---

Quick Reference Table

---

Self-Check Questions

1. Both FFT and DCT convert signals to the frequency domain. What property makes DCT preferable for image compression, and why doesn't standard DFT share this advantage?

2. You need to design a filter that preserves the shape of a pulse waveform exactly. Should you choose FIR or IIR, and what specific property justifies your choice?

3. Compare convolution and correlation: how do they differ mathematically, and what different applications does each serve?

4. A student applies the DFT to a finite signal and observes unexpected high-frequency components that weren't in the original. What phenomenon is this, and which technique would reduce it?

5. An FRQ asks you to analyze an ECG signal where the heart rate varies over time. Why would wavelet analysis be more appropriate than a standard FFT, and what trade-off does the wavelet transform make to achieve this capability?