Dr Noor Mahammad Sk

Center for High Performance Reconfigurable Computing

Indian Institute of Information Technology Design and Manufacturing
(IIITDM) Kancheepuram, Chennai – 600127.

1 May 2018 Dr Noor Mahammad Sk 1

Outline
Quick Review of DSP and Signals
Advantages and Disadvantages of DSP
Basic DSP operations
Superposition Theorem

1 May 2018 Dr Noor Mahammad Sk 2

Quick Review of DSP
Space Space Photograph Enhancement
Data Compression
Intelligent Sensory Analysis by remote space probes

Diagnostic Imaging (CT , MRI and Ultrasound)

Medical Electrocardiogram analysis
Medical Image storage/retrieval

Image and Sound Compression for Multimedia presentation

Movie Special Effects
Commercial Video Conference Calling

Voice and data compression

DSP Telephone Echo reduction
Signal Multiplexing
Filtering

Radar
Military Sonar
Secure Communication

Oil and Mineral Prospecting

Industrial Process Monitoring and Control
Nondestructive testing, CAD and Design Tools

Earthquake recording & analysis

Scientific Data acquisition
Spectral analysis
Simulation and modeling
1 May 2018 Dr Noor Mahammad Sk 3
Applications of DSP
Speech Processing
Noise filtering
Coding
Compression
Recognition
Synthesis
Sampling rate changes

1 May 2018 Dr Noor Mahammad Sk 4

Applications of DSP
Image Processing: enhancement, coding,
compression, pattern recognition
Multimedia: transmission of sound, still images,
motion pictures, digital TV, video conferencing
Music: recording, playback and manipulation
(mixing, special effects), synthesis

1 May 2018 Dr Noor Mahammad Sk 5

Applications of DSP
Communication: encoding and decoding of digital
communication signals, detection, equalization,
filtering, direction finding, echo cancellation
Radar and Sonar: target detection, position and
velocity estimation, tracking
Biomedical Engineering: analysis of biomedical
signals, diagnosis, patient monitoring, preventive
health care, artificial organs

1 May 2018 Dr Noor Mahammad Sk 6

What is Signal?
A function of independent variables such as time,
distance, position, temperature, pressure, etc.
A signal carries information
Examples: speech, music, seismic, image and video
A signal can be a function of one, two or N
independent variables
Speech is a 1-D signal as a function of time
An image is a 2-D signal as a function of space
Video is a 3-D signal as a function of space and time

1 May 2018 Dr Noor Mahammad Sk 7

 Example
Stock price & volume
EEG
position

time
DTMF

Video

time time

1 May 2018 Dr Noor Mahammad Sk 8

Types of Signals
Analog Signals (Continuous-Time Signals)
 Signals that are continuous in both the dependant and independent
variable (e.g., amplitude and time).
 Most environmental signals are continuous-time signals.
Discrete Sequence (Discrete Time Signal)
 Signals that are continuous in the dependant variable (e.g., amplitude) but
discrete in the independent variable (e.g., time).
 They are typically associated with sampling of continuous-time signals.
Digital Signals
 Signals that are discrete in both the dependant and independent variable
(e.g., amplitude and time) are digital signals.
 These are created by quantizing and sampling continuous-time signals or
as data signals (e.g., stock market price fluctuations).

1 May 2018 Dr Noor Mahammad Sk 9

Types of Signals (cont.)

1 May 2018 Dr Noor Mahammad Sk 10

What is DSP?
Changing or analyzing information that is measured
as discrete sequences of numbers
The representation,
transformation, and
manipulation of signals and
the information they contain

1 May 2018 Dr Noor Mahammad Sk 11

Unique Features of DSP
Signals come from the real world
Need to react in real time
Need to measure signals and convert them to digital
numbers
Signals are discrete
Information in between discrete samples is lost

1 May 2018 Dr Noor Mahammad Sk 12

Processing Real Signals
 Most of the signals in our environment are analog such as
sound, temperature and light
 To processes these signals with a computer, we must:
 Convert the analog signals into electrical signals, e.g., using
