Fast Fourier Transform

FFT (Fast Fourier Transform) merupakan algoritma untuk mempercepat perhitungan pada DFT (Discrete Fourier Transform) untuk mendapatkan magnitude dari banyak frekuensi pada sebuah sinyal sehingga lebih cepat dan efisien. Algoritma ini lebih memungkinkan digunakan pada perangkat mikrokontroler dengan memori yang kecil. Sebelum membaca atau mempelajari FFT alangkah lebih baik mempelajari DFT terlebih dahulu karena dasar FFT adalah DFT.

FFT sama seperti DFT yaitu dapat mengetahui banyak frekuensi pada sebuah sinyal dalam domain waktu yang dikonversi menjadi domain frekuensi, hanya saja FFT dapat melakukan perhitungan lebih cepat.

Gambar 1. Ilustrasi sinyal ft terdiri dari beberapa frekuensi sinyal f1, f2 dan f3.

 

FFT juga menghasilkan spektrum dengan indeks frekuensi yang sama seperti DFT. 

Gambar 2. ilustrasi spektrum hasil perhitungan FFT.

DFT melakukan perhitungan penuh pada suatu sinyal sebanyak N sampel. Jika jumlah N cukup banyak maka perhitungan memerlukan waktu lebih lama karena DFT melakukan perkalian sebanyak  kali, sehingga semakin banyak jumlah N maka perhitungan semakin lama.

Sebagai contoh jika sebuah sinyal diambil sampelnya sebanyak 8 (N=8) dengan asumsi nilai hasil sampel adalah x(0), x(1), x(2), x(3), x(4), x(5), x(6) dan x(7), maka indeks frekuensi k yang dapat dicari nilainya adalah sebanyak N-1 yaitu k sama dengan 0 hingga k sama dengan 7.

Dari rumus DFT,

