Discrete-Time Signals and Systems
Convolution and Correlation
1
Discrete-Time Linear Time Invariant System
x(n) discrete-time y(n)
LTI system
{time-varying} {time-varying}
input signal output signal
2
Classification of Signals
Continuous-time vs. discrete-time
Periodic vs. aperiodic
Deterministic vs. random
Energy vs. power
3
Continuous-Time vs. Discrete-Time
A continuous -time signal x(t) is defined for all values of time, t
x(t) need not be a continuous function of time, e.g. unit step
A discrete-time signal x(n) = x(nT) is defined only at discrete values of time
t=nT.
u(t)
1
the unit step function u(t) is an
example of a continuous-time
0
-2 -1 0 1 2 3 t signal containing a discontinuity
4
Converting from Continuous to Discrete Time
A discrete-time signal may be formed by sampling a continuous-time signal
x(nT)
x(t) x(t)
T
0
kT (k+1)T (k+2)T t
x(t) nT x(n)
sampler quantiser
5
Periodic vs. Aperiodic Signals
A continuous -time signal x(t) is periodic if and only if
x(t ) x(t T ) for all t.
The smallest positive value of T for which this is the case is the period of the signal
A discrete-time signal x(n) is periodic if and only if
x ( n) x ( n N ) for all n.
Any signal that is not periodic is aperiodic.
6
Deterministic vs. Random Signals
Deterministic signals are described as algebraic functions of time.
Random (stochastic) signals are described in terms of their statistical properties.
7
Power vs. Energy Signals
The energy in signal x(t) If x(t) is the current (measured in amps) flowing
T
in a resistor of value 1 ohm then E is the total
E Lim (t )dt
2
x
T
T energy (measured in joules) dissipated in that
resistor (over all time) and P is the average
The average power in signal x(t)
T
power (measured in watts).
1
P Lim (t )dt
2
x
T 2T
T
If average power P is finite and non-zero then E will be infinite and x(t) is described
as a power signal.
If E is finite then x(t) is described as an energy signal.
8
Impulse (Delta or Dirac) Function
For continuous-time systems
(t ) 0, t 0
(t )dt 1
For discrete-time systems
1, n 0
d ( n)
0, n 0
d ( n) 1
9
Unit Step Function
For continuous-time systems
1, t 0
u (t )
0, t 0
u ( ) (t )dt
For discrete-time systems
1, n 0
u ( n)
0, n 0
k
u ( k ) d ( n)
10
Sinusoid Function
For continuous-time systems
x(t ) sin( t )
For discrete-time systems
x(n) sin( n T )
Sinusoidal signals pass through (any) linear time-invariant system with no change
to their shape.
11
Complex Exponential Function
For continuous-time systems Im
Asin(ωt)
x(t ) Ae j t rotating vector ωt
Acos(ωt) Re
For discrete-time systems
x(n) Ae jn T
Rotating vector (phasor) in complex plane.
Closely related to sinusoidal signals.
Projections onto real and imaginary axes of complex plane are cosine and sine respectively.
12
Euler’s Formula
1 j t j t
cos( t ) (e e )
2
1 j t j t
sin( t ) (e e )
2j
j t
e cos( t ) j sin( t )
13
Sampling and Reconstruction
Can we recreate from discrete-time samples the continuous-time
signal from which they were taken?
14
Digital to Analogue Conversion Using a Zero-Order Hold
A zero-order hold (ZOH) has the following impulse response
1 T is the sampling period
y ( n) y ( nT )
0 T t
y(nT) h(t) y(t) = y(nT) * h(t)
t t t
T
digital to analogue conversion using a zero-order hold
15
Impulse Response and Linear Systems
A linear time invariant system is characterised by its impulse response h(t) or h(n).
Its output y(t) is formed by convolution of input signal x(t) and system impulse
Response h(t).
y (t ) x( )h(t )d y ( n) x ( k ) h( n k )
k
16
Discrete Time Convolution
An arbitrary input signal y(n) may be decomposed into a sum of (delayed)
weighted impulses.
Corresponding output is formed by summing (delayed) weighted impulse responses.
d(n) h(n)
d(n) LTI y(n)
system
-1 0 1 2 3 n -1 0 1 2 3 n
Delta sequence Impulse response
17
Convolution
Consider convolution from the point of view of the input signal
x(n) x(0)d (n) x(1)d (n 1) x(2)d (n 2)
Each weighted impulse at the system input results in a weighted impulse response
at the system output.
Each input sample contributes to a number of output sample values.
18
output signal y(n) comprises
Convolution response to x(0) sum of responses
0 1 2 3 4 5 n
x(n) response to x(1)
x(n) LTI y(n)
system 0 1 2 3 4 5 n
0 1 2 3 4 n
h(n) response to x(2)
arbitrary input
signal (sequence)
-1 0 1 2 3 n 0 1 2 3 4 5 n
impulse response response to x(3)
0 1 2 3 4 5 n
19
Convolution
A more practical and useful approach is to consider convolution from the point of
view of the output signal
y (n) h(0) x(n) h(1) x(n 1) h(2)d (n 2)
Each output sample value can be computed based on a number of input
sample values
If impulse response is finite h(n) 0, 0n N
N
y ( n) x ( k ) h( n k )
k 0
20
Convolution
Convolution is a fundamental and important building block in digital signal
processing.
Its implementation is a sum of products.
Single cycle MAC and Harvard architecture are suited to its efficient computation.
21
Properties of Convolution
Convolution involving the delta sequence is particularly straightforward
x ( n) * d ( n) x ( n)
x ( n) * d ( n s ) x ( n s )
x( n) * Kd (n) Kx(n)
Commutative property
a ( n) * b( n) b( n) * a ( n )
Associative property
( a ( n) * b( n)) * c( n) a ( n) * (b(n) * c(n))
Distributive property
( a ( n) * b( n) a ( n) * c( n) a ( n) * (b(n) c( n))
22
Correlation
Correlation is concerned with determining the degree of similarity between
two signals
Computationally it bears a resemblance to convolution
Rxy ( p) x ( m) y ( m p )
m
p
23
Correlation
Sum of products
At the heart of the discrete Fourier transform (DFT)
Rxy ( p) x ( m) y ( m p )
m
p
24
Correlation vs. Convolution
The similarities between the computations involved in convolution and correlation
are coincidental.
Convolution describes the relationships between input signal, output signal and
impulse response in a LTI system.
Correlation is a method of determining the degree of similarity between two
signals.
25