a transducer such as a microphone to convert sound into
electrical signal
 Digitize these signals, or convert them from analog to digital,
using an ADC (Analog to Digital Converter)
 In digital form, signal can be manipulated
 Processed signal may need to be converted back to an analog
signal before being passed to an actuator (e.g., a loudspeaker)
 Digital to analog conversion and can be done by a DAC

(Digital to Analog Converter)

1 May 2018 Dr Noor Mahammad Sk 13
Typical DSP System Components
Input lowpass filter (anti-aliasing filter)
Analog to digital converter (ADC)
Digital computer or digital signal processor
Digital to analog converter (DAC)
Output lowpass filter (anti-imaging filter)

1 May 2018 Dr Noor Mahammad Sk 14

DSP System Components
Analog input signal is filtered to be a band-limited
signal by an input low pass filter
Signal is then sampled and quantized by an ADC
Digital signal is processed by a digital circuit, often a
computer or a digital signal processor
Processed digital signal is then converted back to an
analog signal by a DAC
The resulting step waveform is converted to a
smooth signal by a reconstruction filter called an
anti-imaging filter

1 May 2018 Dr Noor Mahammad Sk 15

Advantages of DSP
Versatility:
Digital systems can be reprogrammed for other
applications
Digital systems can be ported to different hardware
Repeatability and stability:
Digital systems can be easily duplicated
Digital systems do not depend on strict component
tolerances
Digital system responses do not drift with
temperature

1 May 2018 Dr Noor Mahammad Sk 16

Advantages of DSP (cont.)
Simplicity:
Some things can be done more easily digitally than
with analog systems (e.g., linear phase filters)
Security can be introduced by encryption/scrambling
Digital signals easily stored on magnetic media
without deterioration

1 May 2018 Dr Noor Mahammad Sk 17

Disadvantages of DSP
DSP techniques are limited to signals with relatively
low bandwidths
The point at which DSP becomes too expensive will
depend on the application and the current state of
conversion and digital processing technology
 Currently DSP systems are used for signals up to video
bandwidths (about 10 MHz)
 The cost of high-speed ADCs and DACs and the amount of
digital circuitry required to implement very high-speed designs
(> 100 MHz) makes them impractical for many applications
 As conversion and digital technology improve, the bandwidths
for which DSP is economical continue to increase

1 May 2018 Dr Noor Mahammad Sk 18

Disadvantages of DSP (cont.)
The need for an ADC and DAC makes DSP not
economical for simple applications (e.g., a simple
filter)
Higher power consumption and size of a DSP
implementation can make it unsuitable for simple
very low-power or small size applications

1 May 2018 Dr Noor Mahammad Sk 19

History of DSP
 Up to 1950’s: signal processing done with analog systems
using electronic circuits or mechanical devices
 1950’s: digital computers used to simulate signal processing
systems before implementing in analog hardware – cheap
way to vary parameters and test system output
 1965: Cooley and Tukey (re)discover efficient algorithm for
Fast Fourier Transforms (FFTs) – made feasible real-time
signal processing as well as algorithms previously thought
impossible to implement on digital computers
 1980’s: IC technology advancements led to very fast fixed-
point and floating-point microprocessors for digital signal
processing

1 May 2018 Dr Noor Mahammad Sk 20

DSP Functions
Common features of DSP applications
They use a lot of multiplying and adding operations
They deal with signals that come from the real world
They require a certain response time
Key DSP operations
Filtering
Correlation
Discrete transformation

1 May 2018 Dr Noor Mahammad Sk 21

Filtering Example
Signals are usually a mix of “useful” information and
noise
How do we extract the useful information?
 Filtering is one way

1 May 2018 Dr Noor Mahammad Sk 22

Filtering Example

1 May 2018 Dr Noor Mahammad Sk 23

Filtering Equations
Let x[n] denote current input value (ECG+noise)
 x[n-1] is previous input value, x[n-k] – k-th previous input
Let y[n] be the current filtered output value
 y[n-1] is previous output value , y[n-k] – k-th previous output
