Digital Signal Processing

Discrete Fourier Transform

(DFT)

Judi Prajetno S.
judi@[Link]
 FT Computation Problem
 Fourier Transform of a signal (continues or
discrete signal) is a function of continues
variable, it cannot stored in the memory of
computer. Computer only have a limited
amount of memory.
 To calculate Fourier Transform, it is
necessary to discretize the frequency (means
sampling in frequency domain) in a limited
amount of memory  Discrete Fourier
Transform (DFT)
Judi Prajetno S. 2004
 Illustration of DFT Development

*
h(t) h(t).0(t) h(t).0(t).x(t) g(kT)
X X

0(t) x(t) 1(t)

Ts T 1/T

Judi Prajetno S. 2004

Judi Prajetno S. 2004
 DFT Theoretical Development
original signal : h(t )

Time sampling signal:  0 (t )    (t  nT ),
n 
s  Ts =Sampling interval

1  -Ts / 2  t  T - Ts / 2  T  Period
Truncation function: x (t )  
0  others

Frequency sampling function: 1 (t )  T   (t  rT )
r 

Judi Prajetno S. 2004

 Sampled signal:
 
h(t ) 0 (t )  h(t )   (t  nTs )   h(nT ) (t  nT )
s s
n  n 

T
Truncation sampled signal (in N = samples):
Ts
 N 1
h(t ) 0 (t ) x(t )  x(t )  h(nTs ) (t  nTs )   h(nTs ) (t  nTs )
n  n 0

Convolving signal (sampling in frequency domain)

 N 1    
 h(t )0 (t ) x(t )  * 1 (t )    h(nTs ) (t  nTs )  *  T   (t  rT ) 
 n 0   r  
 N 1   N 1   N 1 
 ...   T  h( nTs ) (t  T  nTs )    T  h( nTs ) (t  nTs )    T  h(nTs ) (t  T  nTs )   ...
 n0   n0   n 0 

 N 1 
 T    h(nTs ) (t  rT  nTs )   h (t )
r   n  0 
Judi Prajetno S. 2004
 The Fourier series coefficient of h (t ) is
T Ts 2
1
ck   h (t )e  jk0t dt
T Ts 2
T Ts 2
1    N 1    jk0t
 Ts  r
T
T 
  n  0
h ( nTs ) (t  rT  nTs  e
)

dt
2

taking one period only

T Ts 2 T Ts 2
1  N 1   jk0t  N 1   jk0t
ck 
T   
T h ( nTs ) (t  nTs e
) dt    h ( nTs ) (t  nTs e
) dt
Ts 2  n 0  Ts 2  n 0 
T Ts 2
N 1 N 1
2 2
  h(nTs )  e  jk0 t
 (t  nTs )dt   h(nTs )e jk t  0 
0
 ; t  nTs
n 0 Ts 2 n 0 T NTs
N 1 2 N 1 2
 jk nTs j nk
  h(nTs )e NTs
  h(nTs )e N

n 0 n 0
Judi Prajetno S. 2004
 recall that the Fourier transform of periodic signal is
 
1
X ( )  
k 
ck 2 (  k0 )  X ( f )  
k 
ck  ( f  kf 0 ); f0 
T
k
then sampled at f= :
NTs
  N 1 2
k j nk  1
H( )     h(nTs )e N
  ( f  k )
NTs k   n  0  NT s

taking for one periode

N 1 2
k j nk
H( )   h(nTs )e N  Discrete Fourier Transform
NTs n 0

and
N 1 2
1 k

j nk
h(nTs )  H ( ) e N
 Inverse Discrete Fourier Transform
N n 0 NTs
Judi Prajetno S. 2004
 
DTFT : H ()  
n 
h(n)e  jn

1
IDTFT : h(n) 
2  2
H ()e jn d 

N 1 2
j nk
DFT {h( n)}  H (k )   h( n)e N

n 0
N 1 2
1 j nk
IDFT {H ( k )}  h(n) 
N
 H ( k )e
k 0
N

2
j nk
where: WNnk  e N

N 1
DFT {h( n)}  H (k )   h( n)WNnk
n 0
N 1
1
Judi Prajetno S. 2004
IDFT {H ( k )}  h(n) 
N
 H
k 0
( k )WN
 nk
 Twiddle Factor
2
j p j
Twiddle factor W  e N
p N
W86
2
j 0
N  4 W  e 4
0 4
 1 W43
W85 W87
2
j 1
W41  e 4
j
2
j 2
W42  e 4
 1 W84 W42 W21 W20 W40 W80
2 -1 1
j 3
W43  e 4
j

W83
W W
N
p
N
p mod N
W41 W81

WNnk  WN( n  N ) k  WNn ( k  N ) W82

WN( N  n ) k  WNnk 
* -j

