Schnelle Fourier-Transformation

Ein Beispiel FFT-Algorithmusstruktur unter Verwendung einer Zersetzung in halbgroße FFTs

Eine diskrete Fourier -Analyse einer Summe von Cosinus -Wellen bei 10, 20, 30, 40 und 50 Hz

A Schnelle Fourier-Transformation (Fft) ist ein Algorithmus das berechnet die diskrete Fourier-Transformation (DFT) einer Sequenz oder ihrer inversen (IDFT). Fourier -Analyse konvertiert ein Signal aus seiner ursprünglichen Domäne (oft Zeit oder Raum) in eine Darstellung in der Frequenzbereich und umgekehrt. Das DFT wird durch Zersetzung a erhalten Reihenfolge von Werten in Komponenten unterschiedlicher Frequenzen.^[1] Dieser Vorgang ist in vielen Bereichen nützlich, aber es ist oft zu langsam, sie direkt aus der Definition zu berechnen, um praktisch zu sein. Eine FFT berechnet solche Transformationen schnell durch Faktorisierung das DFT -Matrix in ein Produkt von spärlich (meistens Null) Faktoren.^[2] Infolgedessen schafft es die Reduzierung der Komplexität von der DFT von berechnen ${\ displayStyle o \ links (n^{2} \ rechts)}$, was entsteht, wenn man einfach die Definition von DFT anwendet, um auf ${\ displayStyle o (n \ log n)}$, wo ${\ displayStyle n}$ ist die Datengröße. Der Geschwindigkeitsunterschied kann enorm sein, insbesondere für lange Datensätze, bei denen N Kann in den Tausenden oder Millionen sein. In Anwesenheit von RundenfehlerViele FFT -Algorithmen sind viel genauer als die DFT -Definition direkt oder indirekt. Es gibt viele verschiedene FFT -Algorithmen, die auf einer Vielzahl von veröffentlichten Theorien basieren, von einfach komplexes Arithmetik zu Gruppentheorie und Zahlentheorie.

Schnelle Fourier -Transformationen werden häufig verwendet Anwendungen In Ingenieurwesen, Musik, Wissenschaft und Mathematik. Die grundlegenden Ideen wurden 1965 populär gemacht, aber einige Algorithmen waren bereits 1805 abgeleitet.^[1] Im Jahr 1994, Gilbert Strang beschrieb die FFT als "das Wichtigste Numerischer Algorithmus von unserem Leben ",^[3][4] und es wurde in den Top 10 Algorithmen des 20. Jahrhunderts von der enthalten IEEE Zeitschrift Computing in Science & Engineering.^[5]

Die bekanntesten FFT-Algorithmen hängen von der ab Faktorisierung von N, aber es gibt FFTs mit Ö(NProtokollN) Komplexität für alle N, sogar für Prime N. Viele FFT -Algorithmen hängen nur von der Tatsache ab, dass ${\ displayStyle e^{-2 \ pi i/n}}$ ist ein N-Th primitive Wurzel der Einheitund kann so auf analoge Transformationen über jeden angewendet werden endliches Feld, wie zum Beispiel zahlentheoretische Transformationen. Da der inverse DFT das gleiche ist wie der DFT, aber mit dem entgegengesetzten Zeichen im Exponenten und einem 1////N Faktor, jeder FFT -Algorithmus kann leicht dafür angepasst werden.

Geschichte

Die Entwicklung schneller Algorithmen für DFT kann auf verfolgt werden Carl Friedrich Gauß's unveröffentlichte Arbeit im Jahr 1805, als er es brauchte, um die Umlaufbahn von Asteroiden zu interpolieren Pallas und Juno Aus Probenbeobachtungen.^[6][7] Seine Methode war der 1965 veröffentlichten Methode sehr ähnlich von James Cooley und John Tukey, denen allgemein für die Erfindung des modernen generischen FFT -Algorithmus zugeschrieben wird. Während Gaußs Arbeit sogar vorliegt Joseph FourierIn den Ergebnissen von 1822 analysierte er die Berechnungszeit 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 1932 veröffentlichte seine Version genannt Interaktionsalgorithmus, was zur Verfügung stellte Effiziente Berechnung von Hadamard- und Walsh -Transformationen.^[8] Der Algorithmus von Yates wird immer noch auf dem Gebiet des statistischen Designs und der Analyse von Experimenten verwendet. 1942, G. C. Danielson und Cornelius Lanczos veröffentlichte ihre Version, um DFT für zu berechnen Röntgenkristallographie, ein Feld, in dem die Berechnung von Fourier -Transformationen einen beeindruckenden Engpass darstellte.^[9][10] Während sich viele Methoden in der Vergangenheit darauf konzentriert hatten, den konstanten Faktor für zu verringern ${\ displayStyle o \ links (n^{2} \ rechts)}$ Berechnung durch Nutzung von "Symmetrien" stellten Danielson und Lanczos fest analysieren, dies führte zu ${\ displayStyle o (n \ log n)}$ Skalierung.^[11]

