Transformasi Fourier Diskrit

6.1 Pencuplikan Domain Frekuensi :Transformasi Fourier Diskrit

6.1.1 Pencuplikan Domain Frekuensi dan Rekonstruksi Sinyal Waktu Diskrit
Transformasi Fourier Waktu Diskrit (Discrete Time Fourier Transform (DTFT))
dari sinyal aperiodik waktu diskrit


j
X (e )   x n e
n 
 j n

Edisi Semester 1 17/18 EYH 1

Uniform sampling of DTFT spectrum and the evaluate at   2 k / N
2 k
 2 k   j
 x n e
n
X  k  0,1,..., N  1
N
,
 N  n 
1 2 k N 1 2 k 2 N 1 2 k
j j j
 x n e  x  n  e   x n e
n n n
 ...  N N N
 ...
n  N n 0 n N
 lN  N 1 2 k
j
=  x n e
n
N

l  n lN

Change the index n to n - lN

2 k
 2 k  N 1
   j
   x  n  lN  e
n
X  k  0,1,..., N  1
N
,
 N  n  0  l  

xp  n   x  n  lN 
l 
2 k
 2 k  N 1 j
  p 
n
X  x n e N
, k  0,1,..., N  1
 N  n 0

Edisi Semester 1 17/18 EYH 2

x p  n  dinyatakan dalam deret Fourier
N 1 2 k
x p  n    ck e
j n
N
,n  0,1,...,N  1
k 0
N 1 2 k
1 j
 x n e
n
ck  p
N
,k  0,1,...,N  1
N n 0

1  2 k 
ck  X , k  0,1,...,N  1
N  N 
2 k
1  2 k  j N n
N 1
xp  n 
N

k 0
X
 N
e

,n  0,1,...,N  1

x  n  dapat diperoleh kembali dari x p  n  bila tidak ada aliasing

dalam domain waktu. Artinya x  n  terbatas panjangnya, dan lebih kecil
atau sama dengan perioda N dari x p  n  .

Edisi Semester 1 17/18 EYH 3

 DTFT  cuplik IDFT
x(n) j
X(e ) X(k) xp(n)
-A ≤ n < B 0≤n<N

Edisi Semester 1 17/18 EYH 4

Spektrum sinyal waktu diskrit aperiodik dengan panjang L dapat diperoleh
kembali dari sampel-sampel pada frekuensi k  2 k / N , bila N  L.
 2 k 
X  e j  dapat diperoleh dari X   dengan interpolasi.
 N 
2 k
1 N 1
 2 k  j
xp  n  
n
X e
N
,n  0,1,...,N  1
N k 0  N 
 1 N 1  2 k  j 2N k n   jn
X  e  =   X 
N -1
j
e e
n 0  N k 0  N  
N 1
 2 k   1 N 1  j 2 k / N n 
= X    e 
k 0  N   N n 0 
N 1
1 1  e  j N sin  N / 2   j N 1 / 2
Bila P  e  
1
N
j
e
n 0
 j n

N 1 e  j

N sin  / 2 
e maka

 2 k 
 
N 1
X e j
 = X  P e
j    2 k / N 
, NL
k 0  N 

Edisi Semester 1 17/18 EYH 5

 DFT and DTFT

 • frekuensi kontinu 
 x n e
DTFT j  j n
X(e )  • x(n), -<n<
n

N 1 2 kn
j • frekuensi diskrit k=N/2
DFT X k    x n e N
• x(n), 0≤n<N
n 0

Edisi Semester 1 17/18 EYH 6

 DFT and DTFT

• Sample DFT adalah DTFT pada frekuensi diskrit :

X(k)
X  k   X( e )
j
2 k
X(ej)

N
k=1...


Edisi Semester 1 17/18 EYH 7

Finite impulse

1 n0
x n  
0 n  1..N  1
2 kn
j
X  k    n 0 x  k  e
N 1
N
 1 k

Edisi Semester 1 17/18 EYH 8

