Die erste Schwierigkeit besteht darin, dass das aufgezeichnete Signal keine kontinuierliche Kurve ist, sondern aus diskreten Datenpunkten besteht. Je größer der Abstand zwischen den Datenpunkten ist, desto weniger sicher ist, dass die hochfrequenten Signale Teil der Kurve sind. Ein weiteres Problem ist, dass die Aufzeichnung nicht unendlich lang ist, sondern meist nur für einen kurzen Zeitraum stattfindet. Daher kann nicht beurteilt werden, welche der beiden benachbarten Frequenzen tatsächlich im Signal enthalten ist – das Frequenzspektrum wird dadurch unscharf. Die niedrigste Frequenz fwenigstensdie im Wesentlichen gelöst werden kann, ist diejenige, deren Periode lang ist L des gesamten Signals. Die dieser Frequenz entsprechenden Kurven sind gegeben durch sin(2πx/L) und cos(2πx/L) gegeben. Wenn Sie jetzt N Wenn Sie äquidistante Datenpunkte untersuchen möchten, beginnen Sie mit den niedrigsten Frequenzkurven und arbeiten Sie sich bis zu ganzzahligen Vielfachen vor n Häufigkeit vorher: n·fwenigstens. Dies entspricht den Funktionen sin(2 2πx/L), sin(3 2πx/L), sin(4 2πx/L), …, Sünde (N·2πx/L) (Dasselbe natürlich für Cosinus). Es macht keinen Sinn, höhere Frequenzen als zu verwenden N·fwenigstens muss untersucht werden, da die Periode der zugehörigen Funktionen kürzer ist als der Abstand zwischen benachbarten Datenpunkten. Alles, was darüber hinausgeht, übersteigt unsere Fähigkeit, es zu lösen.
© Spektrum der Wissenschaft; Manon Bischoff (Ausschnitt)
Datenpunkte | Die Länge der Aufzeichnung und der Abstand der Datenpunkte begrenzen den Bereich der zu untersuchenden Frequenzen. Orange zeigt die Sinuswelle mit der höchsten Frequenz, Rot die niedrigste.
Um also eine Fourier-Analyse mit diskreten Messungen durchzuführen, multiplizieren Sie alles N Datenpunkte N verschiedene Sinus- und Kosinusfunktionen und bestimmt daraus die von der x-Achse eingeschlossene Fläche. Ein Computer ist also ein Muss N2 Rechenschritte durchführen. Das führt bei großen Datenmengen zu Problemen: Während ein Signal, das aus acht Datenpunkten besteht, augenblicklich in Komponenten zerlegt werden kann, ist es bei einer Million Datenpunkten schwieriger, weil es 10 braucht12 notwendigen Rechenoperationen. Ein moderner Rechner mit 3,5 Gigahertz würde bei Volllast etwa fünf Minuten brauchen. Für Computer in den 1960er Jahren war diese Aufgabe unüberwindbar. Wenn Sie 100-mal mehr Datenpunkte analysieren wollen, erhöht sich die Anzahl der Rechenschritte um das 10.000-fache – auch unsere Rechner wären hoffnungslos überlastet.
Hier kommen Tukey Doodles ins Spiel. Er hatte damals die Idee formuliert, wie die Fourier-Transformation schneller angewendet werden könnte. Über N2 Die Berechnungsschritte sind nur mit seiner Methode möglich N·Protokoll2N. Dies klingt zwar nach einer kleinen Verbesserung, die Einsparungen sind jedoch enorm, wenn viele Datenpunkte vorhanden sind. ab 1012 Die Schritte zur Berechnung einer Million Datenpunkte betragen nur 20.106 übrig bleiben. Auf einem 3,5-Gigahertz-Rechner würde das nur wenige Millisekunden dauern. Der Mathematiker nannte seinen Algorithmus kreativ „Fast Fourier Transform“. Es gilt heute als einer der wichtigsten Programmiercodes der Welt.
Als der Physiker Richard Garwin erkannte, was Tukey auf seinen Blättern berechnet hatte, wollte er wissen, wann Tukey es veröffentlichen würde. Garwin war sich des Potenzials der Methode sofort bewusst. Tukey sagte, er arbeite mit einem Informatiker an der Implementierung, aber es würde wahrscheinlich noch ein paar Jahre dauern. Zu dieser Zeit hatten Computer wenig Speicher, daher war es schwierig, den Algorithmus auf solchen Maschinen zu implementieren. Garwin schien dies jedoch eine lange Zeit zu sein, also schlug er vor, selbst einen Informatiker zu finden, der das Problem schneller lösen könnte.
Also kontaktierte er den Informatiker Jim Cooley. „Garwin sagte mir, dass er ein wichtiges Problem im Zusammenhang mit der Periodizität des Helium-3-3-D-Kristalls hatte. Erst später erfuhr ich, dass er die seismische Fernerkundung verbessern wollte, um das Verbot von Atomwaffentests zu erleichtern“, schrieb Cooley 1987. „Zu diesem Zeitpunkt hatte ich bereits die Helium-3-Experimente durchgeführt und die Fourier-Transformation gemeistert“, gab Garwin zu. Zunächst widmete Cooley dem neuen Forschungsprojekt nicht allzu viel Aufmerksamkeit und konzentrierte sich auf seine eigene Arbeit. Aber Garwins Beharrlichkeit, ihn und seinen Manager anzurufen und nach Fortschritten zu fragen, bedeutete, dass Cooley dem Projekt Priorität einräumte. Trotzdem brauchten Cooley und Tukey ein paar Monate, um den Algorithmus 1965 zu veröffentlichen – zwei Jahre nachdem die Sowjetunion und die Vereinigten Staaten vereinbart hatten, von allen außer unterirdischen Atomtests Abstand zu nehmen.
Teile und herrsche!
Die Fast-Fourier-Transformation basiert auf einem langjährigen Prinzip: Teile und herrsche. Die Sinus- und Kosinusfunktionen haben viele Symmetrien, die durch geschicktes Teilen der Datenpunkte ausgenutzt werden können. Angenommen, acht Datenpunkte sind auf der x-Achse gleichmäßig verteilt mit den Koordinaten 0, 1, 2, …, 7. Alle möglichen Kosinusfunktionen werden für sie aufgetragen (eine ähnliche Beziehung besteht für Sinusfunktionen): cos(0 2πx/8) = 1, cos(2πx/8), cos(4πx/8), …, cos(14πx/8.). Bestimmte Muster lassen sich unterscheiden. Am mittleren Datenpunkt x = 4, zum Beispiel haben alle Funktionen mit gerader Frequenz denselben Wert: cos(0 2π 4/8) = 1, cos(2π) = 1, cos(4π) = 1, cos(6π) = 1. Gerade ungerade Frequenzen ergeben dasselbe Ergebnis: cos(π) = −1, cos(3π) = −1, cos(5π) = −1, cos(7π) = −1. Anstatt also den durchschnittlichen Datenpunkt mit acht Funktionen zu multiplizieren, müssen Sie nur zwei Produkte nehmen. Ähnliche Beziehungen ergeben sich aus anderen Datenpunkten. Auf diese Weise können die ursprünglich geplanten 8*8=64 Berechnungsschritte auf 8*log reduziert werden28 = 24 zum Dampfen.