Filtering operations carried out for this example:
y[n] = 2.4*y[n-1] - 2.6*y[n-2] + 1.5 y[n-3] – 0.4*y[n-4]
+ 0.6*x[n] – 1.9*x[n-1] + 2.8*x[n-2]
- 1.9*x[n-3] + 0.6*x[n-4]

x[n] Filtering y[n]

1 May 2018 Dr Noor Mahammad Sk 24

Transform Example

Can you say which is “1” / ”#” by looking at them?

If not, go to “frequency” domain
 Another way to look at signals
 Done using transforms

1 May 2018 Dr Noor Mahammad Sk 25

Transform Example

1 May 2018 Dr Noor Mahammad Sk 26

Transform Equations
Discrete Fourier Transform
x – Time domain signal
X – Frequency domain representation of x

N 1 2
X [k ]   x[n]e
j ( ) kn
N
,0  k  N  1
n 0

1 May 2018 Dr Noor Mahammad Sk 27

Correlation Example
Provides a measure of similarity between 2 signals
Typical application is locating a known signal
 E.g., transmit a signal and see if you receive it back and
also at what time you receive it back

Radar

Blocked pipes!

1 May 2018 Dr Noor Mahammad Sk 28

Correlation Example (cont.)
Using radar, we transmit the signal shown below

1 May 2018 Dr Noor Mahammad Sk 29

Correlation Example
We receive the following (note the noise!)

1 May 2018 Dr Noor Mahammad Sk 30

Correlation Example

1 May 2018 Dr Noor Mahammad Sk 31

Correlation Equations
Correlation
x – Transmitted signal
y – Received signal
 rxy – Correlation coefficients


rxy [l ]   x[n] * y[n  l ], l  0,1,2,
n  

1 May 2018 Dr Noor Mahammad Sk 32

Filters
 Filter removes unwanted parts of the signal,
 such as random noise, or
 to extract useful parts of the signal, such as the components lying within a
certain frequency range

Raw
(Unfiltered) FILTER Filtered
Signal Signal

1 May 2018 Dr Noor Mahammad Sk 33

Speech Signal

Noisy Signal

FILTER

Denoised Signal

1 May 2018 Dr Noor Mahammad Sk 34

Images

1 May 2018 Dr Noor Mahammad Sk 35

Filters
 Filters are used
 Separation of signals that have been combined
 Restoration of signals that have been distorted in some way
 Signal separation is needed when a signal has been
contaminated with interference, noise, or other signals.
For example:
 Imagine a device for measuring the electrical activity of a baby's heart
(EKG) while still in the womb.
 The raw signal will likely be corrupted by the breathing and heartbeat of
the mother.
 A filter might be used to separate these signals so that they can be
individually analyzed.

1 May 2018 Dr Noor Mahammad Sk 36

Filters
 Signal restoration is used when a signal has been distorted in
some way
Example:
 An audio recording made with poor equipment may be filtered to better
represent the sound as it actually occurred.
 Another example is the deblurring of an image acquired with an
improperly focused lens, or a shaky camera.
 Types of filters
 Analog
 Digital filters
 Analog filters are cheap, fast, and have a large dynamic range
in both amplitude and frequency
 Digital filters, in comparison, are vastly superior in the level
of performance that can be achieved
1 May 2018 Dr Noor Mahammad Sk 37
Introduction to Digital Filters
 A typical low-pass digital filter has a gain of 1 +/- 0.0002 from
DC to 1000 Hertz, and a gain of less than 0.0002 for
frequencies above 1001 hertz.
 The entire transition occurs within only 1 hertz.
 Don't expect this from an op amp circuit!
 Digital filters can achieve thousands of times better
performance than analog filters.
 Limitations of analog filters - handling limitations of the
electronics, such as the accuracy and stability of the resistors
and capacitors
 In digital filter - the signal is represented by a sequence of
numbers, rather than a voltage or current.

1 May 2018 Dr Noor Mahammad Sk 38

Digital Signal Processing

1 May 2018 Dr Noor Mahammad Sk 39

Advantages of Digital Filters
A digital filter is programmable,
 Its operation is determined by a program stored in the processor's
