CHAPTER 2

DISCRETE CONVOLUTION
Faculty of Electrical and Electronic
Engineering

All right reserved. Copyright © 2018. Sharifah Saon 1

 What is convolution?
 When you pass a signal through a system, you
can characterise it in frequency domain or
time domain, the process you get is called
convolution.
h(t)
x[t] H(f) y(t) = x(t) * h(t)

All right reserved. Copyright © 2018. Sharifah Saon 2

 Introduction
 Convolution is a central concept in relating the time
and frequency domains
 Discrete-time convolution is a method of finding the
zero-state response of relaxed linear time-invariant (LTI)
systems.
– Linearity & time invariance
 System information is known  the system impulse
response, ℎ[𝑛].
 If the input is 𝛿[𝑛], a unit sample at the origin
𝑛 = 0, the system response is ℎ[𝑛].

All right reserved. Copyright © 2018. Sharifah Saon 3

 initial

System
Input (impulse output
response)

 ‘Zero-state response’
Initial value zero, so depends fully on input value
only.
 ‘Zero-input response’
Input zero, only depends on the initial value/state.
4
All right reserved. Copyright © 2018. Sharifah Saon 4
 if the input is 𝑥[0]𝛿[𝑛], a scaled impulse at the origin,
the response is 𝑥[0]ℎ[𝑛]  linearity
 if the input is the shifted impulse 𝑥[1]𝛿[𝑛 − 1] at 𝑛 = 1,
the response is 𝑥[1]ℎ[𝑛 − 1]  time invariant
 The response to the shifted impulse 𝑥[𝑘]𝛿[𝑛 − 𝑘] at
𝑛 = 𝑘 is 𝑥[𝑘]ℎ[𝑛 − 𝑘]
 Since input 𝑥[𝑛] is a sequence of samples, it can be
described by a sum of scaled & shifted impulses:

xn    xk  n  k 
k  

All right reserved. Copyright © 2018. Sharifah Saon 5

 By superposition, the response to 𝑥[𝑛] is the sum of
scaled and shifted versions of the impulse response

yn    xk hn  k   xn hn
k  

 It is called linear convolution.

 The expression for computing 𝑦[𝑛] is called the
convolution sum.

All right reserved. Copyright © 2018. Sharifah Saon 6

 The arguments of 𝑥 & ℎ can be interchanged
without affecting the result
 Thus: 
yn    xn  k hk   hn xn
k  

All right reserved. Copyright © 2018. Sharifah Saon 7

 Analytical Evaluation
of Discrete Convolution
 The procedure for analytical convolution can be
implemented if 𝑥[𝑛] and ℎ[𝑛] are described by simple
analytical expressions.
 Resort to a table of closed-form solutions for finite or
infinite series.
 𝑥[𝑘] and ℎ[𝑛 − 𝑘] are functions of the summation
variable 𝑘.
 The summations frequently involve step functions of the
form 𝑢[𝑘] and 𝑢[𝑛 − 𝑘]
 Since 𝑢[𝑘] = 0, 𝑘 < 0 & 𝑢[𝑛 − 𝑘] = 0, 𝑘 > 𝑛, these can
be used as lower & upper limits (𝑘 = 0 & 𝑘 = 𝑛).

All right reserved. Copyright © 2018. Sharifah Saon 8

 Example 2.1 a
(i) Let 𝑥[𝑛] = ℎ[𝑛] = 𝑢[𝑛].
Then 𝑥[𝑘] = 𝑢[𝑘] & ℎ[𝑛 − 𝑘] = 𝑢[𝑛 – 𝑘].
Calculate the output.

All right reserved. Copyright © 2018. Sharifah Saon 9

 Solution
 The lower limit on the convolution sum simplifies
to 𝑘 = 0 (taken from 𝑢[𝑘])
 The upper limit to 𝑘 = 𝑛 (taken from 𝑢[𝑛 – 𝑘])
 and 𝑦 𝑛 = 𝑥 𝑛 ∗ ℎ 𝑛

  uk un  k 
k  

n
 1  n  1 un
k 0

All right reserved. Copyright © 2018. Sharifah Saon 10

 NOTE:

n  1u n  r n  1

un* un  rn  1

All right reserved. Copyright © 2018. Sharifah Saon 11

 Example 2.1 b
(ii) Let, 𝑥 𝑛 = ℎ 𝑛 = 𝑎𝑛 𝑢 𝑛 , 𝑎 < 1.
Thus
𝑥 𝑘 = 𝑎𝑘 𝑢 𝑘 , ℎ 𝑛 − 𝑘 = 𝑎𝑛−𝑘 𝑢 𝑛 − 𝑘 ,
the lower limit 𝑘 = 0 and the upper limit
𝑘 = 𝑛 . Calculate the output 𝑦 𝑛 .

All right reserved. Copyright © 2018. Sharifah Saon 12

 Solution

y  n   a a k nk
u k  u n  k 
k 
n n
 
k 0
a k a nk  a n  a k a k
k 0
n
 an1
k 0

  n  1 a n u  n

All right reserved. Copyright © 2018. Sharifah Saon 13

 Example 2.1 c
(iii) Let 𝑥 [𝑛] = 𝑢[𝑛] and ℎ 𝑛 = 𝑛𝑢 𝑛 ,  < 1
then calculate 𝑦 [𝑛].
Refer to e-book: Digital Signal Processing: An Introduction

All right reserved. Copyright © 2018. Sharifah Saon 14

 Solution
𝑦 𝑛 = 𝛼 𝑛𝑢 𝑛 ∗ 𝑢 𝑛
∞ 𝑘
=σ−∞ 𝛼 𝑢 𝑘 𝑢[𝑛 − 𝑘]
𝑛 𝑘
σ
= 𝑘=0 𝛼

By referring to Finite Summation Formula

1 − 𝛼 𝑛+1
y[n] =
1−𝛼

All right reserved. Copyright © 2018. Sharifah Saon 15

 Example 2.1 d
Let 𝑥 𝑛 = 0.8𝑛 𝑢 𝑛 − 1 & ℎ 𝑛 = 0.4𝑛 𝑢 𝑛 .
Find their convolution.

Answer:
(2(0.8)^n-2(0.4)^n) u[n-1]

16
All right reserved. Copyright © 2018. Sharifah Saon 16
 Convolution Properties
 Many of discrete convolution properties are based on
LTI.
 If 𝑥[𝑛] or h[n] is shifted by 𝑛𝑜, so is 𝑦[𝑛].
 Thus, if 𝑦[𝑛] = 𝑥[𝑛] ∗ ℎ[𝑛], then

𝑥[𝑛 − 𝑛𝑜] ∗ ℎ[𝑛] = 𝑥[𝑛] ∗ ℎ[𝑛 − 𝑛𝑜] = 𝑦[𝑛 − 𝑛𝑜]

 The sum of the samples in 𝑥[𝑛], ℎ[𝑛], & 𝑦[𝑛] are related
by  
 
 
 y  n    x  n    h n 
n   n    n  

All right reserved. Copyright © 2018. Sharifah Saon 17

 For causal systems (ℎ[𝑛] = 0, 𝑛 < 0) & causal signals (𝑥[𝑛] = 0,
𝑛 < 0), 𝑦[𝑛] is also causal. Thus,
n n
yn   xn  hn   hn  xn    xk hn  k    hk  xn  k 
k 0 k 0

 Convolution of two left-sided signals is also left-sided. (Same for

two right-sided signals).
 Some other properties:
 𝛿[𝑛] ∗ 𝑥[𝑛] = 𝑥[𝑛]
 𝛿[𝑛] ∗ 𝛿[𝑛] = 𝛿[𝑛]
 Since step response is the running sum of impulse response, the
convolution of x[n] with a unit step is the running sum of 𝑥[𝑛]:

xn un   xk 
k  

All right reserved. Copyright © 2018. Sharifah Saon 18

 Convolution of Finite Sequence
In practice, normally deal with sequences of finite
length, and their convolution may be found by
several methods.
Convolution
Aperiodic Periodic
• Sum by column • Cyclic
• Sliding strip • Wrap around
• Polynomial (multiplication
concept & zero insert
concept)
19
All right reserved. Copyright © 2018. Sharifah Saon 19
 Convolution of Finite Sequence
 The convolution 𝑦[𝑛] of two finite-length sequences
𝑥[𝑛] and ℎ[𝑛] is also of finite length and is subject to
the following rules;
– The starting index of 𝑦[𝑛] equals the sum of the starting
indices of 𝑥[𝑛] and ℎ[𝑛].
– The ending index of 𝑦[𝑛] equals the sum of the ending
indices of 𝑥[𝑛] and ℎ[𝑛].
– 𝐿𝑦 = 𝐿𝑥 + 𝐿ℎ − 1