Sinusoid periodik :

 2 rn 
x  n   cos  , rI
 N 
1   j 2Nrn 2 rn

 e e N

2 
2 rn 2 rn 2 kn
N 1 1   j  j
X  k    n 0  e N  e N  e N
2 
 N / 2 k  r,k  N  r

 0 lainnya

Edisi Semester 1 17/18 EYH 9

6.1.2 Transformasi Fourier Diskrit (TFD)

N 1 2 k
j
X k    x n e
n
TFD N
, k  0,1, 2,...,N - 1
n 0
2 k
1 N 1
x n   X k  e
j n
Invers TFD N
, n  0,1, 2,...,N - 1
N k 0

Edisi Semester 1 17/18 EYH 10

6.1.3 TFD sebagai Transformasi Linier

N 1
X  k    x  n   WNkn , k  0,1,..., N -1
n 0
2
j
WN  e N

N 1
1
x n 
N
 X  k
k 0
 WN
 nk
, n  0,1,..., N -1

Edisi Semester 1 17/18 EYH 11

 X  0   1 1 1 1   x  0 
  1 WN( N 1 )   x 1 
 X 1  
WN1 WN2
 
 X  2    1 WN2 WN4 2( N 1 )
WN   x  2 
    
    
 X  N  1  1 W ( N 1 ) ( N 1 )2  
  x  N  1 
WN2( N 1 ) 
   N WN
 X  0   x  0 
   
 X 1    x 1  
XN   X  2  xN =  x  2 
   
   
 X  N  1 
 x  N  1 
 
 
1 1 1 1 
1 WN1 WN2 WN( N 1 ) 
 
2( N 1 )
WN  1 
2 4
WN WN WN matriks transformasi linier
 
 
1 W ( N 1 ) W 2( N 1 ) WN( N 1 ) 
2

 N N

X N  WN  x N
x N = WN -1 X N
Edisi Semester 1 17/18 EYH 12
6.2 Sifat-sifat TFD
6.2.1 Sifat Periodik, Linier dan Simetris
Bila x  n  dan X  k  adalah pasangan TFD N sampel, maka
Periodik

x n  N   x n n
X  k  N   X  k  k

Bila x1  n    X 1( K ) dan x2  n  

Linier TFD
N
TFD
N
 X2( K )
maka a1 .x1  n   a2 .x2  n  
TFD
N
 a1 X 1( k )  a2 X 2 ( k )

Sifat Simetri sirkular deretan

N sampel TFD dari x  n  panjang L  N ekivalen dengan N sampel TFD
dari deretan periodik x p  n  , dengan perioda N ,

xp  n   x  n  lN 
l 

Bila deretan periodik x p  n  digeser k sampel ke kanan maka

x ' n , 0  n  N -1
x'  n    p
 0, lainnya
Pergeseran sirkular deretan dapat direpresentasikan dengan indeks modulo N.

Edisi Semester 1 17/18 EYH 13

Pergeseran sirkular deretan dapat direpresentasikan dengan indeks modulo N .
x'  n   x  n  k , modulo N 
 x  n  k N
Misal, k  2 dan N  4,
x'  n   x   n  2  4
x'  0   x   2  4  x  2 
x' 1  x   1 4  x  3
x'  2   x   0  4  x  0 
x'  3  x  1 4  x 1

Deretan N sampel disebut deretan genap sirkular jika simetris terhadap titik nol.
Implikasi
x  N - n  x n 1  n  N -1
Deretan N sampel disebut deretan ganjil sirkular jika antisimetris terhadap titik nol.
Implikasi
x  N - n  x n 1  n  N -1
Pembalikan terhadap waktu untuk deretan N sampel adalah
x   -n   N = x  N - n  0  n  N -1

Edisi Semester 1 17/18 EYH 14

Sifat Simetris TFD

Deretan bernilai riil

Bila x  n  riil
X  N - k   X   k   X  -k 
Konsekuensi X  N - k   X  k  dan X  N - k   X  k 

