DSP
DSP
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
1.
2. π
3. ω π
•
•
Postulate (3)
ω π π π π π π
▪ π
▪
π
▪
•
•
•
•
•
•
•
•
•
•
•
•
…
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
…
•
•
•
•
•
•
•
•
•
•
π π
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
δ
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Transmitted Signal, x(n)
Reflected Signal,
Distance=‘d’
Tx
Rx
•
•ʋ
•
Transmitted Signal, x(n)
Reflected Signal,
Distance=‘d’
Tx
Rx
Transmitted Signal, x(n)
Reflected Signal,
Distance=‘d’
Tx
Rx
Transmitted Signal, x(n)
Reflected Signal,
Distance=‘d’
Tx
Rx
•
•
EE-394 Digital Signal Processing
TE (EE) Fall 2020
Resource Persons: Dr. Saad Ahmed Qazi
Nabeel Fayyaz
Muhammad Omar
1
Part-B
Frequency Analysis/Spectral
Analysis/Harmonic Analysis of
Signals
2
Frequency Analysis of Signals
Introduction
Analysis
Purpose of Analysis
• To observe
• To examine
• To investigate
3
Frequency Analysis of Signals
Introduction
Synthesis
Purpose of Synthesis
4
Frequency Analysis of Signals
Example of Analysis and Synthesis
5
Frequency Analysis of Signals
Signal Analysis
6
Frequency Analysis of Signals
Signal Analysis
7
Frequency Analysis of Signals
Signal Analysis
8
Frequency Analysis of Signals
Signal Analysis
9
Frequency Analysis of Signals
Signal Analysis
11
Frequency Analysis of Signals
Signal Synthesis
12
Frequency Analysis of Signals
Signal Analysis Signal Synthesis
13
Frequency Analysis of Signals
Techniques for Signal Analysis
14
Frequency Analysis of Signals
15
Frequency Analysis of Signals
Source: https://gist.github.com/amroamroamro
16
Frequency Analysis of Signals
Time and Frequency Domain Views of a complicated (non sinusoidal)
Signal
17
Frequency Analysis of Signals
Time and Frequency Domain Views of a complicated (non sinusoidal)
Signal
In the three-dimensional view, when we look at a signal from the side view, each
component appears as a single vertical line (spike) at its own frequency.
This side view of the signal is called the Frequency Domain. Another name for this
view is the Signal Spectrum
18
Frequency Analysis of Signals
Time and Frequency Domain Views of a complicated (non sinusoidal)
Signal
Source: https://commons.wikimedia.org/wiki/File:Fourier_transform_time_and_frequency_domains.gif
19
EE-394 Digital Signal Processing
TE (EE) Fall 2020
Resource Persons: Dr. Saad Ahmed Qazi
Nabeel Fayyaz
Muhammad Omar
1
Discrete Fourier Transform [DFT]
2
Continuous Time Fourier Transform [CTFT]
Analysis Equation
∞
𝑋𝑋 𝐹𝐹 = � 𝑥𝑥 𝑡𝑡 𝑒𝑒 −𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗 𝑑𝑑𝑑𝑑
−∞
∞
3
Discrete Fourier Transform [DFT]
Analysis Equation
𝑁𝑁−1
𝑘𝑘
−𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁
𝑛𝑛=0
𝑁𝑁−1
𝑘𝑘 𝑘𝑘
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 [ cos 2𝜋𝜋 𝑛𝑛 − 𝑗𝑗 sin 2𝜋𝜋 𝑛𝑛 ]
𝑁𝑁 𝑁𝑁
𝑛𝑛=0
𝑁𝑁 ⤏ 𝑡𝑡𝑡𝑡𝑡 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑜𝑜𝑜𝑜 𝑡𝑡𝑡𝑡𝑡 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑎𝑎𝑎𝑎𝑎𝑎 𝑡𝑡𝑡𝑡𝑡 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑖𝑖𝑖𝑖 𝑡𝑡𝑡𝑡𝑡 𝐷𝐷𝐷𝐷𝐷𝐷 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜
𝑘𝑘 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
⤏ 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑜𝑜𝑜𝑜 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑜𝑜𝑜𝑜 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑜𝑜𝑜𝑜 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
𝑁𝑁 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
𝑘𝑘
𝑒𝑒 −𝑗𝑗𝑗𝜋𝜋𝑁𝑁𝑛𝑛 ⤏ 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑜𝑜𝑜𝑜 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
4
Discrete Fourier Transform [DFT]
Analysis Equation
𝑁𝑁−1
𝑘𝑘
−𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁
𝑛𝑛=0
𝑁𝑁−1
𝑘𝑘 𝑘𝑘
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 [ cos 2𝜋𝜋 𝑛𝑛 − 𝑗𝑗 sin 2𝜋𝜋 𝑛𝑛 ]
𝑁𝑁 𝑁𝑁
𝑛𝑛=0
Each DFT output term 𝑋𝑋 𝑘𝑘 is the sum of the term-by-term products of an input
time domain sequence with sequences representing a discrete sine and cosine
wave
The frequency of discrete sine and cosine waves keeps changing on updating the
value of ‘k’
5
Discrete Fourier Transform [DFT]
Analysis Equation
𝑁𝑁−1
𝑘𝑘
−𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁
𝑛𝑛=0
𝑘𝑘 = 0, 1, 2, . . . , 𝑁𝑁 − 1
Synthesis Equation
𝑁𝑁−1
1 𝑘𝑘
+𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑥𝑥 𝑛𝑛 = � 𝑋𝑋 𝑘𝑘 𝑒𝑒 𝑁𝑁
𝑁𝑁
𝑘𝑘=0
𝑛𝑛 = 0, 1, 2, . . . , 𝑁𝑁 − 1
6
Discrete Fourier Transform [DFT]
𝐷𝐷𝐹𝐹𝐹𝐹 𝐼𝐼𝐷𝐷𝐷𝐷𝐷𝐷
𝑥𝑥 𝑛𝑛 𝑋𝑋 𝑘𝑘 𝑥𝑥 𝑛𝑛
𝐼𝐼𝐷𝐷𝐷𝐷𝐷𝐷
𝑤𝑤𝑤𝑤𝑤𝑤𝑤
𝐷𝐷𝐹𝐹𝐹𝐹 1/𝑁𝑁
𝑥𝑥 𝑛𝑛 𝑋𝑋 𝑘𝑘 𝑥𝑥 𝑛𝑛
7
Discrete Fourier Transform [DFT]
Analysis Equation
𝑁𝑁−1
1 𝑘𝑘
−𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁
𝑁𝑁
𝑛𝑛=0
𝑘𝑘 = 0, 1, 2, . . . , 𝑁𝑁 − 1
Synthesis Equation
𝑁𝑁−1
𝑘𝑘
+𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑥𝑥 𝑛𝑛 = � 𝑋𝑋 𝑘𝑘 𝑒𝑒 𝑁𝑁
𝑘𝑘=0
𝑛𝑛 = 0, 1, 2, . . . , 𝑁𝑁 − 1
8
Discrete Fourier Transform [DFT]
𝐷𝐷𝐹𝐹𝐹𝐹 𝐼𝐼𝐷𝐷𝐷𝐷𝐷𝐷
𝑥𝑥 𝑛𝑛 𝑋𝑋 𝑘𝑘 𝑥𝑥 𝑛𝑛
𝐷𝐷𝐹𝐹𝐹𝐹
𝑤𝑤𝑤𝑤𝑤𝑤𝑤
1/𝑁𝑁 𝐼𝐼𝐷𝐷𝐷𝐷𝐷𝐷
𝑥𝑥 𝑛𝑛 𝑋𝑋 𝑘𝑘 𝑥𝑥 𝑛𝑛
9
Discrete Fourier Transform [DFT]
Analysis Equation
𝑁𝑁−1
1 𝑘𝑘
−𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁
𝑁𝑁 𝑛𝑛=0
𝑘𝑘 = 0, 1, 2, . . . , 𝑁𝑁 − 1
Synthesis Equation
𝑁𝑁−1
1 𝑘𝑘
+𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑥𝑥 𝑛𝑛 = � 𝑋𝑋 𝑘𝑘 𝑒𝑒 𝑁𝑁
𝑁𝑁 𝑘𝑘=0
𝑛𝑛 = 0, 1, 2, . . . , 𝑁𝑁 − 1
10
Discrete Fourier Transform [DFT]
When no scaling factor 1⁄𝑁𝑁 is used:
𝐷𝐷𝐹𝐹𝐹𝐹 𝐼𝐼𝐷𝐷𝐷𝐷𝐷𝐷
𝑥𝑥 𝑛𝑛 𝑋𝑋 𝑘𝑘 𝑥𝑥 𝑛𝑛
𝐷𝐷𝐹𝐹𝐹𝐹 𝐼𝐼𝐷𝐷𝐹𝐹𝐹𝐹
𝑤𝑤𝑤𝑤𝑤𝑤𝑤 𝑤𝑤𝑤𝑤𝑤𝑤𝑤
1/ 𝑁𝑁 1/ 𝑁𝑁
𝑥𝑥 𝑛𝑛 𝑋𝑋 𝑘𝑘 𝑥𝑥 𝑛𝑛
11
Discrete Fourier Transform [DFT]
Note
𝑋𝑋 𝑘𝑘 = 8, 4, 2, 0, 0, 0, 2, 4
1
𝑋𝑋 𝑘𝑘 = 8, 4, 2, 0, 0, 0, 2, 4
𝑁𝑁
1
𝑋𝑋 𝑘𝑘 = 8, 4, 2, 0, 0, 0, 2, 4
8
12
Discrete Fourier Transform [DFT]
Note
Discrete Fourier Transform (DFT) is one of the most powerful tools in digital
signal processing; it enables us to find the spectrum of a finite-duration discrete-
time signal 𝑥𝑥(𝑛𝑛)
DFT finds out the frequency domain amplitudes and phases of ‘N’ complex
exponentials (containing both sine and cosine components) present in a discrete-
time signal of length ‘N’ samples
The input given to DFT should be of finite length no matter whether it is taken
from some periodic signal or non-periodic signal
We can use DFT for the analysis of both periodic and non-periodic signals
DFT never cares about the signal periodicity. It simply treats all signals as the time
limited or finite length sequence which corresponds to our signal of
interest/region of interest denoted by ‘N’
13
Discrete Fourier Transform [DFT]
Proof
i.e. 𝑋𝑋 𝑘𝑘 + 𝑁𝑁 = 𝑋𝑋 𝑘𝑘
14
Discrete Fourier Transform [DFT]
Proof
Analysis Equation
𝑁𝑁−1
𝑘𝑘
−𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁
𝑛𝑛=0
𝑁𝑁−1
(𝑘𝑘+𝑁𝑁)
−𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 + 𝑁𝑁 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁
𝑛𝑛=0
𝑁𝑁−1
𝑘𝑘
−𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 + 𝑁𝑁 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁 𝑒𝑒 −𝑗𝑗𝑗𝜋𝜋𝑛𝑛
𝑛𝑛=0
15
Discrete Fourier Transform [DFT]
Proof
𝑁𝑁−1
𝑘𝑘
−𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 + 𝑁𝑁 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁 𝑒𝑒 −𝑗𝑗𝑗𝜋𝜋𝑛𝑛
𝑛𝑛=0
𝑁𝑁−1
𝑘𝑘
−𝑗𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 + 𝑁𝑁 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁
𝑛𝑛=0
𝑋𝑋 𝑘𝑘 + 𝑁𝑁 = 𝑋𝑋 𝑘𝑘
16
Discrete Fourier Transform [DFT]
Proof
𝑋𝑋 𝑘𝑘 + 𝑁𝑁 = 𝑋𝑋 𝑘𝑘
It shows that the DFT output ‘𝑋𝑋 𝑘𝑘 ’ will repeat after every ‘N’ samples
𝑋𝑋 4 = 𝑋𝑋 0+4 = 𝑋𝑋 0
𝑋𝑋 5 = 𝑋𝑋 1+4 = 𝑋𝑋 1
𝑋𝑋 6 = 𝑋𝑋 2+4 = 𝑋𝑋 2
𝑋𝑋 7 = 𝑋𝑋 3+4 = 𝑋𝑋 3
17
EE-394 Digital Signal Processing
TE (EE) Fall 2020
Resource Persons: Dr. Saad Ahmed Qazi
Nabeel Fayyaz
Muhammad Omar
1
Discrete Fourier Transform [DFT]
Lecture Objectives
• Example of DFT
• Example of IDFT
2
Discrete Fourier Transform [DFT]
DFT Frequency axis
DFT converts a time domain sequence of ‘N ’ samples into ‘N ’ equally spaced
frequency domain samples (harmonic components)
The exact frequencies ‘Hz’ of the DFT output depend on both the sampling rate ‘𝐹𝐹𝑠𝑠 ’
at which the original signal was sampled and the number of samples ‘N ’
3
Discrete Fourier Transform [DFT]
Frequency resolution (∆𝐹𝐹)
1 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
∆𝐹𝐹 = Unit:
𝑁𝑁 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
𝐹𝐹𝑠𝑠
∆𝐹𝐹 = Unit: Hz
𝑁𝑁
4
Discrete Fourier Transform [DFT]
Frequency resolution (∆𝐹𝐹)
𝐹𝐹𝑠𝑠
∆𝐹𝐹 =
𝑁𝑁
𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠⁄𝑠𝑠𝑠𝑠𝑠𝑠
∆𝐹𝐹 =
𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
1
∆𝐹𝐹 =
𝑠𝑠𝑠𝑠𝑠𝑠
∆𝐹𝐹 = 𝐻𝐻𝐻𝐻
Bin frequencies/Analysis frequencies
𝑘𝑘𝐹𝐹𝑠𝑠
𝐹𝐹𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘 = 𝐹𝐹𝑘𝑘 = 𝑘𝑘 × ∆𝐹𝐹 =
𝑁𝑁
𝑘𝑘𝐹𝐹𝑠𝑠
𝐹𝐹𝑘𝑘 =
𝑁𝑁
5
Discrete Fourier Transform [DFT]
Frequency resolution (∆𝐹𝐹)
𝐹𝐹𝑠𝑠
∆𝐹𝐹 =
𝑁𝑁
𝑘𝑘𝐹𝐹𝑠𝑠
𝐹𝐹𝑘𝑘 =
𝑁𝑁
100
∆𝐹𝐹 = = 25 𝐻𝐻𝐻𝐻
4
𝐹𝐹𝑘𝑘 = 𝑘𝑘 × ∆𝐹𝐹
𝐹𝐹𝑘𝑘 = 25 [0,1, 2, 3 ]
0 1 2 3
𝑥𝑥 𝑛𝑛 = 1, 1 , 0 , 0
↑
𝑁𝑁 = 4 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
7
Discrete Fourier Transform [DFT]
Solution
0 1 2 3
𝑥𝑥 𝑛𝑛 = 1, 1 , 0 , 0
↑
𝑁𝑁−1
𝑘𝑘 𝑘𝑘
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 [ cos 2𝜋𝜋 𝑛𝑛 − 𝑗𝑗 sin 2𝜋𝜋 𝑛𝑛 ]
𝑁𝑁 𝑁𝑁
𝑛𝑛=0
4−1
𝑘𝑘 𝑘𝑘
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 [ cos 2𝜋𝜋 𝑛𝑛 − 𝑗𝑗 sin 2𝜋𝜋 𝑛𝑛 ]
4 4
𝑛𝑛=0
3
𝑘𝑘 𝑘𝑘
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 [ cos 2𝜋𝜋𝑛𝑛 − 𝑗𝑗 sin 2𝜋𝜋𝑛𝑛 ]
4 4
𝑛𝑛=0
8
Discrete Fourier Transform [DFT]
0 1 2 3
Solution 𝑥𝑥 𝑛𝑛 = 1, 1 , 0 , 0
↑
3
𝑘𝑘 𝑘𝑘
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 [ cos 2𝜋𝜋𝑛𝑛 − 𝑗𝑗 sin 2𝜋𝜋𝑛𝑛 ]
4 4
𝑛𝑛=0
𝑋𝑋 0
0 0 0 0
= 𝑥𝑥 0 cos 2𝜋𝜋. 0 . − 𝑗𝑗 𝑥𝑥 0 sin 2𝜋𝜋. 0 . + 𝑥𝑥 1 cos 2𝜋𝜋. 1 . − 𝑗𝑗 𝑥𝑥 1 sin 2𝜋𝜋. 1 .
4 4 4 4
0 0 0 0
+ 𝑥𝑥 2 cos 2𝜋𝜋. 2 . − 𝑗𝑗 𝑥𝑥 2 sin 2𝜋𝜋. 2 . + 𝑥𝑥 3 cos 2𝜋𝜋. 3 . − 𝑗𝑗 𝑥𝑥 3 sin 2𝜋𝜋. 3 .
4 4 4 4
𝑋𝑋 0 = 1 1 − 𝑗𝑗 1 0 + 1 1 − 𝑗𝑗 1 0
+ 0 1 − 𝑗𝑗 0 0 + 0 1 − 𝑗𝑗 0 0
𝑋𝑋 0 = 1 − 0 + 1 − 0 + 0 − 0 + 0 − 0
𝑋𝑋 0 = 2
9
Discrete Fourier Transform [DFT]
0 1 2 3
Solution 𝑥𝑥 𝑛𝑛 = 1, 1 , 0 , 0
↑
3
𝑘𝑘 𝑘𝑘
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 [ cos 2𝜋𝜋𝑛𝑛 − 𝑗𝑗 sin 2𝜋𝜋𝑛𝑛 ]
4 4
𝑛𝑛=0
𝑋𝑋 1
1 1 1 1
= 𝑥𝑥 0 cos 2𝜋𝜋. 0 . − 𝑗𝑗 𝑥𝑥 0 sin 2𝜋𝜋. 0 . + 𝑥𝑥 1 cos 2𝜋𝜋. 1 . − 𝑗𝑗 𝑥𝑥 1 sin 2𝜋𝜋. 1 .
4 4 4 4
1 1 1 1
+ 𝑥𝑥 2 cos 2𝜋𝜋. 2 . − 𝑗𝑗 𝑥𝑥 2 sin 2𝜋𝜋. 2 . + 𝑥𝑥 3 cos 2𝜋𝜋. 3 . − 𝑗𝑗 𝑥𝑥 3 sin 2𝜋𝜋. 3 .
4 4 4 4
𝑋𝑋 1 = 1 1 − 𝑗𝑗 1 0 + 1 0 − 𝑗𝑗 1 1
+ 0 −1 − 𝑗𝑗 0 0 + 0 0 − 𝑗𝑗 0 −1
𝑋𝑋 1 = 1 − 0 + 0 − 𝑗𝑗 + 0 − 0 + 0 − 0
𝑋𝑋 1 = 1 − 𝑗𝑗
10
Discrete Fourier Transform [DFT]
0 1 2 3
Solution 𝑥𝑥 𝑛𝑛 = 1, 1 , 0 , 0
↑
3
𝑘𝑘 𝑘𝑘
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 [ cos 2𝜋𝜋𝑛𝑛 − 𝑗𝑗 sin 2𝜋𝜋𝑛𝑛 ]
4 4
𝑛𝑛=0
𝑋𝑋 2
2 2 2 2
= 𝑥𝑥 0 cos 2𝜋𝜋. 0 . − 𝑗𝑗 𝑥𝑥 0 sin 2𝜋𝜋. 0 . + 𝑥𝑥 1 cos 2𝜋𝜋. 1 . − 𝑗𝑗 𝑥𝑥 1 sin 2𝜋𝜋. 1 .
4 4 4 4
2 2 2 2
+ 𝑥𝑥 2 cos 2𝜋𝜋. 2 . − 𝑗𝑗 𝑥𝑥 2 sin 2𝜋𝜋. 2 . + 𝑥𝑥 3 cos 2𝜋𝜋. 3 . − 𝑗𝑗 𝑥𝑥 3 sin 2𝜋𝜋. 3 .
4 4 4 4
𝑋𝑋 2 = 1 1 − 𝑗𝑗 1 0 + 1 −1 − 𝑗𝑗 1 0
+ 0 1 − 𝑗𝑗 0 0 + 0 −1 − 𝑗𝑗 0 0
𝑋𝑋 2 = 1 − 0 + (−1) − 0 + 0 − 0 + 0 − 0
𝑋𝑋 2 = 0
11
Discrete Fourier Transform [DFT]
0 1 2 3
Solution 𝑥𝑥 𝑛𝑛 = 1, 1 , 0 , 0
↑
3
𝑘𝑘 𝑘𝑘
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 [ cos 2𝜋𝜋𝑛𝑛 − 𝑗𝑗 sin 2𝜋𝜋𝑛𝑛 ]
4 4
𝑛𝑛=0
𝑋𝑋 3
3 3 3 3
= 𝑥𝑥 0 cos 2𝜋𝜋. 0 . − 𝑗𝑗 𝑥𝑥 0 sin 2𝜋𝜋. 0 . + 𝑥𝑥 1 cos 2𝜋𝜋. 1 . − 𝑗𝑗 𝑥𝑥 1 sin 2𝜋𝜋. 1 .
4 4 4 4
3 3 3 3
+ 𝑥𝑥 2 cos 2𝜋𝜋. 2 . − 𝑗𝑗 𝑥𝑥 2 sin 2𝜋𝜋. 2 . + 𝑥𝑥 3 cos 2𝜋𝜋. 3 . − 𝑗𝑗 𝑥𝑥 3 sin 2𝜋𝜋. 3 .
4 4 4 4
𝑋𝑋 3 = 1 1 − 𝑗𝑗 1 0 + 1 0 − 𝑗𝑗 1 −1
+ 0 −1 − 𝑗𝑗 0 0 + 0 0 − 𝑗𝑗 0 1
𝑋𝑋 3 = 1 − 0 + 0 + 𝑗𝑗 + 0 − 0 + 0 − 0
𝑋𝑋 3 = 1 + 𝑗𝑗
12
Discrete Fourier Transform [DFT]
Solution
0 1 2 3
𝑋𝑋 𝑘𝑘 = 2 , (1 − 𝑗𝑗) , 0 , (1 + 𝑗𝑗)
↑
0 1 2 3
𝑋𝑋 𝑘𝑘 = 2, 2 , 0 , 2
↑
0 1 2 3
∠𝑋𝑋 𝑘𝑘 = 0° , −45° , 0° , 45°
↑
13
Discrete Fourier Transform [DFT]
Alternate Method
14
Discrete Fourier Transform [DFT]
Solution
0 1 2 3
𝑥𝑥 𝑛𝑛 = 1, 1 , 0 , 0
↑
3
𝑘𝑘
−𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 2
𝑛𝑛=0
15
Discrete Fourier Transform [DFT]
Solution 0 1 2 3
𝑥𝑥 𝑛𝑛 = 1, 1 , 0 , 0
↑
3
𝑘𝑘
−𝑗𝑗𝜋𝜋 𝑛𝑛
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 2
𝑛𝑛=0
𝑘𝑘 𝑘𝑘 𝑘𝑘 𝑘𝑘
−𝑗𝑗𝜋𝜋 (0) −𝑗𝑗𝜋𝜋 (1) −𝑗𝑗𝜋𝜋 (2) −𝑗𝑗𝜋𝜋 (3)
𝑋𝑋 𝑘𝑘 = 𝑥𝑥 0 𝑒𝑒 2 + 𝑥𝑥 1 𝑒𝑒 2 + 𝑥𝑥 2 𝑒𝑒 2 + 𝑥𝑥 3 𝑒𝑒 2
𝑘𝑘 𝑘𝑘 𝑘𝑘 𝑘𝑘
−𝑗𝑗𝜋𝜋 (0) −𝑗𝑗𝜋𝜋 (1) −𝑗𝑗𝜋𝜋 (2) −𝑗𝑗𝜋𝜋 (3)
𝑋𝑋 𝑘𝑘 = 1𝑒𝑒 2 + 1𝑒𝑒 2 + 0𝑒𝑒 2 + 0𝑒𝑒 2
𝑘𝑘
−𝑗𝑗𝜋𝜋
𝑋𝑋 𝑘𝑘 = 1(1) + 1𝑒𝑒 2 +0+0
𝑘𝑘
−𝑗𝑗𝜋𝜋
𝑋𝑋 𝑘𝑘 = 1 + 𝑒𝑒 2
16
Discrete Fourier Transform [DFT]
Solution
𝑘𝑘
−𝑗𝑗𝜋𝜋
𝑋𝑋 𝑘𝑘 = 1 + 𝑒𝑒 2 … (𝐴𝐴)
0
−𝑗𝑗𝜋𝜋
𝑋𝑋 0 = 1 + 𝑒𝑒 2 =1+1=2=2
1 𝜋𝜋
−𝑗𝑗𝜋𝜋 −𝑗𝑗
𝑋𝑋 1 = 1 + 𝑒𝑒 2 = 1 + 𝑒𝑒 2 = 1 − 𝑗𝑗
2
−𝑗𝑗𝜋𝜋
𝑋𝑋 2 = 1 + 𝑒𝑒 2 = 1 + 𝑒𝑒 −𝑗𝑗𝜋𝜋 = 1 + −1 = 1 − 1 = 0
3 3𝜋𝜋
−𝑗𝑗𝜋𝜋 −𝑗𝑗
𝑋𝑋 3 = 1 + 𝑒𝑒 2 = 1 + 𝑒𝑒 2 = 1 + 𝑗𝑗
17
Discrete Fourier Transform [DFT]
Solution
𝑘𝑘
−𝑗𝑗𝜋𝜋
𝑋𝑋 𝑘𝑘 = 1 + 𝑒𝑒 2 … (𝐴𝐴)
0 1 2 3
𝑋𝑋 𝑘𝑘 = 2 , (1 − 𝑗𝑗) , 0 , (1 + 𝑗𝑗)
↑
0 1 2 3
𝑋𝑋 𝑘𝑘 = 2, 2 , 0 , 2
↑
0 1 2 3
∠𝑋𝑋 𝑘𝑘 = 0° , −45° , 0° , 45°
↑
18
Discrete Fourier Transform [DFT]
Solution
0 1 2 3
𝑋𝑋 𝑘𝑘 = 2, 2 , 0 , 2
↑
19
Discrete Fourier Transform [DFT]
Solution
20
Discrete Fourier Transform [DFT]
Solution
21
Discrete Fourier Transform [DFT]
Solution
22
Discrete Fourier Transform [DFT]
Solution
23
Discrete Fourier Transform [DFT]
Solution
24
Discrete Fourier Transform [DFT]
Solution
25
Discrete Fourier Transform [DFT]
Solution
26
Discrete Fourier Transform [DFT]
Key Concept: Spectrum for real valued signals
The spectrum of every real valued signal will always be a double sided spectrum [a
spectrum comprises of both +ve frequency phasors and –ve frequency phasors]
−𝐹𝐹𝑠𝑠 +𝐹𝐹𝑠𝑠
≤ 𝐹𝐹 ≤
2 2
−ve frequency +ve frequency
phasors phasors
−𝐹𝐹𝑠𝑠 +𝐹𝐹𝑠𝑠
−−−− − 0 −−−− −
2 2
+𝐹𝐹𝑠𝑠
0 −−−− − −−−− −𝐹𝐹𝑠𝑠
2
+ve frequency −ve frequency
phasors phasors
27
Discrete Fourier Transform [DFT]
Key Concept: Spectrum for real valued signals
The spectrum of every real valued signal will always be a double sided spectrum [a
spectrum comprises of both +ve frequency phasors and –ve frequency phasors]
−1 +1
≤ 𝑓𝑓𝑑𝑑 ≤
2 2
−ve frequency +ve frequency
phasors phasors
−1 +1
−−−− − 0 −−−− −
2 2
+1
0 −−−− − −−−− −1
2
+ve frequency −ve frequency
phasors phasors
28
Discrete Fourier Transform [DFT]
Key Concept: Spectrum for real valued signals
The spectrum of every real valued signal will always be a double sided spectrum [a
spectrum comprises of both +ve frequency phasors and –ve frequency phasors]
29
Discrete Fourier Transform [DFT]
Characteristics of various DFT frequency axis representations
Frequency in 𝐹𝐹 1 1 −1 +1
𝑓𝑓𝑑𝑑 = to
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐⁄𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝐹𝐹𝑠𝑠 𝑁𝑁 2 2
30
Discrete Fourier Transform [DFT]
Key Concept: Useful harmonic components
For real valued signals
𝐹𝐹𝑠𝑠
0 −−−− −
2
𝑁𝑁
0 −−−− −
2
31
Discrete Fourier Transform [DFT]
Key Concept: Useful harmonic components
For real valued signals
𝐹𝐹𝑠𝑠
0 −−−− −
2
𝑁𝑁
0 −−−− −
2
+ve frequency
phasors
32
Discrete Fourier Transform [DFT]
Example of IDFT
0 1 2 3
𝑋𝑋 𝑘𝑘 = 2 , (1 − 𝑗𝑗) , 0 , (1 + 𝑗𝑗)
↑
33
Discrete Fourier Transform [DFT]
Example of IDFT
0 1 2 3
𝑋𝑋 𝑘𝑘 = 2 , (1 − 𝑗𝑗) , 0 , (1 + 𝑗𝑗)
↑
Answer
0 1 2 3
𝑥𝑥 𝑛𝑛 = 1, 1 , 0 , 0
↑
34
Discrete Fourier Transform [DFT]
Practice Problem
samples
Take 𝐹𝐹𝑠𝑠 = 8000
sec
35
Discrete Fourier Transform [DFT]
Practice Problem
Compute 8 point DFT of
samples
Take 𝐹𝐹𝑠𝑠 = 8000
sec
Answer
36
Discrete Fourier Transform [DFT]
Significance of ‘𝐹𝐹𝑠𝑠 ’ and ‘N ’
𝐹𝐹𝑠𝑠
∆𝐹𝐹 =
𝑁𝑁
The higher the value of ‘Fs ’, the higher will be the value of ‘Fs /2’
In other words, ‘N’ will decide with what particular resolution we can observe
signal information or it represents how much detailed information can be
observed
The higher the value of ‘N’, the better will be the frequency resolution. The
finer resolution value is an indication of the detailed information of our signal
37
EE-394 Digital Signal Processing
TE (EE) Fall 2020
Resource Persons: Dr. Saad Ahmed Qazi
Nabeel Fayyaz
Muhammad Omar
Discrete Fourier Transform [DFT]
2
Discrete Fourier Transform [DFT]
Computational Factors:
1) Number of Multiplications
2) Number of Additions
3
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
Nature of Computations:
Complex Multiplications
Complex Computations
Complex Additions
Real Multiplications
Real Computations
Real Additions
4
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
Nature of Computations:
2+3 →
2∗3 →
2 2+3 →
5
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
Nature of Computations:
2 + 3 → 1 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎
2 ∗ 3 → 1 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚
6
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
Nature of Computations:
7
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
Nature of Computations:
𝑎𝑎 + 𝑐𝑐 + 𝑗𝑗 𝑏𝑏 + 𝑑𝑑 → 2 real additions
𝑒𝑒 + 𝑗𝑗𝑗𝑗
8
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
Nature of Computations:
9
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
Nature of Computations:
𝑒𝑒 + 𝑗𝑗𝑗𝑗
10
Discrete Fourier Transform [DFT]
DFT Analysis Equation
𝑋𝑋𝑁𝑁 = 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 𝑥𝑥𝑁𝑁
0 0 0 1 0 𝑁𝑁−1
𝑋𝑋 0 𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 ⋯ 𝑊𝑊𝑵𝑵 𝑥𝑥 0
1 0 1 1 ⋯ 1 𝑁𝑁−1
𝑋𝑋 1 𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 𝑥𝑥 1
𝑋𝑋 2 = 𝑊𝑊𝑵𝑵 2 0
𝑊𝑊𝑵𝑵 2 1 ⋯ 𝑊𝑊𝑵𝑵 2 𝑁𝑁−1 𝑥𝑥 2
⋮ ⋮ ⋮ ⋱ ⋮ ⋮
𝑋𝑋 𝑁𝑁 − 1 𝑁𝑁−1 0 𝑥𝑥 𝑁𝑁 − 1
𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 𝑁𝑁−1 1 ⋯ 𝑊𝑊𝑵𝑵 𝑁𝑁−1 𝑁𝑁−1
11
Discrete Fourier Transform [DFT]
DFT Analysis Equation
0 0 0 1 0 𝑁𝑁−1
𝑋𝑋 0 𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 ⋯ 𝑊𝑊𝑵𝑵 𝑥𝑥 0
1 0 1 1 ⋯ 1 𝑁𝑁−1
𝑋𝑋 1 𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 𝑥𝑥 1
𝑋𝑋 2 = 𝑊𝑊𝑵𝑵 2 0
𝑊𝑊𝑵𝑵 2 1 ⋯ 𝑊𝑊𝑵𝑵 2 𝑁𝑁−1 𝑥𝑥 2
⋮ ⋮ ⋮ ⋱ ⋮ ⋮
𝑋𝑋 𝑁𝑁 − 1 𝑁𝑁−1 0 𝑥𝑥 𝑁𝑁 − 1
𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 𝑁𝑁−1 1 ⋯ 𝑊𝑊𝑵𝑵 𝑁𝑁−1 𝑁𝑁−1
DFT can take a complex valued input as well. We will assume a complex
valued input 𝑥𝑥(𝑛𝑛) in order to cover the maximum possible number of
computations
12
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
13
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
𝑁𝑁 2 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚
14
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
15
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
𝑁𝑁 2 − 𝑁𝑁 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖
16
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
𝑁𝑁 2 + 𝑁𝑁 2 − 𝑁𝑁
2𝑁𝑁 2 − 𝑁𝑁
17
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
18
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
19
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
20
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
Total number of Real Additions
𝐹𝐹𝐹𝐹𝐹𝐹 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑅𝑅𝑅𝑅𝑅𝑅 → {2 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 + 2 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 }
𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡
8𝑁𝑁 2 − 2𝑁𝑁
22
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
𝑁𝑁 2
23
Discrete Fourier Transform [DFT]
Computational Analysis of N-point DFT
𝑁𝑁 2
24
Discrete Fourier Transform [DFT]
Example-1
How many complex and real computations are required to
perform 1024 point DFT ?
2
= 2 1024 − 1024
= 2096128 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
2
= 8 1024 − 2(1024)
= 8386560 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
25
Discrete Fourier Transform [DFT]
Example-2
The incoming data rate is 512 samples/sec and the length of DFT
operation is also 512 samples. If the processor can handle one real
computation in one clock cycle. Suggest the minimum processor speed
that can handle DFT operation in real-time?
26
Discrete Fourier Transform [DFT]
Example-2
The incoming data rate is 512 samples/sec and the length of DFT
operation is also 512 samples. If the processor can handle one real
computation in one clock cycle. Suggest the minimum processor speed
that can handle DFT operation in real-time?
27
Discrete Fourier Transform [DFT]
Example-2
The incoming data rate is 512 samples/sec and the length of DFT
operation is also 512 samples. If the processor can handle one real
computation in one clock cycle. Suggest the minimum processor speed
that can handle DFT operation in real-time?
Solution
𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 = 𝐴𝐴 ∗ 𝐵𝐵 ∗ 𝐶𝐶
28
Discrete Fourier Transform [DFT]
Example-2
Solution
𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 = 𝐴𝐴 ∗ 𝐵𝐵 ∗ 𝐶𝐶
29
Discrete Fourier Transform [DFT]
Example-2
𝐴𝐴
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 = 8𝑁𝑁 2 − 2𝑁𝑁
2
= 8 512 − 2(512)
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
= 2096128
𝐷𝐷𝐷𝐷𝐷𝐷
B
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝐷𝐷𝐷𝐷𝐷𝐷 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 𝑝𝑝𝑝𝑝𝑝𝑝 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 =
30
Discrete Fourier Transform [DFT]
Example-2
𝐴𝐴
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 = 8𝑁𝑁 2 − 2𝑁𝑁
2
= 8 512 − 2(512)
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
= 2096128
𝐷𝐷𝐷𝐷𝐷𝐷
B
𝐹𝐹𝑠𝑠 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠/𝑠𝑠𝑠𝑠𝑠𝑠 𝐷𝐷𝐷𝐷𝐷𝐷
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝐷𝐷𝐷𝐷𝐷𝐷 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 𝑝𝑝𝑝𝑝𝑝𝑝 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 = = =
𝑁𝑁 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠/𝐷𝐷𝐷𝐷𝐷𝐷 𝑠𝑠𝑠𝑠𝑠𝑠
512
=
512
𝐷𝐷𝐷𝐷𝐷𝐷
=1
𝑠𝑠𝑠𝑠𝑠𝑠
C
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑝𝑝𝑝𝑝𝑝𝑝 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 = 1
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
31
Discrete Fourier Transform [DFT]
Example-2
𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 = 𝐴𝐴 ∗ 𝐵𝐵 ∗ 𝐶𝐶
= 2096128 ∗ 1 ∗ 1
= 2096128 Hz
32
Discrete Fourier Transform [DFT]
Example-3
If the ADC speed is 4096 samples/sec and the length of DFT operation
is 512 samples. The processor can handle one real computation in one
clock cycle. Suggest the minimum processor speed that can handle
DFT operation in real-time?
33
Discrete Fourier Transform [DFT]
Example-3
𝐴𝐴
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 = 8𝑁𝑁 2 − 2𝑁𝑁
2
= 8 512 − 2(512)
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
= 2096128
𝐷𝐷𝐷𝐷𝐷𝐷
B
𝐹𝐹𝑠𝑠
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝐷𝐷𝐷𝐷𝐷𝐷 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 𝑝𝑝𝑝𝑝𝑝𝑝 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 =
𝑁𝑁
4096
=
512
𝐷𝐷𝐷𝐷𝐷𝐷
=8
𝑠𝑠𝑠𝑠𝑠𝑠
C
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑝𝑝𝑝𝑝𝑝𝑝 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 = 1
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
34
Discrete Fourier Transform [DFT]
Example-3
𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 = 𝐴𝐴 ∗ 𝐵𝐵 ∗ 𝐶𝐶
= 2096128 ∗ 8 ∗ 1
= 16.769 𝑀𝑀Hz
35
Discrete Fourier Transform [DFT]
Example-4
If the ADC speed is 4096 samples/sec and the length of DFT operation
is 512 samples. The processor can handle one real computation in two
clock cycles. Suggest the minimum processor speed that can handle
DFT operation in real-time?
36
Discrete Fourier Transform [DFT]
Example-4
𝐴𝐴
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 = 8𝑁𝑁 2 − 2𝑁𝑁
2
= 8 512 − 2(512)
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
= 2096128
𝐷𝐷𝐷𝐷𝐷𝐷
B
𝐹𝐹𝑠𝑠
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝐷𝐷𝐷𝐷𝐷𝐷 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 𝑝𝑝𝑝𝑝𝑝𝑝 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 =
𝑁𝑁
4096
=
512
𝐷𝐷𝐷𝐷𝐷𝐷
=8
𝑠𝑠𝑠𝑠𝑠𝑠
C
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑝𝑝𝑝𝑝𝑝𝑝 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 = 2
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
37
Discrete Fourier Transform [DFT]
Example-4
𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 = 𝐴𝐴 ∗ 𝐵𝐵 ∗ 𝐶𝐶
= 2096128 ∗ 8 ∗ 2
= 33.538 𝑀𝑀Hz
38
Discrete Fourier Transform [DFT]
Key Concept
We have done calculations in our numerical by taking length of DFT equal to
512 samples. If we do the same exercise for a higher values of ‘N’ like 1 million
point DFT then we will need a very high speed computing machine because
requirement of computations will be in a order of 1 ∗ 1012
There are also some cases where we might end up with some impractical
processor speeds or a very costly digital system
1
Discrete Fourier Transform [DFT]
• Example of DFT
• Periodicity Property
2
Discrete Fourier Transform [DFT]
or
3
Discrete Fourier Transform [DFT]
Analysis Equation
𝑁𝑁−1
𝑗𝑗𝑗𝜋𝜋𝑘𝑘𝑛𝑛
−
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁
𝑛𝑛=0
Synthesis Equation
𝑁𝑁−1
1 +
𝑗𝑗𝑗𝜋𝜋𝑘𝑘𝑛𝑛
𝑥𝑥 𝑛𝑛 = � 𝑋𝑋 𝑘𝑘 𝑒𝑒 𝑁𝑁
𝑁𝑁
𝑘𝑘=0
4
Discrete Fourier Transform [DFT]
Matrix formulation of N-point DFT
⋮ ⋮ ⋮
𝑗𝑗𝑗𝜋𝜋 𝑁𝑁−1 0 𝑗𝑗𝑗𝜋𝜋 𝑁𝑁−1 1 𝑗𝑗𝑗𝜋𝜋 𝑁𝑁−1 𝑁𝑁−1
𝑋𝑋 𝑁𝑁 − 1 = 𝑥𝑥 0 𝑒𝑒 − 𝑁𝑁 + 𝑥𝑥 1 𝑒𝑒 − 𝑁𝑁 + ……. + 𝑥𝑥 𝑁𝑁 − 1 𝑒𝑒 − 𝑁𝑁
5
Discrete Fourier Transform [DFT]
Matrix formulation of N-point DFT
2𝜋𝜋
−𝑗𝑗
Let 𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁
2𝜋𝜋 𝑘𝑘𝑛𝑛
𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 = 𝑒𝑒 −𝑗𝑗 𝑁𝑁
2𝜋𝜋𝑘𝑘𝑛𝑛
𝑘𝑘𝑛𝑛 −𝑗𝑗
𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁
Transformation Matrix
6
Discrete Fourier Transform [DFT]
Matrix formulation of N-point DFT
0 0 0 1 0 𝑁𝑁−1
𝑋𝑋 0 𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 ⋯ 𝑊𝑊𝑵𝑵 𝑥𝑥 0
1 0 1 1 ⋯ 1 𝑁𝑁−1
𝑋𝑋 1 𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 𝑥𝑥 1
𝑋𝑋 2 = 𝑊𝑊𝑵𝑵 2 0
𝑊𝑊𝑵𝑵 2 1 ⋯ 𝑊𝑊𝑵𝑵 2 𝑁𝑁−1 𝑥𝑥 2
⋮ ⋮ ⋮ ⋱ ⋮ ⋮
𝑋𝑋 𝑁𝑁 − 1 𝑁𝑁−1 0 𝑥𝑥 𝑁𝑁 − 1
𝑊𝑊𝑵𝑵 𝑊𝑊𝑵𝑵 𝑁𝑁−1 1 ⋯ 𝑊𝑊𝑵𝑵 𝑁𝑁−1 𝑁𝑁−1
Let
𝑋𝑋 𝑘𝑘 → 𝑿𝑿𝑁𝑁
𝑥𝑥 𝑛𝑛 → 𝒙𝒙𝑁𝑁
−1
�𝑁𝑁 = 𝑾𝑾𝑵𝑵 𝑘𝑘𝑛𝑛
𝒙𝒙 𝑿𝑿𝑁𝑁
7
Discrete Fourier Transform [DFT]
Analysis and Synthesis equation of DFT in Matrix form
𝑘𝑘𝑛𝑛 −1
𝒙𝒙𝑁𝑁 = 𝑊𝑊𝑁𝑁 𝑿𝑿𝑁𝑁 (2)
8
Discrete Fourier Transform [DFT]
DFT Synthesis Equation
𝑁𝑁−1
1 +
𝑗𝑗𝑗𝜋𝜋𝑘𝑘𝑛𝑛
𝑥𝑥 𝑛𝑛 = � 𝑋𝑋 𝑘𝑘 𝑒𝑒 𝑁𝑁
𝑁𝑁
𝑘𝑘=0
We know that
−𝑗𝑗
2𝜋𝜋 2𝜋𝜋 2𝜋𝜋
𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁 = cos − 𝑗𝑗 sin
𝑁𝑁 𝑁𝑁
∗ +𝑗𝑗
2𝜋𝜋 2𝜋𝜋 2𝜋𝜋
𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁 = cos + 𝑗𝑗 sin
𝑁𝑁 𝑁𝑁
1 𝑘𝑘𝑛𝑛 ∗
𝒙𝒙𝑁𝑁 = 𝑾𝑾𝑁𝑁 𝑿𝑿𝑁𝑁 (3)
𝑁𝑁
9
Discrete Fourier Transform [DFT]
Matrix formulation of N-point DFT
𝑘𝑘𝑛𝑛 −1 � 𝑁𝑁
�𝑁𝑁 = 𝑾𝑾𝑁𝑁
𝒙𝒙 𝑿𝑿
1 ∗
�𝑁𝑁 =
𝒙𝒙 𝑾𝑾𝑁𝑁 𝑘𝑘𝑛𝑛 � 𝑁𝑁
𝑿𝑿
𝑁𝑁
𝑘𝑘𝑛𝑛 −1 1 𝑘𝑘𝑛𝑛 ∗
𝑾𝑾𝑁𝑁 = 𝑾𝑾𝑁𝑁
𝑁𝑁
0 0 0 1 0 2 0 3
𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒
1 0 1 1 1 2 1 3
𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒
𝑊𝑊4 = 2 0 2 1 2 2 2 3
𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒
3 0 3 1 3 2 3 3
𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒
11
Discrete Fourier Transform [DFT]
Example-1
1 1 1 1
1 −𝑗𝑗 −1 +𝑗𝑗
𝑊𝑊4 =
1 −1 1 −1
1 +𝑗𝑗 −1 −𝑗𝑗
12
Discrete Fourier Transform [DFT]
Example-1
1 1 1 1
1 −𝑗𝑗 −1 +𝑗𝑗
𝑊𝑊4 =
1 −1 1 −1
1 +𝑗𝑗 −1 −𝑗𝑗
Note that there are only 4 unique values in 𝑊𝑊4 matrix. FFT will eliminate or minimize this
redundancy
An N-point DFT will have ‘N’ unique values in 𝑁𝑁x𝑁𝑁 transformation matrix
13
Discrete Fourier Transform [DFT]
Example-1
0 0 0 1 0 2 0 3
𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒
1 0 1 1 1 2 1 3
𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒
𝑊𝑊4 = 2 0 2 1 2 2 2 3
𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒
3 0 3 1 3 2 3 3
𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒 𝑊𝑊𝟒𝟒
15
Discrete Fourier Transform [DFT]
Example-1
1 1 1 1
1 −𝑗𝑗 −1 +𝑗𝑗
𝑊𝑊4 =
1 −1 1 −1
1 +𝑗𝑗 −1 −𝑗𝑗
16
Discrete Fourier Transform [DFT]
Example-2
Compute 4 point DFT of the given discrete time signal
0 1 2 3
𝑥𝑥 𝑛𝑛 = 1 , 1 ,0 ,0
↑
17
Discrete Fourier Transform [DFT]
Example-2
𝑋𝑋𝑁𝑁 = 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 𝑥𝑥𝑁𝑁
𝑘𝑘𝑛𝑛
𝑋𝑋4 = 𝑊𝑊4 𝑥𝑥4
1 1 1 1
𝑋𝑋 0 𝑥𝑥 0
1 −𝑗𝑗 −1 +𝑗𝑗
𝑋𝑋 1 𝑥𝑥 1
=
𝑋𝑋 2 𝑥𝑥 2
1 −1 1 −1
𝑋𝑋 3 𝑥𝑥 3
1 +𝑗𝑗 −1 −𝑗𝑗
18
Discrete Fourier Transform [DFT]
Example-2
1 1 1 1
𝑋𝑋 0 1
1 −𝑗𝑗 −1 +𝑗𝑗
𝑋𝑋 1 1
=
𝑋𝑋 2 0
1 −1 1 −1
𝑋𝑋 3 0
1 +𝑗𝑗 −1 −𝑗𝑗
19
Discrete Fourier Transform [DFT]
Example-2
𝑋𝑋 0 1+1+0+0
𝑋𝑋 1 1 − 𝑗𝑗 + 0 + 0
=
𝑋𝑋 2 1−1+0+0
𝑋𝑋 3 1 + 𝑗𝑗 + 0 + 0
𝑋𝑋 0 2
𝑋𝑋 1 1 − 𝑗𝑗
=
𝑋𝑋 2 0
𝑋𝑋 3 1 + 𝑗𝑗
0 1 2 3
𝑋𝑋 𝑘𝑘 = 2 , (1 − 𝑗𝑗) , 0 , (1 + 𝑗𝑗)
↑
20
Discrete Fourier Transform [DFT]
Example-3
Find 𝑥𝑥 𝑛𝑛 for
0 1 2 3
𝑋𝑋 𝑘𝑘 = 2 , (1 − 𝑗𝑗) , 0 , (1 + 𝑗𝑗)
↑
21
Discrete Fourier Transform [DFT]
Example-3 −1
�𝑁𝑁 = 𝑾𝑾𝑁𝑁 𝑘𝑘𝑛𝑛
𝒙𝒙 � 𝑁𝑁
𝑿𝑿
1 𝑘𝑘𝑛𝑛 ∗
�𝑁𝑁 =
𝒙𝒙 𝑾𝑾𝑁𝑁 � 𝑁𝑁
𝑿𝑿
𝑁𝑁
1 𝑘𝑘𝑛𝑛 ∗
𝑥𝑥4 = 𝑊𝑊4 𝑋𝑋4
4
∗
1 1 1 1
𝑥𝑥 0 𝑋𝑋 0
1 −𝑗𝑗 −1 +𝑗𝑗
𝑥𝑥 1 1 𝑋𝑋 1
=
𝑥𝑥 2 4 𝑋𝑋 2
1 −1 1 −1
𝑥𝑥 3 𝑋𝑋 3
1 +𝑗𝑗 −1 −𝑗𝑗
22
Discrete Fourier Transform [DFT]
Example-3 ∗
1 1 1 1
𝑥𝑥 0 2
1 −𝑗𝑗 −1 +𝑗𝑗
𝑥𝑥 1 1 1 − 𝑗𝑗
=
𝑥𝑥 2 4 0
1 −1 1 −1
𝑥𝑥 3 1 + 𝑗𝑗
1 +𝑗𝑗 −1 −𝑗𝑗
1 1 1 1
𝑥𝑥 0 2
1 +𝑗𝑗 −1 −𝑗𝑗
𝑥𝑥 1 1 1 − 𝑗𝑗
=
𝑥𝑥 2 4 0
1 −1 1 −1
𝑥𝑥 3 1 + 𝑗𝑗
1 −𝑗𝑗 −1 +𝑗𝑗
23
Discrete Fourier Transform [DFT]
Example-3
𝑥𝑥 0 2 + 1 − 𝑗𝑗 + 0 + 1 + 𝑗𝑗
𝑥𝑥 1 1 2 + 𝑗𝑗 − 𝑗𝑗 2 − 0 − 𝑗𝑗 − 𝑗𝑗 2
=
𝑥𝑥 2 4 2 − 1 + 𝑗𝑗 + 0 − 1 − 𝑗𝑗
𝑥𝑥 3 2 − 𝑗𝑗 + 𝑗𝑗 2 − 0 + 𝑗𝑗 + 𝑗𝑗 2
𝑥𝑥 0 4
𝑥𝑥 1 1 4
=
𝑥𝑥 2 4 0
𝑥𝑥 3 0
𝑥𝑥 0 1
𝑥𝑥 1 1
=
𝑥𝑥 2 0
𝑥𝑥 3 0
0 1 2 3
𝑥𝑥 𝑛𝑛 = 1 , 1 ,0 ,0
↑
24
Discrete Fourier Transform [DFT]
Properties of DFT Twiddle factors
𝑁𝑁
𝐾𝐾+
Symmetry property 𝑾𝑾𝑁𝑁 2 = − 𝑾𝑾𝑁𝑁 𝑘𝑘
25
Discrete Fourier Transform [DFT]
Proof of Periodicity property
2𝜋𝜋
−𝑗𝑗
𝑾𝑾𝑁𝑁 = 𝑒𝑒 𝑁𝑁
2𝜋𝜋 𝑘𝑘+𝑁𝑁
−𝑗𝑗
𝑾𝑾𝑁𝑁 𝑘𝑘+𝑁𝑁 = 𝑒𝑒 𝑁𝑁
2𝜋𝜋 𝑘𝑘+𝑁𝑁
𝑘𝑘+𝑁𝑁 −𝑗𝑗
𝑾𝑾𝑁𝑁 = 𝑒𝑒 𝑁𝑁
2𝜋𝜋𝑘𝑘 2𝜋𝜋𝑁𝑁
𝑘𝑘+𝑁𝑁 −𝑗𝑗 −𝑗𝑗
𝑾𝑾𝑁𝑁 = 𝑒𝑒 𝑁𝑁 . 𝑒𝑒 𝑁𝑁
2𝜋𝜋𝑘𝑘
𝑘𝑘+𝑁𝑁 −𝑗𝑗
𝑾𝑾𝑁𝑁 = 𝑒𝑒 𝑁𝑁 . 𝑒𝑒 −𝑗𝑗𝑗𝜋𝜋
26
Discrete Fourier Transform [DFT]
Proof of Periodicity property 𝑘𝑘+𝑁𝑁 −𝑗𝑗
2𝜋𝜋𝑘𝑘
𝑾𝑾𝑁𝑁 = 𝑒𝑒 𝑁𝑁 . 𝑒𝑒 −𝑗𝑗𝑗𝜋𝜋
2𝜋𝜋𝑘𝑘
𝑘𝑘+𝑁𝑁 −𝑗𝑗
𝑾𝑾𝑁𝑁 = 𝑒𝑒 𝑁𝑁 . cos 2𝜋𝜋 − 𝑗𝑗 sin 2𝜋𝜋
2𝜋𝜋𝑘𝑘
𝑘𝑘+𝑁𝑁 −𝑗𝑗
𝑾𝑾𝑁𝑁 = 𝑒𝑒 𝑁𝑁 . 1 − 𝑗𝑗𝑗
2𝜋𝜋𝑘𝑘
𝑘𝑘+𝑁𝑁 −𝑗𝑗
𝑾𝑾𝑁𝑁 = 𝑒𝑒 𝑁𝑁
27
Discrete Fourier Transform [DFT]
Proof of Symmetry property
𝑁𝑁
𝐾𝐾+
Symmetry property 𝑾𝑾𝑁𝑁 2 = − 𝑾𝑾𝑁𝑁 𝑘𝑘
2𝜋𝜋
−𝑗𝑗
𝑾𝑾𝑁𝑁 = 𝑒𝑒 𝑁𝑁
𝑁𝑁
𝑁𝑁 2𝜋𝜋 𝑘𝑘+ 2
𝐾𝐾+
𝑾𝑾𝑁𝑁 2 = 𝑒𝑒 −𝑗𝑗 𝑁𝑁
𝑁𝑁
𝑁𝑁 2𝜋𝜋 𝑘𝑘+
𝐾𝐾+ −𝑗𝑗 2
𝑾𝑾𝑁𝑁 2 = 𝑒𝑒 𝑁𝑁
𝑁𝑁 𝑁𝑁
2𝜋𝜋𝑘𝑘 2𝜋𝜋
𝐾𝐾+ −𝑗𝑗 −𝑗𝑗 2
𝑾𝑾𝑁𝑁 2 = 𝑒𝑒 𝑁𝑁 . 𝑒𝑒 𝑁𝑁
𝑁𝑁 2𝜋𝜋𝑘𝑘
𝐾𝐾+ −𝑗𝑗
𝑾𝑾𝑁𝑁 2 = 𝑒𝑒 𝑁𝑁 . 𝑒𝑒 −𝑗𝑗𝜋𝜋
28
Discrete Fourier Transform [DFT]
Proof of Symmetry property 𝑁𝑁
𝐾𝐾+ 2𝜋𝜋𝑘𝑘
−𝑗𝑗
𝑾𝑾𝑁𝑁 2 = 𝑒𝑒 𝑁𝑁 . 𝑒𝑒 −𝑗𝑗𝜋𝜋
𝑁𝑁 2𝜋𝜋𝑘𝑘
𝐾𝐾+ −𝑗𝑗
𝑾𝑾𝑁𝑁 2 = 𝑒𝑒 𝑁𝑁 . cos 𝜋𝜋 − 𝑗𝑗 sin 𝜋𝜋
𝑁𝑁 2𝜋𝜋𝑘𝑘
𝐾𝐾+ −𝑗𝑗
𝑾𝑾𝑁𝑁 2 = 𝑒𝑒 𝑁𝑁 . −1 − 𝑗𝑗𝑗
𝑁𝑁 2𝜋𝜋𝑘𝑘
𝐾𝐾+ −𝑗𝑗
𝑾𝑾𝑁𝑁 2 = − 𝑒𝑒 𝑁𝑁
𝑁𝑁
𝐾𝐾+
𝑾𝑾𝑁𝑁 2 = − 𝑾𝑾𝑁𝑁 𝑘𝑘
Let 𝑁𝑁 = 4 𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘 = 0 Let 𝑁𝑁 = 4 𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘 = 2
𝑾𝑾4 2 = −𝑾𝑾4 0 𝑾𝑾4 4 = −𝑾𝑾4 2
Let 𝑁𝑁 = 4 𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘 = 1 Let 𝑁𝑁 = 4 𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘 = 3
𝑾𝑾4 3 = −𝑾𝑾41 𝑾𝑾4 5 = −𝑾𝑾4 3
29
Discrete Fourier Transform [DFT]
Example
Compute numeric values of 𝑊𝑊4 transformation matrix using periodicity
and symmetry properties
1 1 1 1
1 −𝑗𝑗 −1 +𝑗𝑗
𝑊𝑊4 =
1 −1 1 −1
1 +𝑗𝑗 −1 −𝑗𝑗
30
EE-394 Digital Signal Processing
TE (EE) Fall 2020
Resource Persons: Dr. Saad Ahmed Qazi
Nabeel Fayyaz
Muhammad Omar
Fast Fourier Transform [FFT]
FFT: A faster way to compute DFT
Note:
2
Fast Fourier Transform [FFT]
Why FFT is required?
3
Fast Fourier Transform [FFT]
Need for Speed
4
Fast Fourier Transform [FFT]
5
Fast Fourier Transform [FFT]
Condition of FFT (Radix-2)
i.e. 𝑁𝑁 = 2𝑘𝑘
where 𝑘𝑘 = 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖
6
Fast Fourier Transform [FFT]
Condition of FFT (Radix-2)
If the length of signal is not in a power of 2
Select any 8 consecutive samples to apply 8 point FFT and discard the
remaining samples
• Loss of information
• Degradation in the resultant frequency resolution because
𝐹𝐹𝑠𝑠
↑ ∆𝐹𝐹 =
𝑁𝑁 ↓
7
Fast Fourier Transform [FFT]
Condition of FFT (Radix-2)
We can pad any number of zeros to get the desired value of 𝑁𝑁 = 2𝑘𝑘
8
Fast Fourier Transform [FFT]
Radix-2 FFT algorithm
9
Fast Fourier Transform [FFT]
Radix-2 FFT algorithm
10
Fast Fourier Transform [FFT]
Radix-2 FFT algorithm
11
Fast Fourier Transform [FFT]
Radix-2 FFT algorithm
12
Fast Fourier Transform [FFT]
Radix-2 FFT algorithm
13
Fast Fourier Transform [FFT]
Radix-2 FFT algorithm
15
Fast Fourier Transform [FFT]
Radix-2 FFT algorithm
𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 = 𝑁𝑁 2
16
Fast Fourier Transform [FFT]
Radix-2 FFT algorithm
17
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
𝑁𝑁−1
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
𝑛𝑛=0
18
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
Let 𝑁𝑁 = 8 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
𝑁𝑁−1
� 𝑥𝑥 𝑛𝑛
𝑛𝑛=0
19
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
Let 𝑁𝑁 = 8 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
𝑁𝑁−1
� 𝑥𝑥 𝑛𝑛
𝑛𝑛=0
𝑁𝑁
−1
2
� 𝑥𝑥 2𝑛𝑛
𝑛𝑛=0
+
𝑁𝑁
−1
2
� 𝑥𝑥 2𝑛𝑛 + 1
𝑛𝑛=0
20
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑗𝑗𝑗𝜋𝜋𝑘𝑘(2𝑛𝑛) 𝑗𝑗𝑗𝜋𝜋𝑘𝑘(2𝑛𝑛+1)
− −
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑒𝑒 𝑁𝑁 + � 𝑥𝑥 2𝑛𝑛 + 1 𝑒𝑒 𝑁𝑁
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑗𝑗𝑗𝜋𝜋𝑘𝑘(2𝑛𝑛) 𝑗𝑗𝑗𝜋𝜋𝑘𝑘(2𝑛𝑛) 𝑗𝑗𝑗𝜋𝜋𝑘𝑘
− − −
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑒𝑒 𝑁𝑁 + � 𝑥𝑥 2𝑛𝑛 + 1 𝑒𝑒 𝑁𝑁 𝑒𝑒 𝑁𝑁
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑗𝑗𝑗𝜋𝜋𝑘𝑘(2𝑛𝑛) 𝑗𝑗𝑗𝜋𝜋𝑘𝑘 𝑗𝑗𝑗𝜋𝜋𝑘𝑘(2𝑛𝑛)
− − −
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑒𝑒 𝑁𝑁 + 𝑒𝑒 𝑁𝑁 � 𝑥𝑥 2𝑛𝑛 + 1 𝑒𝑒 𝑁𝑁
𝑛𝑛=0 𝑛𝑛=0
2𝜋𝜋
−𝑗𝑗
Since 𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 2𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 2𝑘𝑘𝑛𝑛
𝑛𝑛=0 𝑛𝑛=0
21
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 2𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 2𝑘𝑘𝑛𝑛
𝑛𝑛=0 𝑛𝑛=0
2𝜋𝜋
−𝑗𝑗
Since 𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁
2𝜋𝜋
−𝑗𝑗
𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁/2
2
and
2𝜋𝜋 2
2 −𝑗𝑗
𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁
2𝜋𝜋 2
2 −𝑗𝑗
𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁
2𝜋𝜋
2 −𝑗𝑗
𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁/2
22
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 2𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 2𝑘𝑘𝑛𝑛
𝑛𝑛=0 𝑛𝑛=0
2𝜋𝜋
2 −𝑗𝑗
𝑊𝑊𝑁𝑁 = 𝑊𝑊𝑁𝑁 = 𝑒𝑒 𝑁𝑁/2
2
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2 2
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2 2
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑁𝑁
𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑘𝑘 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷
2 2
23
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 → (𝐴𝐴)
2 2
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑁𝑁
In equation(A), each of the two point DFTs are periodic in ‘𝑘𝑘’ with period
2 2
𝑁𝑁 𝑁𝑁
So we have two summations whose results can be combined to get the first samples of an
2 2
N-point DFT
𝑁𝑁 𝑁𝑁
For the remaining samples of an N-point DFT output, we will run equation (A) for 𝑘𝑘 +
2 2
24
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 → (𝐴𝐴)
2 2
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑁𝑁
Consider 𝑋𝑋 𝑘𝑘 + output. If we put 𝑘𝑘 + for 𝑘𝑘 in equation(A)
2 2
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑁𝑁 𝑘𝑘+
𝑁𝑁
𝑛𝑛 𝑘𝑘+
𝑁𝑁
𝑘𝑘+
𝑁𝑁
𝑛𝑛
𝑋𝑋 𝑘𝑘 + = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 2 + 𝑊𝑊𝑁𝑁 2 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 2
2 2 2
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑁𝑁 2𝜋𝜋 𝑁𝑁
𝑘𝑘+ 𝑛𝑛 𝑛𝑛 −𝑗𝑗
𝑊𝑊𝑁𝑁 2 = 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
𝑊𝑊𝑁𝑁 2 = 𝑊𝑊𝑁𝑁 [𝑒𝑒𝑘𝑘𝑛𝑛 𝑁𝑁/2 ] 2 𝑛𝑛 = 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 𝑒𝑒 −𝑗𝑗𝑗𝜋𝜋𝑛𝑛 = 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 [1]=𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2 2 2 2 2 2 2
−𝑗𝑗𝑗𝜋𝜋𝑛𝑛
𝑒𝑒 = cos 2𝜋𝜋𝑛𝑛 − 𝑗𝑗 sin 2𝜋𝜋𝑛𝑛 = 1
𝑁𝑁
𝑘𝑘+ 𝑛𝑛
𝑊𝑊𝑁𝑁 2 = 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2 2
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑁𝑁 𝑘𝑘+
𝑁𝑁
𝑋𝑋 𝑘𝑘 + = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 2 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 → (𝐵𝐵)
2 2 2
𝑛𝑛=0 𝑛𝑛=0
25
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑁𝑁 𝑘𝑘+
𝑁𝑁
𝑋𝑋 𝑘𝑘 + = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 2 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 → (𝐵𝐵)
2 2 2
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑁𝑁 2𝜋𝜋 𝑁𝑁
𝑘𝑘+ 𝑘𝑘 𝑘𝑘 −𝑗𝑗
𝑊𝑊𝑁𝑁 2 = 𝑊𝑊𝑁𝑁 𝑊𝑊𝑁𝑁 2 = 𝑊𝑊𝑁𝑁 [𝑒𝑒 𝑁𝑁 ] 2 = 𝑊𝑊𝑁𝑁 𝑘𝑘 𝑒𝑒 −𝑗𝑗𝜋𝜋 = 𝑊𝑊𝑁𝑁 𝑘𝑘 [−1]=−𝑊𝑊𝑁𝑁 𝑘𝑘
𝑁𝑁
𝑘𝑘+
𝑊𝑊𝑁𝑁 2 = −𝑊𝑊𝑁𝑁 𝑘𝑘
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑁𝑁
𝑋𝑋 𝑘𝑘 + = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 −𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 → (𝐶𝐶)
2 2 2
𝑛𝑛=0 𝑛𝑛=0
26
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 → (𝐴𝐴)
2 2
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑁𝑁
𝑋𝑋 𝑘𝑘 + = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 −𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 → (𝐶𝐶)
2 2 2
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁
𝑋𝑋 𝑘𝑘 + = 𝐴𝐴(𝑘𝑘) − 𝑊𝑊𝑁𝑁 𝑘𝑘 𝐵𝐵(𝑘𝑘) → (2)
2
𝑁𝑁
𝑘𝑘 = 0, 1, 2, … … , −1
2
27
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
𝑁𝑁 𝑁𝑁
𝑁𝑁 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 = 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑘𝑘 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷
2 2
𝑁𝑁 𝑁𝑁
𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷
2 2
28
Fast Fourier Transform [FFT]
Radix-2 FFT derivation
𝑁𝑁 𝑘𝑘 𝑁𝑁
𝑁𝑁 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 = 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷
2 2
𝑁𝑁 𝑁𝑁 𝑁𝑁 𝑁𝑁
𝑁𝑁 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 = 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑘𝑘 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑘𝑘 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑘𝑘 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷
4 2 4 4 2 4
𝑁𝑁 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷
𝑁𝑁 𝑘𝑘 𝑁𝑁 𝑘𝑘 𝑁𝑁 𝑘𝑘 𝑁𝑁
= 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷
8 4 8 2 8 4 8
𝑁𝑁 𝑁𝑁 𝑁𝑁 𝑁𝑁
+ 𝑊𝑊𝑁𝑁 𝑘𝑘 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑘𝑘 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑘𝑘 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷 + 𝑊𝑊𝑁𝑁 𝑘𝑘 𝑝𝑝𝑝𝑝 𝐷𝐷𝐷𝐷𝐷𝐷
8 4 8 2 8 4 8
29
Fast Fourier Transform [FFT]
Calculation of Twiddle factors
2𝜋𝜋 0
0 −𝑗𝑗
𝑊𝑊8 = 𝑒𝑒 8 = 1∠0° = 1
2𝜋𝜋 1
1 −𝑗𝑗
𝑊𝑊8 = 𝑒𝑒 8 = 1∠−45° = 0.707 − 𝑗𝑗𝑗.707
2𝜋𝜋 2
2 −𝑗𝑗
𝑊𝑊8 = 𝑒𝑒 8 = 1∠−90° = −𝑗𝑗
2𝜋𝜋 3
−𝑗𝑗
𝑊𝑊8 3 = 𝑒𝑒 8 = 1∠−135° = −0.707 − 𝑗𝑗𝑗.707
30
Fast Fourier Transform [FFT]
Calculation of Twiddle factors
2𝜋𝜋 4
4 −𝑗𝑗
𝑊𝑊8 = 𝑒𝑒 8 = 1∠−180° = −1
2𝜋𝜋 5
5 −𝑗𝑗
𝑊𝑊8 = 𝑒𝑒 8 = 1∠−225° = −0.707 + 𝑗𝑗𝑗.707
2𝜋𝜋 6
6 −𝑗𝑗
𝑊𝑊8 = 𝑒𝑒 8 = 1∠−270° = +𝑗𝑗
2𝜋𝜋 7
−𝑗𝑗
𝑊𝑊8 7 = 𝑒𝑒 8 = 1∠−315° = 0.707 + 𝑗𝑗𝑗.707
31
Fast Fourier Transform [FFT]
Calculation of Twiddle factors
360° 360°
= = 45°
𝑁𝑁 8
32
Fast Fourier Transform [FFT]
Calculation of Twiddle factors
𝑊𝑊𝑁𝑁 𝑘𝑘 Twiddle factors
2
2𝜋𝜋 0
−𝑗𝑗
𝑊𝑊4 0 = 𝑒𝑒 4 = 1∠0° = 1
2𝜋𝜋 1
1 −𝑗𝑗
𝑊𝑊4 = 𝑒𝑒 4 = 1∠−90° = −𝑗𝑗
2𝜋𝜋 2
2 −𝑗𝑗
𝑊𝑊4 = 𝑒𝑒 4 = 1∠−180° = −1
2𝜋𝜋 3
−𝑗𝑗
𝑊𝑊4 3 = 𝑒𝑒 4 = 1∠−270° = +𝑗𝑗
33
Fast Fourier Transform [FFT]
Calculation of Twiddle factors
360° 360°
= = 90°
𝑁𝑁 4
34
Fast Fourier Transform [FFT]
Calculation of Twiddle factors
𝑊𝑊𝑁𝑁 𝑘𝑘 Twiddle factors
4
2𝜋𝜋 0
0 −𝑗𝑗
𝑊𝑊2 = 𝑒𝑒 2 = 1∠0° = 1
2𝜋𝜋 1
1 −𝑗𝑗
𝑊𝑊2 = 𝑒𝑒 2 = 1∠−180° = −1
35
Fast Fourier Transform [FFT]
Calculation of Twiddle factors
360° 360°
= = 180°
𝑁𝑁 2
36
Fast Fourier Transform [FFT]
Calculation of Twiddle factors
𝑊𝑊𝑁𝑁 𝑘𝑘 , 𝑊𝑊𝑁𝑁 𝑘𝑘 , 𝑊𝑊𝑁𝑁 𝑘𝑘 Twiddle factors
2 4
37
EE-394 Digital Signal Processing
TE (EE) Fall 2020
Resource Persons: Dr. Saad Ahmed Qazi
Nabeel Fayyaz
Muhammad Omar
Fast Fourier Transform [FFT]
Radix-2 FFT
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 𝑘𝑘 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 → (𝐴𝐴)
2 2
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑁𝑁
−1 −1
2 2
𝑁𝑁 𝑘𝑘+
𝑁𝑁
𝑋𝑋 𝑘𝑘 + = � 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 + 𝑊𝑊𝑁𝑁 2 � 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛 → (𝐵𝐵)
2 2 2
𝑛𝑛=0 𝑛𝑛=0
𝑁𝑁 𝑘𝑘+
𝑁𝑁
𝑋𝑋 𝑘𝑘 + = 𝐴𝐴(𝑘𝑘) + 𝑊𝑊𝑁𝑁 2 𝐵𝐵(𝑘𝑘) → (2)
2
𝑁𝑁
𝑘𝑘 = 0, 1, 2, … … , −1
2
2
Fast Fourier Transform [FFT]
Calculation of Twiddle factors
𝑊𝑊𝑁𝑁 𝑘𝑘 , 𝑊𝑊𝑁𝑁 𝑘𝑘 , 𝑊𝑊𝑁𝑁 𝑘𝑘 Twiddle factors
2 4
3
Fast Fourier Transform [FFT]
4
Fast Fourier Transform [FFT]
8- point FFT implementation using two 4-point DFTs
𝑁𝑁
2 −1
� 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
𝑁𝑁
−1
2
� 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
5
Fast Fourier Transform [FFT]
8- point FFT implementation using two 4-point DFTs
𝑁𝑁
2 −1
� 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
𝑁𝑁
−1
2
� 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
6
Fast Fourier Transform [FFT]
8- point FFT implementation using two 4-point DFTs
𝑁𝑁
2 −1
� 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
𝑁𝑁
−1
2
� 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
7
Fast Fourier Transform [FFT]
8- point FFT implementation using two 4-point DFTs
𝑁𝑁
2 −1
� 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
𝑁𝑁
−1
2
� 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
8
Fast Fourier Transform [FFT]
8- point FFT implementation using two 4-point DFTs
𝑁𝑁
2 −1
� 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
𝑁𝑁
−1
2
� 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
9
Fast Fourier Transform [FFT]
8- point FFT implementation using two 4-point DFTs
𝑁𝑁
2 −1
� 𝑥𝑥 2𝑛𝑛 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
𝑁𝑁
−1
2
� 𝑥𝑥 2𝑛𝑛 + 1 𝑊𝑊𝑁𝑁 𝑘𝑘𝑛𝑛
2
𝑛𝑛=0
10
Fast Fourier Transform [FFT]
11
Fast Fourier Transform [FFT]
8- point FFT implementation using four 2-point DFTs and two 4-point DFTs
12
Fast Fourier Transform [FFT]
8- point FFT implementation using four 2-point DFTs and two 4-point DFTs
13
Fast Fourier Transform [FFT]
8- point FFT implementation using four 2-point DFTs and two 4-point DFTs
14
Fast Fourier Transform [FFT]
8- point FFT implementation using four 2-point DFTs and two 4-point DFTs
15
Fast Fourier Transform [FFT]
8- point FFT implementation using four 2-point DFTs and two 4-point DFTs
16
Fast Fourier Transform [FFT]
8- point FFT implementation using four 2-point DFTs and two 4-point DFTs
17
Fast Fourier Transform [FFT]
8- point FFT implementation using four 2-point DFTs and two 4-point DFTs
18
Fast Fourier Transform [FFT]
8- point FFT implementation using four 2-point DFTs and two 4-point DFTs
19
Fast Fourier Transform [FFT]
20
Fast Fourier Transform [FFT]
Single Point DFT or 1-point DFT
0
Consider 𝑥𝑥 𝑛𝑛 = 𝑎𝑎
↑
Apply Analysis Equation of DFT
𝑁𝑁−1
𝑗𝑗𝑗𝜋𝜋𝑘𝑘𝑛𝑛
−
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 𝑁𝑁
𝑛𝑛=0
0
𝑗𝑗𝑗𝜋𝜋𝑘𝑘.0
−
𝑋𝑋 𝑘𝑘 = � 𝑥𝑥 𝑛𝑛 𝑒𝑒 1
𝑛𝑛=0
𝑋𝑋 𝑘𝑘 = 𝑎𝑎 (1)
𝑋𝑋 𝑘𝑘 = 𝑎𝑎
𝑋𝑋 𝑘𝑘 = 𝑥𝑥 𝑛𝑛
21
Fast Fourier Transform
Full Decimation in Time (DIT) structure
[FFT]
22
Fast Fourier Transform [FFT]
Full Decimation in Time (DIT) structure
23
Fast Fourier Transform
Full Decimation in Time (DIT) structure
[FFT]
24
Fast Fourier Transform
Full Decimation in Time (DIT) structure
[FFT]
Butterfly
structure
25
Fast Fourier Transform [FFT]
Example
samples
Take 𝐹𝐹𝑠𝑠 = 8000
sec
26
Fast Fourier Transform [FFT]
Example
Solution
𝑥𝑥 𝑡𝑡 = sin 2𝜋𝜋𝜋𝜋𝜋𝜋𝜋𝜋 + 0.5 sin 2𝜋𝜋2000𝑡𝑡 + 3𝜋𝜋/4
1 sec
𝑇𝑇𝑠𝑠 =
8000 sample
1000 2000
𝑥𝑥 𝑛𝑛 = sin 2𝜋𝜋 𝑛𝑛 + 0.5 sin 2𝜋𝜋 𝑛𝑛 + 3𝜋𝜋/4
8000 8000
1 1
𝑥𝑥 𝑛𝑛 = sin 2𝜋𝜋 𝑛𝑛 + 0.5 sin 2𝜋𝜋 𝑛𝑛 + 3𝜋𝜋/4
8 4
27
Fast Fourier Transform [FFT]
Example
1 1
𝑥𝑥 𝑛𝑛 = sin 2𝜋𝜋 𝑛𝑛 + 0.5 sin 2𝜋𝜋 𝑛𝑛 + 3𝜋𝜋/4
8 4
Put 𝑛𝑛 = 0 − 7 in above equation
𝑥𝑥 0 = 0.3535 𝑥𝑥 1 = 0.3535
𝑥𝑥 2 = 0.6464 𝑥𝑥 3 = 1.0607
𝑥𝑥 4 = 0.3535 𝑥𝑥 5 = −1.0607
𝑥𝑥 6 = −1.3535 𝑥𝑥 7 = −0.3535
28
Fast Fourier Transform [FFT]
Example
29
Fast Fourier Transform [FFT]
30
Fast Fourier Transform [FFT]
Example
31
Fast Fourier Transform [FFT]
Example
𝑋𝑋 0 = 𝐴𝐴 0 + 𝑊𝑊8 0 𝐵𝐵 0 = 0 + 1 0 = 0 ∠0°
32
Fast Fourier Transform [FFT]
𝐹𝐹𝑠𝑠 8000
∆𝐹𝐹 = = = 1000 𝐻𝐻𝐻𝐻
𝑁𝑁 8
33
Fast Fourier Transform [FFT]
Data Shuffling and Bit Reversal
The shuffling of the input data is known as bit reversal because the scrambled
order of the input data index can be obtained by reversing the bits of the binary
representation of the normal input data index order
The most significant bit becomes the least significant bit and the least significant
bit becomes the most significant bit
34
Fast Fourier Transform [FFT]
Data Shuffling and Bit Reversal
35
Fast Fourier Transform [FFT]
Data Shuffling and Bit Reversal
36
Fast Fourier Transform [FFT]
Data Shuffling and Bit Reversal
37
Fast Fourier Transform [FFT]
Data Shuffling and Bit Reversal
38
EE-394 Digital Signal Processing
TE (EE) Fall 2020
Resource Persons: Dr. Saad Ahmed Qazi
Nabeel Fayyaz
Muhammad Omar
Fast Fourier Transform [FFT]
2
Fast Fourier Transform [FFT]
3
Fast Fourier Transform [FFT]
4
Fast Fourier Transform [FFT]
Radix-2 FFT 𝑋𝑋 𝑘𝑘 = 𝐴𝐴(𝑘𝑘) + 𝑊𝑊𝑁𝑁 𝑘𝑘 𝐵𝐵(𝑘𝑘) → (1)
𝑁𝑁 𝑘𝑘+
𝑁𝑁
𝑋𝑋 𝑘𝑘 + = 𝐴𝐴(𝑘𝑘) + 𝑊𝑊𝑁𝑁 2 𝐵𝐵(𝑘𝑘) → 2
2
or
𝑁𝑁
𝑋𝑋 𝑘𝑘 + = 𝐴𝐴(𝑘𝑘) −𝑊𝑊𝑁𝑁 𝑘𝑘 𝐵𝐵(𝑘𝑘) → (3)
2
𝑁𝑁
𝑘𝑘 = 0, 1, 2, … … , − 1
2
Substitute 𝑁𝑁 = 8 𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘 = 0
𝑋𝑋 0 = 𝐴𝐴(0) + 𝑊𝑊8 0 𝐵𝐵(0) → (1)
5
Fast Fourier Transform [FFT]
Computational Analysis of N-point Radix-2 FFT
A single 2-point Butterfly structure: The FFT building block
There are two twiddle factors in each 2-point butterfly structure which
are
𝑘𝑘+𝑁𝑁/2
𝑊𝑊𝑁𝑁𝑘𝑘 𝑎𝑎𝑎𝑎𝑎𝑎 𝑊𝑊𝑁𝑁
6
Fast Fourier Transform [FFT]
Computational Analysis of N-point Radix-2 FFT
7
Fast Fourier Transform [FFT]
Computational Analysis of N-point Radix-2 FFT
8
Fast Fourier Transform [FFT]
Property of Twiddle factors
𝑁𝑁
𝑘𝑘 𝐾𝐾+
There are two twiddle factors 𝑾𝑾𝑁𝑁 and 𝑾𝑾𝑁𝑁 2
in each 2-point butterfly structure
which differ from each other by a negative sign only because of
𝑁𝑁
𝐾𝐾+
Symmetry property 𝑾𝑾𝑁𝑁 2 = − 𝑾𝑾𝑁𝑁 𝑘𝑘
For example,
9
Fast Fourier Transform [FFT]
Computational Analysis of N-point Radix-2 FFT
10
Fast Fourier Transform [FFT]
Computational Analysis of N-point Radix-2 FFT
11
Fast Fourier Transform [FFT]
Computational Analysis of N-point Radix-2 FFT
A single 2-point Optimized Butterfly structure
13
Fast Fourier Transform [FFT]
14
Fast Fourier Transform [FFT]
Computational Analysis of N-point Radix-2 FFT
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 = 𝑙𝑙𝑙𝑙𝑙𝑙2 𝑁𝑁
𝑁𝑁
𝑁𝑁𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢 𝑜𝑜𝑜𝑜 𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 𝑝𝑝𝑝𝑝𝑝𝑝 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 =
2
𝑁𝑁
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑜𝑜𝑜𝑜 𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 𝑖𝑖𝑖𝑖 𝑁𝑁 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅 − 2 𝐹𝐹𝐹𝐹𝐹𝐹 = 𝑙𝑙𝑙𝑙𝑙𝑙2 𝑁𝑁
2
𝑁𝑁
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑜𝑜𝑜𝑜 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 = 𝑙𝑙𝑙𝑙𝑙𝑙2 𝑁𝑁
2
𝑁𝑁
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑜𝑜𝑜𝑜 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 = 𝑙𝑙𝑙𝑙𝑙𝑙2 𝑁𝑁 + 𝑁𝑁𝑙𝑙𝑙𝑙𝑙𝑙2 𝑁𝑁
2
3𝑁𝑁
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑜𝑜𝑜𝑜 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 = 𝑙𝑙𝑙𝑙𝑙𝑙2 𝑁𝑁
2
15
Fast Fourier Transform [FFT]
Computational Analysis of N-point Radix-2 FFT
𝑁𝑁
𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑜𝑜𝑜𝑜 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 = 2 𝑙𝑙𝑙𝑙𝑙𝑙2 𝑁𝑁 + 2 𝑁𝑁𝑙𝑙𝑙𝑙𝑙𝑙2 𝑁𝑁
2
16
Fast Fourier Transform [FFT]
Computational Analysis of N-point Radix-2 FFT
𝑁𝑁𝑙𝑙𝑙𝑙𝑙𝑙2 𝑁𝑁
17
Fast Fourier Transform [FFT]
Comparison of DFT and FFT Computations (Complex Multiplications)
18
Fast Fourier Transform [FFT]
Computational Analysis of N-point Radix-2 FFT
Speed Improvement Factor {SIF}
𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑜𝑜𝑜𝑜 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑖𝑖𝑖𝑖 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 𝐷𝐷𝐷𝐷𝐷𝐷
SIF =
𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁 𝑜𝑜𝑜𝑜 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑖𝑖𝑖𝑖 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅 2 𝐹𝐹𝐹𝐹𝐹𝐹
𝑋𝑋
SIF =
𝑌𝑌
SIF shows how many times FFT algorithm is faster than DFT. In other words it indicates
the factor by which speed is improved in calculation of Fourier Transform
19
Fast Fourier Transform [FFT]
Example: Computational Analysis of N-point Radix-2 FFT
a) N= 1024 samples
b) N=2 samples
𝑋𝑋 − 𝑌𝑌
%𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑖𝑖𝑖𝑖 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 = × 100
𝑋𝑋
20
Fast Fourier Transform [FFT]
Example: Computational Analysis of N-point Radix-2 FFT
Solution
a) N= 1024 samples
8𝑁𝑁 2 − 2𝑁𝑁
SIF =
5𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁2 𝑁𝑁
8 1024 2 − 2 1024
SIF =
5 1024 𝑙𝑙𝑙𝑙𝑙𝑙2 1024
8386560
SIF =
51200
21
Fast Fourier Transform [FFT]
Example: Computational Analysis of N-point Radix-2 FFT
Solution
a) N= 1024 samples
𝑋𝑋 − 𝑌𝑌
%𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑖𝑖𝑖𝑖 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 = × 100
𝑋𝑋
8386560 − 51200
%𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑖𝑖𝑖𝑖 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 = × 100
8386560
22
Fast Fourier Transform [FFT]
Example: Computational Analysis of N-point Radix-2 FFT
Solution
b) N=2 samples
8𝑁𝑁 2 − 2𝑁𝑁
SIF =
5𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁2 𝑁𝑁
8 2 2−2 2
SIF =
5 2 𝑙𝑙𝑙𝑙𝑙𝑙2 2
28
SIF =
10
SIF ≈ 3 times
23
Fast Fourier Transform [FFT]
Example: Computational Analysis of N-point Radix-2 FFT
Solution
b) N=2 samples
𝑋𝑋 − 𝑌𝑌
%𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑖𝑖𝑖𝑖 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 = × 100
𝑋𝑋
28 − 10
%𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑖𝑖𝑖𝑖 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 = × 100
28
24
Fast Fourier Transform [FFT]
25
Fast Fourier Transform [FFT]
Computing IFFT using Forward FFT
26
Fast Fourier Transform [FFT]
Computing IFFT using Forward FFT
Steps:
27
Fast Fourier Transform [FFT]
Computing IFFT using Forward FFT
28
Fast Fourier Transform [FFT]
Computing IFFT using Forward FFT
Steps:
29
Fast Fourier Transform [FFT]
Computing IFFT using Forward FFT
Example-1:
By
1) Conjugate Method
2) Swapping Method
30
Fast Fourier Transform [FFT]
Computing IFFT using Forward FFT
Example-2:
By
1) Conjugate Method
2) Swapping Method
31
EE-394 Digital Signal Processing
TE (EE) Fall 2020
Resource Persons: Dr. Saad Ahmed Qazi
Nabeel Fayyaz
Muhammad Omar
Part-C
Discrete-time Systems
2
Discrete time Systems
Discrete Systems
3
Discrete time Systems
Signal-system interaction
Signal-system interaction involving a single-input single-output discrete-time
system is illustrated as:
4
Discrete time Systems
Real-time Processing
• Performs operations on real-time data/live data
• In real-time data, only present and past values of the signal are available at the
time of processing
• In recorded data, all values of the signal are available at the time of processing
5
Discrete time Systems
Difference Equations
❖ Addition
❖ Scalar Multiplication
6
Discrete time Systems
• Time Delay
𝑥 𝑛 original signal
𝑥 𝑛−𝑘 delayed version of original signal 𝑥 𝑛 by ‘k’ samples
7
Discrete time Systems
• Time Delay
Example
−3 −2 −1 0 1 2 3 4 5
𝑥 𝑛 = 1 , 1 , 2 , 3, 4 , 5 , 5 , 5 , 5
↑
−1 0 1 2 3 4 5 6 7
𝑥 𝑛−2 = 1 , 1 , 2 , 3 , 4 , 5 , 5 , 5 , 5
↑
𝑥 𝑛 − 2 means reading the sample values 2 samples before the current one in computer memory (array
or register) of processor
In general,
𝑥 𝑛 − 𝑘 means reading the sample values ‘k’ samples before the current one in computer memory (array
or register) of processor
8
Discrete time Systems
• Time Delay in the case of Recorded data
9
Discrete time Systems
• Time Delay in the case of Real-time data
10
Discrete time Systems
• Time Delay
• Time delay operation is applicable for both real-time and recorded data
• Time delay operation can be used in both real-time processing and post-
processing
11
Discrete time Systems
• Time Advance
𝑥 𝑛 original signal
𝑥 𝑛+𝑘 advanced version of original signal 𝑥 𝑛 by ‘k’ samples
12
Discrete time Systems
• Time Advance
Example
−3 −2 −1 0 1 2 3 4 5
𝑥 𝑛 = 1 , 1 , 2 , 3, 4 , 5 , 5 , 5 , 5
↑
−5 −4 −3 −2 −1 0 1 2 3
𝑥 𝑛+2 = 1 , 1 , 2 , 3 , 4 ,5 , 5 , 5 , 5
↑
𝑥 𝑛 + 2 means reading the sample values 2 samples down in the computer memory (array or
register) of processor
In general,
𝑥 𝑛 + 𝑘 means reading the sample values ‘k’ samples down in the computer memory (array or
register) of processor
13
Discrete time Systems
• Time Advance in the case of Recorded data
14
Discrete time Systems
• Time Advance in the case of Real-time data
15
Discrete time Systems
Time Advance
16
Discrete time Systems
Basic components of Discrete systems
• Adders
• Multipliers
17
Discrete time Systems
Example
For
𝑛, −3 ≤ 𝑛 ≤ 3
𝑥 𝑛 =ቊ
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
1) 𝑦 𝑛 = 𝑥 𝑛
2) 𝑦 𝑛 = 𝑥 𝑛 − 1
3) 𝑦 𝑛 = 𝑥 𝑛 + 1
1
4) 𝑦 𝑛 = 3 𝑥 𝑛 +𝑥 𝑛−1 +𝑥 𝑛+1
5) 𝑦 𝑛 = 𝑚𝑎𝑥 [ 𝑥 𝑛 , 𝑥 𝑛 − 1 , 𝑥 𝑛 + 1 ]
6) 𝑦 𝑛 = σ𝑛𝑘=−∞ 𝑥 𝑘
18
Discrete time Systems
Example
For
𝑛, −3 ≤ 𝑛 ≤ 3
𝑥 𝑛 =ቊ
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
1) 𝑦 𝑛 = 𝑥 𝑛 Identity System
1
4) 𝑦 𝑛 = 3 𝑥 𝑛 +𝑥 𝑛−1 +𝑥 𝑛+1 Moving average system
6) 𝑦 𝑛 = σ𝑛𝑘=−∞ 𝑥 𝑘 Accumulator
19
Discrete time Systems
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
1) 𝑦 𝑛 =𝑥 𝑛
−3 −2 −1 0 1 2 3
𝑦 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
20
Discrete time Systems
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
2) 𝑦 𝑛 = 𝑥 𝑛−1
−2 −1 0 1 2 3 4
𝑦 𝑛 = 3, 2, 1 , 0 ,1 ,2 , 3
↑
21
Discrete time Systems
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
3) 𝑦 𝑛 = 𝑥 𝑛+1
−4 −3 −2 −1 0 1 2
𝑦 𝑛 = 3 , 2 , 1 , 0 ,1, 2 , 3
↑
22
Discrete time Systems
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
1
4) 𝑦 𝑛 = 𝑥 𝑛+1 +𝑥 𝑛 +𝑥 𝑛−1
3
−4 −3 −2 −1 0 1 2
𝑥 𝑛+1 = 3 , 2 , 1 , 0 ,1, 2 , 3
↑ 1 −4 −3 −2 −1 0 1 2 3 4
𝑦 𝑛 = 3 , 5 , 6 , 3 , 2, 3 , 6 , 5 , 3
−3 −2 −1 0 1 2 3 3
↑
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑ −4 −3 −2 −1 0 1 2 3 4
𝑦 𝑛 = 1 , 5/3, 2 , 1 , 2/3 , 1 , 2 , 5/3 , 1
−2 −1 0 1 2 3 4 ↑
𝑥 𝑛−1 = 3 , 2 , 1 , 0 , 1 , 2 , 3
↑
23
Discrete time Systems
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
1
4) 𝑦 𝑛 = 𝑥 𝑛+1 +𝑥 𝑛 +𝑥 𝑛−1
3
1 1
𝑦 −4 = 𝑥 −3 + 𝑥 −4 + 𝑥 −5 = 3+0+0 =1
3 3
1 1
𝑦 −3 = 𝑥 −2 + 𝑥 −3 + 𝑥 −4 = 2 + 3 + 0 = 5/3
3 3
1 1
𝑦 −2 = 𝑥 −1 + 𝑥 −2 + 𝑥 −3 = 1+2+3 = 2
3 3
1 1
𝑦 −1 = 𝑥 0 + 𝑥 −1 + 𝑥 −2 = 0+1+2 = 1
3 3
1 1
𝑦 0 = 𝑥 1 + 𝑥 0 + 𝑥 −1 = 1 + 0 + 1 = 2/3
3 3
1 1
𝑦 1 = 𝑥 2 +𝑥 1 +𝑥 0 = 2+1+0 = 1
3 3
1 1
𝑦 2 = 𝑥 3 +𝑥 2 +𝑥 1 = 3+2+1 = 2
3 3
1 1
𝑦 3 = 𝑥 4 +𝑥 3 +𝑥 2 = 0 + 3 + 2 = 5/3
3 3
1 1
𝑦 4 = 𝑥 5 +𝑥 4 +𝑥 3 = 0+0+3 =1
3 3
24
Discrete time Systems
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
5) 𝑦 𝑛 = 𝑚𝑎𝑥 𝑥 𝑛 +1 , 𝑥 𝑛 ,𝑥 𝑛 −1
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
−2 −1 0 1 2 3 4 −4 −3 −2 −1 0 1 2 3 4
𝑥 𝑛−1 = 3 , 2 , 1 , 0 , 1 , 2 , 3 𝑦 𝑛 = 3 , 3 , 3 , 2 , 1, 2 , 3 , 3 , 3
↑ ↑
−4 −3 −2 −1 0 1 2
𝑥 𝑛+1 = 3 , 2 , 1 , 0 ,1, 2 , 3
↑
25
Discrete time Systems
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
6) 𝑦 𝑛 = σ𝑛𝑘=−∞ 𝑥 𝑘 = 𝑥 𝑛 + 𝑥 𝑛 − 1 + 𝑥 𝑛 − 2 + ⋯
Method-1
• Accumulator is a system which collects all the sample values from −∞ to the current
instant ‘n’ and provides their summation
• Accumulator computes the running sum of all the past input values up to the present
time
−∞ −6 −5 −4 −3 −2 −1 0 1 2 3
𝑥 𝑛 = 0 ……….., 0 , 0 , 0 , 3 , 2 , 1 , 0 , 1 , 2 , 3
↑
26
Discrete time Systems
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
6) 𝑦 𝑛 = σ𝑛𝑘=−∞ 𝑥 𝑘 = 𝑥 𝑛 + 𝑥 𝑛 − 1 + 𝑥 𝑛 − 2 + ⋯
Method-1
• Accumulator is a system which collects all the sample values from −∞ to the current
instant ‘n’ and provides their summation
• Accumulator computes the running sum of all the past input values up to the present
time
−∞ −6 −5 −4 −3 −2 −1 0 1 2 3
𝑥 𝑛 = 0 ……….., 0 , 0 , 0 , 3 , 2 , 1 , 0 , 1 , 2 , 3
↑
−4 −3 −2 −1 0 1 2 3 4 5
𝑦 𝑛 = 0 , 3 , 5 , 6 , 6 , 7 , 9 , 12 , 12 , 12
↑
27
Discrete time Systems
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
6) 𝑦 𝑛 = σ𝑛𝑘=−∞ 𝑥 𝑘
Method-2
𝐶𝑢𝑟𝑟𝑒𝑛𝑡 𝑜𝑢𝑡𝑝𝑢𝑡 = 𝐶𝑢𝑟𝑟𝑒𝑛𝑡 𝑖𝑛𝑝𝑢𝑡 + 𝑃𝑟𝑒𝑣𝑖𝑜𝑢𝑠 𝑜𝑢𝑡𝑝𝑢𝑡
𝑦 𝑛 = 𝑥 𝑛 +𝑦 𝑛−1
−∞ −6 −5 −4 −3 −2 −1 0 1 2 3
𝑥 𝑛 = 0 ……….., 0 , 0 , 0 , 3 , 2 , 1 , 0 , 1 , 2 , 3
↑
−4 −3 −2 −1 0 1 2 3 4 5
𝑦 𝑛 = 0 , 3 , 5 , 6 , 6 , 7 , 9 , 12 , 12 , 12
↑
28
Discrete time Systems
−3 −2 −1 0 1 2 3
𝑥 𝑛 = 3 , 2 , 1 , 0, 1 , 2 , 3
↑
6) 𝑦 𝑛 = σ𝑛𝑘=−∞ 𝑥 𝑘
Method-2
𝐶𝑢𝑟𝑟𝑒𝑛𝑡 𝑜𝑢𝑡𝑝𝑢𝑡 = 𝐶𝑢𝑟𝑟𝑒𝑛𝑡 𝑖𝑛𝑝𝑢𝑡 + 𝑃𝑟𝑒𝑣𝑖𝑜𝑢𝑠 𝑜𝑢𝑡𝑝𝑢𝑡
𝑦 𝑛 = 𝑥 𝑛 +𝑦 𝑛−1
29
Discrete time Systems
Real-time Processing
• Performs operations on real-time data/live data
• Real time signal processing systems cannot deal with future values of signal i.e.
we can use only present and past values of signal during real-time processing
• In recorded data, all values of the signal are available at the time of processing
• In post processing systems, we can access all values of signal including present,
past and future
30
Discrete time Systems
Example
For the following systems, identify which one can process a signal in real-time?
1) 𝑦 𝑛 = 𝑥 𝑛
2) 𝑦 𝑛 = 𝑥 𝑛 − 1
3) 𝑦 𝑛 = 𝑥 𝑛 + 1
1
4) 𝑦 𝑛 = 3 𝑥 𝑛 +𝑥 𝑛−1 +𝑥 𝑛+1
5) 𝑦 𝑛 = 𝑚𝑎𝑥 [ 𝑥 𝑛 , 𝑥 𝑛 − 1 , 𝑥 𝑛 + 1 ]
6) 𝑦 𝑛 = σ𝑛𝑘=−∞ 𝑥 𝑘
31
Discrete time Systems
Example
For the following systems, identify which one can process a signal in real-time?
1) 𝑦 𝑛 = 𝑥 𝑛 Real-time processing
2) 𝑦 𝑛 = 𝑥 𝑛 − 1 Real-time processing
1
4) 𝑦 𝑛 = 3 𝑥 𝑛 +𝑥 𝑛−1 +𝑥 𝑛+1 Non real-time (Off-line) processing
• Memory Requirement
• Causality
• Stability
• Linearity
• Time invariance
2
Memory Requirement
3
Discrete time Systems
• Memory Requirement (Static Vs. Dynamic Systems)
Static/Stationary/Instantaneous/Memoryless System
A system whose current (present) output 𝑦𝑦 𝑛𝑛 depends only on the present values
(samples) of input
𝑦𝑦 𝑛𝑛 = 𝑓𝑓 [𝑥𝑥 𝑛𝑛 ]
4
Discrete time Systems
• Memory Requirement (Static Vs. Dynamic Systems)
Static/Stationary/Instantaneous/Memoryless System
Examples
𝑦𝑦 𝑛𝑛 = 3𝑥𝑥 𝑛𝑛
𝑦𝑦 𝑛𝑛 = 𝑥𝑥 3 𝑛𝑛 + 2𝑥𝑥 𝑛𝑛
𝑦𝑦 𝑛𝑛 = 𝑥𝑥 2 𝑛𝑛 + 4𝑥𝑥 3 𝑛𝑛 + 𝑥𝑥 𝑛𝑛
5
Discrete time Systems
• Memory Requirement (Static Vs. Dynamic Systems)
𝑦𝑦 𝑛𝑛 = 𝑓𝑓 [𝑥𝑥 𝑛𝑛 − 𝑘𝑘 , 𝑥𝑥 𝑛𝑛 + 𝑘𝑘 ]
6
Discrete time Systems
• Memory Requirement (Static Vs. Dynamic Systems)
Examples
𝑦𝑦 𝑛𝑛 = 2𝑥𝑥 𝑛𝑛 − 1
𝑦𝑦 𝑛𝑛 = 3𝑥𝑥 𝑛𝑛 + 2
𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 − 1 + 4𝑥𝑥 𝑛𝑛 + 2
7
Discrete time Systems
• Memory Requirement (Static Vs. Dynamic Systems)
Key Concept
Only those dynamic systems which depend upon previous values (of input or output) to
compute the current output can support real-time processing
The dynamic systems which depend upon future values of input to compute the current
output cannot support real-time processing
• The higher the order of discrete time (dynamic) system, the more will be the
memory requirement
8
Causality
9
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Causal System
𝑦𝑦 𝑛𝑛 = 𝑓𝑓 [𝑥𝑥 𝑛𝑛 , 𝑥𝑥 𝑛𝑛 − 𝑘𝑘 ]
2) A system whose output cannot occur before the start of input sequence i.e. output
of system cannot happen before the application of input
Note:
• All causal systems can support real-time processing i.e. they can process signal in
real-time. No need to provide recorded data.
10
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Causal System
Examples
𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛
𝑦𝑦 𝑛𝑛 = 2𝑥𝑥 𝑛𝑛 − 1
𝑦𝑦 𝑛𝑛 = 0.1𝑥𝑥 𝑛𝑛 + 0.5𝑥𝑥 𝑛𝑛 − 4
11
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Non Causal System
1) A system whose current (present) output 𝑦𝑦 𝑛𝑛 depends upon future values of input
𝑦𝑦 𝑛𝑛 = 𝑓𝑓 [𝑥𝑥 𝑛𝑛 + 𝑘𝑘 ]
2) A system whose output can occur before the start of input sequence
Note:
• All non causal systems can process recorded data only i.e. processing is done off-line
(non real time)
12
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Examples
𝑦𝑦 𝑛𝑛 = 0.2𝑥𝑥 𝑛𝑛 + 1
𝑦𝑦 𝑛𝑛 = 2𝑥𝑥 𝑛𝑛 − 1 + 3𝑥𝑥 𝑛𝑛 + 2
13
Discrete time Systems
Relation between Memory and Causality
Key Concept
14
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-1
0 1 2
Find the response 𝑦𝑦 𝑛𝑛 of the following systems when 𝑥𝑥 𝑛𝑛 = 3 , 2 , 1 is
↑
applied at the system input:
1) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑥𝑥 𝑛𝑛 − 1
2) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑥𝑥 𝑛𝑛 + 1
15
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-1
1) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑥𝑥 𝑛𝑛 − 1
0 1 2
𝑥𝑥 𝑛𝑛 = 3 , 2 , 1
↑
0 1 2 3
𝑥𝑥 𝑛𝑛 − 1 = 0 , 3 , 2 , 1
↑
0 1 2 3
𝑦𝑦 𝑛𝑛 = 3 , 5 , 3 , 1
↑
16
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-1
2) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑥𝑥 𝑛𝑛 + 1
0 1 2
𝑥𝑥 𝑛𝑛 = 3 , 2 , 1
↑
−1 0 1
𝑥𝑥 𝑛𝑛 + 1 = 3 , 2 , 1
↑
−1 0 1 2
𝑦𝑦 𝑛𝑛 = 3 , 5 , 3 , 1
↑
17
Discrete time Systems
• Causality (Causal Vs. Non-Causal Systems)
Impulse Response
Impulse Response ℎ 𝑛𝑛
18
Discrete time Systems
• Causality (Causal Vs. Non-Causal Systems)
Example-2
1) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑥𝑥 𝑛𝑛 − 1
2) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑥𝑥 𝑛𝑛 + 1
19
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-2
𝑥𝑥 𝑛𝑛 will be replaced by 𝛿𝛿 𝑛𝑛
𝑦𝑦 𝑛𝑛 will be replaced by ℎ 𝑛𝑛
1) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑥𝑥 𝑛𝑛 − 1
ℎ 𝑛𝑛 = 𝛿𝛿 𝑛𝑛 + 𝛿𝛿 𝑛𝑛 − 1
0
𝛿𝛿 𝑛𝑛 = 1
↑
0 1
𝛿𝛿 𝑛𝑛 − 1 = 0 , 1
↑
0 1
h 𝑛𝑛 = 1 , 1
↑
20
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-2
𝑥𝑥 𝑛𝑛 will be replaced by 𝛿𝛿 𝑛𝑛
𝑦𝑦 𝑛𝑛 will be replaced by ℎ 𝑛𝑛
2) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑥𝑥 𝑛𝑛 + 1
ℎ 𝑛𝑛 = 𝛿𝛿 𝑛𝑛 + 𝛿𝛿 𝑛𝑛 + 1
0
𝛿𝛿 𝑛𝑛 = 1
↑
−1 0
𝛿𝛿 𝑛𝑛 + 1 = 1 , 0
↑
−1 0
h 𝑛𝑛 = 1 , 1
↑
21
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-3
Determine whether the given discrete time systems support real-time processing or off-line
processing
0 1 2 3
1) ℎ 𝑛𝑛 = 0.9 , 0.8 , 0.7 , 0.6
↑
−1 0 1 2
2) ℎ 𝑛𝑛 = 0.9 , 0.8 , 0.7 , 0.6
↑
0 1 2 3 4
3) ℎ 𝑛𝑛 = 0 , 0.9 , 0.8 , 0.7 , 0.6
↑
−4 −3 −2 −1 0 1 2 3 4
4) ℎ 𝑛𝑛 = 0 , 0 , 0 , 0 , 0 , 0.9 , 0.8 , 0.7 , 0.6
↑
22
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-3
Determine whether the given discrete time systems support real-time processing or off-line
processing
0 1 2 3
1) ℎ 𝑛𝑛 = 0.9 , 0.8 , 0.7 , 0.6 Causal
↑
−1 0 1 2
2) ℎ 𝑛𝑛 = 0.9 , 0.8 , 0.7 , 0.6 Non Causal
↑
0 1 2 3 4
3) ℎ 𝑛𝑛 = 0 , 0.9 , 0.8 , 0.7 , 0.6 Causal
↑
−4 −3 −2 −1 0 1 2 3 4
4) ℎ 𝑛𝑛 = 0 , 0 , 0 , 0 , 0 , 0.9 , 0.8 , 0.7 , 0.6 Causal
↑
23
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-3
Determine whether the given discrete time systems support real-time processing or off-line
processing
−5 −4 −3 −2 −1 0 1 2 3 4
5) ℎ 𝑛𝑛 = 1 , 0 , 0 , 0 , 0 , 0 , 0.9 , 0.8 , 0.7 , 0.6
↑
0 1 2 3 4
6) 𝑦𝑦 𝑛𝑛 = 1 , 0.9 , 0.8 , 0.7 , 0.6
↑
24
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-3
Determine whether the given discrete time systems support real-time processing or off-line
processing
−5 −4 −3 −2 −1 0 1 2 3 4
5) ℎ 𝑛𝑛 = 1 , 0 , 0 , 0 , 0 , 0 , 0.9 , 0.8 , 0.7 , 0.6 Non Causal
↑
0 1 2 3 4
6) 𝑦𝑦 𝑛𝑛 = 1 , 0.9 , 0.8 , 0.7 , 0.6
↑
Since the given output signal is not representing impulse response of a system , we cannot
conclude system characteristics by just looking at 𝑦𝑦 𝑛𝑛 .
For system description, we need input-output pair. In the above example, the given information is
insufficient to answer the question because we do not know what 𝑥𝑥 𝑛𝑛 has been applied
25
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-3
Determine whether the given discrete time systems support real-time processing or off-line
processing
0 1 2 3 4
7) 𝑦𝑦 𝑛𝑛 = 1 , 0.9 , 0.8 , 0.7 , 0.6
↑
0 1 2 3 4
𝑥𝑥 𝑛𝑛 = 0.1 , 0.2 , 0.3 , 0.4 , 0.5
↑
0 1 2 3 4
8) 𝑦𝑦 𝑛𝑛 = 1 , 0.9 , 0.8 , 0.7 , 0.6
↑
−2 −1 0 1 2
𝑥𝑥 𝑛𝑛 = 0.1 , 0.2 , 0.3 , 0.4 , 0.5
↑
26
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-3
Determine whether the given discrete time systems support real-time processing or off-line
processing
0 1 2 3 4
7) 𝑦𝑦 𝑛𝑛 = 1 , 0.9 , 0.8 , 0.7 , 0.6
↑
0 1 2 3 4
𝑥𝑥 𝑛𝑛 = 0.1 , 0.2 , 0.3 , 0.4 , 0.5 Causal
↑
0 1 2 3 4
8) 𝑦𝑦 𝑛𝑛 = 1 , 0.9 , 0.8 , 0.7 , 0.6
↑
−2 −1 0 1 2
𝑥𝑥 𝑛𝑛 = 0.1 , 0.2 , 0.3 , 0.4 , 0.5 Causal
↑
27
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-3
Determine whether the given discrete time systems support real-time processing or off-line
processing
−2 −1 0 1 2
9) 𝑦𝑦 𝑛𝑛 = 1 , 0.9 , 0.8 , 0.7 , 0.6
↑
−1 0 1 2 3
𝑥𝑥 𝑛𝑛 = 0.1 , 0.2 , 0.3 , 0.4 , 0.5
↑
28
Discrete time Systems
• Causality (Causal Vs. Non Causal Systems)
Example-3
Determine whether the given discrete time systems support real-time processing or off-line
processing
−2 −1 0 1 2
9) 𝑦𝑦 𝑛𝑛 = 1 , 0.9 , 0.8 , 0.7 , 0.6
↑
−1 0 1 2 3
𝑥𝑥 𝑛𝑛 = 0.1 , 0.2 , 0.3 , 0.4 , 0.5 Non Causal
↑
29
Stability
30
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
• A system whose impulse response ℎ 𝑛𝑛 exists for finite amount of time i.e.
impulse response contains finite number of samples
• A system whose current (present) output 𝑦𝑦 𝑛𝑛 does not depend upon the
previous (past) output samples
𝑦𝑦 𝑛𝑛 ≠ 𝑓𝑓 [𝑦𝑦 𝑛𝑛 − 𝑘𝑘 ]
31
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Examples
𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑥𝑥 𝑛𝑛 − 1
𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.7 𝑥𝑥 𝑛𝑛 + 1
𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑥𝑥 𝑛𝑛 − 1 + 0.8 𝑥𝑥 𝑛𝑛 − 2
32
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
• A system whose impulse response ℎ 𝑛𝑛 exists for infinite duration of time i.e.
impulse response contains infinite number of samples
𝑦𝑦 𝑛𝑛 = 𝑓𝑓 [𝑦𝑦 𝑛𝑛 − 𝑘𝑘 ]
33
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Examples
𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑦𝑦 𝑛𝑛 − 1
𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑥𝑥 𝑛𝑛 − 1 + 0.8 𝑦𝑦 𝑛𝑛 − 2
34
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-1
1) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑥𝑥 𝑛𝑛 − 1
2) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑥𝑥 𝑛𝑛 − 1 + 0.8 𝑥𝑥 𝑛𝑛 − 2
35
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-1
36
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-1
1) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑥𝑥 𝑛𝑛 − 1
ℎ 𝑛𝑛 = 𝛿𝛿 𝑛𝑛 + 0.9 𝛿𝛿 𝑛𝑛 − 1
ℎ −2 = 𝛿𝛿 −2 + 0.9 𝛿𝛿 −3 = 0 + 0.9(0) = 0
ℎ −1 = 𝛿𝛿 −1 + 0.9 𝛿𝛿 −2 = 0 + 0.9(0) = 0
ℎ 0 = 𝛿𝛿 0 + 0.9 𝛿𝛿 −1 = 1 + 0.9(0) = 1
ℎ 1 = 𝛿𝛿 1 + 0.9 𝛿𝛿 0 = 0 + 0.9 1 = 0.9
ℎ 2 = 𝛿𝛿 2 + 0.9 𝛿𝛿 1 = 0 + 0.9 0 = 0
ℎ 3 = 𝛿𝛿 3 + 0.9 𝛿𝛿 2 = 0 + 0.9 0 = 0
0 1
h 𝑛𝑛 = 1 , 0.9
↑
37
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-1
1) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑥𝑥 𝑛𝑛 − 1
0 1
h 𝑛𝑛 = 1 , 0.9
↑
Stable
38
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-1
2) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑥𝑥 𝑛𝑛 − 1 + 0.8 𝑥𝑥 𝑛𝑛 − 2
ℎ 𝑛𝑛 = 𝛿𝛿 𝑛𝑛 + 0.9 𝛿𝛿 𝑛𝑛 − 1 + 0.8𝛿𝛿 𝑛𝑛 − 2
0 1 2
h 𝑛𝑛 = 1 , 0.9 , 0.8
↑
39
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-1
2) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑥𝑥 𝑛𝑛 − 1 + 0.8 𝑥𝑥 𝑛𝑛 − 2
0 1 2
h 𝑛𝑛 = 1 , 0.9 , 0.8
↑
Stable
40
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
1) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑦𝑦 𝑛𝑛 − 1
2) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 − 0.9 𝑦𝑦 𝑛𝑛 − 1
3) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑦𝑦 𝑛𝑛 − 1
4) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 − 𝑦𝑦 𝑛𝑛 − 1
5) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 1.1 𝑦𝑦 𝑛𝑛 − 1
6) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 − 1.1 𝑦𝑦 𝑛𝑛 − 1
41
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
42
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
1) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑦𝑦 𝑛𝑛 − 1
ℎ 𝑛𝑛 = 𝛿𝛿 𝑛𝑛 + 0.9 ℎ 𝑛𝑛 − 1
ℎ −2 = 𝛿𝛿 −2 + 0.9 ℎ −3 = 0 + 0.9(0) = 0
ℎ −1 = 𝛿𝛿 −1 + 0.9 ℎ −2 = 0 + 0.9(0) = 0
ℎ 0 = 𝛿𝛿 0 + 0.9 ℎ −1 = 1 + 0.9(0) = 1
ℎ 1 = 𝛿𝛿 1 + 0.9 ℎ 0 = 0 + 0.9 1 = 0.9
ℎ 2 = 𝛿𝛿 2 + 0.9 ℎ 1 = 0 + 0.9 0.9 = 0.81
ℎ 3 = 𝛿𝛿 3 + 0.9 ℎ 2 = 0 + 0.9 0.81 = 0.729
0 1 2 3
h 𝑛𝑛 = 1 , 0.9 , 0.81 , 0.729 , ………
↑
h 𝑛𝑛 = 0.9 𝑛𝑛 𝑢𝑢 𝑛𝑛
43
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
1) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 0.9 𝑦𝑦 𝑛𝑛 − 1
0 1 2 3
h 𝑛𝑛 = 1 , 0.9 , 0.81 , 0.729 , ………
↑
𝑛𝑛
h 𝑛𝑛 = 0.9 𝑢𝑢 𝑛𝑛
Stable
44
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
2) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 − 0.9 𝑦𝑦 𝑛𝑛 − 1
ℎ 𝑛𝑛 = 𝛿𝛿 𝑛𝑛 − 0.9 ℎ 𝑛𝑛 − 1
ℎ −2 = 𝛿𝛿 −2 − 0.9 ℎ −3 = 0 − 0.9(0) = 0
ℎ −1 = 𝛿𝛿 −1 − 0.9 ℎ −2 = 0 − 0.9(0) = 0
ℎ 0 = 𝛿𝛿 0 − 0.9 ℎ −1 = 1 − 0.9(0) = 1
ℎ 1 = 𝛿𝛿 1 − 0.9 ℎ 0 = 0 − 0.9 1 = −0.9
ℎ 2 = 𝛿𝛿 2 − 0.9 ℎ 1 = 0 − 0.9 −0.9 = 0.81
ℎ 3 = 𝛿𝛿 3 − 0.9 ℎ 2 = 0 − 0.9 0.81 = −0.729
0 1 2 3
h 𝑛𝑛 = 1 , −0.9 , 0.81 , −0.729 , ………
↑
h 𝑛𝑛 = −0.9 𝑛𝑛 𝑢𝑢 𝑛𝑛
45
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
2) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 − 0.9 𝑦𝑦 𝑛𝑛 − 1
0 1 2 3
h 𝑛𝑛 = 1 , −0.9 , 0.81 , −0.729 , ………
↑
𝑛𝑛
h 𝑛𝑛 = −0.9 𝑢𝑢 𝑛𝑛
Stable
46
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
3) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑦𝑦 𝑛𝑛 − 1
ℎ 𝑛𝑛 = 𝛿𝛿 𝑛𝑛 + ℎ 𝑛𝑛 − 1
ℎ −2 = 𝛿𝛿
−2 + ℎ −3 = 0 + (0) = 0
ℎ −1 = 𝛿𝛿
−1 + ℎ −2 = 0 + (0) = 0
ℎ 0 = 𝛿𝛿
0 + ℎ −1 = 1 + (0) = 1
ℎ 1 = 𝛿𝛿
1 + ℎ 0 = 0+ 1 =1
ℎ 2 = 𝛿𝛿
2 + ℎ 1 = 0+ 1 =1
ℎ 3 = 𝛿𝛿
3 + ℎ 2 = 0+ 1 =1
0 1 2 3
h 𝑛𝑛 = 1 , 1 , 1 , 1 , ………
↑
h 𝑛𝑛 = 1 𝑛𝑛 𝑢𝑢 𝑛𝑛
47
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
3) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑦𝑦 𝑛𝑛 − 1
0 1 2 3
h 𝑛𝑛 = 1 , 1 , 1 , 1 , ………
↑
𝑛𝑛
h 𝑛𝑛 = 1 𝑢𝑢 𝑛𝑛
Marginally Stable/
Conditionally Stable
48
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
4) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 − 𝑦𝑦 𝑛𝑛 − 1
ℎ 𝑛𝑛 = 𝛿𝛿 𝑛𝑛 − ℎ 𝑛𝑛 − 1
ℎ −2 = 𝛿𝛿 −2 − ℎ −3 = 0 − (0) = 0
ℎ −1 = 𝛿𝛿 −1 − ℎ −2 = 0 − (0) = 0
ℎ 0 = 𝛿𝛿 0 − ℎ −1 = 1 − (0) = 1
ℎ 1 = 𝛿𝛿 1 − ℎ 0 = 0 − 1 = −1
ℎ 2 = 𝛿𝛿 2 − ℎ 1 = 0 − −1 = 1
ℎ 3 = 𝛿𝛿 3 − ℎ 2 = 0 − 1 = −1
0 1 2 3
h 𝑛𝑛 = 1 , −1 , 1 , −1 , ………
↑
h 𝑛𝑛 = −1 𝑛𝑛 𝑢𝑢 𝑛𝑛
49
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
4) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 − 𝑦𝑦 𝑛𝑛 − 1
0 1 2 3
h 𝑛𝑛 = 1 , −1 , 1 , −1 , ………
↑
𝑛𝑛
h 𝑛𝑛 = −1 𝑢𝑢 𝑛𝑛
Marginally Stable/
Conditionally Stable
50
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
5) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 1.1 𝑦𝑦 𝑛𝑛 − 1
ℎ 𝑛𝑛 = 𝛿𝛿 𝑛𝑛 + 1.1 ℎ 𝑛𝑛 − 1
ℎ −2
= 𝛿𝛿 −2 + 1.1 ℎ −3 = 0 + 1.1(0) = 0
ℎ −1
= 𝛿𝛿 −1 + 1.1 ℎ −2 = 0 + 1.1(0) = 0
ℎ 0= 𝛿𝛿 0 + 1.1 ℎ −1 = 1 + 1.1(0) = 1
ℎ 1= 𝛿𝛿 1 + 1.1 ℎ 0 = 0 + 1.1 1 = 1.1
ℎ 2= 𝛿𝛿 2 + 1.1 ℎ 1 = 0 + 1.1 1.1 = 1.21
ℎ 3= 𝛿𝛿 3 + 1.1 ℎ 2 = 0 + 1.1 1.21 = 1.331
0 1 2 3
h 𝑛𝑛 = 1 , 1.1 , 1.21 , 1.331 , ………
↑
h 𝑛𝑛 = 1.1 𝑛𝑛 𝑢𝑢 𝑛𝑛
51
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
5) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 1.1 𝑦𝑦 𝑛𝑛 − 1
0 1 2 3
h 𝑛𝑛 = 1 , 1.1 , 1.21 , 1.331 , ………
↑
𝑛𝑛
h 𝑛𝑛 = 1.1 𝑢𝑢 𝑛𝑛
Unstable
52
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
6) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 − 1.1 𝑦𝑦 𝑛𝑛 − 1
ℎ 𝑛𝑛 = 𝛿𝛿 𝑛𝑛 − 1.1 ℎ 𝑛𝑛 − 1
ℎ −2 = 𝛿𝛿 −2 − 1.1 ℎ −3 = 0 − 1.1(0) = 0
ℎ −1 = 𝛿𝛿 −1 − 1.1 ℎ −2 = 0 − 1.1(0) = 0
ℎ 0 = 𝛿𝛿 0 − 1.1 ℎ −1 = 1 − 1.1(0) = 1
ℎ 1 = 𝛿𝛿 1 − 1.1 ℎ 0 = 0 − 1.1 1 = −1.1
ℎ 2 = 𝛿𝛿 2 − 1.1 ℎ 1 = 0 − 1.1 −1.1 = 1.21
ℎ 3 = 𝛿𝛿 3 − 1.1 ℎ 2 = 0 − 1.1 1.21 = −1.331
0 1 2 3
h 𝑛𝑛 = 1 , −1.1 , 1.21 , −1.331 , ………
↑
h 𝑛𝑛 = −1.1 𝑛𝑛 𝑢𝑢 𝑛𝑛
53
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Example-2
6) 𝑦𝑦 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 − 1.1 𝑦𝑦 𝑛𝑛 − 1
0 1 2 3
h 𝑛𝑛 = 1 , −1.1 , 1.21 , −1.331 , ………
↑
𝑛𝑛
h 𝑛𝑛 = −1.1 𝑢𝑢 𝑛𝑛
Unstable
54
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Key Concept
• Since impulse response of all FIR systems converge to zero after a finite
amount of time (samples), therefore all FIR systems are stable
−1 ≤ 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 ≤ 1
55
Discrete time Systems
• Stability (FIR Vs. IIR Systems)
Key Concept
• Higher order
• More memory
• More computations
• Less order
• Less memory requirements
• Less computations
56