Schnelle Fourier-Transformation - Fast Fourier transform

Eine schnelle Fourier-Transformation ( FFT ) ist ein Algorithmus , der die diskrete Fourier-Transformation (DFT) einer Sequenz oder ihre Umkehrung (IDFT) berechnet . Die Fourier-Analyse konvertiert ein Signal aus seinem ursprünglichen Bereich (oft Zeit oder Raum) in eine Darstellung im Frequenzbereich und umgekehrt. Die DFT wird durch Zerlegen einer Folge von Werten in Komponenten unterschiedlicher Frequenzen erhalten. Diese Operation ist in vielen Bereichen nützlich, aber ihre direkte Berechnung aus der Definition ist oft zu langsam, um praktikabel zu sein. Eine FFT berechnet solche Transformationen schnell, indem sie die DFT-Matrix in ein Produkt von wenigen (meist null) Faktoren faktorisiert . Als Ergebnis gelingt es, die Komplexität der Berechnung der DFT von , die entsteht, wenn man einfach die Definition von DFT anwendet, auf , wo die Datengröße ist, zu reduzieren. Der Geschwindigkeitsunterschied kann enorm sein, insbesondere bei langen Datensätzen, bei denen N in die Tausende oder Millionen gehen kann. Bei Vorliegen eines Rundungsfehlers sind viele FFT-Algorithmen viel genauer als die direkte oder indirekte Auswertung der DFT-Definition. Es gibt viele verschiedene FFT-Algorithmen, die auf einer breiten Palette veröffentlichter Theorien basieren, von einfacher komplexer Zahlenarithmetik bis hin zu Gruppentheorie und Zahlentheorie . ${\displaystyle O\left(N^{2}\right)}$${\displaystyle O(N\log N)}$${\displaystyle N}$

Schnelle Fourier-Transformationen werden häufig für Anwendungen in den Bereichen Technik, Musik, Wissenschaft und Mathematik verwendet. Die Grundideen wurden 1965 populär, einige Algorithmen wurden jedoch bereits 1805 abgeleitet. 1994 beschrieb Gilbert Strang die FFT als „den wichtigsten numerischen Algorithmus unserer Lebenszeit“ und wurde in die Top 10 der Algorithmen des 20. Jahrhunderts aufgenommen vom IEEE- Magazin Computing in Science & Engineering .

Die bekanntesten FFT-Algorithmen hängen von der Faktorisierung von N ab , aber es gibt FFTs mit O( N  log  N ) Komplexität für alle N , sogar für Primzahlen  N . Viele FFT-Algorithmen hängen nur von der Tatsache ab, dass es sich um eine N- te primitive Einheitswurzel handelt , und können daher auf analoge Transformationen über jeden endlichen Körper angewendet werden , wie beispielsweise zahlentheoretische Transformationen . Da die inverse DFT die gleiche wie die DFT ist, jedoch mit dem entgegengesetzten Vorzeichen im Exponenten und einem 1/ N- Faktor, kann jeder FFT-Algorithmus leicht darauf angepasst werden. ${\displaystyle e^{-2\pi i/N}}$

Geschichte

Die Entwicklung schneller Algorithmen für die DFT lässt sich auf Carl Friedrich Gauß ' unveröffentlichte Arbeit von 1805 zurückführen, als er sie benötigte, um die Bahn der Asteroiden Pallas und Juno aus Probebeobachtungen zu interpolieren . Seine Methode war der 1965 von James Cooley und John Tukey veröffentlichten sehr ähnlich , denen allgemein die Erfindung des modernen generischen FFT-Algorithmus zugeschrieben wird. Während Gauß' Arbeit 1822 sogar den Ergebnissen von Joseph Fourier vorausging , analysierte er die Rechenzeit nicht und verwendete schließlich andere Methoden, um sein Ziel zu erreichen.

Zwischen 1805 und 1965 wurden einige Versionen von FFT von anderen Autoren veröffentlicht. Frank Yates veröffentlichte 1932 seine Version namens Interaktionsalgorithmus , die eine effiziente Berechnung von Hadamard- und Walsh-Transformationen ermöglichte . Der Algorithmus von Yates wird immer noch im Bereich des statistischen Designs und der Analyse von Experimenten verwendet. 1942 veröffentlichten GC Danielson und Cornelius Lanczos ihre Version zur Berechnung der DFT für die Röntgenkristallographie , ein Gebiet, in dem die Berechnung von Fourier-Transformationen einen gewaltigen Engpass darstellte. Während sich viele Methoden in der Vergangenheit darauf konzentrierten, den konstanten Faktor für die Berechnung durch Ausnutzung von "Symmetrien" zu reduzieren , erkannten Danielson und Lanczos, dass man die "Periodizität" nutzen und einen "Verdoppelungstrick" anwenden konnte, um "[N] mit nur . zu verdoppeln" etwas mehr als den doppelten Arbeitsaufwand", obwohl sie wie Gauß nicht analysierten, dass dies zu einer Skalierung führte. ${\displaystyle O\left(N^{2}\right)}$${\displaystyle O(N\log N)}$

James Cooley und John Tukey haben diese früheren Algorithmen unabhängig voneinander wiederentdeckt und 1965 eine allgemeinere FFT veröffentlicht, die anwendbar ist, wenn N zusammengesetzt und nicht notwendigerweise eine Potenz von 2 ist, sowie die Skalierung analysiert . Auf die Idee kam Tukey während einer Sitzung des Wissenschaftlichen Beratungsausschusses von Präsident Kennedy , wo ein Diskussionsthema darin bestand, Nukleartests durch die Sowjetunion zu entdecken, indem Sensoren aufgestellt wurden, um das Land von außen zu umgeben. Um die Ausgabe dieser Sensoren zu analysieren, wäre ein FFT-Algorithmus erforderlich. Im Gespräch mit Tukey erkannte Richard Garwin die allgemeine Anwendbarkeit des Algorithmus nicht nur für nationale Sicherheitsprobleme, sondern auch für eine Vielzahl von Problemen, darunter eines von unmittelbarem Interesse, nämlich die Bestimmung der Periodizitäten der Spinorientierungen in einem 3D-Kristall von Helium-3. Garwin gab Cooley (beide arbeiteten in den Watson-Labors von IBM ) Tukeys Idee zur Umsetzung. Cooley und Tukey veröffentlichten das Papier in relativ kurzer Zeit von sechs Monaten. Da Tukey nicht bei IBM arbeitete, wurde die Patentierbarkeit der Idee angezweifelt und der Algorithmus ging in die Öffentlichkeit, was FFT durch die Computerrevolution des nächsten Jahrzehnts zu einem unverzichtbaren Algorithmus in der digitalen Signalverarbeitung machte. ${\displaystyle O(N\log N)}$

Definition

Let , ..., werden komplexe Zahlen . Die DFT ist definiert durch die Formel ${\displaystyle x_{0}}$${\displaystyle x_{N-1}}$

${\displaystyle X_{k}=\sum_{n=0}^{N-1}x_{n}e^{-i2\pi kn/N}\qquad k=0,\ldots,N-1, }$

wo ist eine primitive N- te Wurzel von 1. ${\displaystyle e^{i2\pi /N}}$

Die Auswertung dieser Definition erfordert direkt Operationen: Es gibt N Ausgaben X _k , und jede Ausgabe erfordert eine Summe von N Termen. Eine FFT ist jede Methode, um dieselben Ergebnisse in Operationen zu berechnen . Alle bekannten FFT-Algorithmen erfordern Operationen , obwohl kein Beweis dafür bekannt ist, dass eine niedrigere Komplexitätsbewertung unmöglich ist. ${\displaystyle O\left(N^{2}\right)}$${\displaystyle O(N\log N)}$${\displaystyle \Theta (N\log N)}$

Um die Einsparungen einer FFT zu veranschaulichen, betrachten Sie die Anzahl komplexer Multiplikationen und Additionen für N = 4096 Datenpunkte. Die Auswertung der DFT-Summen beinhaltet direkt N ² komplexe Multiplikationen und N ( N − 1) komplexe Additionen, von denen Operationen eingespart werden können, indem triviale Operationen wie Multiplikationen mit 1 eliminiert werden, was etwa 30 Millionen Operationen übrig lässt. Im Gegensatz dazu kann der Radix-2 Cooley-Tukey-Algorithmus für N eine Potenz von 2 das gleiche Ergebnis mit nur ( N /2)log ₂ ( N ) komplexen Multiplikationen berechnen (wiederum werden Vereinfachungen von Multiplikationen mit 1 und ähnliches ignoriert). und N  log ₂ ( N ) komplexe Additionen, insgesamt ca. 30.000 Operationen – tausendmal weniger als bei direkter Auswertung. In der Praxis wird die tatsächliche Leistung auf modernen Computern normalerweise von anderen Faktoren als der Geschwindigkeit der Rechenoperationen dominiert und die Analyse ist ein kompliziertes Thema (siehe beispielsweise Frigo & Johnson , 2005), aber die Gesamtverbesserung von bis bleibt bestehen. ${\displaystyle O(N)}$${\displaystyle O\left(N^{2}\right)}$${\displaystyle O(N\log N)}$

Algorithmen

Cooley-Tukey-Algorithmus

Die mit Abstand am häufigsten verwendete FFT ist der Cooley-Tukey-Algorithmus. Dies ist ein Divide-and-Conquer-Algorithmus , der eine DFT beliebiger zusammengesetzter Größe rekursiv in viele kleinere DFTs der Größe und zerlegt , zusammen mit Multiplikationen mit komplexen Einheitswurzeln, die traditionell Twiddle-Faktoren genannt werden (nach Gentleman und Sande, 1966). ${\displaystyle N=N_{1}N_{2}}$${\displaystyle N_{1}}$${\displaystyle N_{2}}$${\displaystyle O(N)}$

Diese Methode (und die allgemeine Idee einer FFT) wurde 1965 durch eine Veröffentlichung von Cooley und Tukey populär, aber später stellte sich heraus, dass diese beiden Autoren unabhängig voneinander einen Carl Friedrich Gauss bekannten Algorithmus um 1805 neu erfunden (und später wiederentdeckt) hatten mehrmals in begrenzter Form).

Die bekannteste Verwendung des Cooley-Tukey-Algorithmus besteht darin, die Transformation in jedem Schritt in zwei Teile der Größe N /2 zu teilen , und ist daher auf eine Zweierpotenz beschränkt, aber im Allgemeinen kann jede Faktorisierung verwendet werden (wie bisher Gauss und Cooley/Tukey bekannt). Diese werden als Radix-2- bzw. Mixed-Radix- Fälle bezeichnet (und andere Varianten wie die Split-Radix-FFT haben auch ihre eigenen Namen). Obwohl die Grundidee rekursiv ist, ordnen die meisten herkömmlichen Implementierungen den Algorithmus neu an, um eine explizite Rekursion zu vermeiden. Da der Cooley-Tukey-Algorithmus die DFT in kleinere DFTs zerlegt, kann er außerdem beliebig mit jedem anderen Algorithmus für die DFT, wie den unten beschriebenen, kombiniert werden.

Andere FFT-Algorithmen

Es gibt andere FFT-Algorithmen als Cooley-Tukey.

Für N = N ₁ N ₂ mit coprime N ₁ und N ₂ kann man den Primfaktor- Algorithmus (Good-Thomas) (PFA) verwenden, der auf dem chinesischen Restsatz basiert , um die DFT ähnlich wie Cooley-Tukey zu faktorisieren, aber ohne die Drehfaktoren. Der Rader-Brenner-Algorithmus (1976) ist eine Cooley-Tukey-ähnliche Faktorisierung, jedoch mit rein imaginären Twiddle-Faktoren, wodurch Multiplikationen auf Kosten erhöhter Additionen und reduzierter numerischer Stabilität reduziert werden ; es wurde später durch die Split-Radix- Variante von Cooley-Tukey ersetzt (die die gleiche Multiplikationszahl erreicht, aber mit weniger Additionen und ohne Einbußen bei der Genauigkeit). Algorithmen, die die DFT rekursiv in kleinere Operationen außer DFTs faktorisieren, umfassen die Bruun- und QFT- Algorithmen. (Die Rader-Brenner- und QFT-Algorithmen wurden für Zweierpotenzgrößen vorgeschlagen, aber es ist möglich, dass sie an das allgemeine zusammengesetzte N angepasst werden können . Bruuns Algorithmus gilt für beliebige gerade zusammengesetzte Größen.) Insbesondere Bruuns Algorithmus basiert auf zur Interpretation der FFT als rekursive Faktorisierung des Polynoms z ^N  − 1, hier in reell-koeffiziente Polynome der Form z ^M  − 1 und z ^{2 M}  +  az ^M  + 1.

Ein anderer polynomialer Gesichtspunkt wird vom Winograd-FFT-Algorithmus genutzt, der z ^N  − 1 in zyklotomische Polynome faktorisiert – diese haben oft Koeffizienten von 1, 0 oder −1 und erfordern daher wenige (wenn überhaupt) Multiplikationen, sodass Winograd verwendet werden kann, um erhalten minimale Multiplikations-FFTs und wird oft verwendet, um effiziente Algorithmen für kleine Faktoren zu finden. Tatsächlich zeigte Winograd, dass die DFT nur mit O( N ) irrationalen Multiplikationen berechnet werden kann , was zu einer nachgewiesen erreichbaren unteren Schranke für die Anzahl der Multiplikationen für Zweierpotenzgrößen führt; Leider geht dies mit vielen weiteren Ergänzungen einher, ein Kompromiss, der bei modernen Prozessoren mit Hardware-Multiplikatoren nicht mehr günstig ist . Insbesondere macht Winograd auch den PFA sowie einen Algorithmus von Rader für FFTs von prime Größen.

Der Algorithmus von Rader , der die Existenz eines Generators für die multiplikative Gruppe modulo prim N ausnutzt , drückt eine DFT der Primzahl N als zyklische Faltung der (zusammengesetzten) Größe N − 1 aus, die dann durch ein Paar gewöhnlicher FFTs über die berechnet werden kann Faltungssatz (obwohl Winograd andere Faltungsmethoden verwendet). Eine weitere Primzahl-FFT ist auf LI Bluestein zurückzuführen und wird manchmal als Chirp-z-Algorithmus bezeichnet ; es drückt auch eine DFT als Faltung erneut aus, aber diesmal von der gleichen Größe (die mit Nullen auf eine Potenz von zwei aufgefüllt und beispielsweise durch Radix-2-Cooley-Tukey-FFTs ausgewertet werden kann) über die Identität

${\displaystyle nk=-{\frac {(kn)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2 }}.}$

Die sechseckige schnelle Fourier-Transformation (HFFT) zielt darauf ab, eine effiziente FFT für die hexagonal abgetasteten Daten zu berechnen, indem ein neues Adressierungsschema für sechseckige Gitter verwendet wird, das als Array Set Addressing (ASA) bezeichnet wird.

FFT-Algorithmen, die auf reale oder symmetrische Daten spezialisiert sind

In vielen Anwendungen sind die Eingabedaten für die DFT rein reell, in diesem Fall erfüllen die Ausgaben die Symmetrie

${\displaystyle X_{Nk}=X_{k}^{*}}$

und effiziente FFT-Algorithmen wurden für diese Situation entwickelt (siehe zB Sorensen, 1987). Ein Ansatz besteht darin, einen gewöhnlichen Algorithmus (zB Cooley-Tukey) zu verwenden und die redundanten Teile der Berechnung zu entfernen, was ungefähr einen Faktor von zwei an Zeit und Speicher spart. Alternativ ist es möglich, eine DFT mit reellem Eingang gerader Länge als komplexe DFT der halben Länge auszudrücken (deren Real- und Imaginärteil die geraden/ungerade-Elemente der ursprünglichen Realdaten sind), gefolgt von O( N ) nach- Verarbeitungsvorgänge.

