Rychlá Fourierova transformace: Porovnání verzí
Smazaný obsah Přidaný obsah
→Cooley-Tukey algoritmus: cestina |
m →Cooley-Tukey algoritmus: formulace, link |
||
Řádek 14:
Cooley-Tukey algoritmus je nejpoužívanější variantou FFT algoritmu. Je příkladem [[rozděl a panuj]] algoritmu, který [[rekurze|rekurzivně]] dělí DFT s velikostí [[složené číslo|složeného čísla]] do menších DFT o velikostech ''N''<sub>1</sub> a ''N''<sub>2</sub>.
Tato metoda (a obecně myšlenka FFT) byla popularizována v práci
Nejpoužívanější podobou Cooley-Tukey algoritmu je dělení transformace v každém kroku na dva kusy velikosti <math> N / 2</math> (čí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.
| |||