14
j
1
J
.,
(x- 1, y- 1)
(x-1,
y)
(x-1,
y+l)
(x,y-1)
(x,y)
(x,y+ l)
(x
+
l,y)
(x+ l,y+
1)
(x+ l,y-1)
(1,1) (1,2)
(1,3)
(2,1)
(2,2) (2,3)
(3,1)
(3,2)
(3,3)
'-
2,9
Fowier
Transform (FFT)
Fast
Fourier
Transform
adalah
bentuk
penyederhanaan dari
DFT
(Discrete
Fourier
Transform} DFT
dan FFT
memiliki rumus umum
yang
sama,
yaitu:
I
-21!1.
J; =
l:;x,e--;;-1>
f=
Fourier
Transform
k.Jl
x
=
bilangan kompleks
j
=
0,1,2,
... , n-1
i
=
ima,jiner
n
=
banyaknya bi!angan
e
=
bilangan
natural
retapi
penghitungannya berbeda.
Pada
perhitungan
dilakukan
secara
direct
computation
dengan
jum!ah perhitungan
sebanyak
N²,
sedangkan
pada
FFT
perhitungan hanya N log N.
Dalam
suatu
sinyal periodik (berulang), suatu
titik
antara periode yang
satu
dengan yang lain
memiliki
nilai
yang
sama
(faktor twiddle).
Dengan
demikian
terdapat nilai-nilai yang
sama
yang
tidak
perlu
dihitung
kemball.
Algoritma
mencegah suatu
nilai
yang
sama
dihitung dua
kali.
Kemudian
semua Pllai
yang
sama
akan
dijumlahkan. Hal
inilah
yang
menyebabkan
FFT
menjadi
lebih
cepat
daripada
DFT.
Oieh
karena
itu
penghitungan
DFT
menghemat memori,
dan lebih
sederhana dihandingkan dengan
DFT.
 |