Fast-Fourier-Transformation: Ein Algorithmus für den Weltfrieden

Die erste Schwierigkeit besteht darin, dass ein aufgezeichnetes Signal keine kontinuierliche Kurve ist, sondern aus diskreten Datenpunkten besteht. Je größer der Abstand zwischen den Datenpunkten ist, desto weniger sicher ist, dass hochfrequente Signale Teil der Kurve sind. Das zweite Problem ist, dass die Aufnahme nicht sehr lang ist, sondern meist nur kurzzeitig stattfindet. Dadurch kann nicht überprüft werden, welche von zwei nahe beieinander liegenden Frequenzen tatsächlich im Signal vorhanden sind – das Frequenzspektrum wird dadurch unscharf. Die niedrigste Frequenz fwenigstensdie sinnvoll gelöst werden kann, ist eine, deren Zeit lang ist L während des gesamten Signals. Die dieser Frequenz entsprechenden Kurven sind gegeben durch sin(2πx/L) und cos(2πx/L) gegeben ist. Wenn Sie jetzt sind N Wenn Sie Datenpunkte mit gleichem Abstand untersuchen möchten, beginnen Sie mit den niedrigsten Frequenzkurven und arbeiten Sie sich bis zu ganzzahligen Vielfachen vor n die frequenz 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 ist nicht sinnvoll, eine höhere Frequenz als zu verwenden N·fwenigstens auszuwerten, da die Periode der zugehörigen Funktionen kleiner ist als der Abstand benachbarter Datenpunkte. Alles darüber hinaus liegt außerhalb unserer Macht, es zu lösen.

© Spektrum der Wissenschaft; Manon Bischoff (Ausschnitt)

Datenpunkte | Die Länge der Aufzeichnung und der Abstand der Datenpunkte begrenzen den Frequenzbereich, der analysiert werden kann. Orange zeigt die Sinuswelle mit der höchsten Frequenz, Rot zeigt die niedrigste.

Um eine Fourier-Analyse mit diskreten Messungen durchzuführen, multiplizieren Sie daher jede von N Datenpunkte mit N verschiedene Sinus- und Cosinusfunktionen und bestimmen damit die von der x-Achse eingeschlossene Fläche. Es wird also ein Computer benötigt N2 Berechnungsschritte durchführen. Das stellt bei großen Datenmengen ein Problem dar: Während ein aus acht Datenpunkten bestehendes Signal im Handumdrehen in seine Bestandteile zerlegt werden kann, ist es bei einer Million Datenpunkten deutlich schwieriger, denn dafür werden 10 benötigt.12 erforderlichen Berechnungsschritte. Ein moderner Rechner mit 3,5 Gigahertz braucht unter Volllast etwa fünf Minuten. Für Computer in den 1960er Jahren war diese Aufgabe unüberwindbar. Will man 100-mal mehr Datenpunkte analysieren, erhöht sich die Zahl der Berechnungsschritte um den Faktor 10.000 – auch unsere Rechner können überfordert sein.

Auch Lesen :  Polio: New York kämpft gegen Rückkehr der Kinderlähmung | Wissenschaft

Hier kommen Tukeys Kritzeleien ins Spiel. Während dieser Zeit hatte er eine Idee, wie man die Fourier-Transformation einfacher implementieren könnte. Ausser für N2 Die Berechnungsschritte können nur nach seiner Methode durchgeführt werden N· Protokolle2N. Auch wenn dies wie eine kleine Verbesserung erscheinen mag, sind die Einsparungen erheblich, wenn mehr Datenpunkte vorhanden sind. ab 1012 Die Berechnungsschritte für eine Million Datenpunkte bleiben nur 20·106 links. Ein 3,5-Gigahertz-Rechner benötigt dafür nur wenige Millisekunden. Der Mathematiker nannte seinen Algorithmus kreativ „Fast Fourier Transform“. Es gilt heute als einer der wichtigsten Programmiercodes der Welt.

Auch Lesen :  Deutschland bei Patenten von Frauen bei den Schlusslichtern | Freie Presse

Als der Physiker Richard Garwin erkannte, was Tukey in seinen Zetteln berechnet hatte, wollte er wissen, wann Tukey sie veröffentlichen würde. Garwin erkannte sofort das Potenzial der Methode. Tukey entgegnete, er arbeite mit einem Informatiker an der Umsetzung, das werde aber wohl noch ein paar Jahre dauern. Damals hatten Computer sehr wenig Speicher, was es schwierig machte, den Algorithmus auf solchen Maschinen zu implementieren. Garwin scheint dies jedoch zu lange zu dauern, weshalb er vorschlägt, sich einen Informatiker zu suchen, der das Problem schneller lösen kann.

Also kontaktierte er den Informatiker Jim Cooley. „Garwin sagte mir, dass er ein wichtiges Problem im Zusammenhang mit den Periodizitäten eines 3-D-Helium-3-Kristalls hatte. Erst später erfuhr ich, dass er eine Fernüberwachung der seismischen Daten entwickeln wollte, um das Verbot von Atomwaffentests zu erleichtern. ” Cooley schrieb 1987. .” , gab Garwin zu. Zunächst widmete Cooley dem neuen Forschungsprojekt wenig Aufmerksamkeit und konzentrierte sich auf seine eigene Arbeit. Garwins wiederholte Anrufe bei ihm und seinem Manager, um sich nach Fortschritten zu erkundigen, bedeuteten jedoch, dass Cooley dem Projekt eine hohe Priorität einräumte. Es dauerte jedoch mehrere Monate, bis Cooley und Tukey den Algorithmus 1965 veröffentlichten – zwei Jahre nachdem die Sowjetunion und die USA vereinbart hatten, auf alle außer unterirdischen Atomtests zu verzichten.

Auch Lesen :  Krieg gegen die Ukraine: So ist die Lage | Freie Presse

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 feines Splitten der Datenpunkte ausgenutzt werden können. Angenommen, acht Datenpunkte sind auf der x-Achse gleich beabstandet mit den Koordinaten 0, 1, 2, …, 7. Dazu werden alle möglichen Kosinusfunktionen genommen (eine ähnliche, die die Beziehung für Sinusfunktionen ergibt): cos(0 2πx/8) = 1, cos(2πx/8), cos(4πx/8), …, cos(14πx/ 8.). Einige Muster lassen sich erkennen. Am Mittelpunkt der Daten x = 4 haben beispielsweise alle Funktionen mit derselben 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 Mittelpunkt der Daten mit den acht Funktionen zu multiplizieren, müssen Sie die beiden Produkte nehmen. Ähnliche Beziehungen ergeben sich aus anderen Datenpunkten. So können die ursprünglich geplanten 8 * 8 = 64 Rechenschritte auf 8 * log reduziert werden28 = 24 wird verdampfen.

Source

Leave a Reply

Your email address will not be published.

In Verbindung stehende Artikel

Back to top button