Fourier Analysis

of Discrete-Time Signals

Dr. Md. Kamrul Hasan

Professor,
Department of EEE, BUET
 The Fourier Theory

❑ Jean Baptiste Fourier – A 19th Century French Mathematician

◼ Any periodic waveform can be expressed as sum of one or more
sine waves
◼ Any signal can be described either in terms of amplitude versus
time (signal) or energy versus frequency (spectrum)
◼ Introduced the concept of “Time Domain” and “Frequency
Domain” representation of signals
How Does Fourier Look in Fourier Domain?
Time and Frequency Domain Representation of
Signals
x0(n)

= x1(n)

All the components are localized in FD

x2(n)

x3(n)

What is the FT of x(n) = x0 (n) + x1 (n) + x2 (n) + x3 (n) ?

 Discrete-Time Fourier Series (DTFS)
T
x[n] = x[n + N]

TS
A DTFS has N unknown parameters corresponding to N degrees of freedom.
ck N

At most N independent
k (Bin) harmonics
0
0 N 2N 3N N associated weighting
k coefficients
N

k (Bin)
0
N 2N 3N

0
 CT Fourier Series

x(t) = x(t+T)

2𝜋
𝑥 𝑡 = σ∞ 𝑐
𝑛=−∞ 𝑛 𝑒 𝑗𝑛𝜔0 𝑡
, 𝜔0 =
𝑇

1
𝑐𝑛 = ‫׬‬ 𝑥(𝑡) 𝑒 −𝑗𝑛𝜔0𝑡 dt
𝑇 <𝑡>

The exponential form of the Fourier series consists of the exponentials

𝑒 𝑗0𝑡 , 𝑒 ±𝑗𝜔0 𝑡 , 𝑒 𝑗2𝜔0 𝑡 ,……………………….
Fourier Series Representation of DT
Periodic Signals
• x[n] - periodic with fundamental period N, fundamental frequency

• Only ej n which are periodic with period N will appear in the FS

• There are only N distinct signals of this form

• So we could just use

 However, it is often useful to allow the choice of N

consecutive values of k to be arbitrary.
DT Fourier Series Representation
 2 
jk  n
x  n =  ak e  N 

k = N 


k =N 
= Sum over any N consecutive values of k

— This is a finite series

{ak} - Fourier (series) coefficients

Questions:
1) What DT periodic signals have such a representation?

2) How do we find ak?

Answer to Question #1:
Any DT periodic signal has a Fourier series representation
 2 
jk  n
x  n =  ak e  N 
=  ak e jk0 n
k = N  k = N 
A More Direct Way to Solve for ak

Finite geometric series

So, from

𝑁−1
1
𝑎𝑚 = ෍ 𝑥(𝑛)𝑒 −𝑗𝑚⍵0𝑛 , 𝑚 = 0,1,2, … … , 𝑁 − 1
𝑁
𝑚=0
DT Fourier Series Pair

Note:
▪ It is convenient to think of ak as being defined for all integers k.
1) ak+N = ak — Periodicity property of DT Fourier series coefficients.

2) We only use N consecutive values of ak in the synthesis equation.

(Since x(n) is periodic, it is specified by N numbers, either in the time or
frequency domain)
∗
3) . 𝑎𝑘 = 𝑎−𝑘 , if x(n) is real
Example #1: Sum of a pair of sinusoids

0 𝑎𝑘
𝑎15 = 𝑎−1 Fourier Spectra
1/2 𝑎14 = 𝑎−2 1Τ2
1/2 𝑎3 = 𝑎4=⋯=0
1 𝑗𝜋
𝑒 4
2 0 1 2
1 −𝑗𝜋 k bin
𝑒 4
2 < 𝑎𝑘 𝜋
4

0 1 2
k bin
 Frequency De-normalization
ck FS = 10 kHz
3.0777 3.0777
2.5 N =10
0.07265 0.07265
2
0 k (Bin) k0 is the angular freq. bin, where 0 =
N
0 1 2 3 4 5 6 7 8 9

Fs
ck  = 1000
3.0777 3.0777
k
N k
2.5 Fk = Fs where f k =
N N
0.07265 0.07265
0 f (Hz)
0 1000 2000 3000 4000 5000 6000 7000 8000 9000

◼ DTFS is expressed in normalized time and frequency.

◼ To return to proper time scale: n → nTs
◼ To return to proper frequency scale: k → k Fs
N
Example #2: DT Square Wave
Example #2: DT Square wave (continued)
Convergence Issues for DT Fourier Series
Not an issue, since all series are finite sums.