Früher glaubte man, dass DFTs mit realer Eingabe effizienter mit Hilfe der diskreten Hartley-Transformation (DHT) berechnet werden könnten , aber später wurde argumentiert, dass typischerweise ein spezialisierter DFT-Algorithmus mit realer Eingabe (FFT) gefunden werden kann, der weniger Operationen erfordert als den entsprechenden DHT-Algorithmus (FHT) für die gleiche Anzahl von Eingängen. Bruuns Algorithmus (oben) ist eine weitere Methode, die ursprünglich vorgeschlagen wurde, um reale Eingaben zu nutzen, sich jedoch nicht als beliebt erwiesen hat.

Es gibt weitere FFT-Spezialisierungen für die Fälle von reellen Daten, die gerade/ungerade Symmetrie haben, in diesem Fall kann man einen weiteren Faktor von ungefähr zwei an Zeit und Speicher gewinnen und die DFT wird die diskrete Kosinus- / Sinus-Transformation(en) ( DCT / DST ). Anstatt einen FFT-Algorithmus für diese Fälle direkt zu modifizieren, können DCTs/DSTs auch über FFTs von Realdaten kombiniert mit O( N ) -Vor- und Nachverarbeitung berechnet werden .

Rechenprobleme

Grenzen für Komplexität und Betrieb zählen

Eine grundlegende Frage von seit langem theoretischem Interesse besteht darin, untere Schranken der Komplexität und der exakten Operationszahlen schneller Fourier-Transformationen zu beweisen , und es bleiben viele offene Probleme. Es ist nicht rigoros bewiesen, ob DFTs wirklich Ω( N  log  N ) (dh N  log  N oder mehr Ordnung ) Operationen erfordern, selbst für den einfachen Fall der Potenz von zwei Größen, obwohl keine Algorithmen mit geringerer Komplexität bekannt sind. Insbesondere die Anzahl der arithmetischen Operationen steht in der Regel im Mittelpunkt solcher Fragen, obwohl die tatsächliche Leistung auf modernen Computern von vielen anderen Faktoren wie der Cache- oder CPU-Pipeline- Optimierung bestimmt wird.

Nach der Arbeit von Shmuel Winograd (1978) ist eine enge untere Schranke von Θ( N ) für die Anzahl der reellen Multiplikationen bekannt, die von einer FFT benötigt werden. Es kann gezeigt werden, dass nur irrationale reelle Multiplikationen erforderlich sind, um eine DFT mit einer Zweierpotenzlänge zu berechnen . Darüber hinaus sind explizite Algorithmen bekannt, die diese Zählung erreichen (Heideman & Burrus , 1986; Duhamel, 1990). Diese Algorithmen erfordern jedoch zu viele Additionen, um praktisch zu sein, zumindest auf modernen Computern mit Hardware-Multiplikatoren (Duhamel, 1990; Frigo & Johnson , 2005). ${\displaystyle 4N-2\log_{2}^{2}(N)-2\log_{2}(N)-4}$${\displaystyle N=2^{m}}$

Eine enge untere Schranke für die Anzahl der erforderlichen Additionen ist nicht bekannt, obwohl untere Schranken unter einigen restriktiven Annahmen der Algorithmen bewiesen wurden. 1973 bewies Morgenstern eine ( N  log  N ) untere Schranke der Additionszählung für Algorithmen, bei denen die multiplikativen Konstanten begrenzte Größen haben (was für die meisten, aber nicht alle FFT-Algorithmen gilt). Pan (1986) bewies eine ( N  log  N ) untere Schranke unter Annahme einer Schranke für ein Maß der "Asynchronität" des FFT-Algorithmus, aber die Allgemeingültigkeit dieser Annahme ist unklar. Für den Fall der Potenz von zwei N , Papadimitriou (1979) argumentiert , dass die Zahl der komplexen Zahl Ergänzungen erreicht durch Cooley-Tukey Algorithmen ist optimal unter bestimmten Annahmen über die grafische Darstellung des Algorithmus (seine Annahmen implizieren, unter anderem, dass keine additiven Identitäten in den Wurzeln der Einheit ausgenutzt werden). (Dieses Argument würde implizieren, dass zumindest reelle Additionen erforderlich sind, obwohl dies keine enge Grenze ist, da zusätzliche Additionen als Teil von Multiplikationen mit komplexen Zahlen erforderlich sind.) Bisher hat kein veröffentlichter FFT-Algorithmus weniger als Additionen komplexer Zahlen erreicht ( oder ihr Äquivalent) für Zweierpotenzen  N . ${\displaystyle N\log_{2}N}$${\displaystyle 2N\log_{2}N}$${\displaystyle N\log_{2}N}$

Ein drittes Problem besteht darin, die Gesamtzahl der reellen Multiplikationen und Additionen zu minimieren , die manchmal als "arithmetische Komplexität" bezeichnet werden (obwohl in diesem Zusammenhang die genaue Anzahl und nicht die asymptotische Komplexität berücksichtigt wird). Auch hier wurde keine enge untere Schranke nachgewiesen. Seit 1968 wurde die niedrigste veröffentlichte Zahl für Zweierpotenzen N jedoch lange Zeit durch den Split-Radix-FFT-Algorithmus erreicht , der reelle Multiplikationen und Additionen für N > 1 erfordert . Dies wurde kürzlich auf (Johnson und Frigo, 2007; Lundy und Van Buskirk, 2007). Eine etwas größere Zählung (aber immer noch besser als Split-Radix für N ≥ 256) erwies sich unter zusätzlichen Einschränkungen der möglichen Algorithmen (split-radix-like flowgraphs with unit-modulus multiplicative Factors) als nachweislich optimal für N ≤ 512 durch Reduktion zu einem Erfüllbarkeits-Modulo-Theorie- Problem, das durch Brute-Force lösbar ist (Haynal & Haynal, 2011). ${\displaystyle 4N\log_{2}(N)-6N+8}$${\displaystyle \sim {\frac {34}{9}}N\log_{2}N}$

Die meisten Versuche, die Komplexität von FFT-Algorithmen zu verringern oder zu beweisen, haben sich auf den gewöhnlichen Fall komplexer Daten konzentriert, da dieser der einfachste ist. FFTs mit komplexen Daten sind jedoch so eng mit Algorithmen für verwandte Probleme wie Realdaten-FFTs, diskrete Kosinustransformationen , diskrete Hartley-Transformationen usw. Duhamel & Vetterli, 1990).

Näherungen

Alle oben diskutierten FFT-Algorithmen berechnen die DFT exakt (dh unter Vernachlässigung von Gleitkommafehlern ). Es wurden jedoch einige "FFT"-Algorithmen vorgeschlagen, die die DFT ungefähr berechnen , mit einem Fehler, der auf Kosten erhöhter Berechnungen beliebig klein gemacht werden kann. Solche Algorithmen tauschen den Näherungsfehler gegen eine erhöhte Geschwindigkeit oder andere Eigenschaften ein. Ein angenäherter FFT-Algorithmus von Edelman et al. (1999) erreicht mit Hilfe eines schnellen Multipolverfahrens geringere Kommunikationsanforderungen für paralleles Rechnen . Eine Wavelet- basierte approximative FFT von Guo und Burrus (1996) berücksichtigt spärliche Ein-/Ausgänge (Zeit-/Frequenzlokalisation) effizienter als dies mit einer exakten FFT möglich ist. Ein anderer Algorithmus zur ungefähren Berechnung einer Teilmenge der DFT-Ausgaben stammt von Shentov et al. (1995). Der Edelman-Algorithmus funktioniert für dünn besetzte und nicht dünn besetzte Daten gleichermaßen gut, da er auf der Kompressibilität (Rangdefizit) der Fourier-Matrix selbst und nicht auf der Komprimierbarkeit (sparsity) der Daten basiert. Umgekehrt, wenn die Daten spärlich sind – das heißt, wenn nur K von N Fourier-Koeffizienten ungleich Null sind – dann kann die Komplexität auf O( K  log( N ) log( N / K )) reduziert werden , und dies wurde gezeigt auf führen zu praktischen Beschleunigungen im Vergleich zu einer gewöhnlichen FFT für N / K  > 32 in einem großen N- Beispiel ( N  = 2 ²² ) unter Verwendung eines probabilistischen Näherungsalgorithmus (der die größten K- Koeffizienten auf mehrere Dezimalstellen schätzt ).

Genauigkeit

FFT-Algorithmen weisen Fehler auf, wenn Gleitkommaarithmetik mit endlicher Genauigkeit verwendet wird, aber diese Fehler sind normalerweise recht klein; die meisten FFT-Algorithmen, zB Cooley-Tukey, haben aufgrund der paarweisen Summationsstruktur der Algorithmen ausgezeichnete numerische Eigenschaften . Die obere Grenze für die relativen Fehler für den Cooley-Tukey - Algorithmus ist O ( ε lügt N ), im Vergleich zu O ( & epsi; n ^3/2 ) für die naive DFT Formel, wobei ε die Maschine Gleitkommazahlen relative Genauigkeit. In der Tat, die Root Mean Square sind (rms) Fehler viel besser als diese obere Grenze, nur O (wobei & egr; √ log N ) für Cooley-Tukey und O ( & egr; √ N ) für die naiven DFT (Schatzman, 1996). Diese Ergebnisse sind jedoch sehr empfindlich auf die Genauigkeit der twiddle Faktoren in der FFT verwendet (dh die trigonometrischen Funktionswert), und es ist nicht ungewöhnlich für unvorsichtige FFT - Implementierungen viel schlechte Genauigkeit zu haben, zum Beispiel , wenn sie ungenau verwenden trigonometrische Wiederholung Formeln . Einige andere FFTs als Cooley-Tukey, wie der Rader-Brenner-Algorithmus, sind intrinsisch weniger stabil.

Bei der Festkomma-Arithmetik sind die von FFT-Algorithmen akkumulierten Fehler mit endlicher Genauigkeit schlimmer, wobei die Effektivfehler beim Cooley-Tukey-Algorithmus mit O( √ N ) wachsen (Welch, 1969). Um diese Genauigkeit zu erreichen, muss die Skalierung sorgfältig beachtet werden, um den Präzisionsverlust zu minimieren, und Festkomma-FFT-Algorithmen beinhalten eine Neuskalierung in jeder Zwischenstufe der Zerlegung wie Cooley-Tukey.

Um die Korrektheit einer FFT-Implementierung zu überprüfen, können strenge Garantien in O( N  log  N ) Zeit durch ein einfaches Verfahren erhalten werden, das die Linearität, Impulsantwort und Zeitverschiebungseigenschaften der Transformation an zufälligen Eingaben überprüft (Ergün, 1995). .

Mehrdimensionale FFTs

Wie in den definierten mehrdimensionalen DFT Artikeln, die mehrdimensionale DFT

${\displaystyle X_{\mathbf{k}}=\sum_{\mathbf{n}=0}^{\mathbf{N} -1}e^{-2\pi i\mathbf {k} \cdot ( \mathbf{n} /\mathbf{N})}x_{\mathbf{n}}}$

transformiert ein Array x _n mit einem d- dimensionalen Vektor von Indizes durch einen Satz von d verschachtelten Summationen (über für jedes j ), wobei die Division n / N , definiert als , elementweise durchgeführt wird. Äquivalent ist es die Zusammensetzung einer Folge von d Sätzen von eindimensionalen DFTs, die jeweils entlang einer Dimension (in beliebiger Reihenfolge) durchgeführt werden. ${\displaystyle \mathbf{n} =\left(n_{1},\ldots,n_{d}\right)}$${\displaystyle n_{j}=0\ldots N_{j}-1}$${\displaystyle \mathbf{n} /\mathbf{N} =\left(n_{1}/N_{1},\ldots,n_{d}/N_{d}\right)}$

Dieser kompositorische Gesichtspunkt liefert sofort den einfachsten und gebräuchlichsten mehrdimensionalen DFT-Algorithmus, der als Zeilen-Spalten- Algorithmus bekannt ist (nach dem zweidimensionalen Fall unten). Das heißt, man führt einfach eine Folge von d eindimensionalen FFTs durch (mit einem der obigen Algorithmen): zuerst transformiert man entlang der n _1- Dimension, dann entlang der n ₂ -Dimension usw. (oder eigentlich funktioniert jede Reihenfolge) . Es wird leicht gezeigt, dass dieses Verfahren die übliche Komplexität von O( N  log  N ) hat, wobei die Gesamtzahl der transformierten Datenpunkte ist. Insbesondere gibt es N / N ₁ Transformationen der Größe N ₁ usw., so dass die Komplexität der Folge von FFTs ist: ${\displaystyle N=N_{1}\cdot N_{2}\cdot \cdots \cdot N_{d}}$

${\displaystyle {\begin{ausgerichtet}&{\frac {N}{N_{1}}}O(N_{1}\log N_{1})+\cdots +{\frac {N}{N_{d }}}O(N_{d}\log N_{d})\\[6pt]={}&O\left(N\left[\log N_{1}+\cdots +\log N_{d}\right ]\right)=O(N\log N).\end{ausgerichtet}}}$

In zwei Dimensionen kann x _k als Matrix betrachtet werden , und dieser Algorithmus entspricht zunächst der Durchführung der FFT aller Zeilen (bzw. Spalten), der Gruppierung der resultierenden transformierten Zeilen (bzw. Spalten) als weitere Matrix und dann Durchführen der FFT an jeder der Spalten (bzw. Zeilen) dieser zweiten Matrix und ähnliches Gruppieren der Ergebnisse in die endgültige Ergebnismatrix. ${\displaystyle n_{1}\times n_{2}}$ ${\displaystyle n_{1}\times n_{2}}$

Bei mehr als zwei Dimensionen ist es für die Cache- Lokalität oft von Vorteil , die Dimensionen rekursiv zu gruppieren. Zum Beispiel könnte eine dreidimensionale FFT zuerst zweidimensionale FFTs von jedem planaren "Slice" für jedes feste n _{1 durchführen} und dann die eindimensionalen FFTs entlang der n ₁ -Richtung durchführen. Allgemeiner gesagt besteht ein asymptotisch optimaler Cache-Oblivious- Algorithmus darin, die Dimensionen rekursiv in zwei Gruppen zu unterteilen und diese rekursiv zu transformieren (runden, wenn d nicht gerade ist) (siehe Frigo und Johnson, 2005). Dennoch bleibt dies eine einfache Variation des Zeilen-Spalten-Algorithmus, der letztendlich nur einen eindimensionalen FFT-Algorithmus als Basisfall erfordert und immer noch eine Komplexität von O( N  log  N ) hat. Noch eine weitere Variation ist Matrix auszuführen Transpositionen zwischen nachfolgenden Umwandlung Abmessungen, so daß die Transformationen auf zusammenhängende Daten arbeiten; Dies ist besonders wichtig für Situationen außerhalb des Kerns und verteilten Speichers , in denen der Zugriff auf nicht zusammenhängende Daten extrem zeitaufwändig ist. ${\displaystyle (n_{1},\ldots,n_{d/2})}$${\displaystyle (n_{d/2+1},\ldots,n_{d})}$

Es gibt andere mehrdimensionale FFT-Algorithmen, die sich vom Zeilen-Spalten-Algorithmus unterscheiden, obwohl alle von ihnen eine Komplexität von O( N  log  N ) haben. Die vielleicht einfachste Nicht-Zeilenspalten-FFT ist der Vektor-Radix-FFT-Algorithmus , der eine Verallgemeinerung des gewöhnlichen Cooley-Tukey-Algorithmus ist, bei dem man die Transformationsdimensionen bei jedem Schritt durch einen Vektor von Radikalen teilt . (Dies kann auch Cache-Vorteile haben.) Der einfachste Fall von Vektor-Radix ist, wenn alle Radikale gleich sind (zB Vektor-Radix-2 teilt alle Dimensionen durch zwei), aber dies ist nicht notwendig. Vektor-Radix mit nur einem einzigen Nicht-Einheits-Radix zu einem Zeitpunkt, dh , ist im Wesentlichen ein Zeilen-Spalten-Algorithmus. Andere, kompliziertere Verfahren umfassen polynomiale Transformationsalgorithmen nach Nussbaumer (1977), die die Transformation in Form von Faltungen und Polynomprodukten betrachten. Siehe Duhamel und Vetterli (1990) für weitere Informationen und Referenzen. ${\displaystyle \mathbf{r} =\left(r_{1},r_{2},\ldots,r_{d}\right)}$${\displaystyle \mathbf{r} =\left(1,\ldots,1,r,1,\ldots,1\right)}$

