Top Qs
Timeline
Obrolan
Perspektif
Transformasi Fourier cepat
Dari Wikipedia, ensiklopedia bebas
Remove ads
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 ''x0, ...., xN-1 merupakan bilangan kompleks. Transformasi Fourier Diskret didefinisikan oleh rumus:
Menghitung deret ini secara langsung memerlukan operasi aritmetika sebanyak O(N2). 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
Remove ads
Algoritme Cooley-Tukey
![]() | Bagian ini memerlukan pengembangan. Anda dapat membantu dengan mengembangkannya. |
Algoritme TFC lain
![]() | Bagian ini memerlukan pengembangan. Anda dapat membantu dengan mengembangkannya. |
Pranala luar
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads