Rychlá Fourierova transformace - Fast Fourier transform


z Wikipedie, otevřené encyklopedie
Strukturu příklad FFT, pomocí rozkladu do poloviny velikosti FFT
Diskrétní Fourierova analýza součet kosinových vlnami na 10, 20, 30, 40, a 50 Hz

Rychlá Fourierova transformace ( FFT ), jsou různé algoritmy, které počítají diskrétní Fourierova transformace (DFT) sekvence, nebo jeho inverzní (IDFT). Fourierova analýza převádí signál z původního domény (často časově nebo prostorově) na zastoupení ve frekvenční oblasti a naopak. DFT se získá rozkladem sekvence hodnot do složek různých frekvencí. Tato operace je užitečná v mnoha oblastech, ale výpočet přímo z definice je často příliš pomalé být praktický. FFT rychle počítá takových transformací podle factorizing na matrici DFT na produkt řídkých (většinou nula) faktory. V důsledku toho, že se podaří snížit složitost výpočetní DFT z , která vznikne, když se jednoduše aplikuje definici DFT, aby tam, kde je velikost dat. Rozdíl v rychlosti může být obrovská, a to zejména pro dlouhé množin dat, kde N může být v tisících nebo milionech. V přítomnosti zaokrouhlení chyby , mnoho FFT algoritmy jsou také mnohem přesnější, než vyhodnocení definice DFT přímo. Existuje mnoho různých FFT algoritmy založené na širokém spektru publikovaných teorií, z jednoduchého složité-číslem aritmetiky do teorie grup a teorie čísel .

Rychlá Fourierova transformace jsou široce používány pro mnoho aplikací ve strojírenství, vědy a matematiku. Základní myšlenky byly propagovány v roce 1965, ale některé algoritmy byly odvozeny již v roce 1805. V roce 1994 Gilbert Strang popsal FFT jako „nejdůležitější numerického algoritmu z našeho života“ a byl zařazen do Top 10 Algoritmy 20. století IEEE časopis Computing ve vědě a inženýrství . V praxi je doba výpočtu může být snížena o několik řádů v takových případech, a zlepšení je zhruba úměrný N  log  N . Toto obrovské zlepšení provedené při výpočtu DFT praktická; FFTs mají velký význam pro širokou škálu aplikací, od zpracování digitálního signálu a řešení parciálních diferenciálních rovnic na algoritmy pro rychlé násobení velkých čísel .

Nejznámějšími FFT algoritmy závisí na faktorizaci z N , ale existují FFT s O ( N  log  N ) složitost pro všechny N , a to i pro primární  N . Mnoho FFT algoritmy závisí pouze na tom, že je N -tý primitivní kořen jednoty , a tak může být použita k transformacím analogickými než jakékoliv konečného pole , jako je například číslo-teoretické transformace . Vzhledem k tomu, inverzní DFT je stejný jako DFT, ale s opačným znaménkem v exponentu a 1 / N faktor, jakýkoliv FFT algoritmus může být snadno upravena pro to.

Dějiny

Vývoj rychlých algoritmů pro DFT lze vysledovat do Gauss ‚s nepublikovaných prací v roce 1805, když on potřeboval to interpolovat dráhu asteroidů Pallas a Juno ze vzorku pozorování. Jeho metoda byla velmi podobná té, kterou publikoval v roce 1965 Cooley a Tukey , kteří jsou obvykle připsány na vynález moderní generické FFT algoritmu. Zatímco Gauss práce předcházela dokonce Fourier výsledky je v roce 1822, neměl analyzovat výpočetní čas a nakonec se používají jiné metody, aby dosáhl svého cíle.

V letech 1805 a 1965, některé verze FFT byly zveřejněny jinými autory. Frank Yates v roce 1932 publikoval svou verzi s názvem interakce algoritmus , který poskytuje efektivní výpočet Hadamard a Walsh transformuje . Yates' algoritmus se stále používá v oblasti statistického plánu a analýzy experimentů. V roce 1942, GC Danielson a Cornelius Lanczos zveřejněna svou verzi pro výpočet DFT pro rentgenové krystalografie , oblasti, kde výpočet Fourier převádí prezentovány impozantní problémové místo. Zatímco mnoho metod v minulosti zaměřila na snížení konstantní faktor pro výpočet tím, že využije „symetrií“, Danielson a Lanczos si uvědomil, že by bylo možné použít „pravidelnost“ a použít „zdvojnásobení trik“ se dostat runtime.

James Cooley a John Tukey zveřejnila obecnější verzi FFT v roce 1965, která se vztahuje pouze N je kompozitní a nemusí být nutně mocninou 2. Tukey přišel s nápadem na zasedání President Kennedy ‚s Science poradního výboru, kde diskusní téma zapojeni odhalování jaderných zkoušek ze strany Sovětského svazu zřízením senzory, které obepínají zemi zvenčí. Analyzovat výstup těchto senzorů, rychlá Fourierova transformace by bylo zapotřebí algoritmus. V rozhovoru s Tukey, Richard Garwin uznal obecnou použitelnost algoritmu nejen národním bezpečnostním problémům, ale také pro širokou škálu problémů, včetně jednoho z bezprostředního zájmu k němu, stanovení periodicity spinového orientací v 3-D křišťálu Helium-3. Garwin dal Tukey nápad na Cooley (oba pracovali v IBM Watson laboratořích ) k realizaci. Cooley a Tukey vydával noviny v relativně krátkém čase šesti měsíců. Jako Tukey nefungoval u IBM, patentovatelnosti myšlenkou byla zpochybněna a algoritmus šel do veřejné sféry, která prostřednictvím počítačová revoluce příštího desetiletí, z FFT jedním z nepostradatelných algoritmů v digitálním zpracování signálu.

Definice

Nechť x 0 , ...., x N -1 být komplexní čísla . DFT je definována vzorcem

Vyhodnocení této definice přímo vyžaduje O ( N 2 ) operace: jsou N výstupy X K , a každý výstup vyžaduje součet N podmínek. FFT je jakýkoliv způsob pro výpočet stejné výsledky v O ( N  log  N ) operace. Všechny známé FFT algoritmy vyžadují Θ ( N  log  N ) operací, i když není známo, je důkazem, že nižší složitost skóre je nemožné.

Pro ilustraci úspory FFT, zvažte počet komplexních násobení a doplňky pro N = 4096 datových bodů. Vyhodnocení DFT se částky přímo zahrnuje N 2 komplexní násobení a N ( N -1) komplex přísady, z nichž O ( N ), operace mohou být uloženy eliminací triviální operace, jako je násobení 1, což znamená asi 30 milionů operací. Na druhé straně, radix-2 Cooley-Tukey algoritmus , pro N mocninou 2, lze vypočítat stejný výsledek pouze s ( N / 2) log 2 ( N ) komplexní násobení (znovu, ignoruje zjednodušení násobení o 1 a podobně) a N  log 2 ( N ) komplexní dodatky, celkem asi 30.000 operací - tisíckrát menší, než u přímého hodnocení. V praxi je skutečný výkon na moderních počítačích je obvykle dominují jiné, než je rychlost aritmetických operací faktorů a analýza je složité téma (viz např Frigo a Johnson , 2005), ale celkové zlepšení od O ( N 2 ) k O ( N  log  N ) zůstává.

algoritmy

Cooley-Tukey algoritmus

Zdaleka nejčastěji používá FFT je algoritmus Cooley-Tukey. To je rozděl a panuj že rekurzivně štěpí DFT jakéhokoliv kompozitního velikosti N = N 1, N 2 do mnoha menších DFT velikostí N 1 a N 2 , spolu s O ( N ) násobení komplexními kořeny jednoty tradičně nazvaný kroutit faktory (po Gentleman a Sande, 1966).

Tento způsob (a obecná myšlenka FFT) byl propagován v publikaci Cooley a Tukey v roce 1965, ale později bylo zjištěno, že tyto dva autoři se nezávisle re-vynalezl algoritmus známý Carl Friedrich Gauss kolem roku 1805 (a následně nově objevený několikrát v omezené formě).

Nejznámější použití algoritmu Cooley-Tukey je rozdělit transformace do dvou kusů o velikosti N / 2 v každém kroku, a je proto omezeno na napájení dvě velikosti, ale jakýkoliv faktorizace může být použit obecně (jak byl známý jak Gauss a Cooley / Tukey). Ty jsou nazývány radix-2 a smíšené radix případy, v tomto pořadí (a další varianty, jako například s děleným radix FFT mají jejich vlastní jména i). Ačkoli základní myšlenka je rekurzivní, většina tradičních implementací uspořádat algoritmus vyhnout explicitní rekurzi. Také proto, že algoritmus Cooley-Tukey rozbije DFT do menších DFT, lze libovolně kombinovat s jiným algoritmem pro DFT, jako například ty popsané níže.