memory.
 This means the digital filter can easily be changed without affecting the
circuitry (hardware).
 An analog filter can only be changed by redesigning the filter circuit.
 Digital filters are easily designed, tested and implemented
on a general-purpose computer or workstation.
 Digital filters are extremely stable with respect to time and
temperature (No drift problems)
 The characteristics of analog filter circuits (particularly those containing
active components) are subject to drift and are dependent on
temperature.

1 May 2018 Dr Noor Mahammad Sk 40

Advantages of Digital Filters
 Digital filters can handle low frequency signals accurately
compared to analog
 As the speed of DSP technology continues to increase, digital filters
are being applied to high frequency signals in the RF (radio frequency)
domain, which in the past was the exclusive preserve of analog
technology.
 Digital filters are very much more versatile in their ability to
process signals in a variety of ways;
 This includes the ability of some types of digital filter to adapt to
changes in the characteristics of the signal
 Fast DSP processors can handle complex combinations of
filters in parallel or cascade (series),
 making the hardware requirements relatively simple and compact in
comparison with the equivalent analog circuitry.

1 May 2018 Dr Noor Mahammad Sk 41

Superposition: the Foundation of DSP
When we are dealing with linear systems, the only
way signals can be combined is by scaling
(multiplication of the signals by constants) followed
by addition.
For instance, a signal cannot be multiplied by
another signal
Let consider: three signals: x0[n], x1[n] and x2[n] are
added to form a fourth signal, x[n].
This process of combining signals through scaling
and addition is called synthesis.

1 May 2018 Dr Noor Mahammad Sk 42

 Synthesis and Decomposition of Signals
• In Synthesis, two or more signals are added
to form another signal.
• Decomposition is the opposite process,
breaking one signal into two or more additive
component signals.
+
Synthesis

Decomposition

1 May 2018 Dr Noor Mahammad Sk 43

Decomposition
Decomposition is the inverse operation of synthesis,
where a single signal is broken into two or more
additive components.
This is more involved than synthesis, because there
are infinite possible decompositions for any given
signal.
Example: the numbers 15 and 25 can only be
synthesized (added) into the number 40.
 In comparison, the number 40 can be decomposed into:
1 + 39 or 2 + 38 or -30.5 + 60 + 10.5, etc.

1 May 2018 Dr Noor Mahammad Sk 44

The heart of DSP: superposition
The overall strategy for understanding how signals
and systems can be analyzed
Consider an input signal, called x[n], passing through
a linear system, resulting in an output signal, y[n].
the input signal can be decomposed into a group of
simpler signals: x0[n], x1[n], x2[n], etc.
 We will call these the input signal components
 Next each input signal component is individually passed
through the system, resulting in a set of output signal
components : y0[n], y1[n], y2[n], etc.

1 May 2018 Dr Noor Mahammad Sk 45

The Fundamental Concept of DSP

Decomposition

Synthesis
1 May 2018 Dr Noor Mahammad Sk 46
The Fundamental Concept in DSP
 Any signal, such as x [n], can be decomposed into a group of
additive components, shown here by the signals: x0[n], x1[n]
and x2[n]
 Passing these components through a linear system produces
the signals: y0[n], y1[n] and y2[n]
 The synthesis (addition) of these output signals forms y [n],
the same signal produced when x [n] is passed through the
system
 Important Note: the output signal obtained by this method is
identical to the one produced by directly passing the input
signal through the system.
 This is a very powerful idea

1 May 2018 Dr Noor Mahammad Sk 47

The Fundamental Concept in DSP
Instead of trying to understanding how complicated
signals are changed by a system, all we need to know
is how simple signals are modified.
In the jargon of signal processing, the input and
output signals are viewed as a superposition (sum) of
simpler waveforms.
This is the basis of nearly all signal processing
techniques.

1 May 2018 Dr Noor Mahammad Sk 48

