Rychlá Fourierova transformace - Fast Fourier transform

Příklad struktury algoritmu FFT využívající dekompozici na poloviční velikosti FFT
Diskrétní Fourierova analýza součtu kosinových vln při 10, 20, 30, 40 a 50 Hz

Rychlá Fourierova transformace ( FFT ) je algoritmus , který počítá diskrétní Fourierova transformace (DFT) sekvence, nebo jeho inverzní (IDFT). Fourierova analýza převádí signál z jeho původní domény (často času nebo prostoru) na reprezentaci ve frekvenční oblasti a naopak. DFT se získává rozdělením posloupnosti hodnot na složky různých frekvencí. Tato operace je užitečná v mnoha oblastech, ale její výpočet přímo z definice je často příliš pomalý na to, aby byl praktický. FFT rychle počítá takových transformací podle factorizing na matrici DFT na produkt řídké (většinou nula) faktory. Výsledkem je, že dokáže snížit složitost výpočtu DFT z , která vzniká, když jednoduše použijete definici DFT , kde je velikost dat. Rozdíl v rychlosti může být obrovský, zvláště u dlouhých datových sad, kde N může být v tisících nebo milionech. V přítomnosti chyby zaokrouhlení je mnoho algoritmů FFT mnohem přesnější než vyhodnocování definice DFT přímo nebo nepřímo. Existuje mnoho různých algoritmů FFT založených na široké škále publikovaných teorií, od jednoduché aritmetiky komplexních čísel po teorii skupin a teorii čísel .

Rychlé Fourierovy transformace jsou široce používány pro aplikace ve strojírenství, hudbě, vědě a matematice. 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ý algoritmus našeho života“ a byl zařazen do Top 10 algoritmů 20. století. podle IEEE časopisu Computing ve vědě a inženýrství .

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 algoritmů FFT závisí pouze na skutečnosti, že jde o N -tý primitivní kořen jednoty , a lze je tedy použít na analogické transformace v jakémkoli konečném poli , jako jsou například teoretické transformace čísel . Protože inverzní DFT je stejný jako DFT, ale s opačným znaménkem v exponentu a faktorem 1/ N , lze pro něj snadno přizpůsobit jakýkoli algoritmus FFT.

Dějiny

Vývoj rychlých algoritmů pro DFT lze vysledovat k nepublikovanému dílu Carla Friedricha Gausse v roce 1805, kdy jej potřeboval k interpolaci oběžné dráhy asteroidů Pallas a Juno ze vzorkových pozorování. Jeho metoda byla velmi podobná metodě publikované v roce 1965 Jamesem Cooleyem a Johnem Tukeyem , kteří jsou obecně uznáváni za vynález moderního generického algoritmu FFT. Zatímco Gaussova práce předcházela dokonce výsledkům Josepha Fouriera v roce 1822, neanalyzoval čas výpočtu a nakonec použil jiné metody k dosažení svého cíle.

V letech 1805 až 1965 byly některé verze FFT publikovány jinými autory. Frank Yates v roce 1932 publikoval svou verzi nazvanou interakční algoritmus , která zajišťovala efektivní výpočet Hadamardových a Walshových transformací . Yatesův algoritmus se stále používá v oblasti statistického návrhu a analýzy experimentů. V roce 1942 GC Danielson a Cornelius Lanczos vydali svou verzi pro výpočet DFT pro rentgenovou krystalografii , pole, kde výpočet Fourierových transformací představoval impozantní překážku. Zatímco mnoho metod se v minulosti zaměřovalo na snížení konstantního faktoru pro výpočet využitím výhod „symetrií“, Danielson a Lanczos si uvědomili, že lze použít „periodicitu“ a použít „trik zdvojení“ na „zdvojnásobení [N] pouze o něco více než dvojnásobek porodu “, ačkoli jako Gauss neanalyzovali, že to vedlo ke škálování.