All right reserved. Copyright © 2018. Sharifah Saon 20

 The Sum-by-Column Method
 The convolution y[n] equals the sum of the
(shifted) impulse responses due to each of the
impulses that make up the input x[n].Discrete
convolution using the Sum-by-Column method
i. The starting index of y[n] equals the sum of
the starting indices of x[n] and h[n].
ii. The ending index of y[n] equals the sum of
the ending indices of x[n] and h[n].
iii. Ly = Lx + Lh - 1

21
All right reserved. Copyright © 2018. Sharifah Saon 21
 The Sum-by-Column Method

iv. Line up the sequence x[n] below the sequence

h[n].
v. Line up with each sample of x[n], the product
of the entire array h[n] with that sample of
x[n].
vi. Sum the columns of the (successively shifted)
arrays to generate the convolution sequence

22
All right reserved. Copyright © 2018. Sharifah Saon 22
 Example 2.2
An FIR (finite impulse response) filter has an

impulse response given by h  n   {1, 2, 2,3}.


Find its response 𝑦[𝑛] to the input xn  {2,  1, 3}.

Assume that both 𝑥[𝑛] and ℎ[𝑛] start at 𝑛 = 0

All right reserved. Copyright © 2018. Sharifah Saon 24

 Solution
i. Starting index = 0 + 0 = 0
ii. Ending index = 2 + 3 = 5
iii. 𝐿𝑦 = 𝐿𝑥 + 𝐿ℎ − 1
=3+4 −1
= 6.
Then draw the table to fill in the response of
each impulse.

25
All right reserved. Copyright © 2018. Sharifah Saon 25
Iv

vi

26
All right reserved. Copyright © 2018. Sharifah Saon 26
Solution:

27
All right reserved. Copyright © 2018. Sharifah Saon 27
Graphical Illustration

All right reserved. Copyright © 2018. Sharifah Saon 30

 Exercise 2.2
Using sum-by-column method, solve the following problem:
a) An finite impulse response (FIR) filter has an impulse
response given by
2n  1  1  n  1

hn   1 n2
0
 elsewhere
If the input 𝑥 𝑛 is 2𝛿 𝑛 + 2 − 𝛿 𝑛 + 3𝛿 𝑛 − 2 calculate
its output, 𝑦 𝑛 .

All right reserved. Copyright © 2018. Sharifah Saon 31

b) Calculate the response of the signal below:
x[n]  3 n 1  2 n  n  2

h[n]  2 u [n  1]  r [n  1]  u [n]  2 r [n  1]  3u [n  1]  r [n  3]

All right reserved. Copyright © 2018. Sharifah Saon 32

 The Fold, Shift,
Multiply and Sum Concept
 The convolution sum may also be interpreted as follows

 This technique is called the sliding strip method

All right reserved. Copyright © 2018. Sharifah Saon 33

 Example 2.3
Find the discrete convolution of
 
x  n   {2,5, 0, 4}and h  n   {4,1,3}
by using the sliding strip method.

All right reserved. Copyright © 2018. Sharifah Saon 34

 Solution
 Both sequences start at 𝑛 = 0

 Folded sequence is h n  {3, 1, 4}

All right reserved. Copyright © 2018. Sharifah Saon 35

The discrete convolution is

All right reserved. Copyright © 2018. Sharifah Saon 36

 Exercise 2.3
a) Based on a system shown in Figure E2.1

Using sliding strip method, calculate the output signal of the

system. The input and impulse response given by;
x(n)  u(n  3)  r (n  1)  r (n  3)  3u(n  3)
h1 (n)  r (n  1)  r (n)  u (n  1) and h2 (n)  u(n  3)  u(n  2)

All right reserved. Copyright © 2018. Sharifah Saon 37

b) An FIR filter has the following discrete input
signal, 𝑥 𝑛 and the impulse response, ℎ 𝑛
 n  3
xn  3 tri     n  1  r n  1  r n  1  2 u n  2
 3 
 n  1 n
hn  rect    rect  
 4  2

Calculate the system response.

All right reserved. Copyright © 2018. Sharifah Saon 38

 The Polynomials