Properties of DT Fourier Series:

Example:

Show
Fourier Series: Periodic Signals and LTI Systems

𝑦 𝑛 = ෍ ℎ 𝑘 𝑥 𝑛−𝑘
𝑘=−∞

= ෍ ℎ 𝑘 𝑒 −𝑗𝜔𝑘 𝑒 𝑗𝜔𝑛
𝑘=−∞

= 𝐻(𝑒 𝑗𝜔 )𝑒 𝑗𝜔𝑛
 Discrete-Time Fourier Transform (DTFT)
Aperiodic finite duration signal
x[n]

0 n
0 N-1
y[n] Periodic signal N

0 n
0 N 2N
x[n]

If x[n] exists for only finite time, then we can represent it by the
following periodic function y[n] with period N (periodic extension of x[n]).
Discrete-Time Fourier Transform
Provides a frequency description (known as a Fourier
transform) of an aperiodic signal.

y[n] N
x[n]

0 n
0 N 2N
• Given some aperiodic signal x[n] that can be described in
terms of a periodic signal y[n], then we can write
 y[n] n=0,1, ,N -1
x  n =  2
0 otherwise 0 =
N
• As y[n] is a periodic function, we can write x[n] as
 N −1  2 
jk  n

x  n =  
N −1  2 
  N  jk  n
y  n  =  Y ( k )e
Y(k )e n=0,1, ,N -1  N 
k =0
0 k =0
 otherwise
DTFT (Contd.)

 If N →  , the signal x(n) repeats after an infinite interval.

Lt y (n) = x(n)
N →

❖The DTFS representing y(n) will also represent x(n) in the limit N → 

2
y(n) =  ae
k = N 
k
jk0 n
, 0 =
N
N −1 
1 1
ak =
N
 y(n)e
n =0
− jk0 n
=
N

n =−
x(n)e − jk0 n

x(n)=0 for n<0 and n>N

DTFT


Define X ( ) = 
n =−
x(n)e− jn

A continuous function of ω


1 1
Then ak =
N
 x(n)e
n =−
− jk0 n
= X (k0 )
N

▪ ak are (1/N) times the samples of X(ω) taken every ω0 rad/sec.

▪ Thus, (1/N) X(ω) is the envelope for the coefficients ak.
▪ Let N →  by doubling N repeatedly.
▪ Doubling N halves the fundamental frequency ω0
▪ The spacing between successive spectral components is halved.
▪ The envelope of the coefficients ak is halved.
▪ Doubling N repeatedly, the number of components double in each steps; the
spectrum progressively becomes denser while its magnitude ak becomes smaller.
IDTFT

y ( n) = 
k = N 
ak e jk0n

1
= 
N k = N 
X ( k 0 )e jk0 n

As N → , 0 → 0 and y (n) → x(n).

N −1
0 jk n
x(n) = Lt
0 →0
 [ X (k0 )
n =0 2
]e 0

1
x(n) = Lt
 →0 2
  X (k  )e
n = N 
jk  n


1
x ( n) =
2 
2
X ( )e j n d 
Fourier integral
DTFT Pair

X ( ) =  x(n)e
n =−
− j n
DTFT of x(n)

❖ The Fourier spectra are periodic functions of ω with period 2 .

1
x ( n) =
2 
2
X ( )e j n d 
 
X ( + 2 ) =  x(n)e
n =−
− j (  + 2 ) n
=  x(n)e
n =−
− j n − j 2 n
e

= X ( )
▪ We shall choose fundamental frequency range to be (− ,  ) . X(ω) is
unimportant beyond this range.
Symmetry Properties:
| X ( ) |=| X (− ) | even symmetry
X ( ) = −X (− ) odd symmetry
 Discrete-Time Fourier Transform
Example
 Consider a set of samples from a unit-height rectangular pulse
signal, the F.T. would be computed as follows:
 4 4
1− e − j5 
j
Y(e ) = Y(e )e j j ( )
=  yne
n= −
− j n
=  yne
n=0
− j n
= e
n=0
− jn
=
1− e − j
sin(5 / 2)
= e− j 2
sin( / 2) |Y()| Note:
Spectrum is
5 continuous.
y[n]

1 -4/5 -2/5 0 2/5 4/5
F.T.
()
0 n 
0 4 2/5 4/5

-4/5 -2/5 0
-
IDTFT Example
X ( )
Find IDTFT of X(ω) = rect(ω/2ωc) 
c =
4


− −c c 