James Cooley a John Tukey nezávisle znovu objevili tyto dřívější algoritmy a v roce 1965 vydali obecnější FFT, který je použitelný, když N je složený a nemusí nutně mít mocninu 2, stejně jako analýzu škálování. Tukey přišel s tímto nápadem během setkání poradního výboru pro vědu prezidenta Kennedyho, kde se téma diskuse týkalo detekce jaderných testů Sovětským svazem nastavením senzorů, které obklopují zemi zvenčí. K analýze výstupu těchto senzorů by byl zapotřebí algoritmus FFT. V diskusi s Tukeyem Richard Garwin uznal obecnou použitelnost algoritmu nejen na problémy národní bezpečnosti, ale také na celou řadu problémů, včetně těch, které ho bezprostředně zajímají, určování periodicit orientací rotace v 3-D krystalu z hélia-3. Garwin dal Tukeyův nápad Cooleymu (oba pracovali v laboratořích Watson společnosti IBM ) k implementaci. Cooley a Tukey publikovali noviny v relativně krátké době šesti měsíců. Jelikož Tukey nepracoval v IBM, byla patentovatelnost myšlenky zpochybněna a algoritmus se stal veřejným majetkem, což díky počítačové revoluci příštího desetiletí učinilo z FFT jeden z nepostradatelných algoritmů při zpracování digitálního signálu.

Definice

Nechť … jsou složitá čísla . DFT je definována vzorcem

kde je primitivní N th kořen 1.

Vyhodnocení této definice přímo vyžaduje operace: existuje N výstupů X k a každý výstup vyžaduje součet N výrazů. FFT je jakákoli metoda pro výpočet stejných výsledků v operacích. Všechny známé algoritmy FFT vyžadují operace , ačkoli není znám žádný důkaz, že nižší skóre složitosti není možné.

Pro ilustraci úspor FFT zvažte počet komplexních násobení a sčítání pro N = 4096 datových bodů. Vyhodnocení součtů DFT přímo zahrnuje N 2 komplexní multiplikace a N ( N - 1) komplexní adice, z nichž operace lze ušetřit vyloučením triviálních operací, jako je násobení 1, takže zbude asi 30 milionů operací. Naproti tomu algoritmus radix-2 Cooley – Tukey , pro N o síle 2, dokáže vypočítat stejný výsledek pouze s ( N /2) log 2 ( N ) komplexním násobením (opět ignorování zjednodušení násobení o 1 a podobných) a N  log 2 ( N ) komplexních přírůstků, celkem asi 30 000 operací - tisíckrát méně než při přímém vyhodnocení. V praxi skutečnému výkonu na moderních počítačích obvykle dominují jiné faktory, než je rychlost aritmetických operací, a analýza je komplikované téma (například viz Frigo & Johnson , 2005), ale celkové zlepšení od do zůstává.

Algoritmy

Algoritmus Cooley -Tukey

Zdaleka nejčastěji používaným FFT je algoritmus Cooley -Tukey. Jedná se o algoritmus rozděl a panuj, který rekurzivně rozděluje DFT jakékoli kompozitní velikosti na mnoho menších DFT velikostí a spolu s násobením komplexními kořeny jednoty tradičně nazývanými twiddle faktory (po Gentleman a Sande, 1966).

Tato metoda (a obecná myšlenka FFT) byla propagována publikací Cooleyho a Tukeyho v roce 1965, ale později bylo zjištěno, že tito dva autoři kolem roku 1805 nezávisle znovu vynalezli algoritmus známý Carlu Friedrichovi Gaussovi (a následně znovu objevili několikrát v omezené formě).

Nejznámějším použitím algoritmu Cooley-Tukey je rozdělení transformace na dva kusy velikosti N /2 v každém kroku, a je tedy omezeno na velikosti dvou velikostí, ale obecně lze použít jakoukoli faktorizaci (jak byla známý jak Gaussovi, tak Cooleymu/Tukeyovi). Tyto případy se nazývají případy radix-2 a mixed-radix (a další varianty, jako je split-radix FFT, mají také svá vlastní jména). Ačkoli je základní myšlenka rekurzivní, většina tradičních implementací přeskupí algoritmus, aby se vyhnul explicitní rekurzi. Protože také algoritmus Cooley – Tukey rozděluje DFT na menší DFT, lze jej libovolně kombinovat s jakýmkoli jiným algoritmem pro DFT, jako jsou algoritmy popsané níže.

