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 jsou komplexní čísla. DFT je definována vzorcem

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 (čí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 [editovat | editovat zdroj]

Diskrétní FT včetně rychlé FT lze počítat i pomocí zbytkových tříd v , čí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]