Superposition
As a simple example of how superposition is used
multiply the number 2041 by the number 4, in your
head. How did you do it?
You might have imagined 2041 match sticks floating
in your mind, quadrupled the mental image, and
started counting.
The number 2041 can be decomposed into: 2000 +
40 + 1.
Each of these components can be multiplied by 4
and then synthesized to find the final answer, i.e.,
8000 + 160 + 4 = 8164 .

1 May 2018 Dr Noor Mahammad Sk 49

Common Decompositions
The goal of this method is to replace a complicated
problem with several easy ones.
There are two main ways to decompose signals in
signal processing:
Impulse decomposition and
Fourier decomposition.
Other:
Step Decomposition
Even/Odd Decomposition
Interlaced Decomposition

1 May 2018 Dr Noor Mahammad Sk 50

Impulse Decomposition
 Impulse decomposition breaks an N samples signal into N
component signals, each containing N samples.
 Each of the component signals contains one point from the
original signal, with the remainder of the values being zero.
 A single nonzero point in a string of zeros is called an impulse.
 Impulse decomposition is important because it allows signals
to be examined one sample at a time.
 Similarly, systems are characterized by how they respond to
impulses
 By knowing how a system responds to an impulse, the
system's output can be calculated for any given input.
 This approach is called Convolution

1 May 2018 Dr Noor Mahammad Sk 51

 Example of impulse decomposition
•An N point signal is
broken into N
components, each
consisting of a single
nonzero point.
Impulse Decomposition

1 May 2018 Dr Noor Mahammad Sk 52

Step Decomposition
 breaks an N sample signal into N component signals, each
composed of N samples
 Each component signal is a step, that is, the first samples have
a value of zero, while the last samples are some constant
value.
 Consider the decomposition of an N point signal, x[n], into
the components: x0[n], x1[n], … xN-1[n].
 The kth component signal, xk[n], is composed of zeros for
points 0 through k-1, while the remaining points have a value
of: x[k] - x[k-1].
 For example, the 5th component signal, x5[n] , is composed of
zeros for points 0 through 4, while the remaining samples
have a value of: x[5] - x[4] (the difference between sample 4
and 5 of the original signal)
1 May 2018 Dr Noor Mahammad Sk 53
 Step Decomposition
•An N point signal is
broken into N signals,
each consisting of a
step function
Step Decomposition

1 May 2018 Dr Noor Mahammad Sk 54

Even/Odd Decomposition
 breaks a signal into two component signals, one having even
symmetry and the other having odd symmetry.
 An N point signal is said to have even symmetry if it is a mirror
image around point N/2 .
 That is, sample x[N/2 + 1] must equal x[N/2 - 1], sample
x[N/2 + 2] must equal x[N/2 – 2], etc.
 Similarly, odd symmetry occurs when the matching points
have equal magnitudes but are opposite in sign, such as:
x[N/2 + 1] = -x[N/2 - 1], x[N/2 + 2] = -x[N/2 - 2], etc.
 These definitions assume that the signal is composed of an
even number of samples, and that the indexes run from 0 to
N-1

1 May 2018 Dr Noor Mahammad Sk 55

Circular Symmetry of Even/Odd
 The decomposition is calculated from the relations:
 xE[n] = ( x[n] + x[N - n] )/2

 xO[n] = ( x[n] - x[N - n] )/2

 This decomposition is part of an important concept in DSP

called Circular symmetry.
 It is based on viewing the end of the signal as connected to
the beginning of the signal.
 Just as point x[4] is next to point x[5], point x[N-1] is next

to point x[0].
 When even and odd signals are viewed in this circular
manner, there are actually two lines of symmetry, one at
point x[N/2] and another at point x[0].

1 May 2018 Dr Noor Mahammad Sk 56

Circular Symmetry of Even/Odd
 For example, in an even signal, this symmetry around x[0]
means that point x[1] equals point x[N-1], point x[2] equals
point x[N-2], etc.
 In an odd signal, point 0 and point N/2 always have a value of
zero.
 In an even signal, point 0 and point N/2 are equal to the
corresponding points in the original signal.
 The motivation for viewing the last sample in a signal as being
next to the first sample?
 There is nothing in conventional data acquisition to support this
circular notion.
 In fact, the first and last samples generally have less in common than
any other two points in the sequence.

1 May 2018 Dr Noor Mahammad Sk 57

Fourier analysis – Even and Odd
The missing piece to this puzzle is a DSP technique
called Fourier analysis.
The mathematics of Fourier analysis inherently views
the signal as being circular.
Although it usually has no physical meaning in terms
of where the data came from.

1 May 2018 Dr Noor Mahammad Sk 58

Example of even/odd decomposition

Even/ Odd
Decomposition

•An N point signal is broken into two N point signals, one with
even symmetry, and the other with odd symmetry.
1 May 2018 Dr Noor Mahammad Sk 59
Interlaced Decomposition
The interlaced decomposition breaks the signal into two
component signals, the even sample signal and the odd
sample signal
 not to be confused with even and odd symmetry

signals
To find the even sample signal, start with the original
signal and set all of the odd numbered samples to zero.
To find the odd sample signal, start with the original
signal and set all of the even numbered samples to zero.
The interlaced decomposition is the basis for an
extremely important algorithm in DSP, the Fast Fourier
Transform (FFT).

1 May 2018 Dr Noor Mahammad Sk 60

Example of interlaced decomposition

Interlaced
Decomposition

•An N point signal is broken into two N point signals, one

with the odd samples set to zero, the other with the even
samples set to zero.
1 May 2018 Dr Noor Mahammad Sk 61
Interlaced decomposition
The procedure for calculating the Fourier
decomposition has been known for several hundred
years.
Unfortunately, it is frustratingly slow, often requiring
minutes or hours to execute on present day
computers.
The FFT is a family of algorithms developed in the
1960s to reduce this computation time

1 May 2018 Dr Noor Mahammad Sk 62

FFT
The strategy is an exquisite example of DSP:
Reduce the signal to elementary components by
repeated use of the interlace transform;
Calculate the Fourier decomposition of the individual
components;
Synthesize the results into the final answer
The results are dramatic; it is common for the speed
to be improved by a factor of hundreds or thousands.

1 May 2018 Dr Noor Mahammad Sk 63

Fourier Decomposition
 Fourier decomposition is very mathematical and not at all
obvious
 Any N point signal can be decomposed into N+2 signals,
 half of them sine waves and
 half of them cosine waves.
 The lowest frequency cosine wave (called xC0[n] in this
illustration), makes zero complete cycles over the N samples,
i.e., it is a DC signal.
 The next cosine components: xC1[n], xC2[n] and xC3[n], and,
make 1, 2, and 3 complete cycles over the N samples,
respectively.
 This pattern holds for the remainder of the cosine waves, as
well as for the sine wave components.

1 May 2018 Dr Noor Mahammad Sk 64

Fourier Decomposition

Cosine Waves Sine Waves

1 May 2018 Dr Noor Mahammad Sk 65

Fourier Decomposition

Cosine Waves Sine Waves

1 May 2018 Dr Noor Mahammad Sk 66

Fourier Decomposition

Cosine Waves Sine Waves

 An N point signal is decomposed into N+2 signals

 Each having N points
 Half of these signals are cosine waves, and half are sine waves.
 The frequencies of the sinusoids are fixed;
 Only the amplitudes can change.
1 May 2018 Dr Noor Mahammad Sk 67
Fourier Decomposition
Since the frequency of each component is fixed, the
only thing that changes for different signals being
decomposed is the amplitude of each of the sine and
cosine waves.
Fourier decomposition is important for three
reasons:
First, a wide variety of signals are inherently created
from superimposed sinusoids.
 Audio signals are a good example of this.
 Fourier decomposition provides a direct analysis of the
information contained in these types of signals.

1 May 2018 Dr Noor Mahammad Sk 68

Fourier Decomposition
Second, linear systems respond to sinusoids in a
unique way:
 a sinusoidal input always results in a sinusoidal output.
 In this approach, systems are characterized by how they
change the amplitude and phase of sinusoids passing
through them.
 Since an input signal can be decomposed into sinusoids,
 knowing how a system will react to sinusoids allows the
