Algoritma FFT yang dipakai pada Matlab


FFT (Fast Fourier Transform) adalah algoritma yang digunakan untuk menghitung DFT (Descrete Fourier Transform) dengan cepat.

Berikut ini penjelasan yang diterjemahkan dari [1] mengenai jenis algoritma FFT yang dipakai pada Matlab:

Fungsi FFT pada Matlab (fft, fft2, fftn, ifft, ifft2, ifftn) berdasarkan pada library yang disebut FFTW [2], [3]. Untuk menghitung N-point DFT ketika N adalah gabungan (Ketika N=N^1N^2), FFTW library menguraikan masalah dengan menggunakan algoritma Cooley-Turkey [4], yang pertama kali dilakukan adalah menghitung N^1 mentransformasi ukuran N^2, dan kemudian menghitung N^2 mentransformasi ukuran N^1.

Penguraian tersebut diterapkan secara rekursif pada kedua titik DFT N^1 dan N^2 hingga masalahnya terselesaikan dengan menggunakan satu dari beberapa machine-generated fixed-size “codelets.”

Codelets tersebut pada gilirannya menggunakan beberapa kombinasi algoritma, termasuk variasi dari Cooley-Turkey [5], algoritma prime factor [6], algoritma split-radix [7]. Faktorisasi khusus dari N dipilih secara heuristis.

Ketika N adalah bilangan primer, FFTW library pertama kali menguraikan masalah N-point ke dalam tiga masalah (N-1)-point dengan menggunakan algoritma Rader [8]. Ia kemudian menggunakan penguraian Cooley-Tukey untuk menghitung (N-1)-point DFT.

Untuk kebanyakan N, masukan real DFT secara kasar membutuhkan setengah dari waktu menghitung DFT dengan masukan bilangan kompleks. Bagaimanapun juga, ketika N mempunyai faktor primer yang besar, maka perbedaan kecepatan akan kecil atau bahkan tidak ada perbedaannya.

Waktu eksekusi fft tergantung pada panjang transformasi. Ia akan lebih cepat untuk pankat dari 2. Kecepatannya juga hampir sama untuk faktor primer yang kecil.

Kecepatan fft dapat ditingkatkan dengan menggunakan fungsi fftw yang mengendalikan optimisasi algoritma yang digunakan untuk menghitung FFT dari ukuran dan dimensi tertentu.

FFTW adalah sebuah koleksi fast C routines yang gratis untuk menghitung DFT dalam dimensi satu atau lebih. Termasuk transformasi bilangan kompleks, real, simetris, dan paralel. Dan juga dapat menangani secara efisien ukuran array yang berubah-ubah. FFTW secara khusus lebih cepat dari pada implementasi FFT lain yang tersedia untuk umum, dan bahkan bersaing dengan library buatan vendor. Untuk mencapai kinerja ini, FFTW menggunakan teknik novel code-generation dan runtime self-optimization [9].

Inovasi di dalam FFTW terdiri dari dalam memiliki berbagai composable solver, yang merepresentasikan algoritma FFT yang berbeda dan strategi implementasi yang mempunyai kombinasi ke dalam rencana khusus untuk ukuran yang diberikan dapat ditentukan pada runtime menurut karakteristik mesin/compiler kita. Arsitektur software yang aneh ini mengizinkan FFTW untuk beradaptasi dirinya kepada hampir semua mesin. Ada tiga hal yang membuat FFTW begitu cepat [10]:
– FFTW menggunakan berbagai algoritma FFT dan gaya implementasi yang dapat disusun berubah-ubah untuk beradaptasi terhadap mesin.
– FFTW menggunakan pembangkit kode untuk menghasilkan highly-optimized routines untuk menghitung transformasi yang kecil.
– FFTW menggunakan explicit divide-and-conquer untuk mengambil keuntungan dari hierarki memori.

Untuk lebih detail dapat dilihat pada paper [11].

Referensi:

[1] http://www.mathworks.com/help/techdoc/ref/fft.html
[2] FFTW (http://www.fftw.org)
[3] Frigo, M. and S. G. Johnson, “FFTW: An Adaptive Software Architecture for the FFT,” Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, Vol. 3, 1998, pp. 1381-138
[4] Cooley, J. W. and J. W. Tukey, “An Algorithm for the Machine Computation of the Complex Fourier Series,” Mathematics of Computation, Vol. 19, April 1965, pp. 297-30
[5] Oppenheim, A. V. and R. W. Schafer, Discrete-Time Signal Processing, Prentice-Hall, 1989, p. 611.
[6] Oppenheim, A. V. and R. W. Schafer, Discrete-Time Signal Processing, Prentice-Hall, 1989, p. 619.
[7] Duhamel, P. and M. Vetterli, “Fast Fourier Transforms: A Tutorial Review and a State of the Art,” Signal Processing, Vol. 19, April 1990, pp. 259-299.
[8] Rader, C. M., “Discrete Fourier Transforms when the Number of Data Samples Is Prime,” Proceedings of the IEEE, Vol. 56, June 1968, pp. 1107-1108.
[9] http://www.fftw.org/faq/section1.html#whatisfftw
[10] http://www.fftw.org/faq/section4.html#howworks
[11] M. Frigo and S. G. Johnson, “FFTW: An Adaptive Software Architecture for the FFT,” Proc. ICASSP 3, 1381 (1998)

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s