1 
x ( n) =
2 
−
X ( )e j n d 
0.3
1 c
=
2 
− c
e jn d 0.2

x(n)
c 0.1
1
= e j n
j 2 n −c
0

-0.1
sin(c n) c -15 -10 -5 0 5 10 15
= = sin c(c n)
n 
 Relationship Between DTFS & DTFT

|Y()|

5 2
N

-4/5 -2/5 0 2/5 4/5

• The spectral coefficients of an N-point DTFS are samples of the

FT: Y (e j )
X(k) =
N =
2
k
N

• Substituting the appropriate values for Y(ej) gives

2
1 N −1 − jk  n

X(k) =  yne  N 

N n= 0
Properties of the DTFT(1)
Properties of the DTFT(2)
Parseval’s Theorem
Homework
 DT System Analysis by DTFT
Problem: For a system with unit impulse response h(n)=(0.5)n u(n),
determine the (zero-state) response y(n) for the input x(n)=(0.8)n u(n).

x(n)=(0.8)n u(n) y(n) ?

h(n)=(0.5)n u(n)
Discrete Fourier Transform

Allows us to compute an approximation of the Fourier

Transform on a discrete set of frequencies from a discrete
set of time samples.

Given a finite duration discrete-time signal

x(n), n = 0,1, 2, , N -1
The Discrete Fourier Transform (DFT) is defined by

N −1 k
X k  =  xn e
− j 2 n
N
for k = 0, 1, , N − 1
n=0
 x(n), n = 0,1, 2, , N -1
➢Definition: The Discrete Fourier Transform (DFT) is defined by:
N −1 N −1 2 N −1
−j
X (k ) =  x(n)e − jk n =  x(n)e =  x(n)W kn
kn
N

n =0 n =0 n =0

for k = 0,1, 2, , N −1
2
2 −j
where X (k )  X ( k ) and W = e N
N
⚫Where k are the index of the discrete frequencies and n the index of
the time samples

The Inverse Discrete Fourier Transform (IDFT) is defined by:

2
1 N −1 1 N −1
1 N −1
x(n) =  X (k )e jk n =  X ( k )e  X (k )W
j kn
− kn
N
=
N k =0 N k =0 N k =0

for n = 0,1, 2, , N − 1
Discretization of Fourier Transform
 Computing N-point DFT using DFT Matrix
N
The N  N DFT matrix is given by

1 1 1 1   X (0)  1 1 1 1   x(0) 
1 W 1 W N −1   X (1)  1 W 1 W N −1   x(1) 
2
 W W 2
  
D N = 1 W 2 W4 W 2( N −1)    = 1 W 2 W4 W 2( N −1)   
      
      
1 W N −1 W 2( N −1) ( N −1)( N −1)   X ( N − 1)  1 W N −1 W 2( N −1) W ( N −1)( N −1)  
  x( N − 1) 
W 

N-point DFT of x(n) is given by

X N 1 = DN N x N 1
Inverse Discrete Fourier Transform

The inverse formula is:

N −1 k
xn =  X k  e
1 j 2 n
N
for n = 0, 1, , N − 1
N k =0

Where, again, k are the index of the discrete frequencies and n the
index of the time samples.

We have the following properties:

Discrete time periodic spectra
Periodic time discrete spectra
 Inverse DFT (IDFT)
𝑥(0) 1 1 1 ⋯ 1 𝑋(0)
𝑥(1) 1 𝑊 −1 𝑊 −2 ⋯ 𝑊 −(𝑁−1) 𝑋(1)
1
⋮ = 1 𝑊 −2 𝑊 −4 ⋯ 𝑊 −2(𝑁−1) ⋮
⋮ 𝑁 ⋮
⋮ ⋮ ⋮ ⋮ ⋮
𝑥(𝑁 − 1) 1 𝑊 −(𝑁−1) 𝑊 −2(𝑁−1) ⋯ 𝑊 −(𝑁−1)(𝑁−1) 𝑋(𝑁 − 1)
data samples DFT coefficients

−1
x N 1 = D
1 *
−1
N N XN 1 D = DN
N
N
The Fast Fourier Transform (FFT) is a fast algorithm for evaluating the DFT.
Example

Compute 4-point DFT of h(n)={2,2,1,1}

 H (0)   h(0)  1 1 1 1   2  6 
 H (1)   h(1)  1 − j −1 j   2 1 − j 
  = D4  =   =  
 H (2)   h(2)  1 −1 1 −1 1   0 
        
 H (3)   h(3)  1 j −1 − j  1  1 + j 
Fourier Spectra of h(n)
6