Andere Verallgemeinerungen

Eine Verallgemeinerung von O( N ^5/2 log  N ) auf sphärische Harmonische auf der Kugel S ² mit N ² Knoten wurde von Mohlenkamp beschrieben, zusammen mit einem Algorithmus, von dem vermutet (aber nicht bewiesen) wird, dass er O( N ² log ² ( N ) hat) Komplexität; Mohlenkamp stellt auch eine Implementierung in der libftsh-Bibliothek bereit. Ein sphärisch-harmonischer Algorithmus mit O( N ² log  N ) Komplexität wird von Rokhlin und Tygert beschrieben.

Der Fast-Folding-Algorithmus ist analog zur FFT, außer dass er auf einer Reihe von Binned-Wellenformen und nicht auf einer Reihe von reellen oder komplexen Skalarwerten arbeitet. Die Drehung (die in der FFT eine Multiplikation mit einem komplexen Zeiger ist) ist eine kreisförmige Verschiebung der Komponentenwellenform.

Verschiedene Gruppen haben auch "FFT"-Algorithmen für nicht gleich verteilte Daten veröffentlicht, wie in Potts et al. (2001). Solche Algorithmen berechnen die DFT nicht streng (die nur für gleich beabstandete Daten definiert ist), sondern eher eine Annäherung davon (eine nicht gleichförmige diskrete Fourier-Transformation oder NDFT, die selbst oft nur näherungsweise berechnet wird). Allgemeiner gesagt gibt es verschiedene andere Methoden der spektralen Schätzung .

Anwendungen

Die FFT wird in digitaler Aufnahme-, Sampling-, additiver Synthese- und Tonhöhenkorrektur- Software verwendet.

Die Bedeutung der FFT ergibt sich aus der Tatsache, dass sie das Arbeiten im Frequenzbereich ebenso rechentechnisch möglich macht wie das Arbeiten im zeitlichen oder räumlichen Bereich. Einige der wichtigsten Anwendungen der FFT sind:

• schnelle großzahlige und polynomiale Multiplikation,
• effiziente Matrix-Vektor-Multiplikation für Toeplitz , circulant und andere strukturierte Matrizen,
• Filteralgorithmen (siehe Overlap-Add- und Overlap-Save- Methoden),
• schnelle Algorithmen für diskrete Kosinus- oder Sinustransformationen (zB schnelle DCT für JPEG- und MPEG / MP3- Kodierung und Dekodierung),
• schnelle Chebyshev-Näherung ,
• Lösen Differenzengleichungen ,
• Berechnung von Isotopenverteilungen .
• Modulation und Demodulation komplexer Datensymbole mit orthogonalem Frequenzmultiplex (OFDM) für 5G, LTE, Wi-Fi, DSL und andere moderne Kommunikationssysteme.

Forschungsgebiete

Große FFTs

Mit der Explosion von Big Data in Bereichen wie der Astronomie ist der Bedarf an 512K-FFTs für bestimmte Interferometrie-Berechnungen entstanden. Die von Projekten wie WMAP und LIGO gesammelten Daten erfordern FFTs von mehreren zehn Milliarden Punkten. Da diese Größe nicht in den Hauptspeicher passt, sind sogenannte Out-of-Core-FFTs ein aktives Forschungsgebiet.

Ungefähre FFTs

Für Anwendungen wie MRI ist es notwendig, DFTs für ungleichmäßig beabstandete Gitterpunkte und/oder Frequenzen zu berechnen. Multipol-basierte Ansätze können ungefähre Größen mit Faktor der Laufzeiterhöhung berechnen.

Gruppen-FFTs

Die FFT kann auch unter Verwendung der Gruppenrepräsentationstheorie erklärt und interpretiert werden , was eine weitere Verallgemeinerung ermöglicht. Eine Funktion auf einer beliebigen kompakten Gruppe, einschließlich nichtzyklischer, hat eine Erweiterung im Sinne einer Basis irreduzibler Matrixelemente. Es bleibt ein aktives Forschungsgebiet, einen effizienten Algorithmus zu finden, um diesen Basiswechsel durchzuführen. Anwendungen einschließlich effizienter sphärischer harmonischer Expansion, Analyse bestimmter Markov-Prozesse , Robotik usw.

Quanten-FFTs

Der schnelle Algorithmus von Shors für die Faktorisierung ganzer Zahlen auf einem Quantencomputer verfügt über eine Subroutine zur Berechnung der DFT eines binären Vektors. Dies wird als Folge von 1- oder 2-Bit-Quantengattern implementiert, die jetzt als Quanten-FFT bekannt sind, die effektiv die Cooley-Tukey-FFT ist, die als eine bestimmte Faktorisierung der Fourier-Matrix realisiert wird. Eine Erweiterung dieser Ideen wird derzeit geprüft.

Sprach-Referenz

Sprache	Befehl/Methode	Voraussetzungen
R	Statistiken::fft(x)	Keiner
Oktave / MATLAB	fft(x)	Keiner
Python	fft.fft(x)	numpy
Mathematik	Fourier[x]	Keiner
Fortran	fftw_one(plan,ein,aus)	FFTW
Julia	fft(A [,verdunkelt])	FFTW
Rost	fft.process(&mut x);	rustfft
Haskell	dft x	fft

Siehe auch

FFT-bezogene Algorithmen:

• Goertzel-Algorithmus – berechnet einzelne Terme der diskreten Fourier-Transformation

FFT-Implementierungen:

• ALGLIB – eine duale/GPL-lizenzierte C++- und C#-Bibliothek (unterstützt auch andere Sprachen), mit realer/komplexer FFT-Implementierung
• FFTPACK – eine weitere Fortran FFT-Bibliothek (gemeinfrei)
• Architekturspezifisch:
  • Armleistungsbibliotheken
  • Intel Integrated Performance Primitives
  • Intel Math Kernel-Bibliothek
• Viele weitere Implementierungen sind für CPUs und GPUs verfügbar, z. B. PocketFFT für C++

Andere Links:

• Odlyzko-Schönhage-Algorithmus wendet die FFT auf endliche Dirichlet-Reihen an
• Schönhage-Strassen-Algorithmus – asymptotisch schneller Multiplikationsalgorithmus für große ganze Zahlen
• Butterfly-Diagramm – ein Diagramm zur Beschreibung von FFTs
• Spektrale Musik (beinhaltet die Anwendung der DFT-Analyse auf die Musikkomposition)
• Spektrumanalysator – eines von mehreren Geräten, die eine Spektrumanalyse durchführen, oft über eine DFT
• Zeitfolgen
• Schnelle Walsh-Hadamard-Transformation
• Verallgemeinertes Verteilungsrecht
• Spektralanalyse der kleinsten Quadrate
• Mehrdimensionale Transformation
• Mehrdimensionale diskrete Faltung
• Teleskop mit schneller Fourier-Transformation

Verweise

Weiterlesen

• Brigham, E. Oran (2002). „Die schnelle Fourier-Transformation“. New York, USA: Lehrlingshalle . Cite Journal erfordert |journal=( Hilfe )
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "Kapitel 30: Polynome und die FFT". Einführung in Algorithmen (2 Aufl.). MIT Press / McGraw-Hill . ISBN 0-262-03293-7.
• Elliott, Douglas F.; Rao, K. Ramamohan (1982). Schnelle Transformationen: Algorithmen, Analysen, Anwendungen . New York, USA: Akademische Presse .
• Guo, Haiti; Sitton, Gary A.; Burrus, Charles Sidney (1994). „Die schnelle diskrete Fourier-Transformation“. Verfahren von ICASSP '94. Internationale IEEE-Konferenz für Akustik, Sprach- und Signalverarbeitung . Proceedings on the IEEE Conference on Acoustics, Speech, and Signal Processing (ICASSP) . 3 . S. 445–448. doi : 10.1109/ICASSP.1994.389994 . ISBN 978-0-7803-1775-8. S2CID  42639206 .
• Johnson, Steven G.; Frigo, Matteo (2007). "Eine modifizierte Split-Radix-FFT mit weniger arithmetischen Operationen" (PDF) . IEEE-Transaktionen zur Signalverarbeitung . 55 (1): 111-119. Bibcode : 2007ITSP...55..111J . CiteSeerX  10.1.1.582.5497 . doi : 10.1109/tsp.2006.882087 . S2CID  14772428 .
• Presse, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). "Kapitel 12. Schnelle Fourier-Transformation" . Numerische Rezepte: Die Kunst des wissenschaftlichen Rechnens (3 Hrsg.). New York, USA: Cambridge University Press . ISBN 978-0-521-88068-8.
• Singleton, Richard Collom (Juni 1969). „Eine kurze Bibliographie über die schnelle Fourier-Transformation“. Sonderausgabe zur schnellen Fourier-Transformation . IEEE-Transaktionen zu Audio und Elektroakustik . AU-17. IEEE Audio and Electroacoustics Group. S. 166–169. doi : 10.1109/TAU.1969.1162029 . (NB. Enthält umfangreiche Bibliographie.)
• Elena Prestini: "The Evolution of Applied Harmonic Analysis", Springer, ISBN 978-0-8176-4125-2 (2004), Sec.3.10 'Gauss und die Asteroiden: Geschichte der FFT'.

Externe Links

• Fast Fourier Transform for Polynomial Multiplication  – Fast Fourier Algorithmus
• Fast Fourier Transforms , Connexions Online-Buch herausgegeben von Charles Sidney Burrus, mit Kapiteln von Charles Sidney Burrus, Ivan Selesnick, Markus Pueschel, Matteo Frigo und Steven G. Johnson (2008)
• Schnelle Fourier-Transformation – FFT  – FFT-Programmierung in C++ – der Cooley-Tukey-Algorithmus
• Online-Dokumentation, Links, Buch und Code
• Sri Welaratna, „ Dreißig Jahre FFT-Analysatoren “, Sound and Vibration (Januar 1997, 30. Jubiläumsausgabe) – ein historischer Rückblick auf Hardware-FFT-Geräte
• ALGLIB FFT Code  – eine duale/GPL-lizenzierte mehrsprachige (VBA, C++, Pascal usw.) Bibliothek für numerische Analyse und Datenverarbeitung
• SFFT: Sparse Fast Fourier Transform  – Sparse (sublinear time) FFT-Algorithmus des MIT, sFFT und Implementierung
• VB6 FFT  – eine VB6-optimierte Bibliotheksimplementierung mit Quellcode
• Interactive FFT Tutorial  – eine visuelle interaktive Einführung in Fourier-Transformationen und FFT-Methoden