James Cooley und John Tukey haben diese früheren Algorithmen unabhängig wiederentdeckt^[7] und veröffentlicht a Allgemeiner Fft 1965 ist das anwendbar, wenn N ist zusammengesetzt und nicht unbedingt eine Leistung von 2 sowie die Analyse der ${\ displayStyle o (n \ log n)}$ Skalierung.^[12] Tukey hatte die Idee während eines Treffens von Präsident Kennedy's Science Advisory Committee, bei dem ein Diskussionsthema dazu beinhaltete, Atomtests der Sowjetunion zu erkennen, indem Sensoren für die Umgebung des Landes von außen eingerichtet wurden. Um den Ausgang dieser Sensoren zu analysieren, wäre ein FFT -Algorithmus erforderlich. In Diskussion mit Tukey, Richard Garwin Erkannte die allgemeine Anwendbarkeit des Algorithmus nicht nur auf nationale Sicherheitsprobleme, sondern auch auf eine Vielzahl von Problemen, einschließlich eines von unmittelbarem Interesse, das die Periodizität der Spinorientierungen in einem 3-D-Kristall von Helium-3 bestimmt.^[13] Garwin gab Tukeys Idee Cooley (beide arbeiteten bei IBMs Watson Labs) Für die Umsetzung.^[14] Cooley und Tukey veröffentlichten das Papier in einer relativ kurzen Zeit von sechs Monaten.^[15] Da Tukey bei IBM nicht arbeitete, wurde die Patentierbarkeit der Idee bezweifelt und der Algorithmus ging in die Öffentlichkeitsbereich, was durch die Computerrevolution des nächsten Jahrzehnts FFT zu einem der unverzichtbaren Algorithmen in machte digitale Signalverarbeitung.

Definition

Lassen ${\ displayStyle x_ {0}}$,…, ${\ displayStyle x_ {n-1}}$ sein komplexe Zahlen. Das DFT wird durch die Formel definiert

$oder }$

wo ${\ displayStyle e^{i2 \ pi /n}}$ ist ein Primitive NDie Wurzel von 1.

Die direkte Bewertung dieser Definition erfordert direkt ${\ displayStyle o \ links (n^{2} \ rechts)}$ Operationen: Es gibt N Ausgänge X_kund jeder Ausgang erfordert eine Summe von N Bedingungen. Eine FFT ist jede Methode, um die gleichen Ergebnisse zu berechnen ${\ displayStyle o (n \ log n)}$ Operationen. Alle bekannten FFT -Algorithmen erfordern ${\ displayStyle \ theta (n \ log n)}$ OperationenObwohl es keinen Beweis gibt, dass eine geringere Komplexität unmöglich ist.^[16]

Um die Einsparungen eines FFT zu veranschaulichen, berücksichtigen Sie die Anzahl komplexer Multiplikationen und Ergänzungen für N= 4096 Datenpunkte. Die direkte Bewertung der DFT -Summen beinhaltet direkt N² Komplexe Multiplikationen und N(N - 1) komplexe Ergänzungen, von denen ${\ displayStyle o (n)}$ Operationen können gespeichert werden, indem triviale Operationen wie Multiplikationen um 1 beseitigt werden, wobei rund 30 Millionen Operationen zurückbleiben. Im Gegensatz dazu der Radix-2 Cooley -Tukey -Algorithmus, zum N Eine Leistung von 2 kann das gleiche Ergebnis nur mit (nur mit (N/2) Protokoll₂(N) komplexe Multiplikationen (erneut ignorieren Vereinfachungen von Multiplikationen mit 1 und ähnlich) und NProtokoll₂(N) Komplexe Ergänzungen insgesamt etwa 30.000 Operationen - tausendmal weniger als bei direkter Bewertung. In der Praxis wird die tatsächliche Leistung auf modernen Computern normalerweise von anderen Faktoren als der Geschwindigkeit von arithmetischen Operationen dominiert, und die Analyse ist ein kompliziertes Thema (z. B. siehe Frigo & siehe Johnson, 2005),^[17] Aber die allgemeine Verbesserung von ${\ displayStyle o \ links (n^{2} \ rechts)}$ zu ${\ displayStyle o (n \ log n)}$ Überreste.

Algorithmen

Cooley -Tukey -Algorithmus

Der mit Abstand am häufigsten verwendete FFT ist der Cooley -Tukey -Algorithmus. Das ist ein Divide-and-Conquer-Algorithmus das rekursiv bricht eine DFT von jedem ab zusammengesetzt Größe ${\ displayStyle n = n_ {1} n_ {2}}$ in viele kleinere DFTs von Größen ${\ displayStyle n_ {1}}$ und ${\ displayStyle n_ {2}}$, zusammen mit ${\ displayStyle o (n)}$ Multiplikationen mit Komplex Wurzeln der Einheit traditionell genannt Twiddle -Faktoren (Nach Gentleman und Sande, 1966^[18]).

Diese Methode (und die allgemeine Idee eines FFT) wurde durch eine Veröffentlichung von Cooley und Tukey im Jahr 1965 populär gemacht.^[12] aber es wurde später entdeckt^[1] dass diese beiden Autoren einen Algorithmus, der bekannt ist Carl Friedrich Gauß Um 1805^[19] (und anschließend mehrmals in begrenzten Formen wieder entdeckt).

Die bekannteste Verwendung des Cooley -Tukey -Algorithmus besteht darin, die Transformation in zwei Größe der Größe zu unterteilen N/2 bei jedem Schritt und ist daher auf zwei Zweigrößen beschränkt, aber jede Faktorisierung kann im Allgemeinen verwendet werden (wie es sowohl Gauß als auch Cooley/Tukey bekannt war^[1]). Diese werden die genannt Radix-2 und gemischtes Radix Fälle (bzw. andere Varianten wie die Split-Radix FFT habe 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 das DFT in kleinere DFTs zerlegt, kann er willkürlich mit jedem anderen Algorithmus für die DFT kombiniert werden, wie sie unten beschrieben sind.

Andere FFT -Algorithmen

Es gibt andere FFT -Algorithmen als Cooley -tukey.

Zum N = N₁N₂ mit Coprime N₁ und N₂, man kann das verwenden Prime-Faktor (Good -Thomas) -Algorithmus (PFA), basierend auf dem Chinesischer Rest -Theorem, um die DFT ähnlich wie Cooley -tukey zu faktorisieren, jedoch ohne die Twiddle -Faktoren. Der Rader -Brenner -Algorithmus (1976)^[20] ist eine Cooley-tukey-ähnliche Faktorisierung, aber mit rein imaginären Twiddle-Faktoren, wodurch die Multiplikationen auf Kosten erhöhter Ergänzungen reduziert und verringert werden Numerische Stabilität; es wurde später von der ersetzt Split-Radix Variante von Cooley -tukey (die die gleiche Multiplikationsanzahl, jedoch mit weniger Ergänzungen und ohne Opfergenauigkeit erreicht). Algorithmen, die die DFT rekursiv in kleinere Operationen als DFTs faktorisieren, umfassen die Bruun- und QFT -Algorithmen. (Der Rader -Brenner^[20] und QFT-Algorithmen wurden für zwei2er Größen vorgeschlagen, aber es ist möglich, dass sie an allgemeine Komposit angepasst werden können N. Der Algorithmus von Bruun gilt für willkürliche, gleichmäßige Verbundgrößen.) Bruuns Algorithmusinsbesondere basiert auf der Interpretation der FFT als rekursive Faktorisierung der Polynom z^N-1, hier in real-zoeffizienische Polynome der Form z^M- 1 und z^2M+AZ^M+1.

Ein weiterer polynomialer Standpunkt wird vom Winograd FFT -Algorithmus ausgenutzt.^[21][22] was faktorisiert z^N- 1 in Zyklotomische Polynome-Diese haben häufig Koeffizienten von 1, 0 oder –1 und erfordern daher nur wenige (falls vorhanden) Multiplikationen, sodass Winograd verwendet werden kann, um FFTs mit minimaler Multiplikation zu erhalten, und wird häufig verwendet, um effiziente Algorithmen für kleine Faktoren zu finden. In der Tat zeigte Winograd, dass die DFT nur mit O (nur O () berechnet werden kannN) irrationale Multiplikationen, was zu einer nachgewiesenen erreichbaren niedrigeren Größenzahl für die Anzahl der zwei2er Größen führt; Leider ist dies zu so viel mehr Ergänzungen, ein Kompromiss für die moderne Kompromisse Prozessoren mit Hardware -Multiplikatoren. Insbesondere winograd nutzt auch das PFA sowie einen Algorithmus von Strahl für FFTs von Prime Größen.

Rader -Algorithmus, die Existenz von a ausnutzen Generator für das multiplikative Gruppe Modulo Prime Ndrückt eine DFT von Primgröße aus N als zyklisch Faltung von (zusammengesetzter) Größe N - 1, das dann durch ein Paar gewöhnlicher FFTs über die berechnet werden kann Faltungssatz (Obwohl Winograd andere Faltungsmethoden verwendet). Ein weiterer FFT in Prime-Größe ist L. I. Bluestein und manchmal als das genannt Chirp-Z-Algorithmus; Es exprimiert auch eine DFT als Faltung, aber diesmal der gleich Größe (die zu einem Null-Padd zu a Kraft von zwei und bewertet beispielsweise durch Radix-2 Cooley-Tukey-FFTs) über die Identität

$oder }}.}$

Hexagonal Fast Fourier Transformation (HFFT) zielt darauf ab, einen effizienten FFT für die hexagonal-Sampled-Daten mithilfe eines neuen Adressierungsschemas für hexagonale Gitter mit dem Namen Array Set Addressing (ASA) zu berechnen.

FFT -Algorithmen spezialisiert auf reale oder symmetrische Daten

In vielen Anwendungen sind die Eingabedaten für das DFT rein real. In diesem Fall erfüllen die Ausgänge die Symmetrie

${\ displaystyle x_ {n-k} = x_ {k}^{*}}$

Für diese Situation wurden effiziente FFT -Algorithmen entwickelt (siehe z. B. Sorensen, 1987).^[23][24] Ein Ansatz besteht darin, einen gewöhnlichen Algorithmus (z. B. Cooley -tukey) und die redundanten Teile der Berechnung zu entfernen, was ungefähr Zeit und Speicher einen Faktor von zwei spart. Alternativ ist es möglich, eine auszudrücken eben-Length realeinput DFT als komplexe DFT der halben Länge (deren reale und imaginäre Teile die geraden/ungeraden Elemente der ursprünglichen realen Daten sind), gefolgt von O (N) Nachbearbeitungsvorgänge.

Es wurde einst angenommen, dass DFTs mit realem Eingang mithilfe dessen effizienter berechnet werden könnten Diskrete Hartley -Transformation (DHT), aber es wurde anschließend argumentiert, dass ein spezialisierter DFT-Algorithmus (FFT) in der Regel festgestellt werden kann, dass weniger Operationen als der entsprechende DHT-Algorithmus (FHT) für die gleiche Anzahl von Eingaben erforderlich sind.^[23] Bruuns Algorithmus (oben) ist eine andere Methode, die ursprünglich vorgeschlagen wurde, um echte Eingaben zu nutzen, hat sich jedoch nicht als beliebt erwiesen.

Es gibt weitere FFT -Spezialisierungen für die Fälle realer Daten, die haben gerade ungerade Symmetrie, in diesem Fall kann man einen weiteren Faktor von ungefähr zwei zeitlich und Gedächtnis gewinnen, und der DFT wird zum Diskreter Cosinus/Sinus -Transformationen (en) (DCT/Dst). Anstatt einen FFT -Algorithmus für diese Fälle direkt zu modifizieren, können DCTs/DSTs auch über FFTs realer Daten in Kombination mit O berechnet werden ((N) Vor- und Nachbearbeitung.

Rechenprobleme

Grenzen für Komplexität und Betriebszahlen

Eine grundlegende Frage des langjährigen theoretischen Interesses besteht darin, die unteren Grenzen der Komplexität und genaue Betriebszahlen schneller Fourier -Transformationen, und es bleiben viele offene Probleme. Es ist nicht streng bewiesen, ob DFTs wirklich ω benötigen (NProtokollN) (d. H. Bestellung NProtokollN oder größere) Operationen, selbst für den einfachen Fall von Kraft von zwei Obwohl keine Algorithmen mit geringerer Komplexität bekannt sind. Insbesondere ist die Anzahl arithmetischer Operationen in der Regel der Schwerpunkt solcher Fragen, obwohl die tatsächliche Leistung auf modernen Computern durch viele andere Faktoren wie z. Zwischenspeicher oder CPU -Pipeline Optimierung.

Nach Arbeit von Shmuel Winograd (1978),^[21] eine enge θ (N) Die untere Grenze ist für die Anzahl der realen Multiplikationen bekannt, die von einem FFT erforderlich sind. Es kann nur gezeigt werden, dass nur ${\ displayStyle 4n-2 \ log _ {2}^{2} (n) -2 \ log _ {2} (n) -4}$ Irrationale reale Multiplikationen sind erforderlich, um eine dft-zwei-Länge-Leistung zu berechnen ${\ displayStyle n = 2^{m}}$. Darüber hinaus sind explizite Algorithmen, die diese Anzahl erreichen, bekannt (Heideman & Burrus1986;^[25] Duhamel, 1990^[26]). Diese Algorithmen erfordern jedoch zu viele Ergänzungen, um zumindest auf modernen Computern mit Hardware -Multiplikatoren praktisch zu sein (Duhamel, 1990;^[26] Frigo & Johnson, 2005).^[17]

Eine enge untere Grenze ist nicht in der Anzahl der erforderlichen Ergänzungen bekannt, obwohl unter einigen restriktiven Annahmen an den Algorithmen untere Grenzen nachgewiesen wurden. 1973 Morgenstern^[27] bewies ein ω (NProtokollN) Untergrenze an der Additionszahl für Algorithmen, bei denen die multiplikativen Konstanten Größen begrenzt haben (was für die meisten, aber nicht alle FFT -Algorithmen zutrifft). Pfanne (1986)^[28] bewies ein ω (NProtokollN) Untergrenze unter der Annahme einer Grenze an einem Maß des FFT -Algorithmus "Asynchronizität" des FFT -Algorithmus, aber die Allgemeinheit dieser Annahme ist unklar. Für den Fall von zwei zwei Jahren N, Papadimitriou (1979)^[29] argumentierte, dass die Zahl ${\ displayStyle n \ log _ {2} n}$ von komplexen Zahlenergänzungen, die von Cooley-Tukey-Algorithmen erzielt werden, ist optimal unter bestimmten Annahmen über die Graph des Algorithmus (seine Annahmen implizieren unter anderem, dass keine additiven Identitäten in den Wurzeln der Einheit ausgenutzt werden). (Dieses Argument würde das zumindest bedeuten ${\ displayStyle 2n \ log _ {2} n}$ Es sind reale Ergänzungen erforderlich, obwohl dies keine enge gebundene Grenze ist, da im Rahmen komplexer Zahlenmultiplikationen zusätzliche Ergänzungen erforderlich sind.) Bisher hat kein veröffentlichter FFT-Algorithmus weniger erreicht als ${\ displayStyle n \ log _ {2} n}$ Komplexnummer Ergänzungen (oder ihr Äquivalent) für die zweite KraftN.

Ein drittes Problem besteht darin, die zu minimieren gesamt Anzahl der realen Multiplikationen und Ergänzungen, die manchmal als "arithmetische Komplexität" bezeichnet werden (obwohl es in diesem Zusammenhang die genaue Anzahl und nicht die asymptotische Komplexität ist, die berücksichtigt wird). Auch hier wurde keine enge Untergrenze nachgewiesen. Seit 1968 ist jedoch der niedrigste veröffentlichte Zähler für die zweifache Leistung N wurde lange durch die erreicht Split-Radix-FFT-Algorithmus, welches benötigt ${\ displayStyle 4n \ log _ {2} (n) -6n+8}$ echte Multiplikationen und Ergänzungen für N > 1. Dies wurde kürzlich auf reduziert auf ${\ displayStyle \ sim {\ frac {34} {9}} n \ log _ {2} n}$ (Johnson und Frigo, 2007;^[16] Lundy und Van Buskirk, 2007^[30]). Eine etwas größere Anzahl (aber immer noch besser als Split Radix für N Es wurde gezeigt, dass ≥ 256) nachweislich optimal ist für N ≤ 512 unter zusätzlichen Einschränkungen der möglichen Algorithmen (split-radix-ähnliche Durchflussgraphen mit multiplikativen Faktoren mit Einheitenmodulus) durch Reduktion zu a Befriedigungsmodulo -Theorien Problem lösbar durch rohe Gewalt (Haynal & Haynal, 2011).^[31]

Die meisten Versuche, die Komplexität von FFT-Algorithmen zu senken oder zu beweisen, haben sich auf den normalen Fall mit komplexen Daten konzentriert, da dies am einfachsten ist. Komplexen Daten fft sind jedoch so eng mit Algorithmen für verwandte Probleme wie Real-Data-FFTs verbunden. Diskrete Cosinus -Transformationen, Diskrete Hartley transformiertund so weiter, dass jede Verbesserung in einer davon sofort zu Verbesserungen in den anderen führen würde (Duhamel & Vetterli, 1990).^[32]

Annäherungen

Alle oben diskutierten FFT -Algorithmen berechnen die DFT genau (d. H. Vernachlässigung Schwimmpunkt Fehler). Es wurden jedoch einige "FFT" -Algorithmen vorgeschlagen, die die DFT berechnen etwamit einem Fehler, der auf Kosten erhöhter Berechnungen willkürlich gering gemacht werden kann. Solche Algorithmen handeln den Approximationsfehler gegen erhöhte Geschwindigkeit oder andere Eigenschaften. Zum Beispiel ein ungefährer FFT -Algorithmus von Edelman et al. (1999)^[33] Erreicht niedrigere Kommunikationsanforderungen für Parallele Computing mit Hilfe von a Schnelle Multipole -Methode. EIN Wavelet-Basierend ungefähre FFT von Guo und Burrus (1996)^[34] Berücksichtigt spärliche Eingänge/Ausgänge (Zeit-/Frequenzlokalisierung) effizienter als bei einem exakten FFT möglich. Ein weiterer Algorithmus zur ungefähren Berechnung einer Untergruppe der DFT -Ausgänge ist auf Shentov et al. (1995).^[35] Der Edelman-Algorithmus funktioniert gleich gut für spärliche und nicht-sparige Daten, da er eher auf der Kompressibilität (Rangmangel) der Fourier-Matrix selbst als auf der Kompressibilität (Sparsity) der Daten basiert. Umgekehrt, wenn die Daten spärlich sind - das heißt, wenn auch nur K aus N Fourier -Koeffizienten sind ungleich Null - dann kann die Komplexität auf O reduziert werden ((KProtokoll(N) Protokoll(N/K)), und es wurde gezeigt, dass dies zu praktischen Beschleunigungen im Vergleich zu einem gewöhnlichen FFT für führt N/K> 32 in einem großen-N Beispiel (N= 2²²) unter Verwendung eines probabilistischen ungefähren Algorithmus (der das größte schätzt K Koeffizienten an mehreren Dezimalstellen).^[36]

Genauigkeit

FFT-Algorithmen weisen Fehler auf, wenn die Schwimmpunktarithmetik für endliche Präzision verwendet wird, aber diese Fehler sind in der Regel recht klein. Die meisten FFT -Algorithmen, z. Cooley -tukey haben als Folge der hervorragenden numerischen Eigenschaften hervorragende Eigenschaften paarweise Summe Struktur der Algorithmen. Die Obergrenze auf der relativer Fehler Für den Cooley -Tukey -Algorithmus ist o (ε Protokoll N), im Vergleich zu O (εn^3/2) für die naive DFT -Formel,^[18] wobei ε die relative Präzision des Maschinenfloatspunkts ist. In der Tat die quadratischer Mittelwert (RMS) Fehler sind viel besser als diese Obergrenzen, nur O ((ε √Protokoll N) für Cooley -tukey und o (ε √N) für die naive DFT (Schatzman, 1996).^[37] Diese Ergebnisse sind jedoch sehr empfindlich für die Genauigkeit der im FFT verwendeten Twiddle -Faktoren (d. H. Die Trigonometrische Funktion Werte), und es ist nicht ungewöhnlich, dass unnachgiebige FFT -Implementierungen eine viel schlechtere Genauigkeit haben, z. Wenn sie ungenau verwenden Trigonometrisches Rezidiv Formeln. Einige andere FFTs als Cooley -Tukey, wie der Rader -Brenner -Algorithmus, sind anwesend weniger stabil.

Im Fixpunktarithmetik,√N) für den Cooley -Tukey -Algorithmus (Welch, 1969).^[38] Das Erreichen dieser Genauigkeit erfordert sorgfältige Aufmerksamkeit auf die Skalierung, um den Präzisionsverlust zu minimieren, und FFT-FFT-Algorithmen mit festen Punkten beinhalten in jeder Zwischenstufe von Zersetzungen wie Cooley-tukey.

Um die Richtigkeit einer FFT -Implementierung zu überprüfen, können strenge Garantien in O ((NProtokollN) Zeit nach einem einfachen Verfahren, das die Linearität, die Impulsantwort und die Zeitverschiebungseigenschaften der Transformation bei zufälligen Eingaben überprüft (Ergün, 1995).^[39]

Mehrdimensionale FFTs

Wie in der definiert Mehrdimensionaler DFT Artikel, der 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}}}$

