Dr.

Mohammod Abdul Motin, Senior Member IEEE,

Assistant Professor,
Department of Electrical & Electronic Engineering
Rajshahi University of Engineering & Technology
Contact: [email protected]
 DSP

Week Week Week Week

1-3 4-6 7-9 10-12

Analog to Digital Impulse Responses: Fourier Domain

Filters
Conversion FIR, IIR DTFT,DFT, FFT

Discrete time Correlation: Auto, FIR and IIR Filter

Z-transform
signal Cross Design

Discrete time Convolution: Inverse Z- Matlab/Python

System Linear, Circular transform Implementation
Text Book:
1. Alan Oppenheim , Ronald Schafer: Discrete-Time Signal Processing, Prentice Hall, 3rd
Edition

Reference Book:
1. S K Mitra “Digital Signal Processing:A Computer Aided Approach”, Prentice Hall, 4th
Edition

2. Ifeachor M. and Jarvis B.W., “Digital Signal Processing a Practical Approach”.

3. Proakis J.G. and Manolakis D.G., “Digital Signal Processing”, Macmillan Publishing
Company.
Book Reference:
Digital Signal Processing- S Salivahanan
Discrete-Time Signal Processing-Alan V. Oppenheim, Ronald W. Schafer-3rd Edition
Motivating Examples

Sending image data in the usual format vs. sending only low-frequency data. a)
25% of data is in the usual format. b) 6.25% of data in the usual format. c) 25%
of lowest frequency data. d) 6.25% of lowest frequency data. 5
2-d sinusoid surface plot (left) and image (right)

6
2-D sine and its Fourier Transform
A natural image and its Fourier Transform

7
8
9
10
11
 Fourier Series

Fourier Transform

Discrete-Time
Fourier Transform

Uniform sampling of
DTFT spectrum is DFT:

12
The DFT of discrete-time sample signal 𝒙 𝒏
$%&
)*
%(̇ +!
𝑋(𝑘) = & 𝑥 𝑛 𝑒 $

!"#
N = number of samples
n = current sample
k = current frequency, where, k∈ [0, N−1]
x(n) = the value of the signal x(n) nth sample
X(k)= the DFT that includes information of both amplitude and phase

Inverse Discrete Fourier Transform (IDFT):

The inverse DFT (IDFT) takes as input the DFT coefficients and returns the original signal:
$%&
1 )*!+
𝑥(𝑛) = ) 𝑋(𝑘)𝑒 (( $ )
𝑁
!"#

13
1. Periodicity
2. Linearity
3. Shifting Property
4. Time Reversal
5. Multiplication property
6. Complex Conjugate
7. Convolution Theorem
8. Parseval’s Theorem

14
 Periodicity:
If X is periodic with period N
𝑥 𝑛 + 𝑁 = 𝑥(𝑛) for all n
𝑋 𝑘 + 𝑁 = 𝑋(𝑘) for all k
Proof:
$%& $%&
)* )*
%(̇ (+-$)! %(̇ /! % ()*!
𝑋[𝑘 + 𝑁] = . 𝑥 𝑛 𝑒 $ = .𝑥 𝑛 𝑒 $ 𝑒 ̇ = 𝑋[𝐾]
!"# !"#

Time reversal:
If X(k) is an N-point DFT of x(n), then
DFT{𝑥 −𝑛 } → 𝑋 𝑁 − 𝑛
DFT{x 𝑁 − 𝑛 } = 𝑥(−𝑘)! = 𝑋(𝑁 − 𝑘)

Linearity:
If 𝑋" 𝑘 and 𝑋# 𝑘 are N-point DFTs of 𝑥" 𝑛 and (n) 𝑥# 𝑛 respectively, and a
and b are arbitrary constants either real or complex-valued. Then,
𝑎𝑥" 𝑛 +𝑏𝑥# 𝑛 = 𝑎𝑋" (k)+𝑏𝑋# (k)
15
Time shifting:
If X(k) is an N-point DFT of x(n), then
!"#$%
%
𝑥(𝑛 − 𝑙) → 𝑋(𝑘)𝑒 &

'!"#
Or, 𝑥(𝑛 − 𝑙) → 𝑋(𝑘)𝑊$+0 [where, WN=𝑒 $ ]

𝑥(𝑛 + 𝑙) → 𝑋(𝑘)𝑊$%+0

Frequency shifting :
If X(k) is an N-point DFT of x(n), then
$#%&'
𝑥(𝑛)𝑒 & → 𝑋(𝑘 − 𝑙)

𝑥(𝑛)𝑊!(&' → 𝑋(𝑘 − 𝑙)
𝑥(𝑛)𝑊!&' → 𝑋(𝑘 + 𝑙)

16
Complex conjugate property:
If X(k) is an N-point DFT of x(n), then
x * (n) → 𝑋∗(−𝑘) = 𝑋∗(𝑁 − 𝑘)

Multiplication property:
If X(k) is an N-point DFT of x(n), then
𝑥& 𝑛 . 𝑥) 𝑛 = 𝑋& 𝑘 ∗ 𝑋) 𝑘

Correlation Property:
If X(k) is an N-point DFT of x(n), then
𝐷𝐹𝑇 𝑌𝑥𝑦 𝑙 → 𝑋& 𝑘 ∗ 𝑋) 𝑘
Parseval’s energy theorem: If X(k) is an N-point DFT of
x(n), then Parseval’s energy theory will be,

!(" !("
1
5 |𝑥(𝑛)|# = 5 |𝑋(𝑘)|#
𝑁
&)* +)*

17
 DFT of a finite sequence 𝒙 (n); 0≤ 𝒏 ≤ 𝑵 − 𝟏
Where 𝑋 𝑘 : sequencethe in frequency domain
𝑥 𝑛 : sequence in time domain
𝑵(𝟏 𝟐𝜫 𝑵(𝟏
(𝑱̇ 𝑵 𝒌𝒏
𝑫𝑭𝑻 𝒙 𝒏 =𝑿 𝒌 =5 𝒙 𝒏 𝒆 =5 𝒙 𝒏 . 𝑾𝑵 𝒌𝒏
𝒏)𝟎 𝒏)𝟎

𝟐𝜫
(𝑱̇
𝑾𝑵 = 𝒆 𝑵 where 𝑊! is Twiddle factor or phase factor
We use the twiddle factor to reduce the computational complexity of calculating
DFT and IDFT. Alternatively, we can also say that the twiddle factor has
periodicity/a cyclic property.

Computational cost of a standard DFT :

o Complex number multiplications: 𝑁 # .
o Complex number additions: N(N-1).
18
 /-$/)
Symmetry Property: 𝑊$ = −𝑊$/
!"#
%
Proof: 𝑊$ = 𝑒 &

&
/-$/) %2)3 +- .$
𝑊$ =𝑒 "
Periodicity Property:
= 𝑒 %2)3+/$ . 𝑒 %23
𝑊!34! = 𝑊!3 /
$#%
= 𝑒 %2)3/$ . −1
(
𝑊! = 𝑒 ! = −𝑊$/
$#%(34!) $#%3 /-$/)
𝑊!34! =𝑒 ( ! = 𝑒 ( !
. 𝑒 ($#% 𝑊$ = −𝑊$/

$#%3 $#% 3
( ! ( !
= 𝑒 .1 = 𝑒 = 𝑊!3
𝑊!34! = 𝑊!3

19
Periodicity Property: Symmetry Property:
34!/#
𝑊!34! = 𝑊!3 𝑊! = −𝑊!3
012 012
( (
Proof: 𝑊! = 𝑒 3
Proof: 𝑊! = 𝑒 3

$#%(34!) $#%3 3
( ( ! 34!/#
𝑊!34! =𝑒 ! = 𝑒 . 𝑒 ($#% 𝑊! =𝑒
($#% +4
1
.!

$#%3
( !
$#% 3
( !
= 𝑒 ($#%+/! . 𝑒 ($%
= 𝑒 .1 = 𝑒 = 𝑊!3 3
= 𝑒 ($#%/! . −1
𝑊!34! = 𝑊!3
34!/#
𝑊! = −𝑊!3

20
21
Twiddle factor matrix:
4-point twiddle factor matrix (4×4) matrix

w9*.* w9*." w9*.# w9*.: 1 1 1 1

w9".* w9"." w9".# w9".: 1 w9" w9# w9:
w9 = =
w9#.* w9#." w9#.# w9#.: 1 w9# w99 w9;
w9:.* w9:." w9:.# w9:.: 1 w9: w9; w9<

&
𝑤5& = 𝑒 %2)3/5 = 𝑒 %23/) = −𝑗
)
𝑤5) = 𝑒 %2)3/5 = 𝑒 %23 = −1
5 3𝜋 3𝜋 3𝜋 3𝜋
𝑤45 = 𝑒 %6)*/4 = 𝑒 %65*/) = 𝑐𝑜𝑠 − + 𝑗𝑠𝑖𝑛 − = 𝑐𝑜𝑠 − 𝑗𝑠𝑖𝑛 = 0 − 𝑗 −1 = 𝑗
2 2 2 2
5
𝑤55 = 𝑒 %2)3/5 = 𝑒 %263/5 = 𝑒 %2.)3 = 𝑐𝑜𝑠 2𝜋 − 𝑗𝑠𝑖𝑛 2𝜋 = 1
𝑤57 = −1
𝑤58 = −𝑗

1 1 1 1
1 −𝑗 −1 𝑗
𝑤5 =
1 −1 1 −1
1 𝑗 −1 −𝑗 22
4-point twiddle factor matrix:

w9*.* w9*." w9*.# w9*.: 1 1 1 1 1 1 1 1

w9".* w9"." w9".# w9".: 1 w9" w9# w9:
1 −𝑗 −1 𝑗
w9 = = = 𝑤9 =
w9#.* w9#." w9#.# w9#.: 1 w9# w99 w9; 1 −1 1 −1
w9:.* w9:." w9:.# w9:.: 1 w9: w9; w9< 1 𝑗 −1 −𝑗

w9< = -j
4-Point Twiddle factor 8-Point Twiddle factor

23
Example : Compute N point DFT of the signal given by 𝑥 𝑛 = {1, 0, 0, 1} and N=4

!(" 18
(= ̇ +&
We know , 𝑋 𝑘 = 5 𝑥 𝑛 𝑒 3
&)*
!(" 18
(= ̇ +&
𝑋 𝑘=0 =5 𝑥 𝑛 𝑒 3 = ∑:&)* 𝑥 𝑛 𝑒 *
&)*
=𝑥 0 +𝑥 1 +𝑥 2 +𝑥 3 =1+0+0+1=2
!(" !("
#> #>
(=̇ ! +& (=̇ 9 .".&
𝑋 𝑘 = 1 = L𝑥 𝑛 𝑒 = L𝑥 𝑛 𝑒 .
&)* &)*
012
(
=𝑥 0 + 𝑥 1 𝑒 + 𝑥 2 𝑒 ($% + 𝑥(3)𝑒 ($:%/#
9

= 1 + 0 + 0 + 1. 𝑒 ($.:%/# = 1 + 𝑒 ($.:%/# = 1 + 𝑗
!"
$ %'̇ # .).!
𝑋 𝑘=2 = ∑!"# 𝑥(𝑛)𝑒 = 1 + 0 + 0 + 𝑒 %*.$+ = 1−1=0
!" !"
$ %'̇ # .$.! %'̇ # .$.$
𝑋 𝑘=3 = ∑!"# 𝑥(𝑛)𝑒 =1+𝑒 =1−𝑗

So, 𝑋 𝑘 = {2, 1 + 𝑗, 0, 1 − 𝑗}
24
Example: Compute 4-point DFT of the signal 𝑥 𝑛 = {1, 2, 3, 4}
1
2
Solution: Let, 𝑥 4 = [1 2 3 4] 𝑥59 =
3
4
1 1 1 1
1 −𝑗 −1 𝑗
4-point twiddle factor matrix, 𝑤5 =
1 −1 1 −1
1 𝑗 −1 −𝑗

X 4 = 𝑤5 * 𝑥59
1 1 1 1 1 10
1 −𝑗 −1 𝑗 2 −2 + 𝑗2
= . =
1 −1 1 −1 3 −2
1 𝑗 −1 −𝑗 4 −2 − 𝑗2

X 4 = {10, -2+j2, -2, -2-j2}

25
DFT is the most straightforward mathematical procedure for
determining the frequency content of a time-domain sequence, it’s
terribly inefficient. As the number of points in the DFT is
increased to hundreds, or thousands, the amount of necessary
number crunching becomes excessive.

In 1965 a paper was published by Cooley and Tukey describing a

very efficient algorithm to implement the DFT. That algorithm is
now known as the fast Fourier transform (FFT).

Example:

For a two-million-point FFT (N = 2,097,152) on your desktop

computer and it takes 10 seconds.
A two-million-point DFT, on the other hand, using your computer,
will take more than three weeks!
26
The Fast Fourier transform (FFT) is an algorithm that efficiently computes the discrete
Fourier transform(DFT). It eliminates redundancies and greatly reduces the number
of necessary arithmetic operations required for DFT. So FFT requires less number of
multiplications and additions compared to DFT.

!("

𝑋 𝑘 = 5 𝑥 𝑛 𝑊!&+ , 0≤𝑘 ≤𝑁−1

&)*

For DFT For FFT

Required Complex Multiplication: 𝑁 # N * log2 𝑁
Required Complex Addition: N(N-1) N * log2 𝑁
"(
+! %(̇ +!
FFT algorithm take advantage of the periodicity and symmetry of complex number, 𝑊$ =𝑒 &

𝑊! +4!/# = −𝑊! + 𝑊! +4! = 𝑊! +

27
 If N=10! ,
Calculation for DFT, 𝑁 " =10#$ ,
Calculation for FFT, N 𝑙𝑜𝑔"% = 30 ×10!
Let, time per multiplication is 1ns
For DFT : 10#$ ×1 ×10! =10! 𝑠=31.2 years
For FFT : (30×10! ) ×10&! =30s
FFT is computational very efficient than
DFT

Number of complex multiplications in the DFT and

the radix-2 FFT as a function of N.

28
Radix: The radix (r) of FFT algorithm is a very efficient process for
performing DFTs under the constraint that the DFT size be an integral power
of r.

That is, the number of points in the transform is 𝑁 = 𝑟 + , where k is some

positive integer.

r: is the radix

this section we’ll learn the radix-2 FFT

Radix-2 FFT (where r=2)

If N=8 point for Radix-2 FFT, N= 2+ = 2:

29
The N-point DFT of sequence x(n) is given by
$%&

𝑋 𝑘 = ) 𝑥 𝑛 𝑊$!+ , 0 ≤ 𝑘 ≤ 𝑁 − 1
!"#
Splitting x(n) into even and odd points, we obtain
$%& $%&

𝑋 𝑘 = ) 𝑥 𝑛 𝑊$!+ + ) 𝑥 𝑛 𝑊$!+
!"#,! <=<! !"#,! >??
Substituting n=2r for n even and n=2r+1 for n odd, we have
($/)%&) ($/)%&)
()@A&)+
𝑋 𝑘 = ) 𝑥 2𝑟 𝑊$)@+ + ) 𝑥 2𝑟 + 1 𝑊$
@"# @"#
($/)%&) ($/)%&)

= ) 𝑥 2𝑟 (𝑊$) )@+ +𝑊$+ ) 𝑥 2𝑟 + 1 (𝑊$) )@+ N

