Rychlá Fourierova transformace
Kategorie: Nezařazeno (celkem: 23179 referátů a seminárek)
Informace o referátu:
- Přidal/a: anonymous
- Datum přidání: 20. srpna 2008
- Zobrazeno: 2190×
- Licence: GNU Free Documentation License
- Seznam autorů a změn
- Vyloučení odpovědnosti
Příbuzná témata
Rychlá Fourierova transformace
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
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
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ě idea FFT) byla popularizována v práci pánů J. W. Cooley a J. W. Tukey 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.