ELC 4351: Digital Signal Processing

Liang Dong

Electrical and Computer Engineering

Baylor University
liang [email protected]

January 24, 2017

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 1 / 44
Discrete-time Signals and Systems

1 Discrete-time Signals

2 Discrete-time Systems

3 Analysis of Discrete-time Linear Time-Invariant Systems

4 Implementation of Discrete-time Systems

5 Correlation of Discrete-time Signals

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 2 / 44
Elementary Discrete-time Signals

1 Unit sample sequence


1, n = 0
δ(n) =
6 0
0, n =

2 Unit step signal 

1, n ≥ 0
u(n) =
0, n < 0
3 Unit ramp signal 
n, n ≥ 0
ur (n) =
0, n < 0
4 Exponential signal

x(n) = an = (re jθ )n = r n e jθn

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 3 / 44
Classification of Discrete-time Signals

Energy signals vs. power signals

P∞ 2
Energy: E = n=−∞ |x(n)| .

If E is finite, 0 < E < ∞, x(n) is energy signal.

1 PN 1
Power: P = limN→∞ 2N+1 n=−N |x(n)|2 = limN→∞ 2N+1 EN .

E finite ⇒ P = 0.

If P is finite, 0 < P < ∞, x(n) is power signal.

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 4 / 44
Classification of Discrete-time Signals

Periodic signals vs. aperiodic signals

x(n) is periodic with period N > 0 iff

x(n + N) = x(n), ∀n.

The smallest N is the fundamental period.

k
e.g. x(n) = A sin(2πfn), f = N.

1 PN−1
Power: P = N n=0 |x(n)|2 .

Therefore, periodic signals are power signals.

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 5 / 44
Classification of Discrete-time Signals

Symmetric (even) vs. antisymmetric (odd) signals

Even: x(−n) = x(n)

Odd: x(−n) = −x(n)

Any signal can be expressed as a sum of an even signal and an odd signal.

x(n) = xe (n) + xo (n)

Proof.
xe (n) = 12 [x(n) + x(−n)] and xo (n) = 21 [x(n) − x(−n)].

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 6 / 44
Simple Manipulations of Discrete-time Signals

Time-delay: TDk [x(n)] = x(n − k), k > 0.

Folding: FD[x(n)] = x(−n).

Amplitude scaling: y (n) = Ax(n), −∞ < n < ∞.

Sum: y (n) = x1 (n) + x2 (n).

Product: y (n) = x1 (n)x2 (n). (sample-to-sample basis)

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 7 / 44
Discrete-time Systems

Discrete-time System
y (n) = T [x(n)]

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 8 / 44
Input-Output Description of Systems

x(n) →T y (n) y (n) = T [x(n)]

For example, an accumulator:
n
X
y (n) = x(k)
k=−∞
= x(n) + x(n − 1) + x(n − 2) + · · ·
n−1
X
= x(k) + x(n)
k=−∞
= y (n − 1) + x(n)

Initially relaxed at n0 : y (n0 − 1) = 0.

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 9 / 44
Block Diagram Representation of Discrete-time Systems
Adder

Constant Multiplier

Signal Multiplier

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 10 / 44
Block Diagram Representation of Discrete-time Systems

Unit Delay Element

Unit Advance Element

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 11 / 44
Classification of Discrete-time Systems

Static vs. dynamic systems

Static (memoryless):

y (n) = αx(n)
y (n) = n2 x(n) + βx 2 (n)

Dynamic:

y (n) = x(n) + 3x(n − 1)

X∞
y (n) = x(n − k)
k=0

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 12 / 44
Classification of Discrete-time Systems

Time-invariant vs. time-variant systems

Time-invariant:

x(n) →T y (n) implies x(n − k) →T y (n − k).

y (n, k) = T [x(n − k)] = y (n − k)

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 13 / 44
Classification of Discrete-time Systems
Linear vs. nonlinear systems

Linear system iff

T [α1 x1 (n) + α2 x2 (n)] = α1 T [x1 (n)] + α2 T [x2 (n)]

Superposition: Scaling (multiplicative) property + Additive property

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 14 / 44
Classification of Discrete-time Systems

Causal vs. noncausal systems

Causal system iff

y (n) = T [x(n), x(n − 1), x(n − 2), · · · ]

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 15 / 44
Classification of Discrete-time Systems

Stable vs. unstable systems

Bounded input - bounded output (BIBO) stable iff

|x(n)| ≤ Mx < ∞ ⇒ |y (n)| ≤ My < ∞, ∀n.

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 16 / 44
Interconnection of Discrete-time Systems
Cascade:
y (n) = T2 [T1 [x(n)]], Tc = T2 T1
In general, T2 T1 6= T1 T2 .