Jiné algoritmy FFT

Existují jiné algoritmy FFT než Cooley – Tukey.

Pro N = N 1 N 2 s coprime N 1 a N 2 lze použít algoritmus prime-factor (Good – Thomas) (PFA), založený na čínské zbytkové větě , k faktorizaci DFT podobně jako Cooley-Tukey, ale bez twiddle faktory. Algoritmus Rader – Brenner (1976) je faktorizace podobná Cooley – Tukeyovi, ale s čistě imaginárními twiddle faktory, které snižují násobení za cenu zvýšených přírůstků a snížené numerické stability ; později byla nahrazena variantou Cooley – Tukey s rozděleným radixem (která dosahuje stejného počtu násobení, ale s menším počtem přírůstků a bez obětování přesnosti). Algoritmy, které rekurzivně rozdělují DFT na menší operace jiné než DFT, zahrnují algoritmy Bruun a QFT . (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 vztahuje k libovolným i kompozitních velikosti.) Bruun algoritmus , zejména, je založen na interpretaci FFT jako rekurzivní faktorizace polynomu z N  -1, zde na polynomy s reálným koeficientem ve tvaru z M  -1 a z 2 M  +  az M  + 1.

Další polynomiální hledisko využívá Winogradský algoritmus FFT, který rozděluje z N  - 1 na cyklotomické polynomy - ty mají často koeficienty 1, 0 nebo -1, a proto vyžadují několik (pokud vůbec) násobení, takže Winograd lze použít k získat FFT s minimálním násobením a často se používá k nalezení efektivních algoritmů pro malé faktory. Winograd skutečně ukázal, že DFT lze vypočítat pouze s iracionálním násobením O ( N ), což vede k prokázané dosažitelné dolní hranici počtu násobení pro velikosti dvou mocnin; bohužel to stojí za cenu mnoha dalších přírůstků, kompromis již není příznivý pro moderní procesory s multiplikátory hardwaru . Winograd zejména využívá také PFA a algoritmus Rader pro FFT prvotřídních velikostí.

Raderův algoritmus , využívající existenci generátoru pro multiplikativní skupinu modulo prime N , vyjadřuje DFT primární velikosti N jako cyklickou konvoluci (složené) velikosti N - 1, kterou pak lze vypočítat dvojicí běžných FFT pomocí konvoluční věta (ačkoli Winograd používá jiné konvoluční metody). Další FFT primární velikosti je kvůli LI Bluestein a někdy se mu říká algoritmus chirp-z ; také znovu vyjadřuje DFT jako konvoluci, ale tentokrát stejné velikosti (která může být vynulována nulou na sílu dvou a vyhodnocena například radix-2 Cooley – Tukey FFTs), prostřednictvím identity

Hexagonální rychlá Fourierova transformace (HFFT) si klade za cíl vypočítat efektivní FFT pro hexagonálně vzorkovaná data pomocí nového schématu adresování pro hexagonální mřížky, nazývaného Array Set Addressing (ASA).

Algoritmy FFT specializované na skutečná nebo symetrická data

V mnoha aplikacích jsou vstupní data pro DFT čistě reálná, v takovém případě výstupy splňují symetrii

a pro tuto situaci byly navrženy efektivní FFT algoritmy (viz např. Sorensen, 1987). Jeden přístup spočívá v převzetí běžného algoritmu (např. Cooley -Tukey) a odstranění nadbytečných částí výpočtu, čímž se ušetří zhruba faktor dva v čase a paměti. Alternativně je možné vyjádřit sudý DFT s reálným vstupem se sudou délkou jako komplexní DFT s poloviční délkou (jehož skutečné a imaginární části jsou sudé/liché prvky původních skutečných dat), následované O ( N ) post- zpracovatelské operace.