|X(m)|---->|X(2m/4)|
4

0
0 1 2 3 4 5
Angular Frequency, 

1
Angle of X(m)

0.5

-0.5

-1
0 1 2 3 4 5
Angular Frequency, m
Relationship between the Fourier series
coefficients and the Fourier transform of
one period
 Properties of DFT
x(n modulu N ) = x(n), 0  n  N − 1
𝑥 ′ (𝑛) = 𝑥(𝑛 − 𝑛0, modulu 𝑁)
= x(n  kN ), otherwise
1. Circular/Periodic Shifting:
≡ 𝑥((𝑛 − 𝑛0 ))𝑁

Example: x(n)
circular shift
of a sequence

x(2) x(1)
x(3) x(0)
x(n)
x(4)
x(5)

x(4) x(3)
Left shift by 2 x'(n)
x(5) x(2) x(0)
x(2) x(1)
x((n+2))6 x(3) x(5)
x(4)
x(0)
x(1)
 Properties of DFT
Example of circular shifting:

x(n modulu N ) = x(n), 0  n  N − 1

= x(n  kN ), otherwise

If n0= -2 and N=6, we have Define

x (n) = x((n + 2))6

'
Even symmetry

Odd symmetry
Which implies that
x ' (0) = x((2))6 = x(2)
Time reversal
x (1) = x((3))6 = x(3)
'

x ' (2) = x((4)) 6 = x(4)

x ' (3) = x((5))6 = x(5)
x ' (4) = x((6))6 = x(0)
x ' (5) = x((7)) 6 = x(1)
Circular Convolution
x1 (n) DFT N −1

N x3 (n) =  x1 (m) x2 ((n − m)) N

X 1 (k ) X 2 (k ) m=0
× IDFT
x2 ( n ) x1 (n)
DFT
N

N −1 2
−j
X 1 (k ) =  x1 (n)e
kn
N
, k = 0,1,....., N − 1
n =0
N −1 2
−j
X 2 (k ) =  x2 (n)e
kn
N
, k = 0,1,....., N − 1
n=0

X 3 (k ) = X1 (k ) X 2 (k ), k = 0,1,....., N −1
Circular Convolution

1 N −1 k
j 2 n
x3 (n) = IDFT  X 3 (k )  =  X 3 (k ) e N , n = 0, 1, , N −1
N k =0
2
1 N −1
=  X 1 ( k ) X 2 ( k )e N
j kn

N k =0
2 2 2
1  N −1 N −1 − j ki   N −1 − j kl  j kn
=    x1 (i )e
k =0  i =0
N
   x2 (l )e
N
e
N
N   l =0 
1 N −1 N −1  N −1 j 2N k ( n −i −l ) 
=  x1 (i ) x2 (l )  e   N , if l = n − i
=
N i =0 l =0  k = 0  0, otherwise

N −1 Linear shifting of the periodic sequence

x3 (n) =  x1 (i) x2 ((n − i)) N x2 (i ) by n samples is equivalent to
Circular shifting of x2(i) by n samples
i =0
 Example: Circular Convolution

Perform the circular convolution of the two sequences

x1 (n) = 2,1, 2,1

Results: x3 (n) = 12,15,12,15
x2 (n) = 1, 2, 2, 4

Verify the results using DFT and IDFT.

1 2 4

-n
2 2 2 1 2 1

1 4 2
3 x3(0) = 2.1+1.4+2.2+1.2 = 2+4+4+2 = 12
x3 (n) =  x1 (m) x2 ((n − m))4 x3(1) = 2.2+1.1+2.4+1.2 = 4+1+8+2 = 15
m =0 x3(2) = 2.2+1.2+2.1+1.4 = 4+2+2+4 = 12
n=0,1,2,3 x3(3) = 2.4+1.2+2.2+1.1 = 8+2+4+1 = 15
 Circular Convolution using DFT
1 1 1 1  −j
2
1 W 1 W N −1 
 W 2
WN = e N

D N = 1 W 2 W4 W 2( N −1)  kN
= WN
k
  WN
 
1 W N −1 W 2( N −1) W ( N −1)( N −1) 
 N
k
= −WN
k
WN 2

 X 1 (0)  1 1 1 1   2   6 
 X (1)  1 − j −1 j  1   0   X 3 (0)   54 
 1 =   =    X (1)   0 
 X 1 (2)  1 −1 1 −1  2   2   3 = 
        X 3 (2)   −6 
 X 1 (3)  1 j −1 − j  1   0     
 X 3 (3)   0 
