2.1 DiscreteTime LTI Systems: The Convolution Sum
Introduction
The idea of discretetime convolution is exactly the same as that of continuoustime 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.
Derivation of the convolution sum
We know that
any discretetime signal can be represented by a summation of scaled and
shifted discretetime impulses. Since we are assuming the system to be linear
and timeinvariant, 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 H be a discrete time LTI system, we start with the
following equation and work our way down the convolution sum.
_{ }
(1)
Let us take a quick look at the steps taken in the above derivation. After our initial equation we rewrite the function x[n] as a sum of the function times the unit impulse. Next, we can move around the H operator and the summation because H(˙) is a linear, DT system. Because of this linearity and the fact that x[k] is a constant, we pull the constant out and simply multiply it by H(˙). Finally, we use the fact that H(˙) is time invariant in order to reach our final state  the convolution sum!
Above the summation is taken over all integers. However, in many practical cases either x[n] or h[n] or both are finite, for which case the summations will be limited. The convolution equations are simple tools which, in principle, can be used for all input signals. Following is an example to demonstrate convolution; how it is calculated and how it is interpreted.
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 timeinvariance 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 discretetime
signal is just a sum of scaled and shifted discretetime 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 discretetime input signal and the
system's response. The convolution sum is expressed as
_{ }(2)
convolution is represented by the symbol *, and can be written as
y[n] =x[n] *h[n]
By making a
simple change of variables into the convolution sum, k=n−k, we can easily show that convolution is
commutative:
y[n] =x[n] *h[n]
=h[n] *x[n]
(4)
From equation
4 we get a convolution sum that is equivalent to the sum in equation 2:
_{ } (5)
For more information on the characteristics of convolution, read about the Properties of Convolution.
Convolution Through Time (A Graphical Approach)
In this
section we will develop a second graphical interpretation of discretetime
convolution. We will begin this by writing the convolution sum allowing x
to be a causal, lengthm signal and h to be a causal, lengthk, LTI
system. This gives us the finite summation,
_{ }
(6)
Notice that for any given n we have a sum of the m products of x[l] and a timedelayed h[n−l]. This is to say that we multiply the terms of x by the terms of a timereversed h and add them up.
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, h , and
begin its traverse at time 0. 
Figure 7:
We continue the traverse. See that at time 1, we are multiplying two elements
of the input signal by two elements of the impulse response.

Figure 8 
Figure 9:
If we follow this through to one more step, n=4, then we can
see that we produce the same output as we saw in the initial
example. 
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 timereversing, and sliding across is a common approach to presenting
convolution, since it demonstrates how convolution builds up an output through
time.