Kdysi se věřilo, že DFT se skutečným vstupem lze efektivněji vypočítat pomocí diskrétní Hartleyovy transformace (DHT), ale následně se tvrdilo, že lze typicky nalézt specializovaný algoritmus DFT s reálným vstupem (FFT), který vyžaduje méně operací než odpovídající algoritmus DHT (FHT) pro stejný počet vstupů. Bruunův algoritmus (výše) je další metodou, která byla původně navržena tak, aby využívala výhod skutečných vstupů, ale neprokázala popularitu.

Existují další specializace FFT pro případy skutečných dat, která mají sudou / lichou symetrii, v takovém případě lze získat další faktor zhruba dva v čase a paměti a DFT se stane diskrétní kosinus / sinusovou transformací ( DCT / DST) ). Namísto přímé úpravy algoritmu FFT pro tyto případy lze DCT/DST vypočítat také pomocí FFT skutečných dat kombinovaných s předběžným a následným zpracováním O ( N ).

Výpočtové problémy

Limity složitosti a provozu se počítají

Nevyřešený problém v informatice :

Jaká je spodní hranice složitosti algoritmů rychlé Fourierovy transformace? Mohou být rychlejší než ?

Zásadní otázkou dlouhodobého teoretického zájmu je dokázat nižší meze složitosti a přesného počtu operací rychlých Fourierových transformací a mnoho otevřených problémů zůstává. Není přísně prokázáno, zda DFT skutečně vyžadují operace Ω ( N  log  N ) (tj. Objednat N  log  N nebo vyšší), a to ani pro jednoduchý případ výkonu dvou velikostí, ačkoli nejsou známy žádné algoritmy s nižší složitostí. Zejména počet těchto aritmetických operací je obvykle předmětem těchto otázek, ačkoli skutečný výkon na moderních počítačích je určen mnoha dalšími faktory, jako je optimalizace mezipaměti nebo CPU .

Po práci Shmuela Winograda (1978) je těsná spodní hranice Θ ( N ) známá pro počet skutečných násobení požadovaných FFT. Je možné ukázat, že k výpočtu délky DFT o síle dvou jsou zapotřebí pouze iracionální skutečné násobení . Kromě toho jsou známy explicitní algoritmy, které dosahují tohoto počtu (Heideman & Burrus , 1986; Duhamel, 1990). Tyto algoritmy však vyžadují příliš mnoho doplňků, než aby byly praktické, alespoň na moderních počítačích s multiplikátory hardwaru (Duhamel, 1990; Frigo & Johnson , 2005).

Těsná dolní hranice není známa v počtu požadovaných přírůstků, i když spodní hranice byly prokázány za určitých omezujících předpokladů o algoritmech. V roce 1973 prokázal Morgenstern dolní hranici Ω ( N  log  N ) u počtu sčítání u algoritmů, kde multiplikativní konstanty mají ohraničené velikosti (což platí pro většinu, ale ne pro všechny algoritmy FFT). Pan (1986) prokázal dolní hranici Ω ( N  log  N ) za předpokladu vazby na míru „asynchronicity“ FFT algoritmu, ale obecnost tohoto předpokladu není jasná. Pro případ power-of-two 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 nejsou využívány žádné aditivní identity v kořenech jednoty). (Tento argument by znamenal, že jsou vyžadovány alespoň skutečné sčítání, i když to není úzká hranice, protože v rámci násobení komplexních čísel jsou vyžadována další sčítání.) Dosud žádný publikovaný algoritmus FFT nedosáhl méně než sčítání komplexních čísel ( nebo jejich ekvivalent) pro napájení ze dvou-  N .

