📚Signal Processing Unit 5 Review

Linear convolution is a fundamental operation in signal processing that combines two signals to produce a third. It describes how a linear time-invariant (LTI) system modifies an input signal, forming the basis for filtering, smoothing, and many other signal transformations.

Understanding convolution in both the time and frequency domains gives you two complementary tools. The time-domain approach builds strong intuition through a "slide-and-multiply" procedure, while the frequency-domain method leverages the Fourier transform for dramatically faster computation on long signals.

Definition and mathematical representation

Linear convolution takes two signals and produces a third that represents the output of an LTI system. One signal is the input, and the other is the system's impulse response (the system's output when the input is a single unit impulse).

For two discrete-time signals $x[n]$ and $h[n]$ , linear convolution is defined as:

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

where $*$ denotes the convolution operator. At each output index $n$ , you're summing the products of $x[k]$ with a time-reversed, shifted copy of $h$ .

If $x[n]$ has length $N$ and $h[n]$ has length $M$ , the output $y[n]$ has length $N + M - 1$ . This is worth memorizing since it comes up constantly in both computation and exam problems.

Properties and interpretation

Linear convolution satisfies several properties inherited from the LTI framework:

Commutativity: $x[n] * h[n] = h[n] * x[n]$ . You can swap which signal gets flipped and shifted without changing the result.
Associativity: $(x[n] * h_1[n]) * h_2[n] = x[n] * (h_1[n] * h_2[n])$ . Cascading two systems is equivalent to convolving their impulse responses first, then convolving with the input.
Distributivity: $x[n] * (h_1[n] + h_2[n]) = x[n] * h_1[n] + x[n] * h_2[n]$ . Parallel systems add.
Additivity: If $y_1[n] = x_1[n] * h[n]$ and $y_2[n] = x_2[n] * h[n]$ , then $(x_1[n] + x_2[n]) * h[n] = y_1[n] + y_2[n]$ .
Homogeneity (scaling): $(a \cdot x[n]) * h[n] = a \cdot y[n]$ for any constant $a$ .
Shift invariance: If $y[n] = x[n] * h[n]$ , then $x[n - k] * h[n] = y[n - k]$ for any integer shift $k$ .

The practical interpretation: convolution is a filtering operation. The impulse response $h[n]$ acts as a filter that shapes the input. For example, a moving average filter with $h[n] = [0.25, 0.5, 0.25]$ smooths the input by computing a weighted average of adjacent samples, suppressing rapid fluctuations.

Convolution of discrete-time signals

Time-domain computation

Computing convolution by hand (or understanding what the computer does) comes down to a slide-and-multiply procedure:

Flip one signal (typically $h[k]$ ) to get $h[-k]$ .
Shift the flipped signal by $n$ to get $h[n - k]$ .
Multiply $x[k]$ and $h[n - k]$ element-by-element for all $k$ .
Sum all the products to get $y[n]$ at that particular shift.
Repeat for every value of $n$ from the first overlap to the last.

Worked example: Let $x[n] = [1, 2, 3]$ (length 3) and $h[n] = [4, 5]$ (length 2). The output has length $3 + 2 - 1 = 4$ .

$y[0] = 1 \cdot 4 = 4$
$y[1] = 1 \cdot 5 + 2 \cdot 4 = 13$
$y[2] = 2 \cdot 5 + 3 \cdot 4 = 22$
$y[3] = 3 \cdot 5 = 15$

So $y[n] = [4, 13, 22, 15]$ .

Computational complexity

Time-domain convolution of signals with lengths $N$ and $M$ requires $N \cdot M$ multiplications and $(N-1)(M-1)$ additions, giving an overall complexity of $O(NM)$ . When both signals are roughly the same length, this simplifies to $O(N^2)$ .

This becomes expensive fast. Convolving two signals each of length 1000 requires roughly 1 million multiplications. For real-time audio or image processing, that's often too slow, which is exactly why the frequency-domain approach exists.

Frequency-domain convolution using Fourier transforms

Convolution theorem

The convolution theorem is one of the most powerful results in signal processing:

Convolution in the time domain equals pointwise multiplication in the frequency domain.

Mathematically, if $y[n] = x[n] * h[n]$ , then:

$Y(e^{j\omega}) = X(e^{j\omega}) \cdot H(e^{j\omega})$

where $X(e^{j\omega})$ , $H(e^{j\omega})$ , and $Y(e^{j\omega})$ are the DTFTs of $x[n]$ , $h[n]$ , and $y[n]$ , respectively. The multiplication here is ordinary pointwise multiplication of complex-valued functions, which is far simpler than the summation in the convolution formula.

This theorem holds for both continuous-time and discrete-time signals and applies across Fourier transform variants (DTFT, DFT, continuous Fourier transform).

Frequency-domain convolution procedure

To perform linear convolution via the frequency domain using the DFT/FFT:

Zero-pad both $x[n]$ and $h[n]$ to length $N + M - 1$ (where $N$ and $M$ are their original lengths).
Compute the FFT of both zero-padded signals.
Multiply the two FFT results pointwise (element by element).
Compute the inverse FFT of the product to get $y[n]$ in the time domain.

The zero-padding in step 1 is critical. Without it, the DFT computes circular convolution (which wraps around), not linear convolution. Padding to length $N + M - 1$ ensures the circular result matches the linear result exactly.

Using the FFT, each transform costs $O(L \log L)$ where $L = N + M - 1$ , and the pointwise multiplication costs $O(L)$ . The total complexity is $O(L \log L)$ , which is a massive speedup over $O(NM)$ for long signals. For two signals of length 1000, you go from ~1 million operations to roughly 30,000.

Effects of linear convolution on signals

Signal characteristics modification

The impulse response $h[n]$ completely determines how an LTI system modifies the input. Its duration, shape, and frequency response all shape the output:

Amplitude/frequency content: Convolution can attenuate or amplify specific frequency bands. A low-pass filter preserves low frequencies while suppressing high-frequency content. A high-pass filter does the opposite. The system's frequency response $H(e^{j\omega})$ tells you exactly which frequencies get boosted or cut.
Phase response: The phase of $H(e^{j\omega})$ determines how different frequency components are shifted in time. A linear phase filter introduces a constant group delay across all frequencies, which preserves the signal's shape (just delayed). Nonlinear phase can distort the signal's waveform even if the magnitude response is flat.
Duration: Convolution generally spreads signals out in time. The output is longer than either input, which is why the output length is $N + M - 1$ .

Interpretation and applications

Analyzing convolution results means looking at both domains. The time-domain output shows you the waveform shape, while the frequency-domain product $X(e^{j\omega}) \cdot H(e^{j\omega})$ reveals exactly which frequencies were kept, removed, or shifted.

Common applications of linear convolution include:

Filtering: Removing unwanted frequency components or noise (e.g., bandpass filters in communications)
Signal smoothing: Reducing high-frequency noise with averaging or Gaussian kernels
Signal enhancement: Emphasizing desired features, such as sharpening edges in images
Signal synthesis: Generating new signals by convolving with designed impulse responses (e.g., adding reverb to dry audio by convolving with a room impulse response)

Real-world examples span many fields: audio equalizers and reverb effects, image blurring and edge detection kernels, and communication systems using matched filtering for optimal signal detection or channel equalization to undo distortion.

📚Signal Processing Unit 5 Review