Deretan riil genap

Bila x  n  riil dan genap, yaitu x  n   x  N - n  maka X I  k   0
N -1
2 kn
TFD -nya menjadi X  k    x  n  cos 0  k  N 1
n 0 N
X  k  fungsi genap bernilai ril.
1 N -1
2 kn
Invers TFD -nya menjadi x n 
N
 X  k  cos
k 0 N
0  n  N 1

Deretan riil ganjil

Bila x  n  riil dan ganjil yaitu x  n   - x  N - n  maka X R  k   0
N -1
2 kn
TFD -nya menjadi X  k    j  x  n  sin 0  k  N 1
n 0 N
X  k  fungsi ganjil bernilai imajiner.
1 N -1
2 kn
Invers TFD -nya menjadi x n  j
N
 X  k  sin
k 0 N
0  n  N 1

Edisi Semester 1 17/18 EYH 15

6.2.2 Sifat Konvolusi Sirkular
Bila x1  n  
TFD
N
 X 1 (k ) dan x2  n  
TFD
N
 X 2 (k )
maka x1  n  x2  n   TFD
N
 X 1 (k ) X 2 (k )
N 1
x1  n  x2  n    x1  k  x2   n  k   n  0, 1,..., N - 1
k 0 N

Contoh
Tentukan konvolusi sirkular 4 sampel dari dua deretan berikut
x1  n   2, 1, 2,1 , x2  n   1, 2, 3, 4 ,
 
x3  n  = x1  n  x2  n 
3
n0 x3  0  =  x1  k  x2   k    14
k 0
3
n 1 x3 1 =  x1  k  x2  1 k    16
k 0
3
n2 x3  2  =  x1  k  x2   2  k    14
k 0
3
n3 x3  3  =  x1  k  x2   3  k    16
k 0

x3  n   14,16,14,16


Edisi Semester 1 17/18 EYH 16

 N 1

Konvolusi sirkular : g [ n ] N h[ n ]   gmh n  m N 

m0

• Contoh: g[n]={1 2 0 1} h[n]={2 2 1 0}

N1

 gmh n  m N   G[k]H[k]
n n

1 2 3 1 2 3
m0
g[n] 4 h[n]={4 7 5 4}
h[<n - 0>4]
1 2 3
n 1
h[<n - 1>4] n 2
1 2 3
1 2 3 n
h[<n - 2>4]
1 2 3
n 0
check: g[n] * h[n]
h[<n - 3>4]
1 2 3
n 1 ={2 6 5 4 2 1 0}
Edisi Semester 1 17/18 EYH 17
6.2.3 Sifat TFD Lainnya
Pembalikan waktu
Bila x  n  
TFD
N
 X (k )
maka x   n   N  x  N  n  
TFD
N
 X   k   N )  X  N  k 
Bukti
N 1
TFD  x  N - n    x  N - n  e  j 2 kn / N
n 0

Indeks n diganti menjadi m  N - n

N 1
TFD  x  N - n    x  m  e  j 2 k  N  m  / N
m 0
N 1
=  x  m  e j 2 km / N
m 0
N 1
=  x  m  e  j 2 m  N  k  / N  X  N  k 
m 0

X  N  k   X   k   N , 0  k  N -1

Edisi Semester 1 17/18 EYH 18

Pergeseran waktu sirkular deretan
Bila x  n  
TFD
N
 X (k )
maka x   n  l   N 
TFD
N
 X  k  e  j 2 kl / N
Bukti

 
N 1
TFD x   n  l   N   x   n  l   N e  j 2 kn / N
n 0
l 1 N 1
=  x   n  l   N e  j 2 kn / N   x  n  l  e  j 2 kn / N
n 0 n l

x  n  l N  x  N - l  n 
l 1 l 1

 x   n  l   N e j 2 kn / N =
n 0
 x  N - l  n e
n 0
 j 2 kn / N

N 1
=  x  m e
m  N l
 j 2 k  m  l  / N

