Derive the convolution sum

The convolution sum expresses the output of a discrete-time LTI system in terms of the input $x[n]$ and the impulse response $h[n]$ (the output when the input is $\delta[n]$).

Step 1: Any sequence as a sum of shifted impulses

Since $\delta[n-k] = 1$ only at $n = k$, each sample can be picked out:

$$x[n] = \sum_{k=-\infty}^{\infty} x[k]\,\delta[n-k]$$

For example, $x[n] = \{2, \underset{\uparrow}{1}, 3\}$ gives $x[n] = 2\delta[n+1] + \delta[n] + 3\delta[n-1]$.

Step 2: Apply the system properties

Let $T\{\cdot\}$ be the system and $h[n] = T\{\delta[n]\}$.

$$y[n] = T\{x[n]\} = T\left\{\sum_{k} x[k]\,\delta[n-k]\right\}$$

• Linearity (additivity and homogeneity): the $x[k]$ are just constants (weights), so

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

• Time invariance: the response to $\delta[n-k]$ is $h[n-k]$.

Step 3: Result

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

This is the convolution sum. Putting $m = n-k$ gives the equivalent form

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

showing convolution is commutative.

Special cases:

• Causal system ($h[n] = 0$, $n < 0$) and causal input: $y[n] = \sum_{k=0}^{n} x[k]\,h[n-k]$.
• Lengths: if $x$ has $N_1$ samples and $h$ has $N_2$, $y$ has $N_1 + N_2 - 1$ samples.

Procedure: (1) fold $h[k]$ to $h[-k]$; (2) shift by $n$ to get $h[n-k]$; (3) multiply by $x[k]$ sample by sample; (4) sum the products to get $y[n]$; (5) repeat for every $n$.

Example: $x[n] = \{\underset{\uparrow}{1}, 2\}$, $h[n] = \{\underset{\uparrow}{1}, 1, 1\}$:

So $y[n] = \{\underset{\uparrow}{1}, 3, 3, 2\}$, with $2 + 3 - 1 = 4$ samples.