Parallel:
y (n) = T1 [x(n)] + T2 [x(n)], Tp = T1 + T2

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 17 / 44
Techniques for Analysis of Linear Time-invariant Systems

For LTI systems, a general form of the input-output relationship.

N
X M
X
y (n) = − ak y (n − k) + bk x(n − k)
k=1 k=0

A difference equation

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 18 / 44
Techniques for Analysis of Linear Time-invariant Systems
P
We use x(n) = k ck xk (n), where xk (n) are the elementary signal
components.

Suppose that yk (n) = T [xk (n)], we have

" #
X
y (n) = T [x(n)] = T ck xk (n)
k
X X
= ck T [xk (n)] = ck yk (n)
k k

It is chosen that, e.g.

xk = e jωk n , k = 0, 1, . . . , N − 1.
2πk 2π
where, ωk = N . {ωk } are harmonically related. N is the fundamental
frequency.
Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 19 / 44
Resolution of a Discrete-time Signal into Impulses

We choose

xk (n) = δ(n − k)

x(n)δ(n − k) = x(k)δ(n − k)

Therefore,
∞
X
x(n) = x(k)δ(n − k)
k=−∞
X∞
= x(k)xk (n)
k=−∞

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 20 / 44
Resolution of a Discrete-time Signal into Impulses

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 21 / 44
Response of LTI Systems to Arbitrary Inputs

h(n, k) ≡ T [δ(n − k)]

P∞
We use x(n) = k=−∞ x(k)δ(n − k).
∞
X
y (n) = T [x(n)] = x(k)T [δ(n − k)]
k=−∞
∞
X
= x(k)h(n, k)
k=−∞

Time-invariant: h(n) = T [δ(n)] ⇒ h(n, k) = h(n − k) = T [δ(n − k)]

∞
X
y (n) = x(k)h(n − k)
k=−∞

The convolution sum

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 22 / 44
Properties of Convolution and Interconnection of Systems

The convolution sum

y (n) = x(n) ⊗ h(n)

X∞
= x(k)h(n − k)
k=−∞
X∞
= h(k)x(n − k)
k=−∞
= h(n) ⊗ x(n)

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 23 / 44
Properties of Convolution and Interconnection of Systems

Identity and Shifting Properties

y (n) = x(n) ⊗ δ(n) = x(n)

y (n − k) = x(n) ⊗ δ(n − k) = x(n − k)

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 24 / 44
Properties of Convolution and Interconnection of Systems
Commutative Law

x(n) ⊗ h(n) = h(n) ⊗ x(n)

Associative Law

[x(n) ⊗ h1 (n)] ⊗ h2 (n) = x(n) ⊗ [h1 (n) ⊗ h2 (n)]

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 25 / 44
Properties of Convolution and Interconnection of Systems

Distributive Law

x(n) ⊗ [h1 (n) + h2 (n)] = x(n) ⊗ h1 (n) + x(n) ⊗ h2 (n)

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 26 / 44
Causal Linear Time-Invariant Systems

∞
X
y (n0 ) = h(k)x(n0 − k)
k=−∞
∞
X −1
X
= h(k)x(n0 − k) + h(k)x(n0 − k)
k=0 k=−∞
| {z }
ỹ (n)

The second part ỹ (n) depends on the future (w.r.t. n0 ) inputs

x(n0 + 1), x(n0 + 2), . . . It has to be zero for a causal LTI system.

Therefore, the impulse response of the system must satisfy the condition

h(n) = 0, n < 0

An LTI system is causal iff its impulse response is zero for negative values
of n.
Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 27 / 44
Causal Linear Time-Invariant Systems

h(n) = 0, n < 0

∞
X
y (n) = h(k)x(n − k)
k=0
Xn
= x(k)h(n − k)
k=−∞

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 28 / 44
Stability of Linear Time-Invariant Systems

If x(n) is bounded, |x(n)| ≤ Mx < ∞, ∀n.

If y (n) is bounded, |y (n)| ≤ My < ∞, ∀n.

∞
X
y (n) = h(k)x(n − k)
k=−∞
∞
X
|y (n)| = h(k)x(n − k)
k=−∞
X∞
≤ |h(k)||x(n − k)|
k=−∞
X∞
≤ Mx |h(k)|
k=−∞

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 29 / 44
Stability of Linear Time-Invariant Systems

We observe that, for |y (n)| < ∞, a sufficient condition is

∞
X
|h(k)| < ∞
k=−∞

It turns out this condition is not only sufficient but also necessary to
ensure the stability of the system.

A LTI system is stable iff its impulse response is absolutely summable.

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 30 / 44
Systems with Finite-Duration and Infinite-Duration Impulse
Response
A finite-duration impulse response (FIR) system has an impulse response
that is zero outside of some finite time interval.

h(n) = 0, n < 0 and n ≥ M

M−1
X
y (n) = h(k)x(n − k)
k=0

An infinite-duration impulse response (IIR) system has an infinite-duration

impulse response.
X∞
y (n) = h(k)x(n − k)
k=0

where causality is assumed.

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 31 / 44
Implementation of Discrete-time Systems

For example, a first-order system described by the linear

constant-coefficient difference equation.

y (n) = −a1 y (n − 1) + b0 x(n) + b1 x(n − 1)

(1) Use a nonrecursive system followed by a recursive system:

v (n) = b0 x(n) + b1 x(n − 1)

y (n) = −a1 y (n − 1) + v (n)

(2) Use a recursive system followed by a nonrecursive system:

w (n) = −a1 w (n − 1) + x(n)

y (n) = b0 w (n) + b1 w (n − 1)

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 32 / 44
Implementation of Discrete-time Systems

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 33 / 44
Implementation of Discrete-time Systems

N
X M
X
y (n) = − ak y (n − k) + bk x(n − k)
k=1 k=0

(1) Direct form I structure:

M
X
v (n) = bk x(n − k)
k=0
XN
y (n) = − ak y (n − k) + v (n)
k=1

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 34 / 44
Direct Form I Structure

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 35 / 44
Implementation of Discrete-time Systems

N
X M
X
y (n) = − ak y (n − k) + bk x(n − k)
k=1 k=0

(2) Direct form II structure:

N
X
w (n) = − ak w (n − k) + x(n)
k=1
M
X
y (n) = bk w (n − k)
k=0

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 36 / 44
Direct Form II Structure

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 37 / 44
Correlation of Discrete-time Signals

Crosscorrelation of sequences x(n) and y (n) is a sequence rxy (l) defined as

∞
X
rxy (l) = x(n)y (n − l), l = 0, ±1, ±2, . . .
n=−∞
X∞
= x(n + l)y (n), l = 0, ±1, ±2, . . .
n=−∞

where index l is the time shift or lag.

rxy (l) = ryx (−l)

rxy (l) = x(l) ⊗ y (−l)

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 38 / 44
Correlation of Discrete-time Signals

Autocorrelation of sequence x(n) is a sequence rxx (l) defined as

∞
X
rxx (l) = x(n)x(n − l), l = 0, ±1, ±2, . . .
n=−∞
X∞
= x(n + l)x(n), l = 0, ±1, ±2, . . .
n=−∞

where index l is the time shift or lag.

rxx (l) = rxx (−l)

rxx (l) = x(l) ⊗ x(−l)

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 39 / 44
Properties of Autocorrelation and Crosscorrelation
Sequences

|rxx (l)| ≤ rxx (0) = Ex

q p
|rxy (l)| ≤ rxx (0)ryy (0) = Ex Ey

Normalized autocorrelation sequence:

rxx (l)
ρxx (l) = , |ρxx (l)| ≤ 1
rxx (0)

Normalized crosscorrelation sequence:

rxy (l)
ρxy (l) = p , |ρxy (l)| ≤ 1
rxx (0)ryy (0)

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 40 / 44
Correlation of Periodic Sequences

Crosscorrelation:
N−1
1 X
rxy (l) = x(n)y (n − l)
N
n=0

Autocorrelation:
N−1
1 X
rxx (l) = x(n)x(n − l)
N
n=0

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 41 / 44
Correlation of Periodic Sequences

Example: Correlation is used to identify periodicity in an observed physical

signal that is corrupted by random noise/interference.

y (n) = x(n) + w (n)

We observe M samples of y (n), where M  N.

M−1
1 X
ryy (l) = y (n)y (n − l)
M
n=0
M−1
1 X
= [x(n) + w (n)][x(n − l) + w (n − l)]
M
n=0
= rxx (l) + rxw (l) + rwx (l) + rww (l)

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 42 / 44
Correlation of Periodic Sequences

Example: Identify a hidden periodicity in the Wölfer sunspot numbers in

the 100-year period 1770-1869.

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 43 / 44
Input-Output Correlation Sequences

Crosscorrelation between the output and the input signal is

ryx (l) = y (l) ⊗ x(−l) = h(l) ⊗ [x(l) ⊗ x(−l)]

= h(l) ⊗ rxx (l)

Autocorrelation of the output signal is

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)

The autocorrelation rhh (l) of the impulse response h(n) exists if the
system is stable.

Liang Dong (Baylor University) Discrete-Time Signals and Systems January 24, 2017 44 / 44