N 1 N 1l

 x  n  l  e j 2 kn / N 
n l
 x m e
m 0
 j 2 k  m  l  / N

   x m e
N 1
TFD x   n  l   N   j 2 k  m  l  / N

m 0

 X  k  e  j 2 kl / N

Edisi Semester 1 17/18 EYH 19

Pergeseran frekuensi sirkular
Bila x  n  
TFD
N
 X (k )
maka x  n  e j 2 ln/ N 
TFD
N
 X  k  l  N

Sifat konjugat kompleks

Bila x  n  
TFD
N
 X (k )
maka x  n  
TFD
N
 X    k   N  X   N  k 

Perkalian dua deretan

Bila x1  n  
TFD
N
 X 1 (k ) dan x2  n  
TFD
N
 X 2 (k )
1
maka x1  n  x2  n  
TFD
N
 X 1 (k ) X 2 (k )
N

Teorema Parseval
Bila x  n  
TFD
N
 X (k ) dan y  n  
TFD
N
 Y (k )
N -1 N -1
1
maka  x  n  y  n  
n 0 N
 X (k )Y
k 0

(k )

Bila y  n   x  n 
N -1 N -1
1
 x n  X (k )
2 2

n 0 N k 0

Edisi Semester 1 17/18 EYH 20

6.3 Metoda Pemfilteran Linier dengan TFD
6.3.1 Pemfilteran Linier dengan TFD

Misal filter FIR dengan respon impuls h  n  panjang M , diberi input x  n  dengan panjang L,
x  n   0, n  0 dan n  L
h  n   0, n  0 dan n  M
Keluaran filter FIR tersebut adalah,

y n   x k  h n  k   x n  h n
k 

Panjang y  n  adalah M  L - 1.
Dalam domain frekuensi
Y (e j   )  X (e j ).H (e j )
Bila y  n  direpresentasikan secara unik dalam domain frekuensi oleh sampel-sampel
spektrum Y (e j   ) yang terdiri dari satu set frekuensi diskrit maka jumlah sampel
frekuensi diskrit minimum M  L - 1.
Oleh karena itu ukuran DFT N  M  L - 1 agar dapat merepresentasikan
y  n  dalam domain frekuensi.

Y  k   Y (e j    ) 2 k k  0, 1,..., N - 1

n

= X (e j ). H (e j   ) 2 k k  0, 1,..., N - 1

n

Y k   X k  H k  k  0, 1,..., N - 1
Sinyal x  n  dan h  n  disisipkan sampel bernilai nol (zero padding) hingga panjangnya N sampel.

Edisi Semester 1 17/18 EYH 21

Contoh
Tentukan respons y  n  untuk filter FIR dengan respon impuls h  n  yang diberi input x  n  .
h  n   1, 2, 3 , x  n   1, 2, 2, 1 ,
 
Solusi
Panjang x  n  adalah 4, panjang h  n  adalah 3. Panjang sinyal hasil konvolusi linier adalah 6.
Jumlah sampel DFT minimum 6. Untuk menyederhanakan proses perhitungan digunakan N  8.
7 2 k k k 3 k
j j j j
X k    x n e
n
8
=1+2e 4
+2 e 2
 e 4

n 0

2 2 43 2  2 2 43 2 
X 0  6 X 1   j   X  2   1  j X 3   j  
2  2  2  2 
2 2 43 2  2 2 43 2 
X  4  0 X 5   j   X  6   1  j X 7   j  
2  2  2  2 
7 2 k k k
j j j
H k    x n e
n
8 4 2
=1+2e +3 e
n 0

