9/4/2019

Fourier transform theorems

 F.T. is always periodic

X (e j )  X (e j (  2 ) )
 F.T. is linear transform
DIGITAL SIGNAL PROCESSING x1[n]  X 1 (e j )
ECE/EEE F434 Lecture 10-13
Sarang C. Dhongdi x 2 [ n ]  X 2 ( e j )

ax1[n]  bx2 [n]  aX 1 (e j )  bX 2 (e j )

 Example x[n]  a
n
a 1

Fourier transform theorems Fourier transform theorems

 Time shifting
 Frequency shifting
x[n]  X (e j )

x[ n  n0 ]  e  jn0 X (e j ) e j0 n x[n]  X (e j ( 0 ) )

x[n]   [n  n0 ]  e jno

2   o  2k 
e jon  k
 Example  Example
 

Fourier transform theorems Fourier transform theorems

 Time reversal  Differentiation in frequency

x[n]  X (e j )
x[n]  X (e j )

x[n]  X (e  j ) dX (e j )
nx[n]  j
d
 Conjugation

x * [ n]  X * ( e  j )

1
 9/4/2019

Fourier transform theorems Fourier transform theorems

 Convolution theorem  Multiplication theorem

Input x[n]  X (e j ) x1[n]  X 1 (e j )

Impulse response h[n]  H (e j ) x 2 [ n ]  X 2 ( e j )
output j
y[n]  Y (e )
x1[ n] x2 [ n]  X 1 (e j ) * X 2 (e j )
y[n]  x[n] * h[n] 1
 X (e
j
x1[ n] x2 [ n]  ) X 2 (e j (  ) ) d
2
1
j j j
Y (e )  X (e ) H ( e ) 2

Fourier transform theorems Fourier transform theorems

 Modulation theorem  Parseval’s theorem

x[n]  X (e j ) x[n]  X (e j )

n
1
   x[n]
1 2
 X (e
2 j
x[n] cos 0 n  X (e j 0 )  X (e j 0 )  ) d
2 n   2 2

D.T.F.T.  D.F.T.

• Not practical for (real-time) computation on a digital computer.

• The DTFT is not numerically computable transform.

• Solution: limit the extent of the summation to N points and

From D.T.F.T.  D.F.T. evaluate the continuous function of frequency at N equally
spaced points.
DISCRETE FOURIER
TRANSFORM

2
 9/4/2019

Discrete Fourier transform Discrete Fourier transform

D.F.T. is the powerful computational tool that allows to  For sampling the D.T.F.T., we will take N samples in
evaluate F.T. on digital computer or specially designed the principle range.
digital hardware. 2
k  k k  0,1,2,..., N  1
N
D.F.T. is defined only for finite length sequences.  So, we define,
X ( k )  X ( e j ) 2  Periodic?
 k
N
D.T.F.T. is continuous and periodic, D.F.T. is obtained by 2
N 1 j nk
sampling one period of D.T.F.T. at a finite number of X ( k )   x( n )e N k  0,1,2,..., N  1
frequency points. n 0

X (k )  DFT {x[n]}
X (k )  x[n]

Sampling the Fourier transform Review of D.T.F.S. and D.T.F.T.

 Sampling points on unit circle

x[n]  cos o n
X ( e j )

2 -2π-w0 -2π -2π +w0 -w0 0 w0 2π-w0 2π 2π +w0

k  k
N

Sampling the Fourier Transform Sampling the Fourier Transform

 Samples of the DTFT of an aperiodic sequence  It is not necessary to know the DTFT at all
 can be thought of as DFS coefficients frequencies
 of a periodic sequence  To recover the discrete-time sequence in time domain
 obtained through summing periodic replicas of original
sequence  Discrete Fourier Transform
 Representing a finite length sequence by samples of DTFT
 If the original sequence
 is of finite length
 and we take sufficient number of samples of its DTFT
 the original sequence can be recovered by

~x n 0  n  N  1
xn  
 0 else

3
 9/4/2019

Taking D.F.T. of aperiodic sequence Taking D.F.T. of aperiodic sequence

