Transformasi Fourier cepat

Transformasi Fourier cepat (Bahasa Inggris: Fast Fourier Transform, biasa disingkat FFT) adalah suatu algoritme 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 algoritme untuk mengalikan bilangan bulat besar.

Misalkan ''x₀, ...., x_N-1 merupakan bilangan kompleks. Transformasi Fourier Diskret didefinisikan oleh rumus:

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{2\pi i \over N}nk}\qquad k=0,\dots ,N-1.$

Menghitung deret ini secara langsung memerlukan operasi aritmetika sebanyak O(N²). Sebuah algoritme FFT hanya memerlukan operasi sebanyak O(N log N) untuk menghitung deret yang sama. Secara umum algoritme tersebut tergantung pada pemfaktoran N.

Setiap algoritme FFT, dengan penyesuaian, dapat diterapkan pula untuk menghitung DFT invers. Ini karena DFT invers adalah sama dengan DFT, tetapi dengan tanda eksponen berlawanan dan dikalikan dengan faktor 1/N.

Algoritme FFT yang paling awal dan karena itu paling populer adalah algoritme Cooley-Tukey

Pranala luar

• Pautan ke kode dan informasi FFT
• Dokumentasi online, pautan, buku, dan kode.