𝑥(0) 1 1 1 1 54 48
 X 2 (0)  1 1 1 1  1   9  𝑥(1) 1 1 𝑗 −1 −𝑗 0 1 60
 X (1)  1 − j −1 j   2  −1 + 2 j  = =
 2 =   =   𝑥(2) 4 1 −1 1 −1 −6 4 48
𝑥(3) 1 −𝑗 −1 𝑗 0 60
 X 2 (2)  1 −1 1 −1  2   −3 
      
 X 2 (3)  1 j −1 − j   4  −1 − 2 j 
Properties of DFT

Circular time shift of a sequence

x(n) ⎯⎯
DFT
N
→ X (k )
2
−j kn0
x((n − n0 )) N ⎯⎯
→ X ( k )e
DFT
N
N

◼ Time reversal of a sequence

x(n) ⎯⎯
DFT
N
→ X (k )
x((−n)) N = x( N − n) ⎯⎯
→ X ((−k )) N = X ( N − k )
DFT
N
Properties of DFT

◼ Complex conjugate property

x(n) ⎯⎯
DFT
N
→ X (k )
x* (n) ⎯⎯
DFT
N
→ X *
(( − k )) N = X *
(N − k)

The IDFT of X*(k) 1 N −1 * 2

IDFT  X (k )  =  X (k )e N
j kn
*

N k =0
2 *
1  N −1 j k ( N −n ) 
=   X ( k )e N 
N  k =0 

= x* ( N − n) = x* ((−n)) N

x* ((−n)) = x* ( N − n) ⎯⎯
DFT
N
→ X *
(k )
Properties of DFT
Circular Correlation
x(n) ⎯⎯
→ X (k )
DFT
N

y (n) ⎯⎯
DFT
N
→ Y (k )
then rxy (l ) ⎯⎯
DFT
N
→ R xy ( k ) = X ( k )Y *
(k )

Circular cross-correlation is defined as

N −1
r xy (l ) =  x(n) y* ((n − l )) N
n =0

= x(l ) N y* ((−l )) N
Taking N-point DFT
rxy (l ) ⎯⎯
DFT
N
→ R xy ( k ) = X ( k )DFT  ((−l )) N 
y *

= X (k )Y (k )
* rxx (l ) ⎯⎯
DFT
N
→ R xx ( k ) =| X ( k ) |2
Properties of DFT
Parseval’s Theorem

x(n) ⎯⎯
DFT
N
→ X (k )
y (n) ⎯⎯
DFT
N
→ Y (k )
N −1
1 N −1
then  x(n) y (n) =  X (k )Y * (k )
*

n =0 N k =0
PROOF:
N −1
r xy (l ) =  x(n) y* ((n − l )) N
n =0
N −1
r xy (0) =  x(l ) y* (n)
n =0
Parseval’s Theorem
2
1 N −1
r xy (l ) = IDFT  R xy (k )  =  R xy (k ) e N
j kl

N k =0
2
1 N −1
=  X (k )Y * (k ) e N
j kl

N k =0
N −1 N −1
1

n =0
x ( n ) y *
( n ) = r xy (0) = 
N k =0
X ( k )Y *
(k )

For x(n) = y(n)

N −1 N −1
1

n =0
| x ( n ) |2
= 
N k =0
| X ( k ) |2
Properties of DFT

 Multiplication of two sequences

x(n) ⎯⎯
→ X (k )
DFT
N

y (n) ⎯⎯
DFT
N
→ Y (k )

1
x(n) y (n) ⎯⎯
→ X (k ) N Y (k )
DFT
N
N
Linear Convolution

 IDFT gives circular convolution of the  We start with two finite duration signals:
product of DFTs of two finite duration
signals 𝑥 𝑛 0≤𝑛 ≤𝐿−1
 But linear convolution is required for ℎ 𝑛 0≤𝑛 ≤𝑀−1
filtering of in signal processing
 How to get linear convolution results
 x(n) may considered to be the input signal to a linear
using DFT? filter
 h(n) is the impulse response of the filter
 We want to compute the linear convolution:

y(n)= x(n) * h(n)= σ𝐿−1

𝑚=0 𝑥 𝑚 ℎ (𝑛 − 𝑚)

y(n) is nonzero for 0 ≤ 𝑛 ≤ 𝐿 + 𝑀 − 2 𝑤𝑖𝑡ℎ 𝑙𝑒𝑛𝑔𝑡ℎ 𝐿 + 𝑀 − 1