Jiné FFT algoritmy

Existují i ​​jiné FFT algoritmy odlišné od Cooley-Tukey.

Cornelius Lanczos udělala průkopnickou práci na FFT a FFS ( rychlá Fourierova vzorkovací metoda) s GC Danielson (1940).

Pro N = N 1 N 2 s coprime N 1 a N 2 , je možné využít primární faktor (Good-Thomas) algoritmus (PFA), založený na čínském zbytek věty , aby factorize DFT podobně jako Cooley-Tukey ale bez se kroutit faktory. Algoritmus Rader-Brenner (1976) je Cooley-Tukey-jako faktorizace ale s čistě imaginární kroutit faktory, snížení násobení za cenu zvýšených přídavků a snižuje numerické stability ; to bylo později nahrazena děleným radix varianty Cooley-Tukey (který dosahuje stejný počet násobení, ale s menšími dodatky a bez ztráty přesnosti). Algoritmy, které rekurzivně factorize DFT do jiných než DFT menší provozy patří Bruun a QFT algoritmy. (Algoritmy Rader-Brenner a QFT byly navrženy pro napájení ze-dvou velikostí, ale je možné, že by mohly být přizpůsobeny obecného kompozitní n . Bruun algoritmus se vztahuje na libovolných i kompozitních velikostí.) Bruun algoritmus , zejména, je založen na interpretaci FFT jako rekurzivní faktorizace na polynomu z N  - 1, která je zde v reálném koeficient polynomy, které odpovídají vzorci z M  - 1 a z 2, M  +  AZ M  + 1.

Další polynom hledisko je využíván algoritmem Winograd FFT, který factorizes Z N  - 1 do cyclotomic polynomů -Tyto často mají koeficienty 1, 0, nebo -1, a proto vyžadují málo (pokud vůbec), násobení, takže Winogradův může být použit k získat minimální-násobení FFT a je často používán k vyhledání efektivní algoritmy pro malé faktory. Ve skutečnosti, Winograd ukázal, že DFT lze vypočítat pouze s O ( N ) iracionálních násobení, což vede k osvědčená dosažitelný nižší přiléhat k počtu násobení pro napájení dvě velikosti; Bohužel, to je na úkor mnoha dalších dodatků, kompromis již na moderních příznivé procesory s hardwarovými multiplikátorů . Zejména Winogradův také využívá PFA, stejně jako algoritmus Rader pro FFT z hlavních rozměrů.

Rader algoritmus , využívá existenci generátoru pro multiplikativní skupina modulo prime N , vyjadřuje DFT primární velikosti n jako cyklická konvoluce z (kompozitní) velikosti N -1, který pak může být vypočítaný dvojicí běžných FFT prostřednictvím konvoluce věta (i když Winograd používá jiné metody konvoluce). Další prime-size FFT je kvůli LI Bluestein, a je někdy nazýván chirp-z algoritmus ; to také re-vyjadřuje DFT jako konvoluce, ale tentokrát o stejné velikosti, (který může být nulové polstrovaný na mocniny dvou a hodnoceny radix-2 Cooley-Tukey FFT, například), přes totožnosti

Šestihranný rychlá Fourierova transformace se zaměřuje na výpočet efektivní FFT pro data šestiúhelně vzorku pomocí nové schéma adresování pro šestiúhelníkové mříže, volal Array Nastavení adresování (ASA).

FFT algoritmy specializované pro skutečné a / nebo symetrický dat

V mnoha aplikacích, vstupní údaje pro DFT jsou čistě reálné, přičemž v tomto případě výstupy uspokojí symetrii

a účinné FFT algoritmy byly určeny pro tuto situaci (viz například Sorensen, 1987). Jeden přístup sestává z brát obyčejný algoritmus (např Cooley-Tukey) a odstranění nadbytečné části výpočtu, úspory hrubě faktor dva v čase a paměti. Alternativně je možné vyjádřit i délka- reálném vstup DFT jako komplexní DFT polovině délky (jehož skutečné a imaginární části, jsou i / liché prvky původních reálných dat), následuje O ( N ) po uvedení zpracovatelské operace.

To bylo jednou věřil, že skutečné vstupy DFT by mohly být efektivněji vypočítány pomocí diskrétní Hartley transformaci (DHT), ale to bylo později tvrdil, že specializovaný real-input DFT algoritmus (FFT) může typicky zjištěno, že vyžaduje méně operací než odpovídající algoritmus DHT (FHT) pro stejný počet vstupů. Bruun algoritmus (nahoře) je další metoda, která byla původně navržena využít skutečných vstupů, ale to neukázalo se populární.

Existují další FFT specializace pro případy skutečných dat, která mají sudá / lichá symetrie, v kterémžto případě jeden mohou získat další faktor (hrubě) dva v čase a paměti a DFT stane diskrétní kosinová / sine transformace (y) ( DCT / DST ). Místo toho, aby přímo modifikací algoritmu FFT pro tyto případy, DCTs / DST může být také vypočítán pomocí FFT reálných dat v kombinaci s O ( N ) zpracování před / po.

výpočetní problémy

Meze složitosti a provoz se počítá

otázkou dropshade.png Nevyřešeným problémem v oblasti počítačové vědy :
Jaký je dolní mez složitosti rychlá Fourierova transformace algoritmy? Mohou být rychlejší než ?
(více nevyřešených problémů v informatice)

Zásadní otázkou dlouholeté teoretické zájmu je, aby prokázal nižší hranice na složitosti a přesný provoz počtů rychlá Fourierova transformace a mnoho otevřených problémy přetrvávají. Není ani důsledně prokázáno, zda DFT skutečně vyžadují Ω ( N  log  N ) (tj pořadí N  log  N nebo vyšší) operace, a to i na jednoduchém případě síly dvou velikostech, i když nejsou známy žádné algoritmy s menší složitosti. Zejména počet aritmetických operací je obvykle terčem takové otázky, i když skutečný výkon na současných počítačích je určena řada dalších faktorů, jako jsou vyrovnávací paměti nebo CPU potrubí optimalizace.

Následovat průkopnické práce o Winograd (1978), těsnou t Vstup ( N ) dolní mez je známá počtu reálných násobení požadovaných FFT. To může být prokázáno, že pouze iracionální reálné násobení jsou nutné pro výpočet DFT of power-of-dvě délky . Kromě toho, explicitní algoritmy, že dosažení tohoto počtu jsou známy (Heideman & Burruse 1986, Duhamel, 1990). Bohužel, tyto algoritmy vyžadují příliš mnoho dodatky být praktický, alespoň na moderních počítačích s hardwarovými multiplikátorů (Duhamel, 1990; Frigo a Johnson , 2005).

Těsné dolní hranice není známo o počtu požadovaných dodatků, ačkoli dolní hranice bylo prokázáno, že za určitých omezujících předpokladů o vývoji algoritmů. V roce 1973, se ukázal jako Morgenstern Q ( N  log  N ) dolní hranice o přidávání počítat pro algoritmy, kde multiplikativní konstanty se ohraničených veličiny (což platí pro většinu, ale ne ve všech FFT algoritmy). Tento výsledek však platí pouze pro nenormalizované Fourierova transformace (což je měřítko unitární matice o faktor ), a nevysvětluje, proč je Fourier matice je těžší spočítat, než jakýkoli jiný unitární matice (včetně matice identity) v rámci stejného měřítka. Pan (1986), se ukázal jako Q ( N  log  N ), za předpokladu, že dolní hranice vázaný na měřítko FFT algoritmu „asynchronní“, ale obecnost tohoto předpokladu je nejasný. Pro případ power-of-dva N , Papadimitriou (1979) tvrdil, že počet komplexního-počet přírůstků dosažených Cooley-Tukey algoritmů je optimální za určitých předpokladů na grafu algoritmu (jeho předpokladů vyplývá, mimo jiné, že žádná doplňková identity v kořenech jednoty jsou využívány). (Tento argument by znamenalo, že alespoň se požaduje skutečné přírůstky, i když to není pevně vázány, protože další přísady jsou nutné jako součást komplexu-číslo násobení). Dosud není zveřejněn algoritmus FFT dosáhla méně než komplex-číslo přídavky ( nebo jejich ekvivalent) pro napájení ze dvou-  N .

Třetím problémem je, aby se minimalizovalo celkové množství skutečných násobení a doplňky, někdy nazývané „aritmetická složitost“ (ačkoli v této souvislosti, že je přesný počet a ne asymptotic složitost, která se uvažuje). Opět platí, že není pevně dolní odhad byla prokázána. Od roku 1968, nicméně, což je nejnižší počet publikoval pro napájení ze dvou dětí N byl dlouho dosáhnout algoritmem FFT split-radix , která vyžaduje skutečné násobení a sčítání pro N > 1. To byla nedávno snížena na (Johnson a Frigo, 2007; Lundy a Van Buskirk, 2007). O něco větší počet (ale stále lepší, než rozdělení radix pro N ≥256) bylo prokázáno, že prokazatelně optimální pro N ≤512 v dalších omezení možných algoritmů (split-radix podobné flowgraphs s multiplikativních faktory jednotkových modul), redukcí do satisfiability modulo teorií problém řešitelný hrubou silou (Haynal & Haynal, 2011).

Většina z pokusů, jak snížit nebo dokazují složitost FFT algoritmy byly zaměřeny na běžném případu komplexně údajů, protože to je nejjednodušší. Nicméně, komplex-datové FFT jsou tak úzce souvisí s algoritmy pro související problémy, jako je v reálném datových FFT, diskrétní kosinová transformace , diskrétní Hartley transformuje , a tak dále, že jakékoli zlepšení v jednom z nich by okamžitě vést ke zlepšení v ostatních ( Duhamel a Vetterli, 1990).

aproximace

Všechny FFT algoritmů popsaných výše vypočítat DFT přesně (tj zanedbání s plovoucí desetinnou čárkou chyby). Byly navrženy Několik algoritmů „FFT“, nicméně, že výpočet DFT přibližně , s chybou, která může být provedena libovolně malý na úkor zvýšených výpočtů. Takové algoritmy obchodovat chybu aproximace pro zvýšení rychlosti nebo jiné vlastnosti. Například přibližný FFT podle Edelman et al. (1999) dosahuje nižší komunikační požadavky pro paralelní výpočty se za pomoci rychlé metody vícepólové . Wavelet založené přibližný FFT Guo a Burruse (1996) má rozptýlené vstupy / výstupy (čas / frekvence lokalizace) v úvahu efektivněji, než je možné s přesným FFT. Jiný algoritmus pro přibližný výpočet podmnožiny výstupů DFT je kvůli Shentov et al. (1995). Algoritmus Edelman funguje stejně dobře pro řídké a non-řídkých dat, protože je založen na stlačitelnosti (nedostatek rank) Fourierova matice sám spíše než stlačitelnost (řídkost) údajů. Naopak, v případě, že existuje jen málo údajů, to je, je-li pouze K z N Fourierových koeficientů jsou nenulové, pak složitost může být snížena na O ( K  log ( N ) log ( N / K )), a to bylo prokázáno, že vedlo k praktickým speedups ve srovnání s běžnou FFT pro N / k  > 32 v velkokapacitního N například ( N  = 2, 22 ) za použití pravděpodobnostní přibližnou algoritmus (který odhaduje největší k koeficientů na více desetinných míst).

Přesnost

Dokonce i „přesný“ FFT algoritmy mají chyby, když se používá konečný-zavodňování preciznosti-aritmetika bodu, ale tyto chyby jsou obvykle poměrně malé; Většina FFT algoritmy, např Cooley-Tukey, mají vynikající vlastnosti jako číselné důsledku párového sčítacího struktury algoritmů. Horní přiléhat k relativní chyby pro algoritmus Cooley-Tukey je O ( ε log N ), v porovnání s O ( εN 3/2 ) pro naivní DFT vzorce, kde ε je stroj s plovoucí desetinnou čárkou relativní přesnost. Ve skutečnosti je střední kvadratická (RMS) chyby jsou mnohem lepší než tyto horní hranice, být jen O ( e log N ) pro Cooley-Tukey a O ( e N ) pro naivní DFT (Schatzman, 1996). Tyto výsledky jsou však velmi citlivá na přesnost kroutit faktory používanými v FFT (tj goniometrických funkcí hodnoty), a to není neobvyklé, že neopatrný implementace FFT mít mnohem horší správnost, například v případě, že pouze nesprávné trigonometrické opakování rovnice , Některé jiné než Cooley-Tukey FFT, jako je například algoritmus Rader-Brenner, jsou ze své podstaty méně stabilní.

V pevné řádové čárce , že konečný-chyby přesnosti nahromaděné FFT algoritmy jsou horší, s RMS chyby rostoucí jak O ( N ) pro algoritmus Cooley-Tukey (Welch, 1969). Navíc, i dosažení tohoto přesnost vyžaduje pečlivou pozornost měřítka aby se minimalizovala ztráta přesnosti, a pevného bodu FFT algoritmy zahrnují rescaling v každém stadiu meziproduktu rozkladů jako Cooley-Tukey.

Pro ověření správnosti implementace FFT, může být pečlivé záruky získat O ( N  log  N ) čas jednoduchým postupem kontrolu linearity, impulzní odezva, a vlastnosti časový posun transformace na náhodných vstupů (Ergun, 1995) ,

vícerozměrné FFTs

Jak je definováno v multidimenzionální DFT článku, vícerozměrný DFT

transformuje pole x n s d rozměrné vektoru indexů souborem d vnořených součtů (po každé j ), kde se dělení n / N , je definován jako , se provádí prvcích. Ekvivalentně je to, že se složení sekvence d sad jednorozměrných DFT, který probíhá podél jednoho rozměru v čase (v libovolném pořadí).

Tato kompoziční hledisko okamžitě poskytuje nejjednodušší a nejčastější vícerozměrný DFT algoritmus, známý jako řádek sloupci algoritmus (po dvojrozměrném případě, níže). To znamená, že člověk prostě vykonává sekvenci d jednorozměrných FFT (některou z výše uvedených algoritmů): nejprve transformovat podél n 1 rozměr, pak podél n 2 rozměr, a tak dále (nebo vlastně jakékoliv objednávání práce) , Tato metoda je snadno ukázáno, že mají obvyklý O ( N  log  N ) složitost, kde je celkový počet datových bodů transformována. Zejména jsou N / N 1 transformace o velikosti N 1 a tak dále, takže složitost sekvence FFT je:

Ve dvou rozměrech se x k může být chápáno jako matrice , a tento algoritmus odpovídá první provedení FFT všech řad (resp. Sloupce), seskupení výsledných transformovaných řádků (resp. Sloupce) společně jako další matrice, a poté provedení FFT na jednotlivé sloupce (resp. řádky) tohoto druhou matricí, a podobně seskupení výsledky do konečného výsledku matrice.

Ve více než dvou dimenzích, je často výhodné pro vyrovnávací lokalitě seskupit rozměry rekurzívně. Například, trojrozměrná FFT může nejprve provést dvourozměrné FFT každého rovinného „plátek“ pro každé pevné n 1 , a pak provést jednorozměrné FFT podél n 1 směru. Obecněji, An asymptoticky optimální mezipaměti zapomíná algoritmus sestává z rekurzivně rozdělení rozměrů do dvou skupin , a které jsou transformovány rekurzivně (zaoblení pokud d není ani) (viz Frigo a Johnson, 2005). Přesto tento zůstává jednoduché variace algoritmu řádku sloupce, které se nakonec vyžaduje pouze jednorozměrný algoritmu FFT jako základní případ, a má stále O ( N  log  N ) složitost. Ještě další variantou je provedení matrice transpozice mezi transformujících následujících rozměrů, takže transformace působí na souvislé dat; To je důležité zejména pro out-of-jádro a distribuovanou pamětí situacích, kdy přístup k nesouvislých DATA je velmi časově náročný.

Existují i jiné vícerozměrné FFT algoritmy, které jsou odlišné od algoritmu řádku sloupce, i když všechny mají O ( N  log  N ) složitost. Snad nejjednodušší non-řádek-sloupec FFT je algoritmus FFT vektor-základ , který je zobecněním běžného algoritmu Cooley-Tukey kde jeden rozděluje transformace rozměry vektorem z radices v každém kroku. (To může mít také mezipaměti výhody.) Nejjednodušší případ vektorového-soustave je místo, kde všechny radices jsou stejné (např vektor-základ-2 rozděluje všechny rozměrů dvěma), ale to není nutné. Vektor základ s pouze jediným non-jednotka radix v době, tj , je v podstatě algoritmus řádek-sloupec. Jiné, složitější metody zahrnují polynomu přeměnit algoritmy kvůli Nussbaumer (1977), které zobrazit transformace, pokud jde o vln a polynomu produktů. Viz Duhamel a Vetterli (1990) pro více informací a odkazů.

