20
penjumlac'lan kompleks sebanyak N
2
-
N
Akibatnya seperti
teiah
dikatakan sebe!umnya,
bahwa
perhitungan
langsung seperti
ini
tidakiah
efisien
karena tidak memanfaatkan sifat
simetri dan sifat
periodik dati
DFT
itu sendiri
Dengan
menggunakan
algoritma
FFT,
maka
perhitungan
DFT
akan
menjadi
lebih efisien.
Dan
salah satu a!goritma
komputasi
FFT adalah algmitma
FFT radix-2.
Algotitma
FFT radix-2
adalah perhitungan
terhadap
DFT
N-titik
di mana
N
=
r
v,
di
mana ® adalah bilangan radix dan untuk algoritma
ini
bernilai
2,
sehingga
disebut
FFT
radix-2.
Dengan FFT
radix-2 ini, input
yang
diberikan akan
dipecah me71iadi
du.a
bagian
yang
lebih
kecil,
kemudian tiap-tiap
bagian
yang
!ebih
kecil
itu
dipecah
lagi
menjadi
dua
bagian
ya.'1g
lebiil
keci!
lagi,
dau begitu
seterusnya.
Inputnya
harus
merupakan
ke!ipatan
dua {power
of two), seperti
256,
512,
1024
dan
setemsnya.
Algoritrna
FFT
radix-2
ini
dilakukan
dengan
pendekatan
devide-and-conquer,
di
mana
pendekatan
ini
banyak
digunakan
dalam
perhitungan-perhitungan
pemrosesan
sinyal
digital. Dengan pendekatan de,•ide-and-conquer, DFT N-titik
akan di
pecah
menjadi beberapa DFT
yang
lebih
kecil,
baru
kemudian diselesaikan.
Dalam notasi
kompleks, domain
waktu dan
domain frekuensi, masing-masing
memiliki
satu
sinyal yang
terdiri dari sejumlah
titik
kompleks N.
Tiap-tiap titik
tersebut
terdiri
atas
dna
bagian, yaitu
bagian
real.
dan bagian imajinemya.
Dan ketika dua
variabel kompleks dika!ikan, maka
empat
komponen
tersebut
harus
dikombinasikan
untuk
membentuk dua
komponen hasil
perk:aliannya.
FFT
akan memecah sebuah sinyil N-titik (dalam
domain
wa.lztu) ke
dalam N
'
sinyal
(dalam domain
waktu),
di
mana masiP..g-masin t:e;nrydairi atas
satu
titik.
Gambar
2.9 menunjukklli"l sebuah contoh dari
dekomposisi yang di!akukan oleh FFT.
 |