TKE 2403
SISTEM PENGOLAHAN ISYARAT
Kuliah 7 – Transformasi Fourier Cepat (FFT : Fast Fourier Transform)
Indah Susilawati, S.T., M.Eng.
Program Studi Teknik Elektro Fakultas Teknik dan Ilmu Komputer Universitas Mercu Buana Yogyakarta 2009
1
KULIAH 7 SISTEM PENGOLAHAN ISYARAT TRANSFORMASI FOURIER CEPAT (FFT : FAST FOURIER TRANSFORM) Transformasi
Fourier
diskret
telah
didefinisikan
sebelumnya
dan
dinyatakan dengan formula, N −1
X n = ∑ xr e
−j
2π n r N
r =0
(139)
Selama bertahun-tahun, penggunaan formula ini terhalang oleh banyaknya jumlah komputasi yang harus dilakukan. Untuk setiap garis spektral Xn, harus dilakukan evaluasi fungsi sebanyak N (pada eksponensial) dan perkalian sebanyak N. Dan untuk memperoleh seluruh spektrum yang ada maka diperlukan N2 perkalian dan N2 evaluasi fungsi. Jika difokuskan hanya pada jumlah perkaliannya saja maka algoritma untuk memperoleh transformasi Fourier diskret dikatakan mempunyai orde N2 atau O(N2). Persamaan (139) dapat ditulis kembali sebagai, N −1
X n = ∑ xr w r n r =0
(140)
dengan
w=e
−
j 2π N
(141)
Misalkan bahwa N dapat dibagi 2 maka penjumlahan pada persamaan (140) dapat dibagi menjadi 2 juga yaitu penjumlahan untuk r genap dan untuk r ganjil.
2
N −1 2
N −1 2
r =0
r =0
X n = ∑ x2 r w 2 r n + ∑ x( 2 r +1) w ( 2 r +1) n atau N −1 2
N −1 2
r =0
r =0
X n = ∑ x2 r w 2 r n + w n ∑ x( 2 r +1) w 2 r n
(142)
Suku pertama pada persamaan (142) adalah DFT untuk r genap yaitu {x0, x2, ..., xN – 2 } dan ditulis sebagai N −1 2
E n = ∑ x2 r w 2 r n
(143)
r =0
Suku kedua pada persamaan (142) adalah DFT untuk r ganjil yaitu {x1, x3, x5, ..., xN – 1 } dan ditulis sebagai N −1 2
On = ∑ x( 2 r +1) w ( 2 r +1) n r =0
(144)
Dengan demikian DFT dalam deret sebanyak N dapat dinyatakan dengan dua DFT dalam deret sebanyak N/2,
X n = E n + w n On
(145)
Perhatikan bahwa En dan On adalah DFT dalam deret sebanyak N/2, maka hubungan periodisitas menunjukkan
E
n+
N 2
= En
O
dan
3
n+
N 2
= On
(146)
Dengan cara ini maka untuk mencari satu garis spektral tertentu hanya perlu dilakukan
sebanyak 2 x (N/2)2 = 2 x N2/4 = N2/2 perkalian. Jika
memperhitungkan perkalian dengan wn maka jumlah perkalian yang harus dilakukan adalah N2/2 + N. Dengan asumsi N << N2, maka dapat dinyatakan jumlah perkalian yang dibutuhkan adalah dalam orde N2/2 atau O(N2/2), yaitu setengah dari jumlah perkalian yang diperlukan jika digunakan cara lama.
Jika N/2 juga dapat dibagi 2, maka dapat dilakukan yang sama dengan yang telah dilakukan sebelumnya sehingga kita dapat menyatakan DFT N/2 titik masing-masing dengan 2 DFT N/4 titik. Hasilnya adalah pengurangan jumlah perkalian yang lebih banyak lagi. Jika N = 2M (M disebut radiks), maka prosedur di atas dapat dilakukan berulangulang hingga sampai pada DFT 1 titik yaitu X0 = x0 yang berarti tidak diperlukan perkalian. Lalu dimana letak komputasinya? Dengan N = 2M maka berarti ada M tingkat dimana M = log2 N. Pada setiap tingkat harus dilakukan N perkalian, maka algoritma memerlukan N log2 N perkalian. Keuntungan menggunakan FFT dibandingkan DFT adalah sebesar N2 N = N log 2 N M Maka misalkan N = 1024, maka M = 10 sehingga N/M = 1024/10 ≈ 100, dan ini akan membesar dengan membesarnya N. Algoritma FFT ini merupakan salah satu algoritma numeris paling cerdas di abad 20.
4
Sebuah Contoh Misalkan FFT 8 titik yaitu {x0, x1, ..., x8} yang dapat dinyatakan dengan persamaan berikut. 7
X n = ∑ xr w r n
(147)
r =0
Dalam hal ini
w=e
−
jπ 4
(148)
Dan menurut persamaan (145) dapat dinyatakan
3
En = ∑ x2 r w
3
2r n
On = ∑ x( 2 r +1) w 2 r n
dan
r =0
r =0
Dengan mengingat bahwa periodisitasnya 8/2 = 4 maka X0 = E0 + w0 O0 X1 = E1 + w1 O1 X2 = E2 + w2 O2 X3 = E3 + w3 O3 4
(149) 4
X4 = E4 + w O4 = E0 + w O0 X5 = E5 + w5 O5 = E1 + w5 O1 X6 = E6 + w6 O6 = E2 + w6 O2 X7 = E7 + w7 O7 = E3 + w7 O3 Hasil tersebut dapat ditampilkan dalam bentuk diagram, dan seringkali disebut dengan istilah kupu-kupu FFT (FFT Butterfly). Perhatikan Gambar 42 berikut ini.
5
Gambar 42. Kupu-kupu FFT fase pertama
Untuk FFT fase kedua maka harus diperhatikan tentang dekomposisi En. Dalam hal ini, bagian “genap” dan “ganjil” pada deret adalah {x0, x4} dan {x2, x6} Selanjutnya definisikan En = EEn + w 2n OEn
(150)
Dalam hal ini
1
EE n = ∑ x4 r w r =0
1
4r n
dan
OE n = ∑ x( 4 r + 2 ) w 4 r n r =0
dan hasilnya secara detil adalah (dengan periode N/4 = 8/4 = 2),
6
(151)
E0 = EE0 + w0 OE0 E1 = EE1 + w2 OE1
(152)
E2 = EE2 + w4 OE2 = EE0 + w4 OE0 E3 = EE3 + w6 OE6 = EE1 + w6 OE1 Dan kupu-kupu FFT fase kedua yang bersesuaian diperlihatkan pada Gambar 43 berikut ini.
Gambar 43. Sebagian kupu-kupu FFT fase kedua
Masih tersisa satu fase FFT lagi (log2 8 = 3). Misalkan EE0, akan dibagi menjadi 2 DFT dengan panjang N/8 = 8/8 = 1, sehingga EEn = EEEn + w 4n OEEn
(153)
Sehingga EE0 = EEE0 + w 0 OEE0 = x0 + x4 EE1 = EEE1 + w 4 OEE1 = EEE0 + w 4 OEE0= x0 + w4 x4 Dan kupu-kupu FFT fase kedua yang bersesuaian diperlihatkan pada Gambar 44 berikut ini. 7
Gambar 44. Salah satu kupu-kupu FFT fase ketiga (fase terakhir)
Jika semua kupu-kupu FFT yang dihasilkan digambarkan maka akan terlihat bahwa, EEE0 = x0 OEE0 = x4 EOE0 = x2 OOE0 = x6 EEO0 = x1 OEO0 = x5 EOO0 = x3 OOO0 = x7 Misalkan diasumsikan OEO adalah suatu bilangan biner dengan O adalah logika 1 dan E adalah logika 0. Maka OEO adalah bilangan biner 101 yang jika dinyatakan dalam desimal adalah bilangan 5 (yaitu bersesuian dengan indeks x pada hasil tersebut di atas).
Pada kupu-kupu FFT yang lengkap, kolom paling kiri dan paling kanan adalah x0 Æ X0 x4 Æ X1 x2 Æ X2 x6 Æ X3 x1 Æ X4
8
x5 Æ X5 x3 Æ X6 x7 Æ X7 Korespondensi tersebut diperoleh dengan bit reversal. Bit reversal adalah permutasi dimana data dengan indeks n (misalnya n = 5) yang ditulis dalam bilangan biner b4b3b2b1b0 dibalik (di-reversed) menjadi b0b1b2b3b4. Untuk menemukan pasangan xr dan Xn dapat digunakan prosedur berikut. Misalkan akan dicari elemen ke-6. Pertama ubahlah bilangan 6 menjadi bilangan biner yaitu 110. Kemudian lakukan bit reversal sehingga hasilnya adalah 011 dan selanjutnya ubah kembali menjadi desimal, hasilnya adalah 3. sehingga x6 berkorespondensi dengan X3. (Cek untuk pasangan yang lainnya). DFT Sinyal Sinusoidal Misalkan sebuah sinyal sinusoidal dengan frekuensi f Hz sebagai berikut. x(t) = A sin (2π f t)
(154)
Versi tercupliknya adalah x j = A sin (2π f t j) = A sin (2π f j Δt )
(155)
Maka DFT-nya adalah N −1
X n = ∑ A sin(2π f r Δ t ) e
−j
2π n r N
(156)
r =0
Atau dapat dinyatakan dalam bentuk eksponensial sebagai, −j A N −1 j 2π f r Δ t − j 2π f r Δ t Xn = ( e e ) e − ∑ 2 j r =0
2π n r N
n n N −1 j 2π r ( − f Δ t − ) ⎫ A ⎧ N −1 j 2π r ( f Δ t − N ) N = − ∑ (e ⎨∑ e ⎬ 2 j ⎩ r =0 r =0 ⎭
9
Ingat bahwa,
f Δt =
dalam hal ini α =
f α = Δf N N
f , dan merupakan bilangan bulat hanya pada frekuensi Δf
sinusoidal yang bersesuaian dengan garis-garis spektral.
A ⎧ N −1 j 2π Xn = ⎨∑ e 2 j ⎩ r =0
(α − n ) r N
N −1
− ∑ (e
j 2π
r =0
( −α − n ) r N
⎫ ⎬ ⎭
Dalam pertemuan yang terdahulu telah dibahas bahwa N −1
∑e
j 2π
(α − n ) r N
r =0
= Nδ α n
jika α adalah bilangan bulat antara 0 dan N/2. Hal ini berarti bahwa spektrumnya adalah
Xn =
AN (δ α , n − δ −α , n ) 2j
(157)
Jika α adalah bilangan bulat, maka hanya ada 2 garis spektral yang tak – nol yaitu pada ±f. Jika α bukan merupakan bilangan bulat, maka jumlahannya bukan fungsi – delta dan spektranya tak – nol di semua frekuensi namun puncaknya ada di sekitar ±f. Cara lain dalam memandang hal ini adalah jika α adalah bilangan bulat antara 0 dan N/2 maka gelombang sinusnya periodik dalam jendela DFT dan DFT akan dapat menyelesaikannya sehingga hanya ada satu frekuensi saja yang muncul. Jika α bukan merupakan bilangan bulat, maka gelombang sinusnya tidak periodik dalam jendela DFT dan frekuensi-frekuensi yang lain akan muncul.
10
Fenomena dimana ada energi yang tersebar pada beberapa garis spektral jika sinyal tidak periodik pada jendela pencuplikan disebut dengan istilah bocoran (leakage).
SPEKTRA Jendela (Windows) Pada pembahasan yang lalu telah dibahas bahwa jika gelombang sinus tidak periodik pada jendela Fourier, maka energi dalam spektrumnya akan tersebar pada beberapa garis spektral dan fenomena ini disebut leakage. Hal ini dapat dipandang sebagai berikut. Misalkan terdapat sinyal periodik seperti diperlihatkan pada Gambar 45 berikut.
Gambar 45. Sinyal periodik “tidak periodik” pada jendela pencuplikan
Pada gambar di atas, sinyal yang aslinya periodik menjadi tidak periodik setelah diterapkan pencuplikan dengan jendela sepanjang τ. Namun DFT tetap menganggap sinyal tersebut berulang di wilayah luar jendela dan akan merepresentasikan spektral sinyal tercuplik seperti digambarkan pada Gambar 46. 11
Gambar 46. Sinyal periodik yang dihasilkan oleh jendela pencuplikan
Sinyal yang diperlihatkan pada Gambar 46 mempunyai komponen frekuensi yang lain (yang sebelumnya tidak ada pada sinyal aslinya). Biasanya spektrum akan memiliki komponen frekuensi tinggi, hal ini berkaitan dengan transisi yang mendadak pada bagian-bagian sinyal tersebut.
Spektrum yang dihasilkan pada pencuplikan ini dapat dilihat sebagai konvolusi antara sinyal sinus dan jendela kotak (rectangular window) yang dinyatakan sebagai,
W (ω ) =
⎛ ωτ ⎞ sin ⎜ ⎟ ⎝ 2 ⎠
(158)
ω 2
Apakah ada jendela lain yang lebih baik (daripada jendela kotak), dengan fungsi konvolusi yang lebih sempit sehingga dapat diperoleh frekuensi yang lebih tepat? Salah satu jenis jendela yang lebih baik daripada jendela kotak adalah adalah jendela yang kedua ujungnya nol,
misalnya jendela Hanning (Hanning
window).
12
Jendela Hanning dinyatakan dengan persamaan berikut.
⎛ 2π w(t ) = 1 − cos⎜ ⎝ τ
t⎞ ⎟ ⎠
(159)
Spektrum jendela Hanning sedikit lebih rumit daripada jendela kotak, dan dapat dinyatakan sebagai berikut.
W (ω ) =
j (e − jω t − 1)
Dengan ωτ =
ω 2π
τ
j (e − j (ω −ωτ )t − 1) j (e − j (ω +ωτ )t − 1) − − 2(ω − ωτ ) 2(ω + ωτ )
(160)
.
Pada Gambar berikut dibandingkan spektrum jendela kotak dan jendela Hanning.
Gambar 47. Perbandingan fungsi konvolusi untuk jendela kotak dan jendela Hanning
13
Gambar 48. Perbandingan fungsi konvolusi untuk jendela kotak dan jendela Hanning (skala log)
Terdapat dua perbedaan utama. Lebar puncak sentral untuk jendela kotak lebih kecil daripada pada jendela Hanning. Pada kenyataanya tidak ada jendela lain yang mempunyai lobe utama yang lebih sempit lagi. Perbedaan lain adalah baha jendela kotak mempunyai lobe samping (side lobes) yang besar.
14