@"# @"#
G k + 𝑊%, ×H k , 0≤ k≤ −1
𝑋 𝑘 = 2
N N N
= ∑($/)%&)
@"# 𝑥 2𝑟 @+
𝑊$/) + 𝑊$B ∑($/)%&)
@"# 𝑥 2𝑟 + 1 @+
𝑊$/) G k+ + 𝑊%
,.%/"
×H k + , ≤ k ≤ N−1
2 2 2
C ,.%/"
= -𝑊%,
= G(k) + 𝑊$+ ×H k k=0,1,… -1 Using the Symmetry property, 𝑊%
)
N
G k + 𝑊%, ×H k , 0≤ k≤ −1
𝑋 𝑘 = 2
N . N N
G k+ − 𝑊%, H k + , ≤ k ≤ N−1
2 2 2

"#∗" "#
" &'(%/")
∗ 𝑊%" = 𝑒 &'(")/%) = 𝑒 &'( %
)
=𝑒 = 𝑊%/"
For 4 point DFT Method from 8 point DFT (Stage -2):
0
1
%&
G(k) =B g®W2DE
1
@"#
0 0
3
%& 1 3
%&
=B g 2l W +B
4
2 g 2l + 1 W2)GA& E
1 1
F"# F"#
0 0
3
%& 3
%&
=B g 2l W2GE +W2H B g 2l + 1 W2GE ……………………..(i)
3 1 3
F"# F"#