x (n )
x(n) N’=9
0 N’1 n
n
0 8
~
X ( k )  X ( e j ) ~
x ( n) N=12
  2k / N

n
> ~ 0 8 12
N =
< N’ x ( n)
N=7
n
0 8 12

Taking D.F.T. of aperiodic sequence Taking D.F.T. of aperiodic sequence

 Samples of the Fourier transform of an aperiodic sequence can

be thought of as DFS coefficients of a periodic sequence
obtained through periodic replication of x[n]

 If we take sufficient number of samples of F.T. (greater than or

equal to length of x[n]), then F.T. is recoverable from its
samples, and equivalently x[n] is also recoverable.

Taking D.F.T. of aperiodic sequence Computing Discrete Fourier transform

x[0]  1, x[1]  2, x[2]  2, x[3]  1, x[n]  0 , otherwise

3
X k   x[n]e  j 2kn / 4 , k  0, 1, 2, 3
n 0

X k  x[0]e  j 2k ( 0) / 4  x[1]e  j 2k (1) / 4  x[2]e  j 2k ( 2) / 4  x[3]e  j 2k (3) / 4
 1  2e  jk / 2  2e  jk  1e  j 3k / 2 , k  0, 1, 2, 3

 6 k 0
 1  j k  1

Xk  
 0 k 2
 1  j k  3

4
 9/4/2019

Computing I.D.F.T. Computing I.D.F.T.

1
 Inverse D.F.T. x[0]  X 0  X 1  X 2  X 3 
4
N 1 1
x[n] 
1
X k e j 2kn / N , n  0, 1, ..., N  1  6  1  j  1  j 
N k 0 4
1

x[ n] 
1
4

X 0  X 1e j 2 (1) n / 4  X 2 e j 2 ( 2 ) n / 4  X 3e j 2 (3) n / 4  1

x[1]  X 0  X 1e j / 2  X 2 e j  X 3e j 3 / 2
4

1
 6  (1  j ) j  (0)(1)  (1  j )( j )
4
1
 6  j  1  j  1  8 / 4  2
4

Computing I.D.F.T. Simplifying the calculations

1

x[2]  X 0  X 1e j  X 2e j 2  X 3e j 3
4
  Analysis equation

N 1
X k    xnWNkn
1 2
 6  ( 1  j )(1)  (0)  ( 1  j )( 1) j kn
4
1 n 0
e N
 WNkn
 6  1  j  1  j 
4  Synthesis equation
 8/ 4  2
N 1
1
xn   X k W  kn
1

x[3]  X 0  X 1e j 3 / 2  X 2 e j 3  X 3e j18 / 4
4
 N k 0
N

1
 6  (1  j )( j )  (0)  ( 1  j )( j ) DFT
xn  X k 
4
1
 6  j  1  j  1

4
 4/ 4 1

Matrix form Matrix form

3
X k   x[n]e  j 2kn / 4 , k  0, 1, 2, 3  x[0]
n 0 3  x[1] 
X k   x[n]WNkn  x
X k  x[0]e  j 2k ( 0) / 4  x[1]e  j 2k (1) / 4  x[2]e  j 2k ( 2) / 4  x[3]e  j 2k (3) / 4 n 0  x[2] N

 
 1  2e  jk / 2  2e  jk  1e  j 3k / 2 , k  0, 1, 2, 3  x[3]
X (0)  1(1)  2(1)  2(1)  1(1)  6
 X [0] W40 W40 W40 W40   x[0]
X (1)  1(1)  2( j )  2(1)  1( j )  1  j  X [1]   0 1   x[1] 
W4 W4 W42 W43   
X (2)  1(1)  2(1)  2(1)  1(1)  0 XN   
 X [ 2] W4 W42
0 4
W4 W4 6
 x[2]
   0   
X (3)  1(1)  2( j )  2(1)  1( j )  1  j  x[3]
3
 X [3] W4 W4 W46 W49 

5
 9/4/2019

Matrix form
W40 W40
 0
W40 W40  1 1 1 1 
  
The Discrete Fourier Transform
W4 W4
1
W42 W43  1  j 1 j 

