Convolution
The
convolution of two
signals 
and

in

may be
denoted ``

'' and defined by

Note that this is
circular convolution (or ``cyclic''
convolution).
7.4 The importance of convolution in
linear systems theory is discussed in §
8.3.
Cyclic convolution can be expressed in terms of previously defined
operators as
where

and

. This expression suggests
graphical convolution, discussed below in §
7.2.4.
Convolution (cyclic or acyclic) is
commutative,
i.e.,
Proof:
In the first step we made the change of summation variable

, and in the second step, we made use of the fact
that any sum over all

terms is equivalent to a sum from 0 to

.
In a convolution of two
signals

, where both

and

are signals of length

(real or complex), we may interpret either

or

as a
filter that operates on the other signal
which is in turn interpreted as the filter's ``input signal''.
7.5 Let

denote a length

signal that is interpreted
as a filter. Then given any input signal

, the filter output
signal

may be defined as the
cyclic convolution of

and

:
Because the convolution is cyclic, with

and

chosen from the
set of (periodically extended) vectors of length

,

is most
precisely viewed as the
impulse-train-response of the
associated filter at time

. Specifically, the impulse-train
response

is the response of the filter to the
impulse-train signal
![$ \delta\isdeftext [1,0,\ldots,0]\in{\bf R}^N$](http://www.dsprelated.com/josimages_new/mdft/img1169.png)
,
which, by
periodic extension, is equal to
Thus,

is the
period of the impulse-train in samples--there
is an ``impulse'' (a `

') every

samples. Neglecting the assumed
periodic extension of all signals in

, we may refer to

more simply as the
impulse signal, and

as the
impulse
response (as opposed to impulse-
train response). In contrast,
for the
DTFT (§
B.1), in which the discrete-time axis is
infinitely long, the impulse signal

is defined as
and no periodic extension arises.
As discussed below (§
7.2.7), one may embed
acyclic
convolution within a larger cyclic convolution. In this way,
real-world systems may be simulated using fast
DFT convolutions (see
Appendix
A for more on fast convolution algorithms).
Note that only linear, time-invariant (
LTI) filters can be completely
represented by their impulse response (the filter output in response
to an impulse at time 0). The
convolution representation of LTI
digital filters is fully discussed in Book II [
68] of the
music signal processing book series (in which this is Book I).
Convolution Example 1: Smoothing a Rectangular Pulse
Figure 7.3:
Illustration of the convolution of a rectangular pulse
and the impulse response
of an ``averaging filter''
(
).
Filter output signal  .
|
Figure
7.3 illustrates convolution of
with
to get
![$\displaystyle y = x\circledast h = \left[0,0,0,0,\frac{1}{3},\frac{2}{3},1,1,1,1,\frac{2}{3},\frac{1}{3},0,0\right] \protect$](http://www.dsprelated.com/josimages_new/mdft/img1178.png) |
(7.2) |
as graphed in Fig.
7.3(c).
In this case,

can be viewed as a ``moving three-point average''
filter. Note how the corners of the rectangular pulse are ``smoothed''
by the three-point filter. Also note that the pulse is smeared to the
``right'' (forward in time) because the filter impulse response starts
at time zero. Such a filter is said to be
causal (see
[
68] for details). By shifting the impulse response left one
sample to get
(in which case

), we obtain a noncausal filter

which is
symmetric about time zero so that the input signal is smoothed ``in
place'' with no added delay (imagine Fig.
7.3(c) shifted left
one sample, in which case the input pulse edges align with the
midpoint of the rise and fall in the output signal).
Figure 7.4:
Illustration of the convolution of two rectangular pulses with a truncated
exponential impulse response.
Filter output signal  .
|
In this example, the input signal is a sequence of two
rectangular pulses, creating a piecewise constant function, depicted
in Fig.
7.4(a). The filter impulse response, shown in
Fig.
7.4(b), is a truncated
exponential.
7.6
In this example,

is again a
causal smoothing-filter impulse
response, and we could call it a ``moving weighted average'', in which
the weighting is exponential into the past. The discontinuous steps
in the input become exponential ``asymptotes'' in the output which are
approached exponentially. The overall appearance of the output signal
resembles what is called an
attack, decay, release, and sustain
envelope, or
ADSR envelope for short. In a practical ADSR
envelope, the
time-constants for attack, decay, and release may be set
independently. In this example, there is only one time constant, that
of

. The two constant levels in the input signal may be called the
attack level and the
sustain level, respectively. Thus,
the envelope approaches the attack level at the attack rate (where the
``rate'' may be defined as the reciprocal of the time constant), it
next approaches the sustain level at the ``decay rate'', and finally,
it approaches zero at the ``release rate''. These envelope parameters
are commonly used in analog synthesizers and their digital
descendants, so-called
virtual analog synthesizers. Such an
ADSR envelope is typically used to multiply the output of a waveform
oscillator such as a sawtooth or pulse-train oscillator. For more on
virtual analog synthesis, see, for example,
[
78,
77].
Figure 7.5:
Illustration of convolution of
and ``matched filter''
(
).
![\includegraphics[width=2.5in]{eps/conv}](http://www.dsprelated.com/josimages_new/mdft/img1185.png) |
Figure
7.5 illustrates convolution of
to get
![$\displaystyle y\circledast h = [4,3,2,1,0,1,2,3]. \protect$](http://www.dsprelated.com/josimages_new/mdft/img1187.png) |
(7.3) |
For example,

could be a ``rectangularly windowed
signal, zero-padded by
a factor of 2,'' where the signal happened to be
dc (all

s).
For the
convolution, we need
which is the same as

. When

, we say that

is a
matched filter for

.
7.7 In this case,

is matched to look for a
``dc component,'' and also zero-padded by a factor of

. The
zero-padding serves to simulate acyclic convolution using
circular
convolution. Note from Eq.

(
7.3) that the maximum is obtained
in the convolution output at time 0. This peak (the largest
possible if all input signals are limited to
![$ [-1,1]$](http://www.dsprelated.com/josimages_new/mdft/img1190.png)
in magnitude),
indicates the matched filter has ``found'' the dc signal starting at
time 0. This peak would persist in the presence of some amount of
noise and/or
interference from other signals. Thus, matched filtering
is useful for detecting known signals in the presence of
noise and/or
interference [
34].
As mentioned above,
cyclic convolution can be written as
where

and

. It is instructive to interpret this
expression
graphically, as depicted in Fig.
7.5 above. The
convolution result at time

is the
inner product of

and

, or

. For the next time instant,

, we shift

one sample to the right and repeat the
inner product operation to obtain

,
and so on. To capture the cyclic nature of the convolution,

and

can be imagined plotted on a
cylinder.
Thus, Fig.
7.5 shows the cylinder after being ``cut'' along the
vertical line between

and

and ``unrolled'' to lay flat.
Polynomial Multiplication
Note that when you multiply two polynomials together, their
coefficients are
convolved. To see this, let

denote the

th-order polynomial
with coefficients

, and let

denote the

th-order polynomial
with coefficients

. Then we have [
1]
Denoting

by
we have that the

th coefficient can be expressed as
where

and

are doubly infinite sequences, defined as
zero for

and

, respectively.
Since decimal numbers are implicitly just polynomials in the powers of 10,
e.g.,
it follows that
multiplying two numbers convolves their digits. The
only twist is that, unlike normal
polynomial multiplication, we have
carries. That is, when a
convolution result (output digit)
exceeds 10, we subtract
10 from the result and add 1 to the digit in the next higher place.
Next Section: CorrelationPrevious Section: Shift Operator