Rychlá Fourierova transformace

Rychlá Fourierova transformace (Šablona:Cizojazyčně, 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ť x₀, ...., x_N-1 jsou komplexní čísla. DFT je definována vzorcem

$X_k=\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}nk}k=0,\dots ,N-1.$

Přímé vyhodnocení těchto sum by zabralo O(n²) 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.

Při výpočtech diskrétní Fourierovy transformace pomocí FFT, je při výpočtech pomocí datových typů s konečnou přesností (typicky datový typ s plovoucí řádovou čárkou) obecně dosahováno menší numerické chyby, než pro přímý výpočet pomocí prosté DFT, a to především díky menšímu počtu aritmetických operací (součet, rozdíl).

Jelikož je inverzní DFT stejná jako DFT jen s rozdílem opačného znaménka v exponentu komplexní exponenciály a škálovacího koeficientu 1/N a 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 N₁ a N₂.

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 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

Externí odkazy

• Šablona:Commonscat
• Odkazy na zdrojové kódy FFT a informace
• Online dokumentace, odkazy, knihy a zdrojové kódy