Třetím problémem je minimalizovat celkový počet skutečných násobení a sčítání, někdy se jim také říká „aritmetická složitost“ (i když v tomto kontextu se uvažuje o přesném počtu, a nikoli o asymptotické složitosti). Opět nebyla prokázána žádná těsná spodní hranice. Od roku 1968 byl však nejnižší publikovaný počet pro výkon N dvou dlouhodobě dosahován algoritmem FFT s rozděleným radixem , který vyžaduje skutečné násobení a sčítání pro N > 1. To bylo nedávno sníženo na (Johnson a Frigo, 2007; Lundy a Van Buskirk, 2007). Mírně větší počet (ale stále lepší než rozdělený radix pro N ≥ 256) byl prokázán jako prokazatelně optimální pro N ≤ 512 za dodatečných omezení možných algoritmů (tokové diagramy podobné dělenému radixu s multiplikativními faktory jednotkového modulu), snížením k problému teorií modulo uspokojitelnosti řešitelného hrubou silou (Haynal & Haynal, 2011).

Většina pokusů o snížení nebo prokázání složitosti algoritmů FFT se zaměřila na běžný případ komplexních dat, protože je nejjednodušší. FFT komplexních dat jsou však tak úzce spjaty s algoritmy pro související problémy, jako jsou FFT reálných dat, diskrétní kosinové transformace , diskrétní Hartleyho transformace atd., Že jakékoli zlepšení jednoho z nich by okamžitě vedlo ke zlepšení ostatních ( Duhamel & Vetterli, 1990).

Aproximace

Všechny výše uvedené algoritmy FFT počítají DFT přesně (tj. Zanedbávají chyby s plovoucí desetinnou čárkou ). Bylo však navrženo několik algoritmů „FFT“, které přibližně počítají DFT s chybou, kterou lze libovolně zmenšit na úkor zvýšených výpočtů. Takové algoritmy obchodují s chybou aproximace za zvýšenou rychlost nebo jiné vlastnosti. Například přibližný algoritmus FFT od Edelmana a kol. (1999) dosahuje nižších komunikačních požadavků pro paralelní výpočet pomocí rychlé vícepólové metody . Wavelet založené přibližný FFT Guo a Burruse (1996) se rozptýlené vstupy / výstupy (čas / frekvence lokalizace) v úvahu efektivněji, než je možné s přesným FFT. Další algoritmus pro přibližný výpočet podmnožiny výstupů DFT má na svědomí Shentov et al. (1995). Algoritmus Edelman funguje stejně dobře u řídkých i neřídkých dat, protože je založen spíše na stlačitelnosti (nedostatku hodnosti) samotné Fourierovy matice než na stlačitelnosti (řídkosti) dat. Naopak, pokud jsou data řídká - to znamená, že pouze K z N Fourierových koeficientů jsou nenulová -, pak lze složitost snížit na O ( K  log ( N ) log ( N / K )), což bylo prokázáno vést k praktickým zrychlením ve srovnání s běžným FFT pro N / K  > 32 v příkladu velkého N ( N  = 2 22 ) pomocí pravděpodobnostního přibližného algoritmu (který odhaduje největší K koeficienty na několik desetinných míst).

Přesnost

Algoritmy FFT mají chyby, když se používá aritmetika s pohyblivou řádovou čárkou s konečnou přesností, ale tyto chyby jsou obvykle docela malé; většina algoritmů FFT, např. Cooley – Tukey, má vynikající numerické vlastnosti v důsledku struktury párových součtů algoritmů. Horní hranice relativní chyby pro Cooley-Tukeyův algoritmus je O ( ε log N ), ve srovnání s O ( εN 3/2 ) pro naivní vzorec DFT, kde ε je relativní přesnost stroje s plovoucí desetinnou čárkou. Ve skutečnosti jsou střední kvadratické chyby (rms) mnohem lepší než tyto horní hranice, přičemž jsou pouze O ( ε log N ) pro Cooley – Tukey a O ( ε N ) pro naivní DFT (Schatzman, 1996). Tyto výsledky jsou však velmi citlivé na přesnost twiddle faktorů použitých v FFT (tj. Hodnoty goniometrických funkcí ) a není neobvyklé, že neopatrné implementace FFT mají mnohem horší přesnost, např. Pokud používají nepřesné trigonometrické vzorce pro opakování . Některé FFT jiné než Cooley – Tukey, jako například algoritmus Rader – Brenner, jsou ve své podstatě méně stabilní.

V aritmetice s pevným bodem jsou chyby konečné přesnosti nashromážděné algoritmy FFT horší, přičemž chyby rms rostou jako O ( N ) pro Cooley-Tukeyův algoritmus (Welch, 1969). Dosažení této přesnosti vyžaduje pečlivou pozornost při škálování, aby se minimalizovala ztráta přesnosti, a algoritmy FFT s pevným bodem zahrnují změnu měřítka v každé mezistupni dekompozic, jako je Cooley-Tukey.

K ověření správnosti implementace FFT lze v čase O ( N  log  N ) získat přísné záruky jednoduchým postupem, který kontroluje vlastnosti linearity, impulzní odezvy a časového posunu transformace na náhodných vstupech (Ergün, 1995) .

Multidimenzionální FFT

Jak je definováno v multidimenzionálním článku DFT , multidimenzionálním DFT

transformuje pole x n s d -dimenzionálním vektorem indexů pomocí sady d vnořených součtů (více než pro každé j ), kde rozdělení n / N , definované jako , se provádí elementárně. Ekvivalentně je to složení sekvence d sad jednorozměrných DFT, prováděných podél jedné dimenze najednou (v libovolném pořadí).

Toto kompoziční hledisko okamžitě poskytuje nejjednodušší a nejběžnější vícerozměrný DFT algoritmus, známý jako algoritmus řádkových sloupců (po dvojrozměrném případě níže). To znamená, že člověk jednoduše provede posloupnost d jednorozměrných FFT (jakýmkoli z výše uvedených algoritmů): nejprve transformujete podél dimenze n 1 , poté podél dimenze n 2 atd. (Nebo ve skutečnosti jakékoli řazení funguje) . U této metody lze snadno ukázat, že má obvyklou složitost O ( N  log  N ), kde je transformován celkový počet datových bodů. Zejména existují N / N 1 transformace velikosti N 1 atd., Takže složitost sekvence FFT je:

Ve dvou dimenzích lze x k považovat za matici a tento algoritmus odpovídá prvnímu provedení FFT všech řádků (resp. Sloupců), seskupení výsledných transformovaných řádků (resp. Sloupců) jako další matice a poté provedení FFT na každém ze sloupců (resp. řádků) této druhé matice a podobně seskupení výsledků do matice konečných výsledků.

Ve více než dvou dimenzích je pro lokalitu cache často výhodné seskupovat dimenze rekurzivně. Například trojrozměrný FFT může nejprve provést dvourozměrné FFT každého planárního „řezu“ pro každé pevné n 1 , a poté provést jednorozměrné FFT ve směru n 1 . 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 to zůstává přímou variací algoritmu řádků a sloupců, která nakonec vyžaduje pouze jednorozměrný algoritmus FFT jako základní případ a stále má složitost O ( N  log  N ). Ještě další variací je provádět maticové transpozice mezi transformací následujících dimenzí, aby transformace fungovaly na souvislých datech; to je zvláště důležité pro situace mimo jádro a distribuovanou paměť, kde je přístup k nesouvislým datům extrémně časově náročný.

Existují další vícerozměrné algoritmy FFT, které se liší od algoritmu řádků a sloupců, přestože všechny mají složitost O ( N  log  N ). Snad nejjednodušší FFT bez řádkových sloupců je FFT algoritmus s vektorovým radixem , což je zobecnění běžného Cooley-Tukeyova algoritmu, kde se v každém kroku rozdělí transformační dimenze vektorem radik. (To může mít také výhody mezipaměti.) Nejjednodušší případ vector-radix je tam, kde jsou všechny radice stejné (např. Vector-radix-2 dělí všechny dimenze dvěma), ale není to nutné. Vektorový radix pouze s jedním nejednotkovým radixem současně, tj . Je v podstatě algoritmus řádků a sloupců. Mezi další, komplikovanější metody patří polynomiální transformační algoritmy podle Nussbaumera (1977), které pohlížejí na transformaci z hlediska konvolucí a polynomiálních produktů. Další informace a reference viz Duhamel a Vetterli (1990).