Multiplication Concept
The discrete convolution of two finite-length
sequences 𝑥[𝑛] and ℎ[𝑛] is entirely equivalent
to multiplication of two polynomials whose
coefficients are described by the arrays 𝑥[𝑛] and
ℎ𝑛.

All right reserved. Copyright © 2018. Sharifah Saon 39

 Example 2.4

Find the discrete convolution of hn  {2, 5, 0, 4}

and x  n   {4,1,3} by using the polynomials
multiplication method.

All right reserved. Copyright © 2018. Sharifah Saon 40

Solution

All right reserved. Copyright © 2018. Sharifah Saon 41

 The polynomial
Zero Insertion Concept
 If zeroes are inserted between adjacent
samples of each signal to be convolved,
their convolution corresponds to the
original convolution sequence with zeros
inserted between its adjacent samples

42
All right reserved. Copyright © 2018. Sharifah Saon 42
 Example 2.6

Find the discrete convolution of

and

by using the zero insertion method

43
All right reserved. Copyright © 2018. Sharifah Saon 43
Solution

44
All right reserved. Copyright © 2018. Sharifah Saon 44
 Periodic Convolution
 The regular convolution of two signals, both of which
are periodic, does not exist.
 For this reason, periodic convolution is measured by
using averages.
 If both 𝑥𝑝[𝑛] and ℎ𝑝[𝑛] are periodic with identical
period 𝑁, their periodic convolution generates a
convolution result 𝑦𝑝[𝑛] that is also periodic with the
same period 𝑁.
 The periodic convolution or circular convolution
𝑦𝑝[𝑛] of 𝑥𝑝[𝑛] and ℎ𝑝[𝑛] is denoted by;

yp[n] = xp[n]hp[n]

All right reserved. Copyright © 2018. Sharifah Saon 45

• Over one period (𝑛 = 0,1, … , 𝑁 − 1), it is defined by:
y p n  x p n hp n  hp n x p n
N 1 N 1
y p n    x p k h p n  k    h p k  x p n  k 
k 0 k 0

• An averaging factor of 1/𝑁 is sometimes included

with the summation.
• Periodic convolution can be implemented using
wraparound.

All right reserved. Copyright © 2018. Sharifah Saon 46

 Periodic convolution of periodic DT signals
with identical period 𝑁
– Find the linear convolution of one-period
segments of each (this will contain 2𝑁 − 1
samples)
– Append a zero. Wrap around the last 𝑁 samples
and add to the first N samples

All right reserved. Copyright © 2018. Sharifah Saon 47

 Example 2.5
Find the periodic convolution of
 
𝑥𝑝[𝑛] = { 1 , 0, 1, 1} and ℎ𝑝[𝑛] = {1 , 2, 3, 1}

with the period of 𝑁 = 4.

All right reserved. Copyright © 2018. Sharifah Saon 48

 Solution
 Starting index, n=0, ending index=6

Answer same as Sum-by

column method

49
All right reserved. Copyright © 2018. Sharifah Saon 49
 Append a zero, wrapped around the last four
samples and add

50
All right reserved. Copyright © 2018. Sharifah Saon 50
 Exercise 2.5

Find the periodic convolution of x p n  {1, 2, 3}

and h p n  {1, 0, 2} , with period N  3

Answer: Yp n  {5, 8, 5}

All right reserved. Copyright © 2018. Sharifah Saon 53

 Periodic Convolution
by the Cyclic Method
 To find the periodic convolution, we shift the folded
signal 𝑥𝑝[−𝑛] past ℎ𝑝[𝑛], one index at a time, & find the
convolution at each index as the sum of the pointwise
product of their samples but only over a one-period
window (0, 𝑁 − 1).
 Values of 𝑥𝑝[−𝑛] and ℎ𝑝[𝑛] outside the range (0, 𝑁 − 1)
are generated by periodic extension.
 One way to visualize the process is to line up 𝑥[𝑘]
clockwise around a circle & ℎ[𝑘] counterclockwise
(folded).

All right reserved. Copyright © 2018. Sharifah Saon 54

 Example 2.7

 Find the periodic convolution of x p n  {1, 2, 3}

and h p n  {1, 0, 2} with the period of 𝑁 = 3
using the cyclic method

All right reserved. Copyright © 2018. Sharifah Saon 55

 Solution
Rotate outer Rotate outer
sequence sequence
(folded h) (folded h)
clockwise clockwise


yn   {5, 8, 5}

All right reserved. Copyright © 2018. Sharifah Saon 56

 Exercise 2.6
The digital Low Pass Filter (LPF) has an input signal of 𝑥 𝑡 with
time interval of 1s as shown in Figure E2.2, and ℎ 𝑛 = 𝑢 𝑛 for
0 < 𝑛 < 4.
Assume that the initial stage of this system is in a rest condition.
Calculate the periodic output signal of this system using cyclic
method approach.
𝑥 𝑡
1

time

1 2 3 4 5 6

Figure E2.2

All right reserved. Copyright © 2018. Sharifah Saon 57

 Discrete Correlation
 Correlation is a measure of similarity between two
signals and is found using a process similar to
convolution.
 Correlation is the convolution of one signal with a folded
version of the other.
 The discrete cross-correlation (denoted) of x[n] and
h[n] is defined by:
 
rxh n   xn  hn    xk hk  n   xk  nhk 
k   k  
 
rhx n   hn  xn    hk  xk  n   hk  n xk 
k   k  

All right reserved. Copyright © 2018. Sharifah Saon 58

 To find 𝑟𝑥ℎ[𝑛], the last element of ℎ[𝑛] is lined up with
the first element of 𝑥[𝑛] & start shifting ℎ[𝑛] past 𝑥[𝑛].
 The pointwise product of the overlapping values are
summed up to generate the correlation.
 This is equivalent to performing the convolution of
𝑥[𝑛] & the folded signal ℎ[−𝑛].
 The starting index of the correlation equals the sum of
the starting indices of 𝑥[𝑛] and ℎ[−𝑛].
 Similarly, 𝑟ℎ𝑥 [𝑛] equals the convolution of 𝑥[−𝑛] &
ℎ[𝑛], & its starting index equals the sum of the starting
indices of 𝑥[−𝑛] & ℎ[𝑛].

All right reserved. Copyright © 2018. Sharifah Saon 59

 However, 𝑟𝑥ℎ[𝑛] does not equal to 𝑟ℎ𝑥 [𝑛].
 The two are folded versions of each other & related by
𝑟𝑥ℎ[𝑛] = 𝑟ℎ𝑥[−𝑛].
 Some equations need to be remembered:
rxh n  xn hn  xn h n

rhx n  hn xn  hn x n

 Correlation length : 𝑁𝑥 + 𝑁ℎ − 1
 Correlation sum :  rn   xn hn

All right reserved. Copyright © 2018. Sharifah Saon 60

 Autocorrelation
 The correlation 𝑟𝑥𝑥[𝑛] of a signal 𝑥[𝑛] with itself is
called the autocorrelation.
 It is an even symmetric function
(𝑟𝑥𝑥[𝑛] = 𝑟𝑥𝑥[−𝑛]) with a maximum at 𝑛 = 0 and
satisfies the inequality.
 Correlation is an effective method of detecting
signals buried in noise.
 Noise is essentially uncorrelated with the signal

All right reserved. Copyright © 2018. Sharifah Saon 61

 It means that if we correlate a noisy signal with
itself, the correlation will be due only to the signal (if
present) and will exhibit a sharp peak at 𝑛 = 0.
 The autocorrelation is always even symmetric with a
maximum at the origin.
 Some equations need to be remembered:
rxx n  xn xn  xn x n
rxx n  rxx  n
rxx n  rxx 0

All right reserved. Copyright © 2018. Sharifah Saon 62

 Example 2.8
Given x[n] = anu[n], |a| < 1. Find rxx[n] for n ≥ 0

63
All right reserved. Copyright © 2018. Sharifah Saon 63
 Solution
• Since x[k - n] = ak-nu[k - n] starts at k = n, then
   
rxx n   xk xk  n   a
1
k
a k n
 a m n
a am n
a 2m
 an
k   k n m 0 m 0 1 a2

• Since autocorrelation is an even symmetric function,

we have
n
rxx n 
a
1 a2

64
All right reserved. Copyright © 2018. Sharifah Saon 64
 Example 2.9
Calculate the correlation of 𝑥 𝑛 and ℎ 𝑛 , where

xn  {2, 5, 0,4} and hn  {3, 1,4}


All right reserved. Copyright © 2018. Sharifah Saon 65

Exercise 2.7

All right reserved. Copyright © 2018. Sharifah Saon 66