Rychlá Fourierova transformace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Rychlá Fourierova transformace (Fast Fourier transform, zkratkou FFT) je efektivní algoritmus pro spočtení diskrétní Fourierovy transformace (DFT) a její inverze. FFT je velmi důležitá v mnoha oblastech, od digitálního zpracování signálu a řešení parciálních diferenciálních rovnic až po rychlé násobení velkých celých čísel. Tento článek popisuje některé z mnoha algoritmů, více informací o samotné transformaci, jejích vlastnostech a aplikacích najdete v článku diskrétní Fourierova transformace.

Nechť x0, ...., xN-1 je komplexní číslo. DFT je definováno vzorcem

 X_k =  \sum_{n=0}^{N-1} x_n e^{-{2\pi i \over N} nk }
\qquad
k = 0,\dots,N-1.

Přímé vyhodnocení těchto sum by zabralo O(N 2) aritmetických operací. FFT naproti tomu poskytuje složitost pouze O(N log N) operací. Obecně jsou FFT algoritmy založeny na faktorizaci N, nicméně existují i FFT algoritmy se složitostí O(N log N) pro všechna N, tedy i pro prvočísla.

Jelikož je inverzní DFT stejná jako DFT jen s rozdílem opačného znaménka v exponentu a koeficientu 1/N, kterýkoli algoritmus je možné snadno modifikovat i pro počítání inverzní DFT.

Cooley-Tukey algoritmus[editovat | editovat zdroj]

Cooley-Tukey algoritmus je nejpoužívanější variantou FFT algoritmu. Je příkladem rozděl a panuj algoritmu, který rekurzivně dělí DFT s velikostí složeného čísla do menších DFT o velikostech N1 a N2.

Tato metoda (a obecně myšlenka FFT) byla popularizována v práci J. W. Cooleye a J. W. Tukeye z roku 1965, nicméně později se přišlo na to, že tito autoři pouze znovuobjevili algoritmus známý již Gaussovi kolem roku 1805 (který byl poté v omezené podobě několikrát znovu objeven).

Nejpoužívanější podobou Cooley-Tukey algoritmu je dělení transformace v každém kroku na dva kusy velikosti  N / 2 (čímž je omezena na velikosti mocniny dvojky), nicméně je možné použít kteroukoli faktorizaci (čehož si byli vědomi jak Gauss, tak i Cooley a Tukey). Přestože je idea rekurzivní, většina tradičních implementací algoritmus modifikují, aby se vyhnuli explicitní rekurzi. Vzhledem k tomu, že Cooley-Tukey algoritmus dělí DFT do několika menších DFT, je možné zkombinovat tento algoritmus s kterýmkoli jiným DFT.

Počítání v  Z_p[editovat | editovat zdroj]

Diskrétní FT včetně rychlé FT lze počítat i pomocí zbytkových tříd v  Z_p, čímž se vyhneme komplexním číslům a zaokrouhlovacím chybám.

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Fast Fourier transform na anglické Wikipedii.

Externí odkazy[editovat | editovat zdroj]