Transformasi Fourier cepat (Bahasa Inggris: Fast Fourier Transform, biasa disingkat FFT) adalah suatu algoritma untuk menghitung transformasi Fourier diskrit (Bahasa Inggris: Discrete Fourier Transform, DFT) dengan cepat dan efisien. Transformasi Fourier Cepat diterapkan dalam beragam bidang, mulai dari pengolahan sinyal digital, memecahkan persamaan diferensial parsial, dan untuk algoritma untuk mengalikan bilangan bulat besar.
Misalkan ''x0, ...., xN-1 merupakan bilangan kompleks. Transformasi Fourier Diskret didefinisikan oleh rumus:
Menghitung deret ini secara langsung memerlukan operasi aritmetika sebanyak O(N2). Sebuah algoritma FFT hanya memerlukan operasi sebanyak O(N log N) untuk menghitung deret yang sama. Secara umum algoritma tersebut tergantung pada pemfaktoran N.
Setiap algoritma FFT, dengan penyesuaian, dapat diterapkan pula untuk menghitung DFT invers. Ini karena DFT invers adalah sama dengan DFT, namun dengan tanda eksponen berlawanan dan dikalikan dengan faktor 1/N.
Algoritma FFT yang paling awal dan karena itu paling populer adalah algoritma Cooley-Tukey
Algoritma Cooley-Tukey
Algoritma TFC lain
Pranala luar
- Pautan ke kode dan informasi FFT
- Dokumentasi online, pautan, buku, dan kode.
Sumber :
ensiklopedia.web.id, wiki.program-reguler.co.id, id.wikipedia.org, dsb.
