The Mathematica Journal
Departments
Feature Articles
Columns
New Products
New Publications
Classifieds
Calendar
News Bulletins
Mailbox
Letters
Write Us
About the Journal
Staff and Contributors
Submissions
Subscriptions
Advertising
Back Issues
Home
Download this Issue

2. Convolution

One of the most widely used signal/image processing operations is filtering. In many practical cases the filtering operation is linear shift-invariant (LSI) and may be described by the following relation [1]:

[Graphics:../Images/index_gr_1.gif],

where [Graphics:../Images/index_gr_2.gif] is the so-called impulse response of the filter, [Graphics:../Images/index_gr_3.gif] is the input, and [Graphics:../Images/index_gr_4.gif] is the output of the system. Equation (2.1) is called the convolution sum formulation of an LSI system. A single output value is computed by summing over all point-wise products of one sequence with a time-reversed and shifted version of the other.

An important category of discrete-time systems exhibits a finite impulse response (FIR), so [Graphics:../Images/index_gr_5.gif] has finite length. It is common to define [Graphics:../Images/index_gr_6.gif] on the interval [Graphics:../Images/index_gr_7.gif]. In practice, the sequence [Graphics:../Images/index_gr_8.gif] is also finite in length, so that [Graphics:../Images/index_gr_9.gif] can be computed in finite time. Consider two sequences [Graphics:../Images/index_gr_10.gif] and [Graphics:../Images/index_gr_11.gif], of lengths [Graphics:../Images/index_gr_12.gif] and [Graphics:../Images/index_gr_13.gif], respectively, and defined for positive values of n only. Equation (2.1) then reduces to the following finite summation:

[Graphics:../Images/index_gr_14.gif]

The output sequence [Graphics:../Images/index_gr_16.gif] has length [Graphics:../Images/index_gr_17.gif]. Equation (2.2) is called a linear convolution.
Here we define two finite length sequences and evaluate (5).

It is instructive to evaluate the sums in Equation (2.2) given some input sequence [Graphics:../Images/index_gr_18.gif] and impulse response sequence [Graphics:../Images/index_gr_19.gif]. For demonstration purposes, we use two symbolic sequences.

[Graphics:../Images/index_gr_20.gif]

This returns a linear convolution of the two sequences using ListConvolve.

[Graphics:../Images/index_gr_21.gif]
[Graphics:../Images/index_gr_22.gif]
[Graphics:../Images/index_gr_23.gif]
[Graphics:../Images/index_gr_24.gif]
[Graphics:../Images/index_gr_25.gif]
[Graphics:../Images/index_gr_26.gif]
[Graphics:../Images/index_gr_27.gif]
[Graphics:../Images/index_gr_28.gif]
[Graphics:../Images/index_gr_29.gif]

The output sequence may be subdivided into three subranges. The first two output samples represent a transient portion of the output signal due to a partial overlap of nonzero values of the sequences [Graphics:../Images/index_gr_30.gif] and [Graphics:../Images/index_gr_31.gif]. The middle four samples represent a steady state portion of the output sequence (nonzero values of [Graphics:../Images/index_gr_32.gif] and [Graphics:../Images/index_gr_33.gif] are fully overlapped). The last two output samples represent a second transient portion of the output sequence, which again is due to a partial overlap of the two sequences. The lengths of these transients are always given by [Graphics:../Images/index_gr_34.gif], where [Graphics:../Images/index_gr_35.gif]. A result that excludes the transient samples is sometimes sufficient or desirable.

[Graphics:../Images/index_gr_36.gif]
[Graphics:../Images/index_gr_37.gif]
[Graphics:../Images/index_gr_38.gif]
[Graphics:../Images/index_gr_39.gif]
[Graphics:../Images/index_gr_40.gif]

Two additional convolution formulations can be found in the signal processing literature. The first is called periodic convolution and defines a convolution operation for periodic sequences. Assuming two sequences [Graphics:../Images/index_gr_41.gif] and [Graphics:../Images/index_gr_42.gif] have periods M and N, respectively (i.e., [Graphics:../Images/index_gr_43.gif] and [Graphics:../Images/index_gr_44.gif]), we define periodic convolution of the two sequences as

[Graphics:../Images/index_gr_45.gif]

where [Graphics:../Images/index_gr_46.gif]. The output sequence [Graphics:../Images/index_gr_47.gif] is also periodic with period min(N, M). Equation (2.3) looks very much like linear convolution and involves the summation of the products of one sequence with the time-reversed and shifted copy of the other. However, since the sequences in Equation (2.3) are periodic, shifts of such sequences produce results different from shifts of finite-duration signals (see Figure 2.1).

[Graphics:../Images/index_gr_48.gif]

Figure 2.1. Demonstration of a right shift of an aperiodic (left) and periodic (right) signal.

The other convolution formulation is called circular convolution [1]. By analogy with linear convolution, the formulation applies to finite-length signals, but all shifts are "circular" as in periodic convolution (see Figure 2.2). Circular convolution is particularly important, since it arises from a discrete Fourier transform (DFT) implementation of the convolution operation. It is well known that given three sequences of length [Graphics:../Images/index_gr_49.gif], [Graphics:../Images/index_gr_50.gif], [Graphics:../Images/index_gr_51.gif], [Graphics:../Images/index_gr_52.gif], and their respective N-point DFTs, [Graphics:../Images/index_gr_53.gif], [Graphics:../Images/index_gr_54.gif], [Graphics:../Images/index_gr_55.gif], and further given that

[Graphics:../Images/index_gr_56.gif]

it can be shown that the following convolution relationship exists between the sequences:

[Graphics:../Images/index_gr_57.gif]

where [Graphics:../Images/index_gr_59.gif] represents a circular shift of the sequence [Graphics:../Images/index_gr_60.gif]. A well-known algorithm called the fast Fourier transform (FFT) allows a fast computation of the DFT, and thus a fast implementation of convolution. Circular and linear convolutions yield different transient samples and identical steady-state samples.

[Graphics:../Images/index_gr_61.gif]

Figure 2.2. Example of a circular shift of a sequence of length [Graphics:../Images/index_gr_62.gif].

Circular convolution is equivalent to periodic convolution if we consider sequences [Graphics:../Images/index_gr_63.gif] and [Graphics:../Images/index_gr_64.gif] to correspond to single periods of their respective infinite periodic extensions [Graphics:../Images/index_gr_65.gif] and [Graphics:../Images/index_gr_66.gif], such that

[Graphics:../Images/index_gr_57.gif]

We calculate the circular convolution of the two example sequences and compare with linear convolution.

[Graphics:../Images/index_gr_71.gif]
[Graphics:../Images/index_gr_72.gif]
[Graphics:../Images/index_gr_73.gif]
[Graphics:../Images/index_gr_74.gif]
[Graphics:../Images/index_gr_75.gif]
[Graphics:../Images/index_gr_76.gif]
[Graphics:../Images/index_gr_77.gif]

An examination of the last result confirms that circular and linear convolutions yield the same steady-state samples. Note that the last four output samples are the same as the steady-state outputs resulting from linear convolution of the two sequences. It is frequently desirable to have the steady-state samples appear centered in the output list. This is achieved by setting the klist elements [Graphics:../Images/index_gr_78.gif] and [Graphics:../Images/index_gr_79.gif] equal to the index of the center element of fir (see ListConvolve for details).

[Graphics:../Images/index_gr_80.gif]
[Graphics:../Images/index_gr_81.gif]
[Graphics:../Images/index_gr_82.gif]
[Graphics:../Images/index_gr_83.gif]
[Graphics:../Images/index_gr_84.gif]
[Graphics:../Images/index_gr_85.gif]
[Graphics:../Images/index_gr_86.gif]

FIR systems play an especially important role in 2D systems. In digital image processing, many useful operators (i.e., edge detectors) are linear with finite spatial dimensions. The 2D linear convolution sum takes the following form:

[Graphics:../Images/index_gr_57.gif]

for  [Graphics:../Images/index_gr_90new.gif], where [Graphics:../Images/index_gr_91new.gif] are the dimensions of [Graphics:../Images/index_gr_92new.gif], [Graphics:../Images/index_gr_93new.gif] are the dimensions of [Graphics:../Images/index_gr_94new.gif], and [Graphics:../Images/index_gr_95new.gif] are the dimensions of [Graphics:../Images/index_gr_96new.gif]. The properties of the convolution operator defined in Equation (2.7) are straightforward extensions of the 1D linear convolution operator.

In two dimensions, circular convolution is given by

[Graphics:../Images/index_gr_57.gif]

for [Graphics:../Images/index_gr_98new.gif].


Converted by Mathematica      

[Article Index] [Prev Page][Next Page]