verwandelt ein Array x_n mit einer d-Dimensional Vektor von Indizes ${\ displaystyle \ mathbf {n} = \ links (n_ {1}, \ ldots, n_ {d} \ rechts)}$ durch eine Reihe von d verschachtelte Summierungen (über ${\ displayStyle n_ {j} = 0 \ ldots n_ {j} -1}$ für jeden j), wo die Teilung n/N, definiert als $oder$, wird elementisch ausgeführt. Äquivalent ist es die Zusammensetzung einer Sequenz von d Sätze eindimensionaler DFTs, die entlang einer Dimension gleichzeitig (in beliebiger Reihenfolge) durchgeführt wurden.

Dieser sachdurchschnittliche Standpunkt bietet sofort den einfachsten und am häufigsten zu mehrdimensionalen DFT -Algorithmus, der als der bekannt ist Zeile Spalte Algorithmus (nach dem zweidimensionalen Fall unten). Das heißt, man führt einfach eine Sequenz von durch d Eindimensionale FFTs (nach einem der oben genannten Algorithmen): Zuerst verwandeln Sie sich entlang der n₁ Dimension, dann entlang der n₂ Dimension usw. (oder tatsächlich jede Bestellung funktioniert). Diese Methode kann leicht das übliche O haben (NProtokollN) Komplexität, wo ${\ displayStyle n = n_ {1} \ cdot n_ {2} \ cdot \ cdots \ cdot n_ {d}}$ Ist die Gesamtzahl der Datenpunkte transformiert. Insbesondere gibt es N/N₁ Transformationen der Größe N₁usw., also ist die Komplexität der Abfolge von FFTs:

