Thursday, October 11, 2018
Mengenal Fast Fourier Transform (FFT)
Pada tahun 1960, J. W. Cooley dan J. W. Tukey, berhasil merumuskan suatu teknik perhitungan algoritma Fourier Transform yang efisien. Teknik perhitungan algoritma ini dikenal dengan sebutan Fast Fourier Transform atau lebih populer dengan istilah FFT yang diperkenalkan oleh J.S.Bendat dan A.G.Piersol pada 1986. Fast Fourier Transform dalam bahasa indonesia adalah Transformasi Fourier Cepat adalah sumber dari suatu algoritma untuk menghitung Discrete Fourier Transform (transformasi fourier diskri tatau DFT) dengan cepat, efisien dan inversnya.
Fast Fourier Transform (FFT) diterapkan dalam beragam bidang dari pengolahan sinyal digital dan memecahkan persamaan diferensial parsial menjadi algoritma-algoritma untuk penggandaan bilangan integer dalam jumlah banyak. Ada pun kelas dasar dari algoritma FFT yaitu decimation in time (DIT) dan decimation in frequency (DIF). Garis besar dari kata Fast diartikan karena formulasi FFT jauh lebih cepat dibandingkan dengan metode perhitungan algoritma Fourier Transform sebelumnya.
Metode FFT memerlukan sekitar 10000 operasi algoritma matematika untuk data dengan 1000 observasi, 100 kali lebih cepat dibandingan dengan metode sebelumnya. Penemuan FFT dan perkembangan personal komputer, teknik FFT dalam proses analisa data menjadi populer, dan merupakan salah satu metode baku dalam analisa data. Satu bentuk transformasi yang umum digunakan untuk merubah sinyal dari domain waktu ke domain frekuensi adalah Transformasi Fourier:
Pada tahun 1960, J. W. Cooley dan J. W. Tukey, berhasil merumuskan suatu teknik perhitungan algoritma Fourier Transform yang efisien. Teknik perhitungan algoritma ini dikenal dengan sebutan Fast Fourier Transform atau lebih populer dengan istilah FFT yang diperkenalkan oleh J.S.Bendat dan A.G.Piersol pada 1986. Fast Fourier Transform dalam bahasa indonesia adalah Transformasi Fourier Cepat adalah sumber dari suatu algoritma untuk menghitung Discrete Fourier Transform (transformasi fourier diskri tatau DFT) dengan cepat, efisien dan inversnya.
Fast Fourier Transform (FFT) diterapkan dalam beragam bidang dari pengolahan sinyal digital dan memecahkan persamaan diferensial parsial menjadi algoritma-algoritma untuk penggandaan bilangan integer dalam jumlah banyak. Ada pun kelas dasar dari algoritma FFT yaitu decimation in time (DIT) dan decimation in frequency (DIF). Garis besar dari kata Fast diartikan karena formulasi FFT jauh lebih cepat dibandingkan dengan metode perhitungan algoritma Fourier Transform sebelumnya.
Metode FFT memerlukan sekitar 10000 operasi algoritma matematika untuk data dengan 1000 observasi, 100 kali lebih cepat dibandingan dengan metode sebelumnya. Penemuan FFT dan perkembangan personal komputer, teknik FFT dalam proses analisa data menjadi populer, dan merupakan salah satu metode baku dalam analisa data. Satu bentuk transformasi yang umum digunakan untuk merubah sinyal dari domain waktu ke domain frekuensi adalah Transformasi Fourier:
Menjelaskan tentang konsep dasar Discrete Fourier Transform (DFT), metode menghitung DFT, dan Fast Fourier Transform (FFT). Pembahasan kali ini bertujuan untuk memberikan pemahaman tentang teknik dasar melakukan perhitungan DFT, menghitung magnitudo, frekuensi dan fase dari hasil perhitungan DFT, serta melakukan perhitungan dengan metode FFT. Bab ini juga menjelaskan tentang cara menghitung spektrum frekuensi. Transformasi Fourier digunakan untuk mentransformasi sinyal analog dari domain waktu ke domain frekuensi (spektrum frekuensi) seperti ditunjukkan pada Gambar 1 dibawah ini
 |
| Gambar 1 |
Discrete Fourier Transform (DFT) adalah bentuk diskrit dari
transformasi Fourier. DFT mentransformasi sinyal diskrit dari domain
waktu ke domain frekuensi (juga dalam bentuk diskrit). Hal ini
ditunjukkan pada Gambar 2 dibawah ini.
 |
| Gambar 2 |
Ketika sebuah sinyal diskrit, seperti pada Gambar 3, ditransformasi dengan menggunakan DFT, maka akan dihasilkan spektrum frekuensi dalam bentuk diskrit seperti pada Gambar 4.
 |
| Gambar 3 |
 |
| Gambar 4 |
Beberapa hal penting yang dapat diamati dari hasil perhitungan DFT di Gambar 4.4 adalah:
- Sinyal dalam domain waktu ditulis dengan huruf kecil (mis. x(n)), sedangkan hasil perhitungan DFT berada dalam domain frekuensi sehingga ditulis dengan huruf besar (mis. X(k)).
- Nomor sample pada sinyal input (domain waktu) ditulis dengan menggunakan huruf n sedangkan nomor sample di domain frekuensi menggunakan huruf k.
- Sinyal input, x(n), memiliki 20 sample, maka hasil perhitungan DFT, X(k), juga memiliki 20 buah sample. Jika sinyal x(n) memiliki N+1 buah sample maka perhitungan DFT menghasilkan K+1 sample, dimana K = N.
- Setiap nilai k mewakili nilai frekuensi tertentu tergantung pada frekuensi sampling, fs, dari sinyal x(n). Jika f = 25 Hz maka.
- |X(k)| memiliki bentuk yang simetris (pencerminan) pada k=10 (setara f/2). Jadi
|X(19)| = |X(1)|
|X(18)| = |X(2)|
|X(17)| = |X(3)|
|X(16)| = |X(4)|
|X(15)| = |X(5)|
|X(14)| = |X(6)|
...
|X(11)| = |X(9)|
|X(18)| = |X(2)|
|X(17)| = |X(3)|
|X(16)| = |X(4)|
|X(15)| = |X(5)|
|X(14)| = |X(6)|
...
|X(11)| = |X(9)|
Maka jika kita menganalisa hasil dari DFT sinyal tersebut, kita cukup menggunakan |X(k)| untuk 0 < k < 10 atau dengan kata lain dari 0 Hz sampai 12.5 Hz yaitu fs/2.
Jika kita menghitung DFT dari sinyal x(n) untuk 0 < n < N, maka hasil DFT yang digunakan adalah X(k) untuk 0 < k < K/2, dimana K = N.
Hal ini dapat juga menjelaskan mengapa fs harus lebih besar dari dua kali frekuensi sinyal. Jika sinyal di atas memiliki frekuensi lebih besar dari fs/2 (12.5 Hz) maka akan digambar pada k > 10 padahal nilai |X(k)| untuk k > 10 seharusnya hanya merupakan pencerminan dari |X(k)| yang lebih kecil dari 10. Sesungguhnya pencerminan ini terjadi secara berulang. Jika kita dapat menghitung |X(k)| untuk nilai k yang lain maka akan menghasilkan pengulangan seperti pada Gambar 5.
 | |
| Gambar 5 |
Sehingga hasil dari DFT sering digambarkan secara draft seperti pada gambar berikut ini.
 |
| Gambar 6 |