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 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)

The DFT is the mathematical foundation for spectral analysis of discrete signals. Given $N$ time-domain samples, it produces $N$ frequency-domain coefficients via:

$X[k] = \sum_{n=0}^{N-1} x[n] \, e^{-j2\pi kn/N}, \quad k = 0, 1, \ldots, N-1$

• Periodicity assumption means the DFT treats your signal as if it repeats infinitely. If the signal isn't periodic within the analysis window, this creates spectral leakage (energy smearing across frequency bins).
• Computational complexity of $O(N^2)$ makes direct computation impractical for large datasets, since every output bin requires a sum over all $N$ input samples. This motivates the need for faster algorithms.

Fast Fourier Transform (FFT)

The FFT computes the exact same result as the DFT, just far more efficiently. It's what makes real-time spectral analysis possible.

• Reduces complexity from $O(N^2)$ to $O(N \log_2 N)$ by exploiting symmetry and periodicity in the DFT's complex exponentials. For $N = 1024$, that's roughly a 100x speedup.
• Divide-and-conquer strategy recursively splits the $N$-point DFT into smaller DFTs. The most common variant is the Cooley-Tukey radix-2 algorithm, which requires $N$ to be a power of 2. Radix-4 and split-radix variants also exist for further gains.
• Ubiquitous in applications including audio processing, radar, medical imaging, and telecommunications. If you're doing frequency analysis on a computer, you're almost certainly using an FFT under the hood.

Discrete Cosine Transform (DCT)

The DCT decomposes a signal using only cosine basis functions, producing purely real coefficients for real-valued inputs.

• Strong energy compaction is its defining advantage. Most of a typical signal's energy gets packed into just a few low-frequency DCT coefficients, which is exactly what you want for compression.
• Powers JPEG and MPEG compression. In JPEG, each 8×8 pixel block is transformed via DCT, and the many near-zero high-frequency coefficients are quantized away with little perceptual loss.
• Handles boundaries better than the DFT because cosine basis functions implicitly create a symmetric extension of the signal at its edges, avoiding the discontinuities that cause leakage in the DFT.

---

Digital Filtering Architectures

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

Finite Impulse Response (FIR) Filtering

An FIR filter computes each output sample as a weighted sum of the current and past $M$ input samples:

$y[n] = \sum_{k=0}^{M} b_k \, x[n-k]$

There's no feedback, so the impulse response lasts exactly $M+1$ samples and then dies to zero.

• Always stable. Because there are no feedback paths (no poles outside the origin in the z-plane), an FIR filter cannot become unstable regardless of coefficient values.
• Achieves exactly linear phase when the coefficients are symmetric ($b_k = b_{M-k}$). Linear phase means all frequency components are delayed by the same amount, preserving the waveform's shape. This is critical for audio, communications, and biomedical signals.
• Higher computational cost than IIR for equivalent frequency selectivity. Achieving a sharp cutoff with an FIR filter can require hundreds of taps, while an IIR filter might need only a handful of coefficients.

Infinite Impulse Response (IIR) Filtering

An IIR filter feeds past output samples back into the computation:

$y[n] = \sum_{k=0}^{M} b_k \, x[n-k] - \sum_{k=1}^{L} a_k \, y[n-k]$

This feedback means the impulse response theoretically extends forever (though it decays for stable filters).

• Computationally efficient compared to FIR for similar magnitude response. A 4th-order IIR Butterworth lowpass can match a frequency response that would take 50+ FIR taps.
• Introduces nonlinear phase, which distorts the shape of waveforms passing through the filter. This can be mitigated with zero-phase filtering (forward-backward filtering) in offline applications.
• Stability is not guaranteed. You must verify that all poles of the transfer function lie strictly inside the unit circle in the z-plane. Poor coefficient quantization in fixed-point implementations can push poles outside, causing the filter to blow up.

---

Fundamental Signal Operations

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

Convolution

Convolution is how filtering actually works mathematically. For a linear time-invariant (LTI) system with impulse response $h[n]$, the output is:

$y[n] = x[n] * h[n] = \sum_{k=-\infty}^{\infty} x[k] \, h[n-k]$