H 0  6 H 1  1  2  j 3  2   H  2   2  j 2 H 3   1 2  j 3  2  
H  4  2 H 5  1 2  j 3  2   H  6   2  j 2 H 7  1 2  j 3  2 
Y k   X k  H k 
Y  0   36 Y 1  14, 07  17, 48 Y 2  j4 Y  3   0, 07  j0, 515
Y  4  0 Y  5   0, 07  j0, 515 Y 6   j4 Y  7   14, 07  17, 48
2 k
1 7
y n  Y k  e
j n
8
, n  0, 1,..., 7
8 k 0
y  n   1, 4, 9, 11, 8, 3, 0, 0
Hasil konvolusi sirkular 6 sampel untuk x  n  dan h  n  adalah 1, 4, 9,11, 8, 3
Hasil konvolusi linier untuk x  n  dan h  n  adalah 1, 4, 9,11, 8, 3
Edisi Semester 1 17/18 EYH 22
6.3.2 Pemfilteran Deretan yang Panjang

6.3.2.1 Metoda Overlap-save

Asumsi filter FIR, dengan h(n) panjang M.
Data input dipecah menjadi blok data yang panjangnya L sampel, L >> M
Data input diubah menjadi blok data input yang panjangnya N = L +M – 1.
M – 1 sampel pada blok data input sekarang berasal dari blok data input sebelumnya.
DFT N sampel dilakukan pada setiap blok data input.
Dilakukan zero padding sejumlah L-1 pada h(n) sehingga panjangnya N
dan selanjutnya dilakukan DFT N sampel.
Blok data input
 
x1  n   0, 0,..,0,x  0  ,x 1 ,...,x  L  1 
 M 1 points 
 
 
x2  n    x  L  M  1 ,...,x  L  1 ,x  L  ,...,x  2L  1 
 M 1 points from x1 n  L new data points 
 
 
x3  n    x  2 L  M  1 ,...,x  2 L  1 , x  2 L  ,...,x  3L  1 
 M 1 points from x2  n  L new data points 

Edisi Semester 1 17/18 EYH 23

Perkalian N sampel DFT untuk {H(k)} dan {Xm(k)} blok data ke –k adalah

Y m k   H k  X m k  k  0, 1,..., N - 1

N sampel IDFT , y m  n 


      


y m  n   y m  0  y m 1 y m  2  ... y m  M  1 y m  M  ... y m  N  1

L sampel terakhir dari y m  n  sama dengan hasil konvolusi linier

ym  n  ym  n n  M , M  1,..., N - 1

Edisi Semester 1 17/18 EYH 24

6.3.2.2 Metoda Overlap-add
Asumsi filter FIR, dengan h(n) panjang M.
Data input dipecah menjadi blok data yang panjangnya L sampel, L >> M
Data input diubah menjadi blok data input yang panjangnya N = L +M – 1.
Pada setiap blok data input ditambahkan zero M – 1 sampel .
DFT N sampel dilakukan pada setiap blok data input.
Dilakukan zero padding sejumlah L-1 pada h(n) sehingga panjangnya N
dan selanjutnya dilakukan DFT N sampel.
Blok data input
 
x1  n    x  0  ,x 1 ,...,x  L  1 , 0, 0,.., 0 
 M 1 zeros 
 
x2  n    x  L  ,x  L  1 ...,x  2 L  1 , 0, 0,.., 0 
 M 1 zeros 
 
x3  n    x  2 L  ,x  2 L  1 ...,x  3L  1 , 0, 0,.., 0 
 M 1 zeros 

Edisi Semester 1 17/18 EYH 25

 Perkalian N sampel DFT untuk {H(k)} dan {Xm(k)} blok data ke –m adalah

Y m k   H k  X m k  k  0,1,..., N - 1

N sampel IDFT , y m  n 
y  n    y1  0  ,y1 1 ,..., y1  L  1 , y1  L   y2  0  , y1  L  1  y2 1 ,..., y1  N  1  y2  M  1 , y2  M  ,...

Soal :

Diketahui 2 deretan sebagai berikut;

xn   n  1, 0  n  9 dan hn   1,0,1
Implementa sikan pemfilteran menggunaka n overlap - save
method dan overlap - add menggunaka n N  6 untuk
menghitung yn  xn   hn 

