Arduino Specturm Analyzer Part 4 ( Fast Fourier Transform (FFT) dan Inverse FFT (IFFT) )

Fast Fourier Transform (FFT)
FFT dari suatu sinyal, x(n), dihitung dengan:

dimana

FFT ini dihitung dengan metode Butterfly. Metode ini memiliki beberapa langkah yaitu menggambar diagram butterfly, menempatkan input, dan menghitung  pada setiap tahap. Gambar dari diagram butterfly untuk FFT dengan 4 sample adalah seperti pada Gambar 10, sedangkan untuk 8 input ditunjukkan pada Gambar 11.

Gambar 10

Gambar 11

Bagian output dari diagram ini disusun berurut X(0), X(1), ...,X(7) dari atas ke bawah, sedangkan bagian input tidak disusun berurut. Indeks bagian input disusun dengan metode reverse bit seperti pada tabel berikut:

Nilai dari dapat dihitung dengan seperti contoh berikut ini:

Untuk memahami dengan lebih jelas, maka kita akan menghitung spektrum frekuensi dari x(n) sebagai berikut:
x(0) = 6
x(1) = 8
x(2) = 6
x(3) = 2
x(4) = 4
x(5) = 5
x(6) = 3
x(7) = 1

Gambar 12

Cara menghitung dengan diagram butterfly adalah memperlakukan semua angka di bawah garis sebagai faktor pengali.

• Angka 10 pada baris paling atas diperoleh dari 6 + (4 x 1).
• Angka 2 dibawahnya adalah 6 + (4 x 1 x -1).
• Angka 9 diperoleh dari 6 + (3 x 1),
• sedangkan angka -3j diperoleh dari [6 + (3 x 1 x -1)] x –j.

Perhitungan ini akan menghasilkan X(k) sebagai berikut:

X(0) = 35
X(1) = 3.414 - 5.828 j
X(2) = 1 – 10 j
X(3) = 0.586 + 0.172 j
X(4) = 3
X(5) = 0.586 - 0.172 j
X(6) = 1 + 10 j
X(7) = 3.414 + 5.828 j

Kita dapat melakukan perhitungan FFT dari x(n) di atas pada Matlab dengan perintah:

>> x=[6 8 6 2 4 5 3 1]’;
>> X=fft(x)

Anda dapat mempelajari lebih lanjut untuk mengambarkan diagram butterfly untuk 16 atau lebih sample.

Inverse FFT (IFFT)
Inverse FFT mentransformasi spektrum frekuensi, X(k) kembali menjadi sinyal di domain waktu x(n).

Perbedaan persamaan FFT dan IFFT di atas adalah pada pangkat dari W yang menjadi negatif dan hasilnya dikalikan dengan 1/N. Diagram butterfly dapat juga digunakan dengan mengganti pangkat W dan menambahkan pengali 1/N. Gambar 13 menunjukkan diagram butterfly dari proses perhitungan IFFT untuk 8 sample.

Gambar 13

Hasil dari perhitungan IFFT bisa berbentuk bilangan kompleks tetapi yang digunakan hanyalah bagian rilnya saja.