Rychlá Fourierova transformace
From Wikipedia, the free encyclopedia
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(n2) 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.