$oder }}} O (n_ {d} \ log n_ {d}) \\ [6pt] = {} & o \ links (n \ links [\ log n_ {1} +\ cdots +\ log n_ {d} \ rechts ] \ right) = o (n \ log n). \ end {ausgerichtet}}}$

In zwei Dimensionen die x_k kann als als angesehen werden ${\ displayStyle n_ {1} \ times n_ {2}}$ Matrixund dieser Algorithmus entspricht der ersten Durchführung der FFT aller Zeilen (bzw. Spalten), wobei die resultierenden transformierten Zeilen (bzw. Säulen) als eine andere zusammengefasst werden ${\ displayStyle n_ {1} \ times n_ {2}}$ Matrix, und dann die FFT auf jeder der Spalten (bzw. Zeilen) dieser zweiten Matrix ausführen und die Ergebnisse in ähnlicher Weise in die Endergebnismatrix gruppieren.

In mehr als zwei Dimensionen ist es oft vorteilhaft für Zwischenspeicher Lokalität, um die Dimensionen rekursiv zu gruppieren. Zum Beispiel kann ein dreidimensionales FFT zuerst zweidimensionale FFTs jedes planaren "Slice" für jeden festgelegt durchführen n₁und dann die eindimensionalen FFTs entlang der durchführen n₁ Richtung. Allgemeiner ein Asymptotisch optimal cache-obliviös Der Algorithmus besteht darin, die Dimensionen rekursiv in zwei Gruppen zu unterteilen ${\ displayStyle (n_ {1}, \ ldots, n_ {d/2})}$ und ${\ displayStyle (n_ {d/2+1}, \ ldots, n_ {d})}$ das werden rekursiv transformiert (Rundung, wenn d ist nicht gerade) (siehe Frigo und Johnson, 2005).^[17] Dennoch bleibt dies eine einfache Variation des Zeilen-Säulen-Algorithmus, der letztendlich nur einen eindimensionalen FFT-Algorithmus als Basisfall erfordert und immer noch O ((O) hat ((((NProtokollN) Komplexität. Eine weitere Variation besteht darin, Matrix durchzuführen Transpositionen zwischen den transformierenden nachfolgenden Dimensionen, so dass die Transformationen mit zusammenhängenden Daten arbeiten; Dies ist besonders wichtig für Out-of-Core und Verteilter Speicher Situationen, in denen der Zugriff auf nicht zusammenhängende Daten extrem zeitaufwändig ist.

Es gibt andere mehrdimensionale FFT-Algorithmen, die sich vom Zeilen-Säulen-Algorithmus unterscheiden, obwohl alle O O (O () ((NProtokollN) Komplexität. Vielleicht ist das einfachste FFT ohne Reihen-Säule die Vektor-Radix-FFT-Algorithmus, was eine Verallgemeinerung des gewöhnlichen Cooley -Tukey -Algorithmus ist, bei dem man die Transformationsdimensionen durch einen Vektor teilt ${\ displaystyle \ mathbf {r} = \ links (r_ {1}, r_ {2}, \ ldots, r_ {d} \ rechts)}$ von Radices bei jedem Schritt. (Dies kann auch Cache-Vorteile haben.) Der einfachste Fall von Vector-Radix ist der Ort, an dem alle Radices gleich sind (z. B. Vektor-Radix-2-Divids alle der Dimensionen um zwei), aber dies ist nicht notwendig. Vektorradix mit nur einem einzelnen Unit-Radix gleichzeitig, d.h. ${\ displayStyle \ mathbf {r} = \ links (1, \ ldots, 1, r, 1, \ ldots, 1 \ rechts)}$ist im Wesentlichen ein Zeilen-Spal-Algorithmus. Andere, kompliziertere Methoden umfassen polynomiale Transformationsalgorithmen aufgrund von Nussbaumer (1977).^[40] die die Transformation in Bezug auf Konvolutionen und Polynomprodukte betrachten. Siehe Duhamel und Vetterli (1990)^[32] Weitere Informationen und Referenzen.

Andere Verallgemeinerungen

Ein o (N^5/2ProtokollN) Verallgemeinerung zu sphärische Harmonische auf der Sphäre S² mit N² Knoten wurden von Mohlenkamp beschrieben,^[41] zusammen mit einem Algorithmus vermutet (aber nicht bewährt), O (N² Protokoll²(N)) Komplexität; MoHlenkamp bietet auch eine Implementierung in der Bibliothek Libftsh.^[42] Ein kugelharmonischer Algorithmus mit O (N²ProtokollN) Die Komplexität wird von Rokhlin und Tygert beschrieben.^[43]

Das Schneller Faltalgorithmus ist analog zum FFT, außer dass es eher auf einer Reihe von Banned -Wellenformen als auf einer Reihe realer oder komplexer Skalarwerte arbeitet. Drehung (die in der FFT eine Multiplikation durch einen komplexen Phasor ist) ist eine kreisförmige Verschiebung der Komponentenwellenform.

Verschiedene Gruppen haben auch "FFT" -Algorithmen für nicht ausgeglichene Daten veröffentlicht, wie in Potts überprüft et al. (2001).^[44] Solche Algorithmen berechnen das DFT (das nur für gleichberechtigte Daten definiert ist), sondern eher einige Annäherungen davon (a ungleichmäßige diskrete Fourier-Transformation, oder ndft, das selbst oft nur ungefähr berechnet wird). Allgemeiner gibt es verschiedene andere Methoden von Spektralschätzung.

Anwendungen

Die FFT wird bei der digitalen Aufnahme, Abtastung verwendet, Additive Synthese und Tonhöhenkorrektur Software.^[45]

Die Bedeutung der FFT ergibt sich aus der Tatsache, dass sie in der Frequenzdomäne gleichermaßen rechnerisch wie in der zeitlichen oder räumlichen Domäne rechnerisch machbar gemacht hat. Einige der wichtigen Anwendungen des FFT sind:^[15][46]

• Schnelle Large- und Polynommultiplikation,
• effiziente Matrix -Vektor -Multiplikation für Toeplitz, Kreislauf und andere strukturierte Matrizen,
• Filteralgorithmen (siehe Überlappung - Add und Überlappung - Save Methoden),,
• Schnelle Algorithmen für Diskreter Cosinus oder Sinus transformiert (z.B. Schneller DCT benutzt für JPEG und MPEG/MP3 Codierung und Dekodierung),
• schnell Chebyshev -Annäherung,
• Lösung Differenzgleichungen,
• Berechnung von Isotopenverteilungen.^[47]
• Modulation und Demodulation komplexer Datensymbole unter Verwendung von orthogonaler Frequenzabteilung Multiplexing (OFDM) für 5G, LTE, Wi-Fi, DSL und andere moderne Kommunikationssysteme.

Forschungsgebiete

Große FFTs

Mit der Explosion von Big Data in Feldern wie Astronomie ist die Notwendigkeit von 512K -FFTs für bestimmte Interferometrieberechnungen entstanden. Die Daten, die von Projekten gesammelt wurden, z. WMAP und Ligo benötigen FFTs von zehn Milliarden Punkten. Da diese Größe nicht in das Hauptspeicher passt, sind so genannte FFTs außerhalb des Kerns ein aktives Forschungsbereich.^[48]

Ungefähre FFTs

Für Anwendungen wie MRT ist es erforderlich, DFTs für ungleichmäßig verteilte Netzpunkte und/oder Frequenzen zu berechnen. Multipolbasierte Ansätze können ungefähre Größen mit dem Anstieg der Laufzeit berechnen.^[49]

Gruppe FFTS

Die FFT kann auch mit Verwendung erklärt und interpretiert werden Gruppenrepräsentationstheorie eine weitere Verallgemeinerung ermöglichen. Eine Funktion in jeder kompakten Gruppe, einschließlich nicht-kyklischer, hat eine Ausdehnung in Bezug auf eine Grundlage irreduzibler Matrixelemente. Es bleibt ein aktives Forschungsbereich, um einen effizienten Algorithmus für die Durchführung dieser Basisänderung zu finden. Anwendungen einschließlich effizienter sphärische harmonische Expansion, analysieren bestimmter Markov Prozesse, Robotik usw.^[50]

Quantum FFTs

Shors schneller Algorithmus für Ganzzahlfaktorisierung Auf einem Quantencomputer verfügt über eine Unterroutine zur Berechnung der DFT eines binären Vektors. Dies wird als Sequenz von 1- oder 2-Bit-Quantengatern implementiert, die heute als Quanten-FFT bezeichnet werden. Dies ist effektiv die Cooley-Tukey-FFT, die als bestimmte Faktorisierung der Fourier-Matrix realisiert wird. Die Erweiterung dieser Ideen wird derzeit untersucht.^[51]

Sprach-Referenz

Siehe auch

FFT-bezogene Algorithmen:

• Goertzel -Algorithmus - Berechnet die individuellen Begriffe der diskreten Fourier -Transformation

FFT -Implementierungen:

• Alglib -Eine Doppel/GPL-lizenzierte C ++-und C# -Bibliothek (auch andere Sprachen unterstützt) mit realer/komplexer FFT-Implementierung
• Fftpack - Eine weitere Forran FFT -Bibliothek (gemeinfrei)
• Architekturspezifisch:
  • ARM -Performance -Bibliotheken^[52]
  • Intel Integrierte Leistungsprimitive
  • Intel Mathematikkernbibliothek
• Viele weitere Implementierungen sind verfügbar,^[53] Für CPUs und GPUs wie Pocketfft für C ++

Andere Links:

• Odlyzko -Schönhage -Algorithmus wendet die FFT auf endlich an Dirichlet -Serie
• Schönhage -Strassen -Algorithmus - Asymptotisch schneller Multiplikationsalgorithmus für große ganze Zahlen
• Schmetterlingsdiagramm - Ein Diagramm zur Beschreibung von FFTs
• Spektralmusik (beinhaltet die Anwendung der DFT -Analyse auf musikalische Zusammensetzung)
• Spektrumanalysator - eines von mehreren Geräten, die Spektrumanalysen durchführen, oft über ein DFT
• Zeitfolgen
• Schneller Walsh -Hadamard -Transformation
• Verallgemeinerter Verteilungsrecht
• Spektralanalyse am kleinsten Quadrat
• Mehrdimensionale Transformation
• Mehrdimensionale diskrete Faltung
• Schnelles Fourier -Transform -Teleskop

Verweise

Weitere Lektüre

• Brigham, E. Oran (2002). Die schnelle Fourier -Transformation. New York: Prentice-Hall.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Kapitel 30: Polynome und die FFT". Einführung in Algorithmen (2 ed.). 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, Haitao; Sitton, Gary A.; Burrus, Charles Sidney (1994). "Die schnelle diskrete Fourier -Transformation". Proceedings of ICASSP '94. IEEE Internationale Konferenz über Akustik, Sprach und Signalverarbeitung. Verfahren zur IEEE -Konferenz über Akustik, Sprache und Signalverarbeitung (ICASSP). Vol. 3. S. 445–448. doi:10.1109/ICASSP.1994.389994. ISBN 978-0-7803-1775-8. S2CID 42639206.
• Johnson, Steven G.; Frigo, Matteo (2007). "Ein modifizierter 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.
• Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). "Kapitel 12. Fast Fourier Transform". Numerische Rezepte: Die Kunst des wissenschaftlichen Computers (3 ed.). 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 bei Fast Fourier Transformation. IEEE -Transaktionen auf Audio und Elektroakustik. Vol. AU-17. IEEE Audio und Electroacustics Group. S. 166–169. doi:10.1109/tau.1969.1162029. (NB. Enthält umfangreiche Bibliographie.)
• Elena Prestini: "Die Entwicklung der angewandten harmonischen Analyse", Springer, ISBN 978-0-8176-4125-2 (2004), Sec.3.10 'Gauß und die Asteroiden: Geschichte des FFT'.

Externe Links

• Schnelle Fourier -Transformation für die Polynommultiplikation- Schneller Fourier -Algorithmus
• Fast Fourier transformiert, Verbindung Online -Buch bearbeitet 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",", Klang und Vibration (Ausgabe von Januar 1997, 30. Jahrestag) - Eine historische Überprüfung der Hardware -FFT -Geräte
• Alglib FFT -Code-Eine numerische Analyse- und Datenverarbeitungsbibliothek mit Dual/GPL-lizenziert (VBA, C ++, Pascal usw.) und Datenverarbeitungsbibliothek
• SFFT: Sparse Fast Fourier -Transformation-MITs spärlicher (sublinearer Zeit) FFT-Algorithmus, SFFT und Implementierung
• VB6 FFT- Eine VB6 -optimierte Bibliotheksimplementierung mit Quellcode
• Interaktives FFT -Tutorial- Ein visuelles interaktives Intro zu Fourier -Transformationen und FFT -Methoden