• Convolution in time equals multiplication in frequency. This duality is one of the most powerful results in signal processing: $Y(e^{j\omega}) = X(e^{j\omega}) \cdot H(e^{j\omega})$. It means you can filter a signal by transforming to the frequency domain, multiplying, and transforming back.
• FFT-based fast convolution exploits this duality to reduce the cost from $O(N^2)$ to $O(N \log N)$. For long signals, overlap-add or overlap-save methods break the signal into blocks and convolve each block via FFT.

Correlation

Correlation measures the similarity between two signals as a function of a time lag $\tau$. It's mathematically similar to convolution, but without time-reversing one signal:

$R_{xy}[\tau] = \sum_{n} x[n] \, y[n + \tau]$

• Cross-correlation finds time delays between related signals. In radar, you correlate the transmitted pulse with the received echo; the lag at the correlation peak gives you the round-trip delay (and thus the target's range). GPS and sonar work on the same principle.
• Auto-correlation (correlating a signal with itself) reveals periodicity and is used in pitch detection, power spectral estimation (via the Wiener-Khinchin theorem), and characterizing random processes.

---

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

When you compute the DFT of a finite-length signal, you're implicitly multiplying the true signal by a rectangular window (ones inside, zeros outside). This abrupt truncation creates sharp edges that produce artificial high-frequency content in the spectrum, known as spectral leakage.

Window functions taper the signal smoothly to zero at its edges, reducing leakage at the cost of some frequency resolution.

• The core trade-off is main lobe width vs. side lobe level. A narrow main lobe gives better ability to distinguish closely spaced frequencies, but higher side lobes can mask weak signals near strong ones.
• Common windows and their characteristics:
  • Rectangular: Narrowest main lobe (best resolution) but highest side lobes (-13 dB). Use when you need to resolve closely spaced frequencies of similar amplitude.
  • Hamming: Good general-purpose choice. Side lobes around -43 dB with moderate main lobe widening.
  • Hanning (Hann): Similar to Hamming but with better side lobe roll-off. Very widely used.
  • Blackman: Lowest side lobes (~-58 dB) but widest main lobe. Best when you need to detect weak signals near strong ones.

---

Sample Rate Conversion

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

Decimation and Interpolation

Decimation (downsampling by factor $M$) reduces the sample rate by keeping every $M$-th sample and discarding the rest.

1. Apply a lowpass anti-aliasing filter with cutoff at $\pi/M$ to prevent high-frequency content from folding into the baseband.
2. Discard every $M-1$ out of $M$ samples.

The filter must come before the downsampler. Skipping it causes aliasing that cannot be undone.

Interpolation (upsampling by factor $L$) increases the sample rate by inserting $L-1$ zeros between each original sample.

1. Insert $L-1$ zeros between each sample (this creates spectral images at multiples of the original sampling frequency).
2. Apply a lowpass anti-imaging filter with cutoff at $\pi/L$ and gain $L$ to smooth the result.

Multi-rate processing combines both operations for rational sample rate conversion by a factor of $L/M$. For example, converting 44.1 kHz audio to 48 kHz requires upsampling by 160 and downsampling by 147 (since $48000/44100 = 160/147$). In practice, polyphase filter structures make this efficient by avoiding computation on the zero-valued samples.

---

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

The Fourier transform tells you what frequencies are present in a signal, but not when they occur. The wavelet transform solves this by decomposing the signal using scaled and shifted versions of a localized "mother wavelet" $\psi(t)$:

$W(a, b) = \int x(t) \, \frac{1}{\sqrt{a}} \psi\!\left(\frac{t - b}{a}\right) dt$

where $a$ controls the scale (inversely related to frequency) and $b$ controls the time shift.

• Adaptive resolution is the key advantage. At high frequencies (small $a$), the wavelet is narrow, giving fine time resolution. At low frequencies (large $a$), the wavelet is wide, giving fine frequency resolution. This matches how most real signals behave: fast transients are high-frequency events that need precise timing, while slow oscillations need precise frequency identification.
• Ideal for non-stationary signals where frequency content evolves over time, such as speech, music transients, ECG signals, and seismic data.
• Enables efficient compression and denoising. Signal energy concentrates in a few large wavelet coefficients, while noise spreads across many small ones. Thresholding the small coefficients removes noise while preserving signal structure. JPEG 2000 uses the wavelet transform instead of DCT for this reason.

---

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 the 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 ECG signal has a heart rate that 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?