Discrete-time signals and systems

1
 DISCRETE-TIME DYNAMICAL SYSTEMS

- -
x(t) G y(t)

Linear system: Output y(n) is a linear function of the inputs sequence:

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

h(k): impulse response of the system: Impulse

x(0) = 1, x(n) = 0, n ̸= 0

gives
y(n) = h(n), all n

2
Some terminology:

• Linear Time Invariant (LTI) System:

Impulse response from input x(n − k) to output y(n) does not depend
on time n, but only on k

• Causal system:
Output y(n) does not depend on future inputs, but only on present and
past inputs x(n), x(n − 1), . . .,

y(n) = h(0)x(n) + h(1)x(n − 1) + · · ·

(i.e., h(k) = 0, k < 0).

3
Any process which transform a signal {x(n)} to another signal {y(n)}
is a discrete-time system (for example, an audio signal is transformed by
reflections, etc).

Often a (linear) discrete-time system is designed in order to process a signal,

for example to remove noise. Then we call such a system a digital filter.

4
DIGITAL FILTER TYPES

• FIR (Finite Impulse Response) filters

- have finite memory; output depends only on a finite number of inputs
- modeled by (weighted) moving average models

y(n) = h(0)x(n) + h(1)x(n − 1) + · · · + h(N − 1)x(n + 1 − N )

• IIR (Infinite Impulse Response) filters

- have infinite memory; output depends on an infinite number of (past)
inputs
- modeled by difference equations

y(n) + a1y(n − 1) + · · · + aN y(n − N ) =

= b0x(n) + b1x(n − 1) + · · · + bM x(n − M )

5
Calculation of filter output

FIR filters:
The operation

y(n) = h(0)x(n)+h(1)x(n−1)+· · ·+h(N −1)x(n+1−N ), n = 0, 1, 2, . . . , M

between the impulse response sequence

{h(k)} = {h(0), h(1), . . . , h(N − 1)} and the input sequence
{x(n)} = {x(0), x(1), . . . , x(M − 1)}
to give the output sequence {y(n)} = {y(0), y(1), . . .} is called convolution,
and is often denoted as

{y(n)} = {h(k)} ∗ {x(n)}

Computational burden: calculation of output sequence requires N M flops

6
Efficient software for DSPs exist

In Matlab: y = conv(h,x)
or
y = filter(h,1,x) (cf. below)

7
IMPORTANT PROPERTY:

Convolution corresponds to polynomial multiplication:

If we define the polynomials

Ŷ (z) = y(0) + y(1)z −1 + · · · + y(M − 1)z −M +1

X̂(z) = x(0) + x(1)z −1 + · · · + x(M − 1)z −M +1
H(z) = h(0) + h(1)z −1 + · · · + h(N − 1)z −N +1

then we see that

( )
−1
H(z)X̂(z) = h(0)x(0) + h(0)x(1) + h(1)x(0) z + · · ·
( )
−n
+ h(0)x(n) + h(1)x(n − 1) + · · · + h(N − 1)x(n + 1 − N ) z + · · ·
−1 −M +1
= y(0) + y(1)z + · · · + y(M − 1)z
= Ŷ (z)

8
⇒ the convolution {y(n)} = {h(k)} ∗ {x(n)} can be represented as
polynomial multiplication

Ŷ (z) = H(z)X̂(z)

X̂(z): z-transform of sequence {x(n)}

Ŷ (z): z-transform of sequence {y(n)}
H(z): transfer function of the system having impulse response
h(0), h(1), . . .

9
Relation between convolution and polynomial multiplication leads to an
efficient implementation of convolution

FFT CONVOLUTION (’high-speed convolution’)

The Fourier transform X(k) of {x(n)} is precisely a polynomial in z −1,

with z = ej2πk/N :

Recall the Fourier transform of {x(n)}:

X(k) = x(0) + x(1)e−j2πk/N + · · · + x(N − 1)e−j2π(N −1)k/N

( )−1 ( )−(N −1)
= x(0) + x(1) e j2πk/N
+ · · · + x(N − 1) ej2πk/N

Comparison with X̂(z) shows that:

X(k) = X̂(zk ), zk = ej2πk/N

Hence X(k) evaluates X̂(z) at N points zk , k = 0, 1, . . . , N − 1

10
Hence we can compute the convolution as follows:

1. Compute FFT X(k) of sequence {x(n)}. Then X(k) = X̂(zk ), zk =

ej2πk/N .

2. Compute FFT H(k) of sequence {h(n)}. Use zero padding to obtain

sequences of the same length. Then H(k) = H(zk ), zk = ej2πk/N .

3. Compute Y (k) as the element-wise product Y (k) = H(k)X(k). Then

Y (k) = Ŷ (zk ), zk = ej2πk/N .

4. Compute inverse Fourier transform {y(n)} of {Y (k)}. Then {y(n)} is

the convolution {y(n)} = {h(k)} ∗ {x(n)}
 TRANSFER FUNCTIONS

- -
x(t) G y(t)

In the z-transform domain, we have the simple relation

Ŷ (z) = H(z)X̂(z)

where
H(z) = h(0) + h(1)z −1 + · · ·

12
 GENERAL LINEAR DISCRETE-TIME DYNAMICAL SYSTEMS

General LTI systems can be described by a difference equation:

y(n) + a1y(n − 1) + · · · + aN y(n − N ) =

= b0x(n) + b1x(n − 1) + · · · + bM x(n − M )

Discrete-time counterpart of differential equations.

Left-hand side is a convolution between the sequence 1, a1, . . . , aN and

{y(n)}, or in the z-transform:
( −1 −N
)
1 + a1 z + · · · + aN z Ŷ (z)

Right-hand side is a convolution between the sequence b0, . . . , bM and