G(k)=A(k)+ W2E B(k)

1

Where A(k) is the (N/4)-point DFT of even numbers of the above sequence and
B(k) is the (N/4)-point DFT of odd numbers of the above sequence.
Similarly,
0 0
%& %&
3 3
H(k) = B h 2l W0FE +W2E B h 2l + 1 W2GE
3 1 3
F"# F"#

H(k)= C(k) + W2E D(k) …………………………………..(ii)

1
8 Point DFT:

There is paired There is paired There is paired

between two points between four points between eight points
 &'")
7
W56 = 𝑒 %
So, we can get for 8 point
W$8 = 1
W$# = 0.707 − 𝑗 0.707
W$" = −𝑗
W$9 = −0.707 − 𝑗 0.707
W$: = −1
W$; = −0.707 + 𝑗 0.707
W$< = +𝑗
W$= = 0.707 + 𝑗 0.707
Decimation-in-frequency FFT decomposes the DFT by recursively splitting the sequence element,
&
%&
x(k) = ∑!"# 𝑥(𝑛) W?@A +∑$%&
" @A
!"$/) 𝑥(𝑛) W?
& &
%& %& $ (@-?/))A
= ∑!"#
"
𝑥(𝑛) W?@A + ∑!"# 𝑥(𝑛 + ) W?
"
)
& &
%& (?/))A %& $
= ∑!"#
"
𝑥(𝑛) W?@A + W? + ∑!"# 𝑥(𝑛 + ) W?@A
"
)

For Even number (k=2r),

&
%& $
X(2r) = ∑!"# [ 𝑥 𝑛 + −1
" )B
𝑥(𝑛 + )] W?)C@
)
&
%& $ $
D
= ∑!"# [ 𝑥 𝑛 + 𝑥(𝑛 + )] W?/)
"
,0≤r≤ –1
) )
D
[since W?) = 𝑊$/) , W?)D = W?/) ]
For odd number (k = 2r + 1),
&
%& $ ()C-&)@
X(2r +1) = N!"# [x n + (−1))B-& x(n+ )] W?
"
)
&
%& $
=N!"# [x n − x(n+ )] W?@ W?/)
" )C@
; 0 ≤ 𝑟 ≤ (𝑁/2) − 1
)

ts X(k) in the frequency domain into sets of smaller and smaller subsequences.