output of the system to be found.

1 May 2018 Dr Noor Mahammad Sk 69

Fourier Decomposition
Third, the Fourier decomposition is the basis for a
broad and powerful area of mathematics called
Fourier analysis, and the even more advanced
Laplace and z-transforms.
Most cutting-edge DSP algorithms are based on
some aspect of these techniques.

1 May 2018 Dr Noor Mahammad Sk 70

The Delta Function and Impulse Response

A signal can be decomposed into a group of

components called impulses
An impulse is a signal composed of all zeros, except a
single nonzero point.
In effect, impulse decomposition provides a way to
analyze signals one sample at a time.
The fundamental concept of DSP:
 The input signal is decomposed into simple additive
components,
 Each of these components is passed through a linear
system, and
 The resulting output components are synthesized (added).
1 May 2018 Dr Noor Mahammad Sk 71
Convolution
When impulse decomposition is used, the procedure
can be described by a mathematical operation called
convolution.
Delta function δ(n):
 The delta function is a normalized impulse,
 Sample number zero has a value of one, while all other
samples have a value of zero.
 For this reason, the delta function is frequently called the
unit impulse.
Impulse response:
 The impulse response is the signal that exits a system
when a delta function (unit impulse) is the input.
1 May 2018 Dr Noor Mahammad Sk 72
Impulse Response
Any impulse can be represented as a shifted and
scaled delta function.
Consider a signal, a[n], composed of
 All zeros except sample number 8, which has a value of -3.
 This is the same as a delta function shifted to the right by 8
samples, and multiplied by -3.
 In equation form: a[n] = -3δ[n-8].
Scaling and shifting the input results in an identical
scaling and shifting of the output.
If δ[n] results in h[n], it follows that -3δ[n-8] results
in -3h[n-8].

1 May 2018 Dr Noor Mahammad Sk 73

Delta function and Impulse response

Delta Function Impulse Response

1 May 2018 Dr Noor Mahammad Sk 74

Convolution
Let's summarize this way of understanding how a
system changes an input signal into an output signal
 First, the input signal can be decomposed into a set of
impulses, each of which can be viewed as a scaled and
shifted delta function.
 Second, the output resulting from each impulse is a scaled
and shifted version of the impulse response
 Third, the overall output signal can be found by adding
these scaled and shifted impulse responses
In other words, if we know a system's impulse
response, then we can calculate what the output will
be for any possible input signal.
This means we know everything about the system.
1 May 2018 Dr Noor Mahammad Sk 75
Impulse Response in Different Systems
If the system being considered is a filter
 The impulse response is called the filter kernel, the
convolution kernel, or simply, the kernel.
In image processing,
 The impulse response is called the point spread function.

1 May 2018 Dr Noor Mahammad Sk 76

Convolution

Convolution is a formal mathematical operation,

 just as multiplication, addition, and integration.
Addition takes two numbers and produces a third
number, while convolution takes two signals and
produces a third signal
Convolution is used in the mathematics of many
fields, such as probability and statistics.
1 May 2018 Dr Noor Mahammad Sk 77
 Low Pass Filtering Using Convolution

•In this example, the input

signal is a few cycles of a sine
wave plus a slowly rising ramp

•These two components are

separated by using properly
selected impulse responses.

1 May 2018 Dr Noor Mahammad Sk 78

High Pass Filtering Using Convolution

1 May 2018 Dr Noor Mahammad Sk 79

Convolution - The Input Side Algorithm

 A nine point input signal, convolved with a four point impulse

response, results in a twelve point output signal.
 Each point in the input signal contributes a scaled and shifted
impulse response to the output signal.
 These nine scaled and shifted impulse responses are shown in
the following Figures
1 May 2018 Dr Noor Mahammad Sk 80
Convolution - The Input Side Algorithm

•In these signals, each point that results from a scaled and shifted impulse
response is represented by a square marker
•The remaining data points, represented by diamonds, are zeros that have been
added as place holders.
1 May 2018 Dr Noor Mahammad Sk 81
Convolution - The Input Side Algorithm

