space-invariant system.
366
Lee & Varaiya, Signals and Systems
9. FILTERING
of systems, and build up to detailed descriptions of software that can implement certain
kinds of LTI (or LSI) systems. These imperative descriptions are based on convolution.
9.1.1
Convolution sum and integral
For discrete-time signals the convolution operator is called the convolution sum, and for
continuous-time signals it is called the convolution integral. We define these two operators
now and note some important properties.
Let x, y ∈ [Z → R] be two discrete-time signals. The convolution of x and y is the discrete-
time signal, denoted x ∗ y, given by the convolution sum,
∞
∀n ∈ Z, (x ∗ y)(n) = ∑ x(k)y(n − k).
(9.1)
k=−∞
We note two properties. First, the order in the convolution does not matter, x ∗ y = y ∗ x.
Indeed, if in (9.1) we change the variables in the summation, letting m = n − k, we get
∞
∀n ∈ Z, (x ∗ y)(n) =
∑ x(k)y(n − k)
k=−∞
∞
=
∑ x(n − m)y(m).
m=−∞
Thus,
(x ∗ y)(n) = (y ∗ x)(n).
(9.2)
This property is called commutativity of the convolution operator.1
Another property of convolution is linearity. That is, if x, y1, y2 are three signals and a1
and a2 are real numbers, then
x ∗ (a1y1 + a2y2) = a1(x ∗ y1) + a2(x ∗ y2),
(9.3)
which may be checked directly by applying definition (9.1) to both sides.
1Matrix multiplication is an example of an operator that is not commutative, while matrix addition is.
Since the sum of two matrices M and N (of the same size) does not depend on the order, i.e., M + N = N + M,
the matrix sum is a commutative operator. However, the product of two matrices depends on the order, i.e., it
is not always true that M × N = N × M, so the matrix product is not commutative.
Lee & Varaiya, Signals and Systems
367
9.1. CONVOLUTION
We now use the convolution sum to define some LTI systems. Fix a discrete-time signal
h, and define the system
S : [Z → R] → [Z → R]
by
∀ x ∈ [Z → R], S(x) = h ∗ x.
Thus the output signal y = S(x) corresponding to the input signal x is given by
∞
∀ n ∈ Z, y(n) = ∑ h(k)x(n−k).
k=−∞
We now show that S is LTI. The linearity of S follows immediately from the linearity
property of the convolution. To show time-invariance, we must show that for any integer
M, and any input signal x,
DM(h ∗ x) = h ∗ (DM(x)),
where DM is a delay by M. But this is easy to see, since for all n,
(DM(h ∗ x))(n) = (h ∗ x)(n − M)
∞
=
∑ h(k)x(n − M − k), by definition (9.1)
k=−∞
∞
=
∑ h(k)z(n − k), where z = DM(x)
k=−∞
=
(h ∗ z)(n).
Thus every discrete-time signal h defines an LTI system via convolution. In the next
section we will see the converse result, that every LTI system is defined by convolution
with some signal h.
Example 9.1: Consider a discrete-time signal h defined by
∀
1/3
if n ∈ {0, 1, 2}
n ∈ Z,
h(n) =
0
otherwise
This is shown in Figure 9.2. Let us define a system S as follows. If the input is x,
then the output is
y = S(x) = h ∗ x.
368
Lee & Varaiya, Signals and Systems
9. FILTERING
h( n)
...
1/3
...
n
Figure 9.2: Signal in example 9.1.
I.e.,
∞
∀ n ∈ Z, y(n) =
∑ h(k)x(n − k)
k=−∞
2
=
∑ (1/3)x(n − k)
k=0
=
(x(n) + x(n − 1) + x(n − 2))/3.
(9.4)
This system calculates the three-point moving average!
We now turn to the continuous time case. Let x, y ∈ [R → R] be two continuous-time
signals. The convolution of x and y is the continuous-time signal, denoted x ∗ y, given by
the convolution integral
∞
∀ t ∈
R
R,
(x ∗ y)(t) =
x(τ)y(t − τ)dτ.
(9.5)
−∞
By a change of variable in the integral we can check that convolution again is commuta-
tive, i.e.,
∀ t ∈ R, (x ∗ y)(t) = (y ∗ x)(t),
(9.6)
and it is linear; i.e. if x, y1, y2 are three continuous-time signals and a1, a2 are real numbers,
then
x ∗ (a1y1 + a2y2) = a1(x ∗ y1) + a2(x ∗ y2).
(9.7)
Again fix h ∈ [R → R], and define the system
S : [R → R] → [R → R]
Lee & Varaiya, Signals and Systems
369
9.1. CONVOLUTION
h( t)
1/3
t
3
Figure 9.3: Signal in example 9.2.
by
∀ x ∈ [R → R], S(x) = h ∗ x.
Then in exactly the same way as for the discrete-time case, we can show that S is LTI.
Example 9.2: Consider a continuous-time signal h defined by
∀
1/3
if t ∈ [0, 3]
t ∈ R,
h(t) =
0
otherwise
This is shown in Figure 9.3. Let us define a system S as follows. If the input is x,
then the output is
y = S(x) = h ∗ x.
I.e,
∞
Z
∀ t ∈ R, y(t) =
h(τ)x(t − τ)dτ
−∞
3
1 Z
=
x(t − τ)dτ.
(9.8)
3
0
This system is the length-three continuous-time moving average!
Note that we are using the same symbol ‘*’ for the convolution sum and the convolution
integral. The context will determine which operator is intended.
370
Lee & Varaiya, Signals and Systems
9. FILTERING
!( n)
1
...
...
n
Figure 9.4: The Kronecker delta function, a discrete-time impulse.
9.1.2
Impulses
Intuitively, an impulse is a signal that is zero everywhere except at time zero. In the
discrete-time case, the Kronecker delta function,
δ : Z → R
is defined by
∀
1
if n = 0
n ∈ Z,
δ(n) =
(9.9)
0
otherwise
Its graph is shown in Figure 9.4.
The continuous-time case, which is called the Dirac delta function, is mathematically
much more difficult to work with. Like the Kronecker delta function, it is zero everywhere
except at zero. But unlike the Kronecker delta function, its value is infinite at zero. We
will not concentrate on its subtleties, but rather just introduce it and assert some results
without fully demonstrating their validity. The Dirac delta function is defined to be
δ : R → R++
where R++ = R ∪ {∞, −∞}, and
∀ t ∈ R where t = 0, δ(t) = 0
and where the following property is satisfied for any ε > 0 in R++,
ε
Z
δ(t)dt = 1
−ε
Lee & Varaiya, Signals and Systems
371
9.1. CONVOLUTION
!( t)
1
t
Figure 9.5: The Dirac delta function, a continuous-time impulse.
For the latter property to be satisfied, clearly no finite value at t = 0 would suffice. This
is why the value must be infinite at t = 0. Notice that the Kronecker delta function has a
similar property,
a
∑ δ(n) = 1
n=−a
for any integer a > 0, but that in this case, the property is trivial. There is no mathematical
subtlety.
The Dirac delta function is usually depicted as in Figure 9.5. In any figure, of course,
the infinite value at t = 0 cannot be shown directly. The figure suggests that infinite value
with a vertical arrow. Next to the arrow is the weight of the delta function, ‘1’ in this case.
In general, a Dirac delta function can be multiplied by any real constant a. Of course, this
does not change its value at t = 0, which is infinite, nor does it change its value at t = 0,
which is zero. What it does change is its integral,
ε
Z
aδ(t)dt = a.
−ε
Thus, although the impulse is still infinitely narrow and infinitely high, the area under the
impulse has been scaled by a.
9.1.3
Signals as sums of weighted delta functions
Any discrete-time signal x : Z → R can be expressed as a sum of weighted Kronecker
delta functions,
∞
∀ n ∈ Z, x(n) = ∑ x(k)δ(n − k).
(9.10)
k=−∞
372
Lee & Varaiya, Signals and Systems
9. FILTERING
...
0 !( n+1)
...
...
n
(1/3)!( n)
...
1/3
...
n
(!( n) + !( n # 1) + !( n # 2))/3
(1/3)!( n # 1)
...
1/3
...
n
...
1/3
...
n
"
(1/3)!( n # 2)
...
1/3
...
n
0 !( n # 3)
...
...
n
...
Figure 9.6: A discrete-time signal is a sum of weighted delta functions.
Lee & Varaiya, Signals and Systems
373
9.1. CONVOLUTION
The kth term in the sum is x(k)δ(n − k). This term, by itself, defines a signal that is zero
everywhere except at n = k, where it has value x(k). This signal is called a weighted delta
function because it is a (time shifted) delta function with a specified weight. Thus, any
discrete-time signal is a sum of weighted delta functions, much the way that the Fourier
series describes a signal as a sum of weighted complex exponential functions.
Example 9.3: The signal h in example 9.1 can be written in terms of Kronecker
delta functions,
∀ n ∈ Z, h(n) = (δ(n) + δ(n − 1) + δ(n − 2))/3.
This has the form of (9.10), and is illustrated in Figure 9.6. It is described as a sum of signals where each signal contains only a single weighted impulse.
Equation (9.10) is sometimes called the sifting property of the Kronecker delta function
because it “sifts out” the value of a function x at some integer n. That is, the infinite
sum reduces to a single number. This property can often be used to eliminate infinite
summations in more complicated expressions.
The continuous-time version of this is similar, except that the sum becomes an integral
(integration, after all, is just sum over a continuum). Given any signal x : R → R,
∞
Z
∀ t ∈ R, x(t) =
x(τ)δ(t − τ)dτ.
(9.11)
−∞
Although this is mathematically much more subtle than the discrete-time case, it is very
similar in structure. It describes a signal x as a sum (or more precisely, an integral) of
weighted Dirac delta functions.
Example 9.4: The signal h in Figure 9.3 and example 9.2 can be written as a sum (an integral, actually) of weighted Dirac delta functions,
Z
∞
∀ t ∈ R, h(t) =
h(τ)δ(t − τ)dτ
−∞
Z
3
=
(1/3)δ(t − τ)dτ.
0
374
Lee & Varaiya, Signals and Systems
9. FILTERING
This has the form of (9.11).
Equation (9.11) is sometimes called the sifting property of the Dirac delta function,
because it sifts out from the function x the value at a given time t. The sifting property
can often be used to eliminate integrals, since it replaces an integral with a single value.
9.1.4
Impulse response and convolution
Consider a discrete-time LTI system S : [Z → R] → [Z → R]. Define its impulse re-
sponse h to be the output signal when the input signal is the Kronecker delta function (an
impulse), h = S(δ), that is,
∀ n ∈ Z, h(n) = (S(δ))(n).
Now let x be any input signal, and let y = S(x) be the corresponding output signal. In
(9.10), x is given as sum of components, where each component is a weighted delta func-
tion. Since S is LTI, the output can be given as a sum of the responses to these compo-
nents. Each component is a signal x(k)δ(n − k) for fixed k, and the response to this signal
is x(k)h(n −k). The response to a scaled and delayed impulse will be a scaled and delayed
impulse response. Thus, the overall output is
∞
∀ n ∈ Z, y(n) = ∑ x(k)h(n − k) = (x ∗ h)(n) = (h ∗ x)(n).
k=−∞
Thus, the output of any discrete-time LTI system is given by the convolution of the input
signal and the impulse response.
Example 9.5: The three-point moving average system S of example 9.1 has im-
pulse response
∀ n ∈ Z, h(n) = (δ(n) + δ(n − 1) + δ(n − 2))/3.
This can be determined from (9.4) by just letting the input be x = δ. The impulse
response, after all, is defined to be the output when the input is an impulse. The
impulse response is shown in Figure 9.2.
Lee & Varaiya, Signals and Systems
375
9.1. CONVOLUTION
Consider now a continuous-time LTI system S : [R → R] → [R → R]. Define its impulse
response to be the output signal h when the input signal is the Dirac delta function, h =
S(δ), i.e.,
∀t ∈ R, h(t) = S(δ)(t).
Now let x be any input signal and let y = S(x), be the corresponding output signal. By the
sifting property we can express x as the sum (integral) of weighted delta functions,
Z
∞
x(t) =
x(τ)δ(t − τ)dτ.
−∞
Since S is LTI, the output is a sum (integral) of the responses to each of the components
(the integrand for fixed τ), or
∞
∀ t ∈
R
R,
y(t) =
x(τ)h(t − τ)dτ = (x ∗ h)(t) = (h ∗ x)(t).
(9.12)
−∞
Thus,
The output of any continuous-time LTI system is given by the convolution of the input
signal and the impulse response.
Example 9.6: The length-three continuous-time moving average system S of ex-
ample 9.2 has impulse response
∀
1/3
if t ∈ [0, 3]
t ∈ R,
h(t) =
0
otherwise
This can be determined from (9.8) by just letting the input be x = δ and then using
the sifting property of the delta function. The impulse response, after all, is defined
to be the output when the input is an impulse. The impulse response is shown
in Figure 9.3. In general, a moving average has an impulse response with this
rectangular shape.
Example 9.7: Consider an M-step discrete-time delay system, as in example 8.9,
where the output y is given in terms of the input x by the difference equation
∀ n ∈ Z, y(n) = x(n − M).
(9.13)
376
Lee & Varaiya, Signals and Systems
9. FILTERING
The impulse response can be found by letting x = δ, to get
h(n) = δ(n − M).
The output can be given as a convolution of the input and the impulse response,
∞
y(n) = ∑ x(k)δ(n − M − k) = x(n − M),
k=−∞
using the sifting property. Of course, this agrees with (9.13).
Example 9.8:
Consider a T second continuous-time delay system, where the
output y is given in terms of the input x by the equation
∀ t ∈ R, y(t) = x(t − T).
(9.14)
The impulse response can be found by letting x = δ, to get
h(t) = δ(t − T ).
The output can be given as a convolution of the input and the impulse response,
∞
Z
y(t) =
x(τ)δ(t − T − τ)dτ = x(t − T ),
−∞
using the sifting property. Of course, this agrees with (9.14).
Example 9.9: Suppose that we have two LTI systems (discrete or continuous time)
with impulse responses h1 and h2, and we connect them in a cascade structure as
shown in Figure 9.7. We can find the impulse response of the cascade composition
by letting the input be an impulse, x = δ. Then the output of the first system will be
its impulse response, w = h1. This provides the input to the second system, so its
Lee & Varaiya, Signals and Systems
377
9.2. FREQUENCY RESPONSE AND IMPULSE RESPONSE
h
h 1
h 2
x
w
y
Figure 9.7: A cascade combination of two discrete-time LTI systems.
output will be y = h1 ∗ h2. Thus, the overall impulse response is the convolution of
the two impulse responses,
h = h1 ∗ h2.
We also know from the previous chapter that the frequency responses relate in a
very simple way, namely
H(ω) = H1(ω)H2(ω).
We will find that, in general, convolution in the time domain is equivalent to multi-
plication in the frequency domain.
9.2
Frequency response and impulse response
If a discrete-time LTI system has impulse response h, then the output signal y correspond-
ing to the input signal x is given by the convolution sum,
∞
∀ n ∈ Z, y(n) = ∑ h(m)x(n−m).
m=−∞
In particular, suppose the input is the complex exponential function
∀n ∈ Z, x(n) = eiωn,
for some real ω. Then the output signal is
∞
∞
∀ n ∈ Z, y(n) = ∑ h(m)eiω(n−m) = eiωn ∑ h(m)e−iωm.
m=−∞
m=−∞
378
Lee & Varaiya, Signals and Systems
9. FILTERING
Recall further that when the input is a complex exponential with frequency ω, then the
output is given by
∀ n ∈ Z, y(n) = H(ω)eiωn
where H(ω) is the frequency response. Comparing these two expressions for the output
we see that the frequency response is related to the impulse response by
∞
∀ω ∈ R, H(ω) = ∑ h(m)e−iωm.
(9.15)
m=−∞
This expression allows us, in principle, to calculate the frequency response from the im-
pulse response. Equation (9.15) gives us a way to transform h, a time-domain function,
into H, a frequency domain function. Equation (9.15) is called a discrete-time Fourier
transform (DTFT). Equivalently, we say that H is the DTFT of h. So the frequency
response of a discrete-time system is the DTFT of its impulse response.
Example 9.10: Consider the M-step delay from example 9.7. Its impulse response
is
∀ n ∈ Z, h(n) = δ(n − M).
We can find the frequency response by calculating the DTFT,
∞
∀ ω ∈ R, H(ω) =
∑ h(m)e−iωm
m=−∞
∞
=
∑ δ(m − M)e−iωm
m=−∞
=
e−iωM
where the last step follows from the sifting property. This same result was obtained
more directly in example 8.9. Note that the magnitude response is particularly
simple,
|H(ω)| = 1.
This is intuitive. An M-step delay does not change the magnitude of any complex
exponential input. It only shifts its phase.
Lee & Varaiya, Signals and Systems
379
9.2. FREQUENCY RESPONSE AND IMPULSE RESPONSE
Notice from (9.15) that
If h is real-valued then H∗(−ω) = H(ω)
(9.16)
(just conjugate both sides of (9.15) and evaluate at −ω). This property is called conjugate
symmetry. It implies
|H(−ω)| = |H(ω)|.
(9.17)
This says that for any LTI system with a real-valued impulse response, a complex expo-
nential with frequency ω experiences the same amplitude change as a complex exponen-
tial with frequency −ω.
Notice further from (9.15) that
∀ ω ∈ R, H(ω + 2π) = H(ω).
(9.18)
I.e., the DTFT is periodic with period 2π. This says that a complex exponential with
frequency ω experiences the same amplitude and phase change as a complex exponential
with frequency ω + 2π. This should not be surprising since the two complex exponentials
are in fact identical,
∀ n ∈ Z, ei(ω+2π)n = eiωnei2πn = eiωn,
because ei2πn = 1 for any in