Edisi Semester 1 17/18 EYH 26

 Konvolusi Overlap-Add

x(n) h(n)

n n
x0(n) h(n)  x0(n)

n n
x1(n) h(n)
 x1(n)

n n
x2(n) h(n)
 x2(n)

n n
N 2N 3N valid OLA
h(n)  x(n)
n
N 2N 3N
Edisi Semester 1 17/18 EYH 27
Soal
Diketahui 2 deretan sebagai berikut;
x1 n   1,2,2,1 dan x2 n   1,1,1,1
a.Tentukan konvolusi linier x3 n  kedua deretan diatas
b. Tentukan konvolusi sirkular x4 n  kedua deretan diatas untuk
N  4,5,6 dan 7.
c. Jika en   x4 n   x3 n , tentukan en  untuk N  4,5,6 dan 7.

Edisi Semester 1 17/18 EYH 28

6.4 Analisa Frekuensi Sinyal dengan TFD
xn   cos0.48n   cos0.52n ,0  n  9
Transformasi Fourier Diskrit 10 sample dari xn  adalah
2nk
j
X k   n 0 xn e
9
N

Edisi Semester 1 17/18 EYH 29

xn   cos0.48n   cos0.52n ,0  n  49
Transformasi Fourier Diskrit 50 sample dari xn  adalah
2nk
j
X k   n 0 xn e
49
N

Edisi Semester 1 17/18 EYH 30

xn   cos0.48n   cos0.52n ,0  n  51
Transformasi Fourier Diskrit 52 sample dari xn  adalah
2nk
j
X k   n 0 xn e
51
N

Edisi Semester 1 17/18 EYH 31

  cos0.48n   cos0.52n ,0  n  9
xn   
0, 10  n  99
Transformasi Fourier Diskrit 100 sample dari xn  adalah
2nk
j
X k   n 0 xn e
99
N

Edisi Semester 1 17/18 EYH 32

xn   cos0.48n   cos0.52n ,0  n  9
Transformasi Fourier Diskrit 10 sample dari xn  adalah
2nk
j
X k   n 0 xn e
9
N

Edisi Semester 1 17/18 EYH 33

 DFT
2
j
• DFT: ( WN  e N )
N1 WN@2/N
X[k]   kn
x[n]WN WNr dgn N
harga berbeda
n0
Bentuk matriks: 
algoritma efisien ?
 X[0]  1 1 1 1  x[0] 
   1 2  
X[1] 1 W W WN(N1)  x[1] 
    N N
 X[2] 1 WN2 WN4 WN2(N1)  x[2] 
    
    
(N1) (N1) 2
X[N1] 1 WN WN2(N1) WN x[N1]

Edisi Semester 1 17/18 EYH 34


 Kompleksitas perhitungan
N1
X[k]   kn
x[n]WN
n0
• (N perkalian kompleks + N-1 penjumlahan kompleks)  N sample (k =
0..N-1)
– perkalian kompleks : (a+jb)(c+jd) = ac - bd + j(ad+bc)= 4 perkalian
real + 2 penjumlahan real

– penjumlahan kompleks = 2 penjumlahan real
• Total: 4N2 perkalian real, 4N2-2N penjumlahan real

Edisi Semester 1 17/18 EYH 35

6.5 Fast Fourier Transform FFT

• Mengurangi kompleksitas DFT dari O(N2)

menjadi O(N·logN)
• Dekomposisi DFT menjadi beberapa tahap DFT yang lebih kecil DFT

Edisi Semester 1 17/18 EYH 36

 Desimasi Waktu FFT
(Decimation in Time )
• Rumus DFT disusun sbb:
N1
X k    x n nk
 WN
n0
N
1

 x2m  
2
2m1k
  WN2mk  x 2m 1  WN
m0
N
2
1 N
2
1
  x2m  W N
2
mk k
 WN  x2m 1  W N
2
mk

m0 X0[<k>N/2] m0 X1[<k>N/2]

