Mengenal FFT-IFFT

28 09 2010

Mengenal FFT dan IFFT

Fast Fourier Transform adalah suatu algoritma yang digunakan untuk merepresentasikan sinyal dalam domain waktu diskrit dan domain frekuensi. Sementara itu, IFFT adalah singkatan dari Inverse Fast Fourier Transform. Membahas mengenai FFT-IFFT tentunya tidak dapat dilepaskan dari DFT (Discrete Fourier Transform). DFT merupakan metode transformasi matematis untuk sinyal waktu diskrit ke dalam domain frekuensi. Secara sederhana dapat dikatakan bahwa DFT merupakan metode transformasi matematis sinyal waktu diskrit, sementara FFT adalah algoritma yang digunakan untuk melakukan transformasi tersebut.

Secara matematis, DFT dapat dirumuskan sebagai berikut :

dimana disebut sebagai twiddle factor, memiliki nilai , sehingga

Sementara itu, Inverse Discrete Fourier Transform (IDFT) dapat dirumuskan sebagai berikut :

Sehingga persamaan IDFT dapat dituliskan juga sebagai berikut :

FFT dipergunakan untuk mengurangi kompleksitas transformasi yang dilakukan dengan DFT. Sebagai perbandingan, bila kita menggunakan DFT, maka kompleksitas transformasi kita adalah sebesar O(N2), sementara dengan menggunakan FFT, selain waktu transformasi yang lebih cepat, kompleksitas transformasi pun menurun, menjadi O(N log (N)). Untuk jumlah sample yang sedikit mungkin perbedaan kompleksitastidak begitu terasa, namun lain ceritanya bila kita mengambil jumlah sample yang sedikit lebih banyak. Misalnya kita hanya mengambil 2 sample, dengan menggunakan DFT, tingkat kompleksitas transformasi kita adalah 4, sementara dengan menggunakan FFT kompleksitasnya sebesar 0,602. Perbedaan yang semakin mencolok tampak bila kita mengambil jumlah sample yang lebih banyak lagi, misalnya kita ingin meninjau 64 titik sample, maka kompleksitas dengan menggunakan DFT adalah sebesar 4096, sementara dengan menggunakan FFT kompleksitasnya menjadi 115,6. Perbedaan yang sangat mencolok melihat perbandingan yang mencapai hampir 40 kali lipatnya. Kompleksitas transformasi ini terutama menjadi vital saat diimplementasikan pada perangkat riil. Perbandingan kompleksitas DFT dan FFT dapat dilihat pada gambar berikut

Secara umum, terdapat dua buah pendekatan yang dijalankan dalam algoritma FFT. Pendekatan tersebut yaitu Decimation in Time (DIT) serta pendekatan Decimation in Frequency (DIF). DIT merupakan usulan pendekatan yang dikemukakan oleh Cooley-Tukey, sementara DFT merupakan usulan pendekatan algoritma yang dikemukakan oleh Sande-Tukey. Perbedaan utama antara dua pendekatan ini dapat dilihat pada gambar berikut ini

Algoritma Cooley-Tukey

Algoritma Sande-Tukey

Dalam implementasi perangkat, pendekatan DIF lebih disenangi karena data input dapat langsung dimasukkan sesuai dengan posisi aslinya, natural, sementara dalam pendekatan DIT data input harus terlebih dahulu diubah secara bit-reversed.

Pengertian susunan data masukan natural atau bit-reversed secara lebih mudah dapat dilihat pada contoh berikut

Input ke – Deretan bit pada urutan normal Deretan bit-reversed
1 000 (0) 000 (0)
2 001 (1) 100 (4)
3 010 (2) 010 (2)
4 011 (3) 110 (6)
5 100 (4) 001 (1)
6 101 (5) 101 (5)
7 110 (6) 011 (3)
8 111 (7) 111 (7)

Dalam transformasi sinyal waktu diskrit dengan menggunakan FFT dikenal istilah butterfly. Butterfly adalah elemen terkecil dari suatu operasi FFT, seperti tampak pada gambar (1) dan (2).

Masing-masing jenis pendekatan algoritma FFT dapat dikelompokkan lagi menjadi beberapa jenis. Beberapa jenis yang sering digunakan dalam pendekatan FFT adalah Radix-2, Radix-4 serta Radix-8.

Radix-2

Radix-2 berarti, sejumlah N-sample yang akan ditransformasikan dibagi menjadi 2 kelompok dalam tiap kali rekursi yang terjadi. Pada gambar berikut ini dapat dilihat bagaimana proses kerja Radix-2

Dari contoh di atas kita dapat melihat, untuk mentransformasikan 8 titik sample dengan menggunakan Radix-2, maka dibutuhkan 3 tahap proses, angka ini diperoleh dari

Oleh karena tiap tahapannya data masukan dikomputasi menjadi dua bagian, maka jumlah data masukan Radix-2 harus sebesar .

Radix-4

Radix-4 membagi data masukan dalam 4 kelompok dalam tiap kali rekursi. Pada dasarnya Radix-4 adalah Radix-2 untuk 4 titik sample. Oleh karena itu, dapat dikatakan bahwa Radix-4 adalah salah satu generalisasi dari Radix-2. Oleh karena jumlah titik sample harus sebesar , maka ada beberapa kasus yang dapat ditangani dengan menggunakan algoritma Radix-2 namun tidak dapat ditangani dengan menggunakan Radix-4. Pada gambar ini akan ditunjukkan visualisasi dari algoritma Radix-4

Pipeline Streaming

Berbeda dengan Radix-2 serta turunannya, Pipeline Streaming memungkinkan pemrosesan data masukan secara kontinu, tanpa pembagian dalam beberapa tahapan.


Actions

Information

2 responses

28 09 2010
ilmaismail

blep,,blepp,bleep *suara orang tenggelam*

25 11 2010
dina

ini kan disebutkan pendekatan FFT ada radix-2 radix-4 sama radix-8
lalu gimana yang radix-8 kug gak ada?
saya baru mau blajar FFT, jadi masih belum paham… tolong dijelaskan yang radix-8
thanks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: