Rychlá Fourierova transformace

Rychlá Fourierova transformace ( 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 jsou komplexní čísla. DFT je definována 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(n2) aritmetických operací. FFT naproti tomu poskytuje složitost pouze O(n log n) operací. +more 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

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. +more 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. +more 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 Zp

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

Reference

Externí odkazy

[url=http://www.fftw.org/links.html]Odkazy na zdrojové kódy FFT a informace[/url] * [url=http://www.jjj.de/fxt/]Online dokumentace, odkazy, knihy a zdrojové kódy[/url]

Kategorie:Algoritmy Kategorie:Zpracování digitálního signálu Kategorie:Numerická matematika