Discrete-Time Convolution

Introduction

Discrete-time convolution is the fundamental operation for computing the output of any discrete-time LTI system. Given the system\'s impulse response $h[n]$ and an input sequence $x[n]$, the output is their convolution sum. Unlike continuous-time convolution (which involves integration), discrete-time convolution is a summation — making it directly implementable on digital hardware and in software.

Every FIR and IIR filter, every digital reverb, and every convolution-based operation in signal processing ultimately reduces to computing this sum. Understanding its mechanics — both the mathematical formulation and practical computation methods — is essential for working with digital signals.

The Convolution Sum

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

At each output index $n$, multiply each input sample $x[k]$ by the corresponding impulse response value $h[n-k]$, then sum all products.

Equivalently (by commutativity): $$y[n] = \sum_{k=-\infty}^{\infty} h[k] x[n-k]$$

This second form is often more intuitive: for each past sample $x[n-k]$, weight it by the impulse response value $h[k]$, and sum.

Graphical Method (Flip and Slide)

Step 1: Plot $x[k]$ and $h[k]$ as functions of $k$.

Step 2: Flip $h[k]$ to get $h[-k]$.

Step 3: For each value of $n$, shift to get $h[n-k]$.

Step 4: Multiply $x[k] \cdot h[n-k]$ element by element and sum.

Step 5: The sum is $y[n]$ for that particular $n$. Repeat for all $n$.

Tabular (Matrix) Method

For finite-length sequences, the tabular method is systematic and error-free:

Example: $x[n] = \{1, 2, 3\}$ (for $n = 0,1,2$) and $h[n] = \{1, 1, 1, 1\}$ (for $n = 0,1,2,3$).

Multiply each element of $x$ by the entire $h$ sequence and align:

Result: $y[n] = \{1, 3, 6, 6, 5, 3\}$ for $n = 0, 1, 2, 3, 4, 5$.

Output Length

If $x[n]$ has length $N$ and $h[n]$ has length $M$, the convolution $y[n]$ has length:

$$L_y = N + M - 1$$

This is because the first non-zero output occurs when the leading edge of $h$ first overlaps $x$, and the last non-zero output occurs when the trailing edge finishes passing.

Direct Computation Example

$x[n] = \{2, 1, -1\}$ for $n = 0, 1, 2$ and $h[n] = \{1, -1, 2\}$ for $n = 0, 1, 2$.

Computing each output sample:

$y[0] = x[0]h[0] = 2(1) = 2$

$y[1] = x[0]h[1] + x[1]h[0] = 2(-1) + 1(1) = -1$

$y[2] = x[0]h[2] + x[1]h[1] + x[2]h[0] = 2(2) + 1(-1) + (-1)(1) = 2$

$y[3] = x[1]h[2] + x[2]h[1] = 1(2) + (-1)(-1) = 3$

$y[4] = x[2]h[2] = (-1)(2) = -2$

Result: $y[n] = \{2, -1, 2, 3, -2\}$, length = $3 + 3 - 1 = 5$ ✓

Implementation Considerations

Direct Form

The direct implementation computes each output sample using the definition:

Computational cost: $O(NM)$ multiplications and additions for the full convolution.

FFT-Based Convolution

For large sequences, convolution can be computed efficiently using the FFT:

1. Compute $X = \text{FFT}(x)$ and $H = \text{FFT}(h)$ (zero-padded to length $N+M-1$)
2. Multiply: $Y = X \cdot H$ (element-wise)
3. Inverse FFT: $y = \text{IFFT}(Y)$

Cost: $O((N+M)\log(N+M))$ — much faster than direct computation when $N$ and $M$ are large.

Block Convolution (Overlap-Add / Overlap-Save)

For real-time processing of long input streams with a fixed filter, the input is segmented into blocks, each block is convolved with $h$, and results are combined:

• Overlap-Add: Convolve each block, then add the overlapping tails
• Overlap-Save: Overlap input blocks, convolve, then discard corrupted samples

Both methods achieve the same result as linear convolution while enabling real-time, block-by-block processing.

Convolution vs. Correlation

Convolution and correlation are closely related: $$\text{Convolution}: y[n] = \sum_k x[k]h[n-k] \quad \text{(flip and slide)}$$ $$\text{Correlation}: R_{xh}[n] = \sum_k x[k]h[n+k] \quad \text{(slide without flip)}$$

Correlation is convolution with a time-reversed second signal: $R_{xh}[n] = x[n] * h[-n]$.

Key Takeaways

• Discrete convolution: $y[n] = \sum_k x[k]h[n-k]$ — multiply and accumulate
• Output length = $N + M - 1$ (sum of input lengths minus one)
• The tabular method provides a systematic, error-free computation approach
• FFT-based convolution is $O(N\log N)$ vs $O(N^2)$ for direct computation
• Block convolution (overlap-add/save) enables real-time processing of continuous streams
• Correlation is convolution without the flip — related by time reversal