Convolution

calendarDec 12, 2024 · 3 min read · signals convolution filtering lti-systems dsp  ·
Share on: linkedincopy

Fundamental operation for LTI systems and filtering.

Definition

Continuous-Time

$$ y(t) = (x * h)(t) = \int_{-\infty}^{\infty} x(\tau) h(t - \tau) d\tau $$

Discrete-Time

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

Physical Interpretation

Convolution represents the output of an LTI system:

  • $x[n]$: Input signal
  • $h[n]$: Impulse response
  • $y[n]$: Output signal

Meaning: Each input sample creates a scaled and shifted copy of the impulse response.

Properties

Commutative

$$x * h = h * x$$

Associative

$$x * (h_1 * h_2) = (x * h_1) * h_2$$

Distributive

$$x * (h_1 + h_2) = x * h_1 + x * h_2$$

Identity

$$x * \delta = x$$

Implementation

Python (Direct)

 1import numpy as np
 2
 3def convolve_direct(x, h):
 4    """Direct convolution (slow but clear)"""
 5    N = len(x)
 6    M = len(h)
 7    y = np.zeros(N + M - 1)
 8    
 9    for n in range(len(y)):
10        for k in range(M):
11            if 0 <= n - k < N:
12                y[n] += x[n - k] * h[k]
13    
14    return y
15
16# NumPy built-in (optimized)
17y = np.convolve(x, h, mode='full')  # Full convolution
18y = np.convolve(x, h, mode='same')  # Same length as x
19y = np.convolve(x, h, mode='valid') # Only where fully overlapping

Python (FFT-based, Fast for Long Signals)

 1def convolve_fft(x, h):
 2    """Fast convolution using FFT"""
 3    N = len(x) + len(h) - 1
 4    # Zero-pad to next power of 2
 5    N_fft = 2**int(np.ceil(np.log2(N)))
 6    
 7    X = np.fft.fft(x, N_fft)
 8    H = np.fft.fft(h, N_fft)
 9    Y = X * H
10    y = np.fft.ifft(Y)
11    
12    return np.real(y[:N])

Go

 1package signals
 2
 3func Convolve(x, h []float64) []float64 {
 4    N := len(x)
 5    M := len(h)
 6    y := make([]float64, N+M-1)
 7    
 8    for n := 0; n < len(y); n++ {
 9        for k := 0; k < M; k++ {
10            if n-k >= 0 && n-k < N {
11                y[n] += x[n-k] * h[k]
12            }
13        }
14    }
15    
16    return y
17}

Common Applications

1. Moving Average Filter

1# 5-point moving average
2h = np.ones(5) / 5
3y = np.convolve(x, h, mode='same')

2. Gaussian Smoothing

 1def gaussian_kernel(sigma, size=None):
 2    """Generate Gaussian kernel"""
 3    if size is None:
 4        size = int(6 * sigma + 1)
 5        if size % 2 == 0:
 6            size += 1
 7    
 8    x = np.arange(size) - size // 2
 9    kernel = np.exp(-x**2 / (2 * sigma**2))
10    return kernel / kernel.sum()
11
12# Apply Gaussian smoothing
13h = gaussian_kernel(sigma=2.0)
14y = np.convolve(x, h, mode='same')

3. Edge Detection

1# Simple edge detector
2h = np.array([-1, 0, 1])  # Derivative approximation
3edges = np.convolve(signal, h, mode='same')

Convolution vs Correlation

Correlation

$$ (x \star h)[n] = \sum_{k=-\infty}^{\infty} x[k] h[n + k] $$

Key difference: No time reversal in correlation.

1# Convolution
2y_conv = np.convolve(x, h)
3
4# Correlation
5y_corr = np.correlate(x, h)
6
7# Relationship
8y_corr = np.convolve(x, h[::-1])  # h reversed

Performance Considerations

MethodComplexityBest For
Direct$O(NM)$Short filters ($M < 50$)
FFT-based$O(N \log N)$Long filters ($M > 50$)

Further Reading

Related Snippets