Introduction
The idea of discrete-time convolution is exactly
the same as that of continuous-time convolution. For this
reason, it may be useful to look at both versions to help your
understanding of this extremely important concept.
Convolution is a very powerful tool in determining a
system's output from knowledge of an arbitrary input and the
system's impulse response.
It also helpful to see convolution graphically, i.e. by using transparencies or Java Applets.
Johns Hopkins University has an excellent
Discrete time convolution applet.
Using this resource will help understanding this crucial concept.
Derivation of the convolution sum
We know that any discrete-time signal can be represented by a
summation of scaled and shifted discrete-time impulses, see
(Reference). Since
we are assuming the system to be linear and time-invariant, it
would seem to reason that an input signal comprised of the sum
of scaled and shifted impulses would give rise to an output
comprised of a sum of scaled and shifted impulse responses.
This is exactly what occurs in convolution.
Below we present a more rigorous and mathematical look at the
derivation:
Letting ℋ ℋ
y n = ℋ x n = ℋ ∑ k = - ∞ ∞ x k δ n - k = ∑ k = - ∞ ∞ ℋ x k δ n - k = ∑ k = - ∞ ∞ x k ℋ δ n - k = ∑ k = - ∞ ∞ x k h n - k
y
n
ℋ
x
n
ℋ
k
x
k
δ
n
k
k
ℋ
x
k
δ
n
k
k
x
k
ℋ
δ
n
k
k
x
k
h
n
k
x n
x
n
ℋ ˙
ℋ
˙
x k
x
k
ℋ ˙
ℋ
˙
ℋ ˙
ℋ
˙
Above the summation is taken over all integers. Howerer, in many practical
cases either
x n
x
n
h n
h
n
Graphical illustration of convolution properties
A quick graphical example may help in demonstrating why
convolution works.
Figure 1:
A single impulse input yields the system's impulse response.
|
Figure 2:
A scaled impulse input yields a scaled response, due to
the scaling property of the system's linearity.
|
Figure 3:
We now use the time-invariance property of the system to
show that a delayed input results in an output of the same
shape, only delayed by the same amount as the input.
|
Figure 4:
We now use the additivity portion of the linearity
property of the system to complete the picture. Since any
discrete-time signal is just a sum of scaled and shifted
discrete-time impulses, we can find the output from
knowing the input and the impulse response.
|
Convolution Sum
As mentioned above, the convolution sum provides a concise,
mathematical way to express the output of an LTI system based
on an arbitrary discrete-time input signal and the system's
response. The convolution sum is expressed
as
y n = ∑ k = - ∞ ∞ x k h n - k
y
n
k
x
k
h
n
k
y n = x n * h n
y
n
x
n
h
n
k = n - k
k
n
k
y n = x n * h n = h n * x n
y
n
x
n
h
n
h
n
x
n
y n = ∑ k = - ∞ ∞ h k x n - k
y
n
k
h
k
x
n
k
Convolution Through Time (A Graphical Approach)
In this section we will develop a second graphical
interpretation of discrete-time convolution. We will begin
this by writing the convolution sum allowing
x
x
h
h
y n = ∑ l = 0 m - 1 x l h n - l
y
n
l
0
m 1
x
l
h
n
l
n
n m m
x l
x
l
h n - l
h
n
l
x
x
h
h
Going back to the previous example:
Figure 5:
This is the end result that we are looking to
find.
|
Figure 6:
Here we reverse the impulse response,
|
Figure 7:
We continue the traverse. See that at time
|
Figure 8 |
Figure 9:
If we follow this through to one more step,
|
What we are doing in the above demonstration is reversing the
impulse response in time and "walking it across" the input
signal. Clearly, this yields the same result as scaling,
shifting and summing impulse responses.
This approach of time-reversing, and sliding across is a
common approach to presenting convolution, since it
demonstrates how convolution builds up an output through time.