1 May 2018 Dr Noor Mahammad Sk 82

Convolution - The Input Side Algorithm
 A 9 point input signal, x[n] , is passed through a system with a
4 point impulse response, h[n] , resulting in a 9 + 4 – 1 = 12
point output signal, y[n].
 Let's look at several of these nine signals in detail
 We will start with sample number four in the input signal, i.e., x[4].
 This sample is at index number four, and has a value of 1.4.
 When the signal is decomposed, this turns into an impulse
represented as: 1.4δ[n-4].
 After passing through the system, the resulting output component will
be: 1.4 h[n-4].
 Notice that this is the impulse response, h[n], multiplied by
1.4, and shifted four samples to the right.
 Zeros have been added at samples 0-3 and at samples 8-11 to
serve as place holders.
1 May 2018 Dr Noor Mahammad Sk 83
Convolution - The Input Side Algorithm

Above figure uses squares to represent the data points

that come from the shifted and scaled impulse response,
and
Diamonds for the added zeros.

1 May 2018 Dr Noor Mahammad Sk 84

Convolution - The Input Side Algorithm

 Now examine sample x[8], the last point in the input signal
 This sample is at index number eight, and has a value of -0.5.
 x[8] results in an impulse response that has been shifted to the right by
eight points and multiplied by -0.5.
 Place holding zeros have been added at points 0-7.
 Lastly, examine the effect of points x[0] and x[7].
 Both these samples have a value of zero, and therefore produce
output components consisting of all zeros.
1 May 2018 Dr Noor Mahammad Sk 85
Convolution - The Input Side Algorithm
Let us consider: x[n] a four point signal, and h[n] a
nine point signal.
The same two waveforms are used, they are just
swapped.
As shown by the output signal components, the four
samples in x[n] result in four shifted and scaled
versions of the nine point impulse response.
Convolution is commutative: a[n] * b[n] = b[n] * a[n]
.

1 May 2018 Dr Noor Mahammad Sk 86

Convolution - The Input Side Algorithm

1 May 2018 Dr Noor Mahammad Sk 87

Convolution - The Input Side Algorithm
 Output signal components
 Since convolution is commutative, the output signals for the
two examples are identical.

1 May 2018 Dr Noor Mahammad Sk 88

Convolution - The Output Side Algorithm
The first viewpoint of convolution analyzes how each
sample in the input signal affects many samples in the
output signal.
In this second viewpoint, we reverse this by looking at
individual samples in the output signal, and finding the
contributing points from the input
Sample n in the output signal is equal to some
combination of the many values in the input signal and
impulse response
This requires a knowledge of how each sample in the
output signal can be calculated independently of all
other samples in the output signal
The output side algorithm provides this information
1 May 2018 Dr Noor Mahammad Sk 89
Convolution - The Output Side Algorithm
 look at an example of how a single point in the output signal
is influenced by several points from the input
 The example point we will use is y[6]
 This point is equal to the sum of all the sixth points in the nine
output components

1 May 2018 Dr Noor Mahammad Sk 90

Convolution - The Output Side Algorithm
 Now, look closely at these nine output components and
identify which can affect y[6]
 That is, find which of these nine signals contains a nonzero
sample at the sixth position
 Five of the output components only have added zeros (the
diamond markers) at the sixth sample, and can therefore be
ignored.

1 May 2018 Dr Noor Mahammad Sk 91

Convolution - The Output Side Algorithm
Only four of the output components are capable of
having a nonzero value in the sixth position
These are the output components generated from
the input samples: x[3], x[4], x[5], and x[6] .
By adding the sixth sample from each of these
output components, y[6] is determined as: y[6] =
x[3]h[3] + x[4]h[2] + x[5]h[1] + x[6]h[0] .
That is, four samples from the input signal are
multiplied by the four samples in the impulse
response, and the products added.

1 May 2018 Dr Noor Mahammad Sk 92

Reference
Steven W. Smith, The Scientist and Engineer’s Guide
to Digital Signal Processing.
Avilable at: http://www.dspguide.com/

1 May 2018 Dr Noor Mahammad Sk 93