W4 W42
0 4
W4 W4 6
1 1 1 1 • Consider a finite length sequence x[n] of length N
 0   
W4 W4
3
W46 W49  1 j 1  j  xn  0 outside of 0  n  N 1
If we assume that the inverse exists, then
• For given length-N sequence associate a periodic sequence
x N  WN1 X N 
~
x n 
By the definition of IDFT  xn  rN
r  
1 *
xN  WN X N • Since x[n] is of length N there is no overlap between terms of x[n-rN]
N and we can write the periodic sequence as

1 * ~
x n  xn mod N  xnN 
WN1  WN 𝑊 ∗ 𝑊 = 𝑁𝐼
N

Circular Shifting x(n)

The Discrete Fourier Transform 3
4

2 N=4
1
• Shift the periodic sequence by k units n
0 1 2 3
𝑥[𝑛]
4 4 4 4 4 4
𝑥 𝑛 = 𝑥 𝑛−𝑘 = 𝑥(𝑛 − 𝑘 − 𝑟𝑁) 3 3 3 3 3 3
2 2 2 2 2 2
1 1 1 1 1 1
• Then the finite duration sequence, n
-4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11
𝑥 [𝑛] = 𝑥 [𝑛 − 2]
𝑥 𝑛 = 𝑥 [n] 0≤𝑛 ≤𝑁−1 = 𝑥(𝑛 − 2 − 𝑟𝑁)
4 4 4 4 4 4
= 0 otherwise 3 3 3 3 3 3
2 2 2 2 2 2
1 1 1 1 1 1

-4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 n

Circular Shift
Circular Shifting
4
3 𝑥′ 𝑛 = 𝑥(𝑛 − 2)
2 𝑥 𝑛 = 𝑥( 𝑛 − 𝑘 ) 𝑥(1) 𝑥′(1)
1

-4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11
n
𝑥(2) 𝑥(0) 𝑥′(2) 𝑥′(0)
𝑥 𝑛 = 𝑥 𝑛 − 𝑘, 𝑚𝑜𝑑 𝑁 = 𝑥[[𝑛 − 𝑘]]
𝑥 𝑛 = 𝑥[[𝑛 − 2]]
𝑥(3) 𝑥′(3)
𝒙𝟏 𝟎 = 𝒙[[−𝟐]]𝟒 = 𝒙(𝟐) 𝒙𝟏 𝟐 = 𝒙[[𝟎]]𝟒 = 𝒙(𝟎)

𝒙𝟏 𝟏 = 𝒙[[−𝟏]]𝟒 = 𝒙(𝟑)
x(n) 𝑥′ 𝑛 = 𝑥(𝑛 − 2)
𝒙𝟏 𝟑 = 𝒙[[𝟏]]𝟒 = 𝒙(𝟏)

6
 9/4/2019

Circular shifting
Convolution
N 1
x3 n   x mx n  m 
1 2 N
m0

The Discrete Fourier Transform

• Tomaintain duality between time and frequency, We
choose one period of X~ k  as the Fourier transform of
x[n]

~Xk  0  k  N  1 ~
DFT-PROPERTIES Xk   
 0 else
Xk   Xk mod N  Xk N 

Properties of DFT Properties of DFT

Linearity Circular convolution

ax1 n  bx2 n  aX 1 k   bX 2 k  N 1

x1 (n)  x2 (n)   x1 (m) x2 ((n  m)) N , 0  n N  1
N3=max(N1,N2): N3-point DFT m 0

DFT [ x1 (n)  x2 ( n)]  X 1 ( k ) X 2 ( k )

Circular Folding

 x (0 ) k 0 Multiplication
x(( n)) N  
 x( N  k ) 1  k  N  1
k 0 1
 X (0) DFT [ x1 (n)  x2 (n)]  X 1 (k )  X 2 (k )
DFT [ x(( n)) N ]  X ((k )) N   N
 X (N  k ) 1  k  N 1

7
 9/4/2019

Circular convolution
𝑥 𝑚 = 𝑥𝑛ℎ 𝑚−𝑛 0≤𝑚 ≤𝑁−1
Find the circular convolution of

