Optimasi Algoritme FFT Split Radix

Abstract

Algoritma dasar FFT Split Radix merupakan algoritma yang efisien untuk menghitung Discrete Fourier Transform (DFT). Parameter utama yang menentukan waktu komputasi algoritma FFT Split Radix adalah cacah perkalian dan cacah penjumlahannya. Penelitian ini bertujuan untuk mencari satu bentuk algoritma FFT Split Radix yang berkinerja optimum, melalui modifikasi algoritma dasar FFT Split Radix sehingga cacah perkalian dan cacah penjumlahannya minimum. Metode yang digunakan untuk mendapatkan kinerja algoritma FFT Split Radix yang optimum adalah: (1) mereduksi cacah perkalian dan cacah penjumlahan algoritma dasar FFT Split Radix melalui nilai sinus dan cosinus yang besarnya diketahui; (2) memodifikasi bentuk algoritma FFT Split Radix, sehingga melibatkan 3 operasi perkalian dan 3 operasi penjumlahan untuk manipulasi satu bilangan kompleks; dan (3) menabelkan nilai sinus dan cosinus dalam bentuk array. Hasil penelitian menunjukkan bahwa untuk titik transformasi sebesar N = 2^M, reduksi cacah perkalian yang dihasilkan adalah: (1/3)MN - (19/9)N + (1/9)(-1)^M - 4, sedangkan reduksi cacah penjumlahannya adalah: (-1/3)MN + (23/9)N + (4/9)(-1)^M - 4. Meskipun bentuk algoritma yang dimodifikasi menjadi lebih panjang, namun dengan metode yang dilakukan diperoleh kinerja algortma FFT Split Radix yang optimum.