{x(n)}, or in the z-transform:
( −1 −M
)
b0 + b1z + · · · + bM z X̂(z)

13
⇒

( −1 −N
) ( −1 −M
)
1 + a1z + · · · + aN z Ŷ (z) = b0 + b1z + · · · + bM z X̂(z)

or,
b0 + b1z −1 + · · · + bM z −M
Ŷ (z) = −1 −N
X̂(z)
1 + a1 z + · · · + aN z

Hence the system has transfer function

b0 + b1z −1 + · · · + bM z −M
Ŷ (z) = H(z)X̂(z), H(z) =
1 + a1z −1 + · · · + aN z −N

14
 STABILITY
Example: First-order system

y(n) + ay(n − 1) = bu(n)

For the input {u(n)} = {1, 0, 0, 0, . . .} we have:

y(0) = b (assuming y(−1) = 0)

y(1) = −ay(0) + bu(1) = −ab
y(2) = −ay(1) + bu(2) = a2b
..

y(n) = (−a)nb

• y(n) → 0 if as t → ∞ if |a| < 1 – system is stable

• |y(n)| → ∞ as t → ∞ if |a| > 1 – system is unstable

15
Characterization of stability in terms of system transfer function:

b
H(z) =
1 − az −1

A value p for which H(p) becomes infinite is called a pole of H(z).

Here, p is the solution of 1 − ap−1 = 0 ⇒ p = a.
⇒ System is stable if its pole p = a has absolute value |p| < 1
The results generalizes to higher-order systems:
A linear discrete-time dynamical system with transfer function

b0 + b1z −1 + · · · + bM z −M
H(z) =
1 + a1z −1 + · · · + aN z −N

is stable if and only if all its poles, i.e. the solutions pi of the equation

1 + a1z −1 + · · · + aN z −N = 0

satisfy |pi| < 1 (i.e., they are inside the unit circle in the complex plane).

16
 INTERCONNECTED SYSTEMS
Using transfer functions, it is easy to analyze connected systems
Example: Series connection.

y1(n)
x(n) -
H1 -
H2 -
y(n)

Introducing z-transforms X̂(z), Ŷ1(z), Ŷ (z) and transfer functions

H1(z), H2(z) gives:

Ŷ (z) = H2(z)Ŷ1(z)
= H2(z)H1(z)X̂(z) = H(z)X̂(z)

⇒ Series connection has impulse response function {h(k)} with z-transform

H(z) = H2(z)H1(z).
But this is equal to the convolution {h(k)} = {h2(k)} ∗ {h1(k)}.
Hence the impulse response of the series connection is obtained by a
convolution of the individual impulse responses

17
Example: Time shift.

Consider a time shift

y(n) = x(n − l)
Then:
Ŷ (z) = z −lX̂(z)

In other words, if the signal {x(n)} has z-transform X̂(z), then the time-
shifted signal {x(n − l)} has z-transform z −lX̂(z).

z is a so-called shift operator.

18
Example: Feedback connection.

Determine the output {y(n)} as function of the input {x(n)} in the

following feedback connection:

{x(n)} +- i {e(n)}- {y(n)}

-
G
6 −

{r(n)} 
K

where the system G is described by the difference equation

y(n) − 0.8y(n − 1) = e(n)

the K is described by

r(n) − 0.5r(n − 1) = y(n − 1) + 0.1y(n − 2)

19
 SOLUTION OF DIFFERENCE EQUATIONS BY THE Z-TRANSFORM
In analogy with the the Laplace transform for differential equations,
tabulated z-transforms can be applied to solve difference equations as
follows:
Problem: Determine the solution {y(n)} of the difference equation

y(n) + a1y(n − 1) + · · · + aN y(n − N ) =

= b0x(n) + b1x(n − 1) + · · · + bM x(n − M )

for a given input sequence {x(n)}.

Solution:
1. Write the difference equation in the z-transform plane:

b0 + b1z −1 + · · · + bM z −M
Ŷ (z) = −1 −N
X̂(z)
1 + a1z + · · · + aN z

where X̂(z) is the z-transform of the input sequence {x(n)}.

2. Solve for Ŷ (z) and find the corresponding sequence {y(n)} whose
transform Ŷ (z) is.

20
The calculation of X̂(z) in stage 1 and of sequence {y(n)} in stage 2
is facilitated by tabulated z-transforms for several common signals (Table
7.1).

Example: z-transform of a signal

The exponentially decaying signal
{
0, n<0
x(n) =
an, n ≥ 0

has z-transform
∞
∑ ∞
∑
X̂(z) = x(n)z −n = an · z −n
n=0 n=0

= 1 + az −1 + a2z −2 + · · ·
= 1 + az −1 + (az −1)2 + · · ·
1 z
= =
1 − az −1 z − a

Compare with Table 7.1, line 5, with c = 1, e−α = a.

21
Example: Solution of difference equation

Consider the difference equation

y(n) − 0.75y(n − 1) = x(n − 1)

with {
0, n<0
x(n) =
(−0.5)n, n≥0

Then:
z −1
Ŷ (z) = X̂(z)
1 − 0.75z −1
and (cf. above)
1
X̂(z) =
1 + 0.5z −1

22
Hence,
z −1 1
Ŷ (z) = ·
1 − 0.75z −1 1 + 0.5z −1
A partial fraction expansion gives

4/5 4/5
Ŷ (z) = −
1 − 0.75z −1 1 + 0.5z −1

or ( )
4 z z
Ŷ (z) = −
5 z − 0.75 z + 0.5
z
By Table 7.1, z−a is the z-transform of the sequence {an}. Hence Ŷ (z) is
the z-transform of the sequence

4
y(n) = [0.75n − (−0.5)n]
5

which is the solution of the difference equation.

23