N/2 sample DFT dari x utk n genap N/2 sample DFT dari x utk n genap
Edisi Semester 1 17/18 EYH 37
 Desimasi Waktu FFT
(Decimation in Time )
• Deretan terbatas x[n], 0 ≤ n < N, N = 2M
– Panjangnya : pangkat 2
• Membagi TZ menjadi bgn genap dan ganjil
dari n :
X z    x nz  X0 z  z X1 z    
N1 n 2 1 2
n0
1 1
X0 z    X1 z   
N N
2
x 2nz n 2
x 2n 1z n
n0 n0
TZ N/2 sample berasal dari TZ N/2 sample berasal dari
sample genap x[n] sample ganjil x[n]
Edisi Semester 1 17/18 EYH 38
 Decimation in Time (DIT) FFT
DFTN x n X
ˆ k   X z  ze j 2 k / N W 1 N


 X 0 e   e
j 2 k / N 2  j 2 k / N
X1 e 
j 2 k / N 2

 e j2 k / N 2
 e j2 k / N / 2 
 WN 1
2

 X k   DFTN x 2n k
 WN DFTN x 2n 1
2 2


k = 0..N-1
 X0 k   N
2
 WNk X1 k  N
2
N/2 sample DFT
k = 0..N/2-1

 Edisi Semester 1 17/18 EYH 39

 Decimation in Time (DIT) FFT
DFTN x n  DFTN x0 n WNk DFTN x1 n
2 2

• Evaluasi N sample DFT diperlukan evaluasi N/2

sample DFT (plus beberapa mult/add)
• Bila DFTN{•} ~ O(N2)
maka DFTN/2{•} ~ O((N/2)2) = 1/4 O(N2)
 Total komputasi~ 2  1/4 O(N2)
= 1/2 komputasi (+e) DFT secara langsung

Edisi Semester 1 17/18 EYH 40

 Flowgraph DIT 1 tahap
 
X k   X0 k N
2
 WNk X1 k   N
2

Sample
Genap
x[n]


Sample
Ganjil
x[n]

Struktur FFT klasik

Edisi Semester 1 17/18 EYH 41
 DIT beberapa tahap
• Bila dekomposisi satu DFTN menjadi dua
DFTN/2 yang lebih kecil dapat mereduksi
algoritma maka……..
Bagaimana jika selanjutnya dibagi menjadi
DFTN/4 ?
0≤k<N
   
X k   X0 k N  WNk X1 k
2
N
2

• X0 k   X00
0 ≤ k < N/2
k  W X k 
N
4
N
2
k
01 N
4

 N/4-sample DFT sample N/4-sample DFT sample

genap dari subset genap x[n] ganjil dari subset genap x[n]

 X1 k   X10 k   W X k 
Edisi Semester 1 17/18 EYH
N
4
k
N
2
11 N
4
42
Flowgraph DIT 2 tahap

Edisi Semester 1 17/18 EYH 43

 Multi-stage DIT FFT
• Desimasi dilakukan hingga 2 point DFT:
elemen“butterfly”
DFT2
X[0] = x[0] + x[1]
X[1] = x[0] - x[1]
 1 = W2 0
-1 = W21
 N = 2M-sample DFT berkurang menjadi M
tahap twiddle faktor & penjumlahan
 perkalian real < M·4N , penjumlahan real <
2M·2N
 complexity ~ O(N·M) = O(N·log2N)
Edisi Semester 1 17/18 EYH 44
 Implementasi FFT
• Pada satu tahap :
XX0[r] XX[r] 2 perkalian
•• W Nr •• kompleks
• •
XX1[r] XX[r+N/2] 2  r N 
WNr+N/2 r N2 j 2

WN e N
2 r 2 N / 2
j j
• disederhanakan: e e N N

 WNr
XX0[r] XX[r]
hanya 1
XX1[r] X [r+N/2] perkalian kompleks
W Nr -1 X
SUB
Edisi Semester 1 17/18 EYH 45