17
e
+
e
e
+
e
e
e
W
?
2.5.2.
Fast Fourier Transform (FFT)
Fast
Fourier
Transform
(FFT)
merupakan algoritma
yang
sangat
efisien
dalam
mengimplementasikan DFT.
Dalam
perkembangannya,
ada
berbagai
macam
algoritma
yang
dikembangkan
untuk
FFT
ini,
namun
yang akan digunakan adalah algoritma FFT radix-2.
Algoritma FFT
radix-2 digunakan untuk
menghitung DFT
dengan
ukuran
batasan
berupa
perpangkatan dari
2
(N
=
2
k
).
Jumlah
dari
perhitungan yang
dibutuhkan
untuk
memproses
FFT
sejumlah
N-titik
adalah (N/2) log2 N
Dari persamaan pada N-titik pada DFT, yaitu
N - 1
X
(
m
) =
?
n = 0
x
(
n )
j ²
p
nm
/
N
(2-6)
FFT memisahkan input data x(n) menjadi dua bagian, yaitu elemen ganjil
dan elemen genap, sehingga persamaan (2-6) menjadi
X
(
m
)
=
(
N / ² ) -
1
?
n
=
0
x
(
2
n
)
-
j
2
p
(
2
n
)
m
/
N
(
N / ² ) -
1
?
n
=
0
x
(
2
n
+
1)
-
j
2
p
(
2
n
+ ) m / N
(2-7)
Dengan mengeluarkan fase sudut yang konstan dari penjumlahan tersebut
X
(
m
)
=
(
N
/
2
)
-1
?
n
=
0
x
(
2
n
)
-
j
2
p
(
2
n
)
m
/
N
-
j
2
pm / N
(
N
/
2
)
-1
?
n
=
0
x
(
2
n
+
1)
-
j
2
p
(
2
n
)
m
/
N
(2-8)
Dengan notasi baku yang baru, yaitu W
N
=
e
-j2p/N
, maka persamaan (2-8)
berubah menjadi
X
(
m
)
=
(
N
/
2
)
-1
?
n
=
0
x
(
2
n
)
2
nm
+
N
(
N
/
2
)
-1
m
N
n
=
0
x
(
2
n
+
1)
2
nm
N
(2-9)
 |