Linear Convolution of Two Finite Length Sequences
Using the DFT Compute the N-point DFT X[k] and H[k] of the
▪
two sequences x[n] and h[n], respectively.
▪ Compute the product X3[k] = X[k]H[k] for 0  k
Length L Length M Length L+M-1  N-1.
x(n) y(n) ▪ Compute the sequence x3[n] = x[n] Nh[n] as the
h(n) IDFT of X3[k].

0≤ n ≤L+M-2
0≤ n ≤L-1
0≤ n ≤M-1 y(n) = x(n)* h(n) ⎯⎯
DTFT
→Y ( ) = X ( ) H ( )
N ≥ L+M - 1
𝑌(𝑘) = 𝑋(𝑘)𝐻(𝑘)
▪ Zero-pad x[n] by M-1 zeros
𝑥 𝑛 N ℎ𝑧𝑝 𝑛 , 0≤𝑛 ≤𝑁−1 ▪ Zero-pad h[n] by L-1 zeros
𝑦 𝑛 = 𝑥 𝑛 ∗ ℎ 𝑛 = ቊ 𝑧𝑝
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 ▪ Both sequences will be of
length N=L+M-1

Circular Convolution = Linear convolution, if N ≥ L+M-1

 Circular vs. Linear Convolution
The N-point circular convolution of two sequences x(n), 0,1,….,L-1 and h(n), 0,1,….,M-1
of length (where N=L+𝑀 − 1) may be written in matrix form as
 y (0)   h(0) h( N − 1) h( N − 2) h(1)   x(0) 
 y (1)   h(1) h(0) h( N − 1) h(2)   x(1) 
  
 y (2)  =  h(2) h(1) h(0) h(3)   x(2) 
    
    
 y ( N − 1)   h( N − 1) h( N − 2) h( N − 3) h(0)   x( N − 1) 

y = Hc x
ℎ(0) 0 0 ⋯ 0
𝑦(0) ℎ(1) ℎ(0) 0 ⋯ 0 𝑥(0)
𝑦(1) ℎ(2) ℎ(1) ℎ(0) ⋯ 0 𝑥(1)
𝑦(2) = ⋮ ⋮ ⋮ ⋮ 𝑥(2)
ℎ(𝑀 − 1) 0
⋮ ℎ(𝑀 − 2) ℎ(𝑀 − 3) ⋯ ⋮
0 0
𝑦(𝑁 − 1) 0 0 … 𝑥(𝐿 − 1)
: ℎ(0)
: 0
0
𝐿

y = Hl x
Problems
P-2. Consider the two sequences

 2 n   2 n 
x1 = cos   x2 = sin  
 N   N 

a) Find the N-point circular convolution of x1(n) with x2(n)

b) Find the N-point correlation of x1(n) with itself.
c) Find the N-point circular correlation of x1(n) with x2(n)

1 𝑗2𝜋𝑛/𝑁 −𝑗2𝜋𝑛/𝑁
1 𝑗2𝜋𝑛/𝑁
𝑥1 (𝑛) = 𝑒 +𝑒 = 𝑒 + 𝑒 𝑗2𝜋(𝑁−1)𝑛/𝑁
2 2

1 j 2 n / N j 2 ( N −1) n / N
x2 (n) =  e − e 
2j  
 2 2
N −1 −j N −1 n (1− k )  N for k = 1
X ( k ) =  x ( n )e = e
nk j
1
1
1
1
N N
=
n =0 n =0 0 else

The N-point DFTs are

N
 k = 1 and k = N − 1
X 1 (k ) =  2
0 else
𝑁
𝑘=1
2𝑗
𝑋2 (𝑘) = 𝑁
− 𝑘 =𝑁−1
2𝑗
0 else

N2
4j k =1

 N 2 IDFT 1  2 n 
X (k ) = X 1 (k ) X 2 (k ) = − k = N −1 x(n) = x1 (n) N x2 (n) = N sin  
 4 j 2  N 
0 else


 Example
The DFT of the circular AC of x1(n) is

N2
 k = 1 and k = N − 1
Rxx (k ) =| X 1 (k ) | =  4
2

0
 else
1  2 n 
rxx (n) = N cos  
2  N 
◼ The DFT of the circular correlation of x1(n) with x2(n) is
 N2
− 4 j k =1

 N 2 IDFT 1  2 n 
Rx1x2 (k ) = X 1 (k ) X 2 (k ) = 
*
k = N −1 rx1x2 (n) = − N sin  
 4 j 2  N 
0 else


Test on Fourier Analysis of DT Signals

1. Compute 4-point DFT of x(n) = 1, 0, 2, 0

