Digital Signal Processing
Discrete-Time Signals and Systems (2)
Moslem Amiri, V´aclav Pˇrenosil
Embedded Systems Laboratory
Faculty of Informatics, Masaryk University
Brno, Czech Republic
amiri@mail.muni.cz
prenosil@fi.muni.cz
March, 2012
Techniques for the Analysis of Linear Systems
Methods for analyzing behavior or response of a linear system to a
given input
First method: through difference equations (will not be discussed)
Second method:
1 Decompose input signal into a weighted sum of elementary signals
x(n) =
k
ck xk (n)
2 Using linearity property of system, responses of system to elementary
signals are added to obtain total response of system
Assuming system is relaxed
yk (n) ≡ τ[xk (n)]
y(n) = τ[x(n)] = τ
k
ck xk (n) =
k
ck τ[xk (n)] =
k
ck yk (n)
Resolution of input signals into a weighted sum of unit sample
(impulse) sequences is mathematically convenient and general
2 / 41
Resolution of a Discrete-Time Signal into Impulses
An arbitrary signal x(n) is to be resolved into a sum of unit sample
sequences
We select elementary signals xk (n) to be
xk (n) = δ(n − k)
If x(n) and δ(n − k) are multiplied, result is another sequence that is
zero everywhere except at n = k, where it is x(k)
x(n)δ(n − k) = x(k)δ(n − k)
Consequently
x(n) =
∞
k=−∞
x(k)δ(n − k)
3 / 41
Resolution of a Discrete-Time Signal into Impulses
Figure 1: Multiplication of a signal x(n) with a shifted unit sample sequence.
4 / 41
Resolution of a Discrete-Time Signal into Impulses
Example
Resolve following finite-duration sequence into a sum of weighted
impulse sequences
x(n) = {2, 4
↑
, 0, 3}
x(n) is nonzero for n = −1, 0, 2
x(n) = 2δ(n + 1) + 4δ(n) + 3δ(n − 2)
5 / 41
The Convolution Sum
The response y(n, k) of any relaxed linear system to the input unit
sample sequence at n = k is denoted by h(n, k)
y(n, k) ≡ h(n, k) = τ[δ(n − k)]
If impulse at input is scaled by ck, response of system is
ckh(n, k) = x(k)h(n, k)
For input x(n)
x(n) =
∞
k=−∞
x(k)δ(n − k)
response of system is following superposition summation
y(n) = τ[x(n)] = τ
∞
k=−∞
x(k)δ(n − k) =
∞
k=−∞
x(k)τ[δ(n − k)]
=
∞
k=−∞
x(k)h(n, k)
6 / 41
The Convolution Sum
If response of LTI (Linear Time-Invariant) system to δ(n) is denoted as
h(n) ≡ τ[δ(n)]
then
h(n − k) = τ[δ(n − k)]
Consequently, response of system is
y(n) =
∞
k=−∞
x(k)h(n − k) (1)
This formula is called a convolution sum
Input x(n) is convolved with impulse response h(n) to yield output y(n)
7 / 41
The Convolution Sum
Suppose we wish to compute output of system at n = n0
y(n0) =
∞
k=−∞
x(k)h(n0 − k)
Process of computing convolution between x(k) and h(k):
1 Folding. Fold h(k) about k = 0 to obtain h(−k)
2 Shifting. Shift h(−k) by n0 to right (left) if n0 is positive (negative) to
obtain h(n0 − k)
3 Multiplication. υn0 (k) ≡ x(k)h(n0 − k)
4 Summation. Sum all values of υn0
(k) to obtain output at n = n0
8 / 41
The Convolution Sum
Example
Impulse response of an LTI system is
h(n) = {1, 2
↑
, 1, −1}
Determine response of system to input signal
x(n) = {1
↑
, 2, 3, 1}
To compute output at n = 0
y(n) =
∞
k=−∞
x(k)h(n − k) −→ y(0) =
∞
k=−∞
x(k)h(−k)
First fold h(k) - no shifting is required - then do multiplication
υ0(k) ≡ x(k)h(−k)
Finally, sum of all terms in product sequence yields
y(0) =
∞
k=−∞ υ0(k) = 4
9 / 41
The Convolution Sum
Figure 2: Graphical computation of convolution.
10 / 41
The Convolution Sum
Example (continued)
Response of system at n = 1
y(n) =
∞
k=−∞
x(k)h(n − k) −→ y(1) =
∞
k=−∞
x(k)h(1 − k)
h(1 − k) is h(−k) shifted to right by one unit
Product sequence
υ1(k) = x(k)h(1 − k)
Sum of all values in product sequence
y(1) =
∞
k=−∞ υ1(k) = 8
By shifting h(−k) farther to right, multiplying and summing, we obtain
y(2) = 8, y(3) = 3, y(4) = −2, y(5) = −1
For n > 5, y(n) = 0 because product sequences contain all zeros
11 / 41
The Convolution Sum
Example (continued)
To evaluate y(n) for n = −1
y(n) =
∞
k=−∞
x(k)h(n − k) −→ y(−1) =
∞
k=−∞
x(k)h(−1 − k)
h(−1 − k) is h(−k) shifted one unit to left
Product sequence
υ−1(k) = x(k)h(−1 − k)
Sum of all values in product sequence
y(−1) =
∞
k=−∞ υ−1(k) = 1
Further shifts of h(−1 − k) to left result in all-zero product sequence
y(n) = 0 for n ≤ −2
Entire response of system for −∞ < n < ∞
y(n) = {. . . , 0, 0, 1, 4
↑
, 8, 8, 3, −2, −1, 0, 0, . . .}
12 / 41
The Convolution Sum
Convolution operation is commutative
It is irrelevant which of two sequences is folded and shifted
y(n) =
∞
k=−∞
x(k)h(n − k)
m=n−k
−−−−−→ y(n) =
∞
m=−∞
x(n − m)h(m)
replace m by k
−−−−−−−−−−−→ y(n) =
∞
k=−∞
x(n − k)h(k) (2)
Product sequences in (1) and (2) are not identical
If
υn(k) = x(k)h(n − k)
ωn(k) = x(n − k)h(k)
then
υn(k) = ωn(n − k)
therefore
y(n) =
∞
k=−∞
υn(k) =
∞
k=−∞
ωn(n − k)
Both sequences contain same values in a different arrangement
13 / 41
The Convolution Sum
Example
Determine output y(n) of a relaxed LTI system with impulse response
h(n) = anu(n), |a| < 1
when input is a unit step sequence: x(n) = u(n)
We use
y(n) =
∞
k=−∞
x(n − k)h(k)
14 / 41
The Convolution Sum
Figure 3: Graphical computation of convolution example. 15 / 41
The Convolution Sum
Example (continued)
We obtain outputs
y(0) = 1
y(1) = 1 + a
y(2) = 1 + a + a2
for n > 0
y(n) = 1 + a + a2
+ . . . + an
=
1 − an+1
1 − a
For n < 0, product sequences consist of all zeros. Hence
y(n) = 0, n < 0
Since |a| < 1
y(∞) = lim
n→∞
y(n) =
1
1 − a
16 / 41
Properties of Convolution - Interconnection of LTI Systems
An asterisk is used to denote convolution operation
y(n) = x(n) ∗ h(n) ≡
∞
k=−∞
x(k)h(n − k)
y(n) = h(n) ∗ x(n) ≡
∞
k=−∞
h(k)x(n − k)
Identity and shifting properties
δ(n) is identity element for convolution
y(n) = x(n) ∗ δ(n) = x(n)
Shifting δ(n) by k, convolution sequence is also shifted by k
x(n) ∗ δ(n − k) = y(n − k) = x(n − k)
17 / 41
Properties of Convolution - Interconnection of LTI Systems
Commutative law
x(n) ∗ h(n) = h(n) ∗ x(n)
Figure 4: Interpretation of the commutative property of convolution.
Associative law
[x(n) ∗ h1(n)] ∗ h2(n) = x(n) ∗ [h1(n) ∗ h2(n)]
Figure 5: Implications of the associative (a) and the associative and
commutative (b) properties of convolution.
18 / 41
Properties of Convolution - Interconnection of LTI Systems
Example
Determine impulse response for cascade of two LTI systems having
impulse responses
h1(n) = (1
2)nu(n) and h2(n) = (1
4)nu(n)
Convolve h1(n) and h2(n)
h(n) = ∞
k=−∞ h1(k)h2(n − k)
υn(k) = h1(k)h2(n − k) = (
1
2
)k
u(k)(
1
4
)n−k
u(n − k)
υn(k) is nonzero for k ≥ 0 and n − k ≥ 0 (or n ≥ k ≥ 0)
h(n) =
n
k=0
(
1
2
)k
(
1
4
)n−k
= (
1
4
)n
n
k=0
2k
= (
1
4
)n
(2n+1
− 1) = (
1
2
)n
[2 − (
1
2
)n
], n ≥ 0
For n < 0 −→ υn(k) = 0 for all k −→ h(n) = 0, n < 0 19 / 41
Properties of Convolution - Interconnection of LTI Systems
Distributive law
x(n) ∗ [h1(n) + h2(n)] = x(n) ∗ h1(n) + x(n) ∗ h2(n)
Figure 6: Interpretation of the distributive property of convolution: two LTI
systems connected in parallel can be replaced by a single system with
h(n) = h1(n) + h2(n).
20 / 41
Causal Linear Time-Invariant Systems
For an LTI system, causality can be translated to a condition on
impulse response
Consider an LTI system at time n = n0
y(n0) =
∞
k=−∞
h(k)x(n0 −k) =
∞
k=0
h(k)x(n0 −k)+
−1
k=−∞
h(k)x(n0 −k)
First sum: present and past inputs (x(n) for n ≤ n0)
Second sum: future inputs (x(n) for n > n0)
If output at n = n0 is to depend only on present and past inputs, then
h(n) = 0, n < 0
An LTI system is causal iff its h(n) = 0 for negative values of n. Thus
y(n) =
∞
k=0
h(k)x(n − k) =
n
k=−∞
x(k)h(n − k)
21 / 41
Causal Linear Time-Invariant Systems
A sequence that is zero for n < 0 is called a causal sequence
If nonzero for n < 0 and n > 0, it is called a noncausal sequence
If input to a causal LTI system is a causal sequence
y(n) =
n
k=0
h(k)x(n − k) =
n
k=0
x(k)h(n − k)
Example
Determine unit step response of LTI system with impulse response
h(n) = anu(n), |a| < 1
Both input signal (unit step) and system are causal
y(n) =
n
k=0
h(k)x(n − k) =
n
k=0
ak
=
1 − an+1
1 − a
y(n) = 0 for n < 0
22 / 41
Stability of Linear Time-Invariant Systems
Taking absolute value of both sides of convolution formula, we obtain
|y(n)| =
∞
k=−∞
h(k)x(n − k) ≤
∞
k=−∞
|h(k)||x(n − k)|
If input is bounded, there exists a finite number Mx such that
|x(n)| ≤ Mx
|y(n)| ≤ Mx
∞
k=−∞
|h(k)|
Output is bounded if
Sh ≡
∞
k=−∞
|h(k)| < ∞
An LTI system is stable if its impulse response is absolutely summable
This condition implies that h(n) goes to zero as n approaches infinity
23 / 41
Stability of Linear Time-Invariant Systems
Suppose |x(n)| < Mx for n < n0 and x(n) = 0 for n ≥ n0
y(n0 + N) =
N−1
k=−∞
h(k)x(n0 + N − k) +
∞
k=N
h(k)x(n0 + N − k)
First sum is zero since x(n) = 0 for n ≥ n0
|y(n0 + N)| =
∞
k=N
h(k)x(n0 + N − k) ≤
∞
k=N
|h(k)||x(n0 + N − k)|
≤ Mx
∞
k=N
|h(k)|
lim
N→∞
∞
k=N
|h(k)| = 0 −→ lim
N→∞
|y(n0 + N)| = 0
In a stable system, any finite duration input produces a transient output
24 / 41
Stability of Linear Time-Invariant Systems
Example
Determine range of values of parameter a for which LTI system with
h(n) = anu(n) is stable
System is causal
Sh ≡
∞
k=−∞
|h(k)| −→
∞
k=0
|ak
| =
∞
k=0
|a|k
= 1 + |a| + |a|2
+ · · ·
Geometric series converges to
∞
k=0
|a|k
=
1
1 − |a|
provided that |a| < 1. Therefore, system is stable if |a| < 1
Otherwise, it diverges and becomes unstable
25 / 41
Stability of Linear Time-Invariant Systems
Example
Determine range of a and b for which following LTI system is stable
h(n) =
an, n ≥ 0
bn, n < 0
System is noncausal
∞
n=−∞
|h(n)| =
∞
n=0
|a|n
+
−1
n=−∞
|b|n
−1
n=−∞
|b|n
=
∞
n=1
1
|b|n
=
1
|b|
1 +
1
|b|
+
1
|b|2
+ · · · =
1/|b|
1 − 1/|b|
where 1/|b| < 1
System is stable if |a| < 1 and |b| > 1
26 / 41
Systems with Finite & Infinite-Duration Impulse Response
We can subdivide LTI systems into two types
1 Those having a finite-duration impulse response (FIR)
2 Those having an infinite-duration impulse response (IIR)
For causal FIR systems
h(n) = 0, n < 0 and n ≥ M
y(n) =
M−1
k=0
h(k)x(n − k)
FIR system acts as a window that views only most recent M input
samples in forming output
Thus, FIR system has a finite memory of length-M samples
For causal IIR systems
y(n) =
∞
k=0
h(k)x(n − k)
IIR system has an infinite memory
27 / 41
Correlation of Discrete-Time Signals
Correlation closely resembles convolution
But objective in computing correlation between two signals is to
measure the degree to which they are similar
28 / 41
Crosscorrelation and Autocorrelation Sequences
For two real signal sequences x(n) and y(n) each having finite energy
Crosscorrelation of x(n) and y(n) is a sequence rxy (l)
rxy (l) =
∞
n=−∞
x(n)y(n − l) =
∞
n=−∞
x(n + l)y(n), l = 0, ±1, ±2, . . .
Index l is (time) shift (or lag) parameter
Reversing roles of x(n) and y(n)
ryx (l) =
∞
n=−∞
y(n)x(n − l) =
∞
n=−∞
y(n + l)x(n), l = 0, ±1, ±2, . . .
rxy (l) = ryx (−l)
ryx (l) is folded version of rxy (l), where folding is about l = 0
Hence, ryx (l) provides exactly same info as rxy (l), with respect to
similarity of x(n) to y(n)
29 / 41
Crosscorrelation and Autocorrelation Sequences
Example
Determine crosscorrelation sequence rxy (l) of sequences
x(n) = {. . . , 0, 0, 2, −1, 3, 7, 1
↑
, 2, −3, 0, 0, . . .}
y(n) = {. . . , 0, 0, 1, −1, 2, −2, 4
↑
, 1, −2, 5, 0, 0, . . .}
For l = 0
rxy (l) =
∞
n=−∞
x(n)y(n − l)
l=0
−−→ rxy (0) =
∞
n=−∞
x(n)y(n)
υ0(n) = x(n)y(n) = {. . . , 0, 2, 1, 6, −14, 4
↑
, 2, 6, 0, . . .} −→ rxy (0) = 7
For l > 0 (l < 0), shift y(n) to right (left) relative to x(n) by l units,
compute υl (n) = x(n)y(n − l), and sum over all values of υl (n)
rxy (l) = {10, −9, 19, 36, −14, 33, 0, 7
↑
, 13, −18, 16, −7, 5, −3}
30 / 41
Crosscorrelation and Autocorrelation Sequences
Except for folding operation in convolution, computations of
crosscorrelation and convolution are similar
rxy (l) = x(l) ∗ y(−l)
In special case where y(n) = x(n), we have autocorrelation of x(n)
rxx (l) =
∞
n=−∞
x(n)x(n − l) =
∞
n=−∞
x(n + l)x(n)
If x(n) and y(n) are causal sequences of length N
rxy (l) =
N−|k|−1
n=i
x(n)y(n − l)
rxx (l) =
N−|k|−1
n=i
x(n)x(n − l)
where i = l, k = 0 for l ≥ 0, and i = 0, k = l for l < 0
31 / 41
Properties of Autocorrelation & Crosscorrelation Sequences
Assume x(n) and y(n) with finite energy and their linear combination
ax(n) + by(n − l)
Energy in this signal
∞
n=−∞
[ax(n) + by(n − l)]2
= a2
∞
n=−∞
x2
(n) + b2
∞
n=−∞
y2
(n − l)
+ 2ab
∞
n=−∞
x(n)y(n − l)
= a2
rxx (0) + b2
ryy (0) + 2abrxy (l)
rxx (0) = Ex = energy of x(n)
ryy (0) = Ey = energy of y(n)
32 / 41
Properties of Autocorrelation & Crosscorrelation Sequences
It is obvious
a2rxx (0) + b2ryy (0) + 2abrxy (l) ≥ 0
Assuming b = 0
rxx (0) a
b
2
+ 2rxy (l) a
b + ryy (0) ≥ 0
Since this quadratic is nonnegative, its discriminant is nonpositive
4[r2
xy (l) − rxx (0)ryy (0)] ≤ 0
|rxy (l)| ≤ rxx (0)ryy (0) = Ex Ey
When y(n) = x(n)
|rxx (l)| ≤ rxx (0) = Ex
This means max value of autocorrelation of a signal is at zero lag
By scaling signals, shape of crosscorrelation sequence does not change
Only amplitudes of crosscorrelation sequence are scaled accordingly
Since scaling is unimportant, auto and crosscorrelation sequences are
normalized to range from -1 to 1, in practice
ρxx (l) =
rxx (l)
rxx (0)
and ρxy (l) =
rxy (l)
rxx (0)ryy (0)
33 / 41
Properties of Autocorrelation & Crosscorrelation Sequences
As shown before
rxy (l) = ryx (−l)
With y(n) = x(n)
rxx (l) = rxx (−l)
Hence autocorrelation is an even function
It suffices to compute rxx (l) for l ≥ 0
34 / 41
Properties of Autocorrelation & Crosscorrelation Sequences
Example
Compute autocorrelation of x(n) = anu(n), 0 < a < 1
If l ≥ 0
rxx (l) =
∞
n=l
x(n)x(n − l) =
∞
n=l
an
an−l
= a−l
∞
n=l
(a2
)n
=
1
1 − a2
al
If l < 0
rxx (l) =
∞
n=0
x(n)x(n − l) = a−l
∞
n=0
(a2
)n
=
1
1 − a2
a−l
rxx (l) =
1
1 − a2
a|l|
, −∞ < l < ∞
rxx (0) =
1
1 − a2
normalized
−−−−−−−−−−−→
autocorrelation
ρxx (l) =
rxx (l)
rxx (0)
= a|l|
, −∞ < l < ∞
35 / 41
Properties of Autocorrelation & Crosscorrelation Sequences
Figure 7: Computation of the autocorrelation of the signal x(n) = an
, 0 < a < 1.
36 / 41
Correlation of Periodic Sequences
If x(n) and y(n) are power signals
rxy (l) = lim
M→∞
1
2M + 1
M
n=−M
x(n)y(n − l)
rxx (l) = lim
M→∞
1
2M + 1
M
n=−M
x(n)x(n − l)
If x(n) and y(n) are two periodic sequences, each with period N
rxy (l) =
1
N
N−1
n=0
x(n)y(n − l)
rxx (l) =
1
N
N−1
n=0
x(n)x(n − l)
37 / 41
Correlation of Periodic Sequences
Correlation can be used to identify periodicities in an observed physical
signal which may be corrupted by random interference
y(n) = x(n) + ω(n)
x(n) is a periodic sequence of unknown period N
ω(n) is an additive random interference
Suppose we observe M samples of y(n)
0 ≤ n ≤ M − 1, M >> N, y(n) = 0 for n < 0 and n ≥ M
ryy (l) =
1
M
M−1
n=0
y(n)y(n − l) =
1
M
M−1
n=0
[x(n) + ω(n)][x(n − l) + ω(n − l)]
=
1
M
M−1
n=0
x(n)x(n − l) +
1
M
M−1
n=0
[x(n)ω(n − l) + ω(n)x(n − l)]
+
1
M
M−1
n=0
ω(n)ω(n − l) = rxx (l) + rxω(l) + rωx (l) + rωω(l)
38 / 41
Correlation of Periodic Sequences
rxx (l) will contain large peaks at l = 0, N, 2N, and so on
rxω(l) and rωx (l) will be small since x(n) and ω(n) are unrelated
rωω(l) will contain a peak at l = 0, but because of its random
characteristics will decay rapidly toward zero
Consequently, only rxx (l) will have large peaks for l > 0, so we can
detect presence of periodic signal x(n) and identify its period
39 / 41
Input-Output Correlation Sequences
x(n) with known rxx (l) is applied to an LTI system with h(n) producing
y(n) = h(n) ∗ x(n) = ∞
k=−∞ h(k)x(n − k)
Crosscorrelation between output and input signal
ryx (l) = y(l) ∗ x(−l) = h(l) ∗ [x(l) ∗ x(−l)]
= h(l) ∗ rxx (l)
Replacing l by −l
rxy (l) = h(−l) ∗ rxx (l)
Autocorrelation of output signal
ryy (l) = y(l) ∗ y(−l) = [h(l) ∗ x(l)] ∗ [h(−l) ∗ x(−l)] =
[h(l) ∗ h(−l)] ∗ [x(l) ∗ x(−l)] = rhh(l) ∗ rxx (l)
rhh(l) exists if system is stable. Stability insures that system does not
change type (energy or power) of input signal
l = 0 provides energy (or power) of output in terms of autocorrelations
ryy (0) =
∞
k=−∞ rhh(k)rxx (k)
40 / 41
References
John G. Proakis, Dimitris G. Manolakis, Digital Signal
Processing: Principles, Algorithms, and Applications, Prentice
Hall, 2006.
41 / 41