Další generalizace

Zevšeobecnění O ( N 5/2 log  N ) na sférické harmonické na sféře S 2 s N 2 uzly popsal Mohlenkamp spolu s algoritmem předpokládaným (ale neprokázaným), že má O ( N 2 log 2 ( N )) složitost; Mohlenkamp také poskytuje implementaci v knihovně libftsh. Rokhlin a Tygert popisují sféricko-harmonický algoritmus se složitostí O ( N 2 log  N ).

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 (což je v FFT násobení komplexním fázorem) je kruhový posun křivky složky.

Různé skupiny také publikovaly "FFT" algoritmy pro data, která nejsou ekvipasovaná, jak je popsáno v Potts et al. (2001). Takové algoritmy nevypočítávají striktně DFT (který je definován pouze pro data s rovnoměrným rozložením), ale spíše jeho aproximaci ( nejednotná diskrétní Fourierova transformace nebo NDFT, který sám je často počítán pouze přibližně). Obecněji existují různé další metody spektrálního odhadu .

Aplikace

FFT se používá v softwaru pro digitální nahrávání, vzorkování, aditivní syntézu a korekci výšky tónu .

Důležitost FFT vyplývá ze skutečnosti, že díky ní je práce ve frekvenční oblasti stejně výpočetně proveditelná jako práce v časové nebo prostorové oblasti. Některé z důležitých aplikací FFT zahrnují:

Oblasti výzkumu

Velké FFT
S explozí velkých dat v oblastech, jako je astronomie, vyvstala potřeba 512 000 FFT pro určité interferometrické výpočty. Data shromážděná projekty, jako jsou WMAP a LIGO, vyžadují FFT desítky miliard bodů. Protože se tato velikost nevejde do hlavní paměti, jsou aktivní oblastí výzkumu takzvané out-of-core FFT.
Přibližné FFT
Pro aplikace, jako je MRI, je nutné vypočítat DFT pro nerovnoměrně rozmístěné body a/nebo frekvence mřížky. Vícepólové přístupy mohou vypočítat přibližné veličiny s faktorem zvýšení doby běhu.
Skupina FFT
FFT lze také vysvětlit a interpretovat pomocí teorie skupinové reprezentace umožňující další generalizaci. Funkce na jakékoli kompaktní skupině, včetně necyklické, má expanzi, pokud jde o základ neredukovatelných maticových prvků. Zůstává aktivní oblastí výzkumu najít účinný algoritmus pro provádění této změny základu. Aplikace zahrnující efektivní sférickou harmonickou expanzi, analýzu určitých Markovových procesů , robotiku atd.
Kvantové FFT
Shorův rychlý algoritmus pro celočíselnou faktorizaci na kvantovém počítači má podprogram pro výpočet DFT binárního vektoru. Toto je implementováno jako sekvence 1- nebo 2bitových kvantových bran, nyní známá jako kvantová FFT, což je ve skutečnosti Cooley-Tukey FFT realizovaná jako konkrétní faktorizace Fourierovy matice. V současné době se zkoumá rozšíření těchto myšlenek.

Odkaz na jazyk

Jazyk Příkaz/metoda Předpoklady
R. statistiky :: fft (x) Žádný
Octave / MATLAB fft (x) Žádný
Krajta fft.fft (x) otupělý
Mathematica Fourier [x] Žádný
Fortran fftw_one (plán, vstup, výstup) FFTW
Julie fft (A [, stmívání]) FFTW
Rez fft.process (& mut x); rustfft
Haskell dft x fft

Viz také

Algoritmy související s FFT:

Implementace FFT:

  • ALGLIB -duální/GPL licencovaná knihovna C ++ a C# (podporuje také jiné jazyky), se skutečnou/komplexní implementací FFT
  • FFTPACK - další Fortran FFT knihovna (veřejná doména)
  • Specifické pro architekturu:
  • K dispozici je mnoho dalších implementací pro CPU a GPU, například PocketFFT pro C ++

Další odkazy:

Reference

Další čtení

externí odkazy