1, for n = 0
2. Compute DTFT of x(n) = 
0, otherwise
 Parseval’s Theorem

◼ Parseval’s theorem states the power of the signal in either the time
or frequency domain is a constant.
◼ In the time-domain, both signal and noise occur at the same time, whereas
in the frequency-domain, most of the noise occurs at frequency locations
not occupied by signal.

For Complex Form DTFS For DFT

N −1 N −1
1
1 N−1 2

N −1
x [n] =  X(k)
2 
n =0
| x ( n ) |2
= 
N k =0
| X ( k ) |2

N n=0 k= 0
 Summary

❑ DSP techniques involving DTFS, DTFT, DFT and

FFTs were described

❑ DSP-based test techniques enable test techniques not

available with bench-top equipment, i.e.,
▪ Frequency-domain filtering
▪ Time-domain interpolation
▪ Noise-reduction
❑ DFT can be computed with 𝑁𝑙𝑜𝑔2 𝑁 complexity
using FFT algorithm
Block Convolution
 When needed?
 The input signal x(n) is often very long
 To overcome memory problem
 The impulse response h(n) is of finite length M where M << L (block length)
 The result of convolution is needed in real-time
 Want to compute convolution in blocks of shorter length using
DFT/IDFT

 Approach
Break the input signal into shorter segments
The impulse response will be of one segment of extended length
by zero padding
Compute convolutions of each input block with the impulse
response
Combine the outputs appropriately
 Overlap-save Method
❑ Size of the input data blocks, N=L+M-1
❑ Size of DFT and IDFT are of length N
store
DFT
h(𝑛) 𝐻(𝑘)
N
Input signal DFT
𝑥𝑚 (𝑛) 𝑋𝑚 (𝑘)
L L L N
M-1
zeros For the m-th block
x1[n]
𝑌𝑚𝑏 𝑘 = 𝐻 𝑘 𝑋𝑚 𝑘 , 𝑘 = 0,1, … … . . , 𝑁 − 1
x2[n] Then the N-point IDFT yields the result

x3[n] IDFT
last M-1 data points of 𝑌𝑚𝑏 𝑘 𝑏 𝑛 ,
𝑦𝑚 𝑛 = 0,1, … … . , 𝑁 − 1
the pervious data block N
 Overlap-save Method (contd.)

▪ The first M-1 points of 𝑏 𝑛

𝑦𝑚 are redundant (corrupted due to time aliasing)
▪ The last L points of 𝑏
𝑦𝑚 𝑛 are exactly the same as the result from linear
convolution
𝑏 𝑛 ,
𝑦𝑚 𝑛 = 𝑦𝑚 𝑛 = 𝑀, 𝑀 + 1, … … . . , 𝑁 − 1

Output Signal
𝑦1 𝑛 𝑦𝑚 𝑛 = 𝑦1 𝑛 𝑦2 𝑛 𝑦3 𝑛
𝑦1𝑏 𝑛
𝑦2 𝑛
𝑦2𝑏 𝑛
𝑦3 𝑛
Discard M-1 points 𝑦3𝑏 𝑛

Overlap-save method
Overlap-add Method
For the m-th block
𝑌𝑚𝑏 𝑘 = 𝐻 𝑘 𝑋𝑚 𝑘 , 𝑘 = 0,1, … … . . , 𝑁 − 1
IDFT yields data blocks of length N that are free
Then the N-point IDFT yields the result of aliasing since the size of the DFT and IDFT
is N=L+M-1
IDFT
𝑌𝑚𝑏 𝑘 𝑏 𝑛 ,
𝑦𝑚 𝑛 = 0,1, … … . , 𝑁 − 1
N

L L L
M-1 points add
𝑦1𝑏 𝑛 together
M-1
zeros 𝑦2𝑏 𝑛 omit
x1[n]
M-1
M-1 points add
x2[n] zeros
together
𝑦3𝑏 𝑛

x3[n] Overlap-add method

 Examples
 Find the N-point DFT of the sequence
𝑥(𝑛) = cos 𝑛𝜔0 , 0 ≤ 𝑛 ≤ 𝑁 − 1
2𝜋 2𝜋
Compare X(k) when 𝜔0 =
𝑁 0
𝑘 to those when 𝜔0 ≠
𝑁 0
𝑘

1 𝑁−1 −𝑗2𝜋𝑛(𝑘−𝑘0 ) 1 𝑁−1 −𝑗2𝜋𝑛(𝑘+𝑘0 )