Ostatní zobecnění

Kyslíkový ( N 5/2 log  N ) zobecnění do sférických na oblast S 2 s N 2 uzly popsal Mohlenkamp, spolu s algoritmem tušené (ale ne prokázáno) mít O ( N 2 log 2 ( N )) složitost; Mohlenkamp také poskytuje implementaci v knihovně libftsh. Kulovitá harmonické algoritmus s O ( N 2 log  N ) složitost je popsána Rokhlin a Tygert.

Rychlý skládací algoritmus je analogický s FFT, kromě toho, že pracuje na sérii nesloučených křivek spíše než řada skutečných nebo komplexních hodnot skalárních. Rotace (který v FFT je násobení komplexní fázoru) je kruhový posun křivky komponent.

Různé skupiny byly také publikovány „FFT“ algoritmů pro non-rovnoměrně rozmístěny údajů, jak přezkoumáno Potts et al. (2001). Takové algoritmy nejsou zcela vypočítat DFT (který je definován pouze pro rovnoměrně rozmístěny dat), ale některé aproximace jejich (a nestejnoměrné diskrétní Fourierova transformace , nebo NDFT, který sám o sobě je často počítána pouze přibližně). Obecněji řečeno existují různé jiné metody spektrální odhadu .

Aplikace

FFT význam pochází ze skutečnosti, že při zpracování signálu a zpracování obrazu, kterého dosáhla pracuje ve frekvenční oblasti stejně výpočetně proveditelná jako pracující v časové nebo prostorové doméně. Některé z důležitých aplikací FFT obsahuje,

oblasti výzkumu

  • Big FFTs : Při výbuchu velkých dat v oblastech, jako jsou astronomie, je potřeba 512 FFTs došlo u některých výpočtů interferometrie. Údaje shromážděné v rámci projektů, jako je MAP a LIGO vyžadují FFTs desítek miliard bodů. Vzhledem k tomu, velikost nevejde do hlavní paměti, tzv out-of-jádra FFT je aktivní oblastí výzkumu.
  • Přibližné FFTs : Pro aplikace, jako je MRI, je třeba počítat DFT pro nerovnoměrně rozložených bodech sítě a / nebo frekvencí. Vícepólové přístupy založené může počítat přibližné množství s faktorem zvýšení runtime.
  • Skupina FFT : FFT lze rovněž vysvětlit a interpretovány s použitím skupiny teorie reprezentace , který umožňuje další generalizace. Funkce na jakékoliv kompaktní skupiny, včetně necyklický, má rozšíření, pokud jde o bázi nerozložitelné prvky matic. Zůstává aktivní oblast výzkumu najít efektivní algoritmus pro provedení této změny základu. Aplikace včetně účinného sférické harmonické rozšíření, analýze některých Markovových procesů, robotika atd.
  • Kvantové FFTs : rychlý algoritmus Shorův pro faktorizace celého čísla na kvantový počítač má podprogram pro výpočet DFT binárního vektoru. To je implementováno jako sekvence 1- nebo 2-bitových kvantové brány nyní známý jako kvantové FFT, který je účinně Cooley-Tukey FFT realizována jako konkrétní faktorizace Fourierova matice. Rozšíření těchto myšlenek je v současné době předmětem zkoumání.

referenční jazyk

Jazyk Command / Metoda Předpoklady
R Statistiky :: fft (x) Žádný
Octave / MATLAB fft (x) Žádný
Krajta fft.fft (x) numpy
Mathematica Fourierova [x] Žádný
Julie fft (A [, ztlumí]) FFTW

viz též

FFT související algoritmy:

implementace FFT:

  • ALGLIB - C ++ a C # knihovna s reálnou / areálu realizace FFT.
  • FFTW „Nejrychlejší Fourierova transformace na Západě“ - C knihovna pro diskrétní Fourierova transformace (DFT) v jednom nebo více rozměrech.
  • FFT - Nejrychlejší Fourierova transformace na jihu.
  • FFTPACK - jiná knihovna Fortran FFT (public domain)
  • Math Kernel Library

Další odkazy:

Reference

Další čtení

externí odkazy