21
2.3.5. Fast Fourier Transform
Fast
Fourier
Transform
(FFT)
yang
ditemukan
tahun
1965
merupakan
pengembangan dari Fourier Transform (FT). Penemu FT adalah J. Fourier pada
tahun
1822.
FT
membagi
sebuah
sinyal
menjadi
frekuensi yang
berbeda-beda
dalam fungsi eksponensial yang kompleks.
(2. 5)
Adapun
t
menyatakan
waktu,
f
menyatakan
frekuensi,
X(f)
menyatakan
sinyal dalam domain frekuensi, dan x(t) menyatakan sinyal dalam domain waktu.
Untuk
pemprosesan
sinyal
diskrit,
sebuah
algoritma
baru
yang
disebut
Discrete
Fourier
Transform
(DFT) diciptakan.
DFT
memiliki
rumus
sebagai
berikut.
(2. 6)
Adapun
N
menyatakan jumlah
sampel.
Persamaan
(2.5)
memiliki
kompleksitas
algoritma
O(N/2).
FFT
membagi
sampel
N
menjadi
dua
buah
N¹
dan
N²
secara
rekursif
bersama
perkalian
dengan
hasil
yang
didapatkan lalu
dikalikan
dengan
sampel
.
Hal
ini
membuat
FFT
hanya
memiliki
kompleksitas O(N log N). Dalam pemprosesan sinyal suara, FFT akan mengubah
sinyal suara dalam domain waktu menjadi domain frekuensi.
 |