𝑥[𝑛] = [2 1 2 1] 𝑥 0 = 𝑥𝑛ℎ −𝑛

ℎ[𝑛] = [1 2 3 4]

𝑥 𝑛 = 𝑥𝑚ℎ 𝑛−𝑚 0 ≤ 𝑛 ≤ 𝑁−1

𝑥 𝑚 = 𝑥𝑛ℎ 𝑚−𝑛 0≤𝑚 ≤𝑁−1

𝑥 𝑚 = 𝑥𝑛ℎ 𝑚−𝑛 0≤𝑚 ≤𝑁−1 𝑥 𝑚 = 𝑥𝑛ℎ 𝑚−𝑛 0≤𝑚 ≤𝑁−1

𝑥 1 = 𝑥𝑛ℎ 1−𝑛 𝑥 2 = 𝑥𝑛ℎ 2−𝑛

𝑥 𝑚 = 𝑥𝑛ℎ 𝑚−𝑛 0≤𝑚 ≤𝑁−1

ℎ 𝑚 =[ℎ 0 ℎ 1 ℎ 2 …… ℎ 𝑁 − 2 ℎ 𝑁 −1 ]
𝑥 3 = 𝑥𝑛ℎ 3−𝑛

ℎ −𝑚 = [ ℎ 0 ℎ 𝑁 − 1 ℎ 𝑁−2 …ℎ 2 ℎ 1 ]
ℎ 1 − 𝑚 = [ℎ 1 ℎ 0 ℎ 𝑁 − 1 ℎ 𝑁 − 2 …ℎ 2 ]

ℎ 2 − 𝑚 = [ℎ 2 ℎ 1 ℎ 0 ℎ 𝑁 − 1 ℎ 𝑁 − 2 …]

8
 9/4/2019

Circular convolution using DFT

ℎ 0 ℎ 3 ℎ 2 ℎ(1) 𝑥(0)
3

𝑥 𝑛 =
ℎ 1 ℎ 0 ℎ 3 ℎ(2) 𝑥(1) X k   x[n]e  j 2kn / 4 , k  0, 1, 2, 3
ℎ 2 ℎ 1 ℎ 0 ℎ(3) 𝑥(2) n 0

ℎ 3 ℎ 2 ℎ 1 ℎ(0) 𝑥(3) 3
X k   x[n]WNkn
n 0
1 4 3 2 2 14
2 1 4 3 1 16  X [0] W40 W40 W40 W40   x[0]
𝑥 𝑛 = =  X [1]   0 1   x[1] 
3 2 1 4 2 14 W4 W4 W42 W43   
XN   
4 3 2 1 1 16  X [ 2] W40 W42 W44 W46   x[2]
   0   
 x[3]
3
 X [3] W4 W4 W46 W49 

Linear convolution using circular convolution

Matrix form Find the linear convolution using circular convolution
strategy
W40 W40 W40 W40  1 1 1 1 
 0   
W4 W4
1
W42 W43  1  j 1 j 
 𝑥[𝑛] = [2 1 2 1]
W4 W42
0 4
W4 W4 6
1 1 1 1
 0   
W4 W4
3
W46 W49  1 j 1  j  ℎ[𝑛] = [1 2 3 4]

N 1
x3  n    x  m h   n  m   N 
1 * m 0
xN  WN X N
N

Linear Convolution using Circular convolution Circular convolution

Find the linear convolution using circular convolution
𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒 𝑥 𝑛 𝑜𝑓 𝑙𝑒𝑛𝑔𝑡ℎ 𝑙1
strategy.
𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒 ℎ 𝑛 𝑜𝑓 𝑙𝑒𝑛𝑔𝑡ℎ 𝑙2
𝑦 𝑛 =𝑥 𝑛 ∗ℎ 𝑛 𝑙𝑒𝑛𝑔𝑡ℎ 𝑁 = 𝑙1 + 𝑙2 − 1
𝑥 [n] = [2 1 2 1 0 0 0]
𝐷𝑒𝑓𝑖𝑛𝑒 𝑡ℎ𝑒 𝑡𝑤𝑜 𝑙𝑒𝑛𝑔𝑡ℎ − 𝑁 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒𝑠
ℎ [n] = [1 2 3 4 0 0 0 ]
𝑥𝑛 0 ≤ 𝑛 ≤ 𝑙1 − 1
𝑥 𝑛 =
0 𝑙1 ≤ 𝑛 ≤ 𝑁 − 1
ℎ𝑛 0 ≤ 𝑛 ≤ 𝑙2 − 1
ℎ 𝑛 = 𝑥 𝑛 = 𝑥 𝑚ℎ 𝑛−𝑚 0 ≤ 𝑛 ≤ 𝑁−1
0 𝑙2 ≤ 𝑛 ≤ 𝑁 − 1

𝑦 𝑛 =𝑥 𝑛 ⊗ ℎ 𝑛 0≤𝑛≤𝑁−1

9
 9/4/2019

Linear and Circular convolution

1 0 0 0 4 3 2 2 2
Find the circular convolution of
2 1 0 0 0 4 3 1 5
3 2 1 0 0 0 4 2 10 x[ n]  [1,2]
𝑥 𝑛 = 4 3 2 1 0 0 0 1 = 16 h[ n]  [1,2,4]
0 4 3 2 1 0 0 0 12
0 0 4 3 2 1 0 0 11
0 0 0 4 3 2 1 0 4 Find the linear convolution of

x[n]  [1,2]
h[n]  [1,2,4]

Linear Convolution using DFT Linear Convolution using DFT

𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒 𝑥 𝑛 𝑜𝑓 𝑙𝑒𝑛𝑔𝑡ℎ 𝑙1
𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒 ℎ 𝑛 𝑜𝑓 𝑙𝑒𝑛𝑔𝑡ℎ 𝑙2 𝑥 𝑛
Zero padding 𝑋 𝑘
𝑥𝑛 (l1+l2-1) point
𝑦 𝑛 =𝑥 𝑛 ∗ℎ 𝑛 𝑙𝑒𝑛𝑔𝑡ℎ 𝑁 = 𝑙1 + 𝑙2 − 1 with (l2-1)
𝑙𝑒𝑛𝑔𝑡ℎ 𝑙1 DFT
zeros
(l1+l2-1) point
𝐷𝑒𝑓𝑖𝑛𝑒 𝑡ℎ𝑒 𝑡𝑤𝑜 𝑙𝑒𝑛𝑔𝑡ℎ − 𝑁 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒𝑠 IDFT
Zero padding
𝑥𝑛 0 ≤ 𝑛 ≤ 𝑙1 − 1 ℎ𝑛 (l1+l2-1) point
with (l1-1)
𝑥 𝑛 = 𝑙𝑒𝑛𝑔𝑡ℎ 𝑙2 DFT y𝑛
0 𝑙1 ≤ 𝑛 ≤ 𝑁 − 1 zeros
ℎ 𝑛 𝐻 𝑘 𝑙𝑒𝑛𝑔𝑡ℎ
ℎ𝑛 0 ≤ 𝑛 ≤ 𝑙2 − 1 𝑙1 + 𝑙2 − 1
ℎ 𝑛 =
0 𝑙2 ≤ 𝑛 ≤ 𝑁 − 1
• Take N point DFT of xe[n] (i.e. Xe(k)) and N point DFT of he[n] (i.e. He(k)).
• Take N point IDFT of the product Xe(k) He(k)

Solve
• Let 𝑋 𝑘 , 0 ≤ 𝑘 ≤ 11, be the 12-point DFT of a length-12 real
sequence x[n] with first 7 samples of X[k] given by,
• X[k] = { 11, 8-j2, 1-j12, 6+j3, -3+j2, 2+j, 15} 𝟎≤𝒌 ≤𝟔

• Determine the remaining samples of X[k]. Evaluate the following

functions of x[n] without computing the IDFT of X[k].

• 𝑥(0)
•∑ 𝑥[𝑛]
•∑ 𝑥[𝑛]

10