𝑋 𝑘 = σ 𝑒 𝑁 + σ 𝑒 𝑁
2 𝑛=0 2 𝑛=0

𝑁
𝑋(𝑘) = ቐ 2 𝑘 = 𝑘0 and 𝑘 = 𝑁 − 𝑘0
0 else
 Find the N-point DFT of the sequence
2𝜋
𝑥(𝑛) = 4+𝑐𝑜𝑠 2 𝑛 ,0≤𝑛 ≤𝑁−1
𝑁
 Example
2 2𝜋 2𝜋
𝑥(𝑛) = 4+𝑐𝑜𝑠
𝑁
𝑛 ,0≤𝑛 ≤𝑁−1 Here, 𝜔𝑘 = 𝑁
𝑘, 𝑘=1

▪ Nonlinear function of single frequency cosine function

2𝜋 9 1 𝑗 2𝜋.2.𝑛 1 −𝑗 2𝜋.2.𝑛
𝑥 𝑛 = 4+𝑐𝑜𝑠 2 𝑛 = + 𝑒 𝑁 + 𝑒 𝑁
𝑁 2 4 4
▪ 𝑘 = 2, 𝑡ℎ𝑎𝑡 𝑖𝑠 2𝑛𝑑 ℎ𝑎𝑟𝑚𝑜𝑛𝑖𝑐 𝑖𝑠 𝑔𝑒𝑛𝑒𝑟𝑎𝑡𝑒𝑑 due to nonlinear operation on the cosine wave

9 𝑁−1
2𝜋
𝑁, 𝑘=0 𝑋𝑖 𝑘 = ෍ 𝑥𝑖 𝑛 𝑒 −𝑗 𝑁 𝑘𝑛
, 𝑘 = 0,1, . . . . . , 𝑁 − 1
2
𝑛=0
𝑋(𝑘) = 𝑁 i = 1,2,3
𝑘 = 2 𝑎𝑛𝑑 𝑘 = 𝑁 − 2
4
0 elsewhere 9
𝑋𝑖 0 = 𝑁
2
Example 1 𝜋 2 𝑑𝜔
‫׬‬ |𝑋(𝜔)| = σ∝
𝑛=−∝ |𝑥 𝑛 |
2
2𝜋 −𝜋

❑ Let x(n) be the sequence

𝑥 𝑛 = 2𝛿 𝑛 + 2 − 𝛿 𝑛 + 1 + 3𝛿 𝑛 − 𝛿 𝑛 − 1 + 2𝛿 𝑛 − 2

𝜋
Evaluate ‫׬‬−𝜋 |𝑋(𝜔)|2 𝑑𝜔 without explicitly finding 𝑋 𝜔 .

❑ A linear time-invariant system has a frequency response

𝑗𝜔
1
𝐻 𝜔 =𝑒
1.1 + 𝑐𝑜𝑠𝜔
Find the difference equation that relates the input to the output.
2
𝐻 𝜔 = 𝑦 𝑛 = −2.2𝑦 𝑛 − 1 − 𝑦 𝑛 − 2 + 2𝑥(𝑛)
1 + 2.2𝑒 −𝑗𝜔 + 𝑒 −2𝑗𝜔
Example
❑ The input to an LTI system is
𝑛𝜋 3𝑛𝜋 𝜋
𝑥 𝑛 = 2 𝑐𝑜𝑠( ) + 3 𝑠𝑖𝑛( + )
4 4 8

Find out the output if the unit sample response of the system is
𝜋 𝜋
sin[ 𝑛 − 1 ] 𝐻1 (𝜔) 𝜔𝑐 =
ℎ 𝑛 =2 2 2
1.0
(𝑛 − 1)𝜋

ℎ 𝑛 = 2ℎ1 𝑛 − 1 
− −c c 
𝜋
2𝑒 −𝑗𝜔 , for |𝜔| ≤
𝐻(𝜔) = 2 sin 𝑛𝜔𝑐 1, for |𝜔| ≤ 𝜔𝑐
𝜋 ℎ1 𝑛 = 𝐻1 (𝜔) = ቊ
0, < |𝜔| ≤ 𝜋 𝑛𝜋 0, 𝜔𝑐 < |𝜔| ≤ 𝜋
2
 Example

y 𝑛 = 𝐴|𝐻 𝜔0 |cos(𝑛𝜔0 + 𝜑ℎ (𝜔0 ))

𝜋 𝜋 𝜋 𝜋 𝜋
y 𝑛 =2 𝐻 cos 𝑛 + 𝜑ℎ = 4cos 𝑛 + −
4 4 4 4 4