Judi Prajetno S. 2004

 Example:
 h[n]=[0 1 1 0], find out DFT{h(n)}
N 1 2 N 1
j
DFT {h(n)}  H (k )   h( n)e   h(n)WNnk
nk
N

n 0 n0

n 0 1 2 3
H (0)  0  1.W41.0  1.W42.0  0  1  1  2
H (1)  0  1.W41.1  1.W42.1  0   j  1
H (2)  0  1.W41.2  1.W42.2  0  1  1  0
H (3)  0  1.W41.3  1.W42.3  0  j  1

Judi Prajetno S. 2004

H ( k )  [2 (1  j ) 0 (1  j )]
 DFT relationship to DTFT

X ( )  
n 
x(n)e jn  x(n)  0 if n<0 or n  N
N 1
  x(n)e  jn
n 0

2
 sampled at k:
N
2
2 N 1 j
X ()  2 k  X ( k )  X (k )   x(n)e
nk
N
N N n0

Judi Prajetno S. 2004

 DFT relationship to CTFT

X ( )  

x(t )e  jt dt  x(t )  0 if t>T

T 2
sampled at N  point,  t=[Link] , dt=Ts ,   k
Ts T
N 1 2
j k .nTs
X ( )   x (nTs )e NTs
Ts
n 0
N 1 2
j nk
 Ts  x(nTs )e N


n 0

X (k )

Judi Prajetno S. 2004

X ( )  Ts X (k )
 Better CTFT approximation by DFT*)


 x(t )e
 j t
X ( )  dt


with sampling interval Ts small enough in variation of x(t) in interval nTs  t  NTs  Ts
 nTs Ts
X ( )    x(t )e  jt dt
n 0 nTs

  
t  nTs Ts
 nTs Ts  jt 

1  jt 1  e  jTs 
    e dt  x(nTs )    e  x(nTs )   x(nT )e  j nTs
    j  j
s
n 0
 nTs  n 0
 t  nTs  n 0

2
take   k
NTs
2 2
j k 2 j k
2 1 e N 
1 e
j N
2

nk
X( k)  x ( nT ) e  N
X ( k )  take  =
NTs 2 s
2 NTs
j k 
n 0
j k
NTs X (k ) NTs
1  e  jk
X (k )  X (k )
j k
Judi Prajetno S. 2004
*) Kamen & Heck, p. 306
 DFT relationship to DTFS
Discrette Time Fourier series:
N 1 N 1 2
x( n)   ck e j0 nk   ck e
j nk
N

n 0 n 0

and the coefficient:

N 1 2
1 1 N 1 j nk
ck 
N
 x ( n ) e  j0 nk
  x ( n)e
N 
N

n 0 n 0
 
X (k )

1
ck  X (k )
Judi Prajetno S. 2004 N
 DFT relationship to CTFS

x(t )  
k 
ck e jk0t 
T
1 T
ck   x(t )e  jk0t dt  sampled at Ts 
T 0 N
N 1 2
1  jk nTs
 
T n0
x(nTs )e NTs
Ts
2
1 T N 1 j nk
 
T N 
x(nTs )e N

n 0

X (k )

1
ck  X (k )
N
Judi Prajetno S. 2004
 DFT Properties

Judi Prajetno S. 2004

 Example:
 Proof the time shifting properties of DFT
2
j mk
h ( n  m )  H ( k )e N

proof:
assume r  n - m
N 1 2
1 j
 H (k )e
rk
IDFT {H ( k )}  h(r )  N
N k 0
N 1 2
1 j ( nm )k
h( n - m) 
N
 H (k )e
k 0
N

N 1 2 2
1 j
 
mk j nk
 H (k )e e N N
// qed
Judi Prajetno S. 2004 N k 0
DFT {h ( n  m )}
 Example:
 h(n)=[1 1 0 0], find out DFT{h(n-3)}

N 1 2
j mk
H ( k )   h( n)W nk
N  DFT {h( n  m)}  H ( k )e N

n 0
2
j 3.0
H (0)  1.W 4
0.0
 1.W 1.0
4 00  2  DFT {h(n  3)}  2.e 4
2
2
j 3.1
H (1)  1.W 4
0.1
 1.W
4
1.1
 0  0  1 j  DFT {h(n  3)}  (1  j ).e 4
 1 j
2
j 3.2
H (2)  1.W 4
0.2
 1.W 4
1.2
00  0  DFT {h(n  3)}  0.e 4
0
2
j 3.3
H (3)  1.W 4
0.3
 1.W 4
1.3
 0  0  1 j  DFT {h(n  3)}  (1  j ).e 4
 1  j

DFT {h(n  3)}  [2 (1  j ) 0 (1  j )]

Judi Prajetno S. 2004