dapat dilihat bahwa setiap nilai indeks frekuensi k memiliki total 8 perkalian sampel (karena jumlah sampel N adalah 8, kemudian total k adalah sama dengan jumlah N yaitu k sama dengan 8 sehingga total perkalian adalah N x k sama dengan  sama dengan 8 x 8 sama dengan 64 perkalian. Jika jumlah sampel semakin banyak maka jumlah perkalian pada DFT semakin banyak sebanyak kuadrat jumlah sampel () sehingga membutuhkan waktu perhitungan lebih lama tergantung dari jumlah sampel, dimana semakin banyak sampel maka perhitungan DFT semakin lama. Perkalian dimaksud disini adalah perkalian antara nilai sampel ke n atau x(n) dalam nilai diskrit dengan bilangan eksponensial atau lebih dikenal dengan perkalian bilangan kompleks.

Mengapa FFT lebih cepat dibanding DFT?

Ilustrasi sederhana FFT adalah dengan membagi total sampel N menjad dua kelompok sehingga masing-masing kelompok memiliki N/2 sampel, kemudian pada masing-masing kelompok  dikerjakan menggunakan DFT sehingga jumlah perkalian lebih sedikit dan lebih cepat. 

Karena jumlah total perkalian pada DFT adalah  maka perhitungan jumlah perkalian bilangan kompleks FFT adalah berikut :

Dari perhitungan terlihat bahwa perkalian FFT lebih sedikit dibanding dengan DFT. Jumlah perkalian di atas terlihat bahwa FFT memiliki dua perkalian yang sama, padahal pada DFT dan FFT memiliki kesamaan yaitu setiap hasil perhitungam pada nilai indeks frekuensi k merupakan  penjumlahan setiap sampel n (x(n)) yang dikalikan bilangan eksponensial. Untuk melihat cara kerja FFT dan mengetahui jumlah perkalian secara pasti adalah dengan membuat salah satu kelompok memiliki sampel ganjil, dan kelompok lainnya adalah sampel genab seperti dituliskan di bawah. Lalu 1/N sementara dihilangkan untuk mempersingkat penulisan karena 1/N menandakan nilai rata-rata dari penjumlahan semua nilai n sebanyak sampel N.

Dari pejelasan di atas dasar FFT dapat dituliskan sebagai berikut:

Kemudian dapat dijabarkan :

Jika urutan n genab dituliskan sebagai n = 2r dan urutan n ganjil dituliskan sebagai n = 2r + 1 dengan r adalah bilangan bulat positif maka FFT dapat dituliskan : 

Untuk menyederhanakan penulisan rumus FFT di atas dapat dilakukan dengan mengasumsikan bilangan eksponensial dengan W dimana bilangan eksponensial dengan sampel N/2 dapat dituliskan sebagai berikut:

Dari penjelasan rumus 4, maka rumus 3 dapat ditulis bahwa R = 2rk, sehingga rumus 3 secara keseluruhan dapat ditulis menjadi :

karena  tidak memiliki variabel r maka dapat dikeluarkan dari penjumlahan (sigma), sehingga :

dari,

maka FFT dapat disederhanakan menjadi :

Dari rumus FFT di atas dapat dilihat bahwa setiap nilai indeks frekuensi k memiliki dua kelompok perkalian yaitu kelompok sampel genab dengan bilangan eksponensial dan kelompok sampel ganjil dengan bilangan eksponensial. Hal yang perlu diperhatikan disini adalah pada setiap nilai indeks frekuensi k pada masing-masing kelompok memiliki jumlah sampel maksimum adalah N/2 - 1 yang berarti nilai indeks frekuensi k masing-masing kelompok adalah 0 hingga k sama dengan N/2 - 1.

Untuk mempermudah memahami alur perkalian dan penjumlahan pada FFT seperti yang telah dijelakan di atas maka penulisan FFT dapat diasumsikan sebagai berikut :

Kelompok sampel genab diwakili dengan notasi E[k] :

Kelompok sampel ganjil diwakili dengan notasi O[k]:

sehingga FFT (DFT N/2) dapat disederhanakan menjadi bentuk :

Bentuk FFT di atas menyatakan bahwa X[k] dengan nilai k sama dengan 0 hingga k=N-1 merupakan hasil penjumlahan DFT kelompok genab dan ganjil dimana nilai k pada E[k] dan O[k] adalah 0 hingga k=N/2-1 (mengikuti aturan DFT).  Jika diambil jumlah sampel N = 8 maka terdapat 2 kelompok dimana masing-masing kelompok memiliki 4 sampel genab dan 4 sampel ganjil kemudian masing masing kelompok dilakukan perhitungan DFT, kemudian hasilnya dijumlahkan.

Jika sampel N adalah 8 maka alur FFT dapat dituliskan sebagai berikut :

Alur FFT di atas seolah-olah tidak dapat dilanjutkan karena k maksimum adalah 3 karena jumlah sampel setiap kelompok adalah 4. Akan tetapi, sebuah sinyal pada FFT maupun DFT diasumsikan sebagai sinyal periodik dimana magnitude-nya berulang dalam satu siklus waktu yang dapat diasumsikan sebagai titik dengan posisi sudut tertentu pada sebuah lingkaran seperti ditunjukan pada Gambar 3.

Gambar 3. Ilustrasi sampel N = 8

Sehingga saat k = N/2  hingga k = N-1 dapat dicari dari pengulangan  hasil perhitungan DFT sebelumnya diaman notasi X[k] diganti menjadi notasi X[k + N/2] maka alur nilai k adalah sebagai berikut :

Saat k = 0 -> X[0 + 8/2] = X[4]

Saat k = 1 -> X[1 + 8/2] = X[5]

Saat k = 2 -> X[2 + 8/2] = X[6]

Saat k = 3 -> X[3 + 8/2] = X[7]

sehingga bentuk dasar rumus 8 FFT untuk k = N/2 hingga k = N-1 ditulis sebagai berikut :

dari bentuk eksponensial,

dengan r adalah bilangan bulat positif, maka:

dan,

sehingga:

Sehingga dapat disederhanakan menjadi:

Dari rumus 14,  alur FFT saat k lebih besar N/2-1 dapat dituliskan menjadi: 

Alur FFT di atas dapat digambarkan dengan diagram kupu-kupu seperti ditunjukan pada Gambar 4.

Gambar 4. Diagram kupu-kupu FFT 8 sampel

Diagram kupu-kupu yang memperlihatkan ilustrasi alur DFT N/2 lebih detil ditunjukan pada Gambar 5.

Gambar 5. Diagram kupu-kupu detil FFT 8 sampel

Pembuktian total perkalian bilangan kompleks pada FFT  di atas lebih sedikit dibanding FFT adalah sebagai berikut :

Radix-2 Decimation in Time (DIT) FFT

Secara umum radix-2 FFT mirip dengan  FFT, yang membedakan adalah sampel DFT N/2 (FFT) dibagi lagi dengan 2 terus menerus hingga menyisakan kelompok terkecil dengan 2 sampel setiap kelompoknya. Secara detil, pada satu siklus sebuah sinyal diambil sampel sejumlah N kemudian sampel tersebut dikelompokan menjadi 2 kelompok yaitu ganjil dan genab, kemudian masing-masing kelompok dibagi 2 terus menerus hingga menyisakan 2 sampel, setiap kelompok dilakuan DFT per atau setiap 2 sampel. Radix-2 FFT merupakan bentuk umum FFT Algoritma Cooley-Tukey dan mampu mengurangi jumlah perkalian DFT  menjadi N log2 N perkalian. 

Pada radix-2 FFT, proses DFT dilakukan dengan membagi sampel N DFT dengan bilangan dua pangkat sehingga memiliki tahapan atau langkah sebanyak p dimana nilai tahapan p ditentukan oleh :

Ilustrasi alur FFT radix-2 dapat dilihat pada Gambar 6.

Gambar 6. Ilustrasi alur FFT radix-2 dengan 8 sampel

Penjelasan dasar radix-2 FFT dengan 8 sampel (8 point)

Dari penjelasan radix-2 FFT di atas FFT dengan 8 sampel memiliki 3 tahapan DFT  dimana setiap tahapan dijelaskan pada penjelasan di bawah ini.

Gambar 7 menunjukan hasil sampling atau sampel dari sebuah sinyal dengan jumlah sampel N adalah 8 dimana n adalah urutan sampel dari sampel awal (0) hingga N-1, x(n) merupakan amplitudo hasil sampling sampel ke n.

Gambar 7. Ilustrasi sampel 8 point 

Dengan 8 sampel berarti jumlah tahapan DFT ada 3 mengingat 2 pangkat 3 adalah 8 sehingga beberapa pada FFT radix-2 8 sampel dapat ditulis sebaai berikut:

Tahap 1

Pada tahap 1 dilakukan pengambilan 8 sampel pada sebuah sinyal analok atau sinyal kontinyu sehingga didapatkan 8 data nilai diskrit seperti ditunjukan pada ilustrasi Gambar 6.

Tahap 2: Sampel pada tahap 1 dikelompokan menjadi 2 bagian yaitu kelompok genab dan ganjil dengan masing-masing bagian memiliki 4 sampel (N/2) sehinga kelompok genab memiliki sampel 0, 2, 4 dan 6 sedangkan kelompok ganjil memiliki sampel 1, 3, 5 dan 7, sehingga jumlah r masing masing kelompok adalah 4 yaitu 0, 1, 2 dan 3. Pada tahap ini bisa diwakili dengan rumus 8 dan 11, tapi perlu diingat tahap ini belum final sehingga tahap ini merupakan ilustrasi saja.

Tahap 3: Dari masing-masing kelompok genab dan janjil tahap 2 pada rumus 8 dibagi lagi menjadi 2 supaya menyisakan 2 sampel setiap kelompok dan juga supaya memiliki jumlah r adalah 2 yaitu 0 dan 1 yang berarti telah memenuhi definisi radix-2 FFT yaitu sampel setiap kelompok terkecil memiliki 2 sampel saja. 

Angka 4r mungkin bisa diasumsikan angka pembagi. sehingga saat N/2 maka x(n) adalah 2r, saat N/4 maka x(n) sama dengan 4r. Tinggal disesuaikan 2r atau 4r berada pada sampel ganjil atau genab sehingga menentukan penjumlahannya. 

Jika dilihat dari rumus 9, E[k] memiliki jumlah k adalah 4 dan r adalah 4 sehingga ini juga berlaku untuk rumus 18 sehingga alur DFT bisa dituliskan sebagai berikut: 

Untuk k=0, maka:

Untuk k=1, maka:

Untuk nilai k lebih besar dari (N/2-1) dapat melihat penjelasan rumus 12 hingga 15 sehingga,

Untuk k = 2, maka:

Untuk k = 3, maka:

Sehingga E[k] dapat digambarkan menggunakan diagram kupu-kupu seperti di bawah ini

Gambar 8. Diagram kupu-kupu DFT tahap 3 dan 2 kelompok genab.

Untuk kelompok ganjil pada tahap 3 merupakan kelompok ganjil pada rumus 10 sehingga kelompok ganjil pada DFT tahap 3 ini dituliskan sebagai berikut:

Jika dilihat dari rumus 10, O[k] memiliki jumlah k adalah 4 dan r adalah 4 sehingga ini juga berlaku untuk rumus 21 sehingga alur detil bisa dituliskan sebagai berikut: 

Untuk nilai k lebih besar dari (N/2-1) sampel ganjil yaitu k = 2 dan k = 3 dapat dicari dengan penjelasan rumus 12 hingga 15, sehingga didapatkan:

Gambar 9. Diagram kupu-kupu DFT tahap 3 dan 2 kelompok ganjil

Dari penjelasan FFT dan FFT radix-2 pada masing-masing tahap serta penggabungan Gambar 8, 9 serta Gambar 4, maka diagram kupu-kupu FFT radix-2 ditunjukan pada Gambar 10.

Gambar 10. Diagram kupu-kupu FFT radix-2 dengan 8 sampel data

Dari penjalasan FFT radix-2 di atas dapat diungkapkan dengan kata-kata alur dari FFT radix-2 sebagai berikut:

1. Mengambil sampel dari sebuah sinyal sebanyak N sampel.
2. Membagi dua sampel N sehingga terdapat dua kelompok data yaitu kelompok data genab dan kelompok data ganjil,  kemudian masing masing data sampel ganjil dimasukan ke kelompok ganjil dan sampel data genab dimasukan ke kelompok genab sehingga satu kelompok merupakan data sampel genab dan kelompok satunya lagi adalah berisi data sampel ganjil.
3. Masing masing sampel genab dan ganjil dibagi dua lagi secara terus menerus hingga menyisakan 2 sampel DFT.
4. Proses FFT radix-2 dimulai dari DFT per dua sampel, kemudian masing masing DFT 2 sampel pada masing-masing kelompok dikombinasikan dengan 2 DFT lainnya (masih dalam satu kelompok).
5. Kemudian hasil kombinasi DFT sampel ganjil dan hasil kombinasi DFT sampel genab dijumlahkan sehingga mendapatkan nilai magnitude pada index frekuensi sebanyak jumlah sampel yang diambil.

Semua penjelasan di atas adalah penjelasan untuk mencari rumus FFT radix-2 hingga menggambarkan diagram-kupu masih dianggap membingungkan, ada cara yang lebih mudah untuk menggambarkan diagram kupu-kupu dan memahami FFT radix-2 yaitu dengan menggunakan teknik bit-reversal (pembalikan bit).

Bit reversal merupakan teknik yang mengganti urutan asli nilai bit yang didapatkan dari pengambilan sampel DIT FFT dari 0 hingga N-1 dengan nilai bit reversalnya. Sebagai contoh  pengambilan 8 sampel sebuah sinyal maka urutan data sampel (index) adalah  0, 1, 2, 3, 4, 5, 6, 7, kemudian masing- masing index n dibuat nilai binary-nya. Lalu dari nilai binary tersebut dicari bit reversal-nya yang ditunjukan pada Tabel 1.

Tabel 1. Bit-reversal Index

Tabel 1 menunjukan bahwa dengan bit reversal menghasilkan dua kelompok data yaitu genab dan ganjil tanpa harus menggunakan cara dijelaskan sebelumnya. Kemudian setiap dua data pada masing-masing kelompok dilakukan DFT dimana hasilnya dikombinasikan dengan dua data lainnya hingga menghasilkan 4 data kemudian masing-masing 4 data ganjil dan genab dijumlahkan dengan alur diagram kupu-kupu Gambar 10. 

EoF