Kommentar
Herzlichen Glückwunsch FFT!
Im Jahr 1965 nachten James W. Cooley und John W. Tukey die Welt mit dem FFT-Algorithmus bekannt. Danach war sie eine andere – denn plötzlich konnten Computer Berechnungen durchführen, die bis dahin weit jenseits ihrer Möglichkeiten lagen.
Vor 60 Jahren erschien der berühmte Artikel »An Algorithm for the Machine Calculation of Complex Fourier Series«. Heute kennen wir den Algorithmus, den Cooley und Tukey entwickelt haben, unter dem Namen Fast Fourier Transformation, kurz FFT.
Die FFT ist allgegenwärtig. Ob es darum geht, Bilder zu komprimieren und übers Internet zu versenden, ob es um bildgebende Verfahren in der Medizintechnik oder zur Qualitätsüberwachung in der Produktionstechnik oder um Künstliche Intelligenz geht, nichts könnte ohne die FFT funktionieren. Auch der Siegeszug der Mobilkommunikation – von Smartphones bis 5G – wäre ohne die FFT nicht denkbar. Denn die FFT war schon vor 60 Jahren um den Faktor 100 schneller als die bis dahin bekannte Diskrete Fourier-Transform: Denn die FFT erforderte weniger Rechenschritte, und der benötigte Speicherplatz war deutlich kleiner.
Entwickelt wurde die FFT ursprünglich zu einem anderen Zweck: Es sollten Atombombentests aufgespürt werden, die die Sowjetunion durchführte. Seismometer messen die Erschütterungen über weite Entfernungen hinweg. Auf Basis der Fouriertransformation kann man auf den Ort und die Stärke der Explosion schließen – sofern die Berechnungen schnell genug durchgeführt werden können. Bis zum Durchbruch von Cooley und Tukey war das aber unmöglich, die Computer waren dafür nicht leistungsfähig genug. Doch danach klappte es wunderbar. Und es zeigte sich, dass die FFT geradezu ein Wundermittel für viele andere Anwendungsfelder war, die oben bereits angesprochen wurden.
Deshalb sehen viele diesen Algorithmus als den wichtigsten Algorithmus unserer Zeit an. Interessant ist, dass Cooley und Tukey keine neue mathematische Theorie entwickelt haben – diese Ehre kommt Fourier zu –, sondern einen neuen algorithmischen Zugang. Das ist ein mindestens gleichwertiges Verdienst, der FFT ist es zu verdanken, grundlegenden theoretischen Einsichten in der Praxis zum Durchbruch zu verhelfen. »Der eigentliche Fortschritt in der Mathematik besteht in neuen Notationen«, sagte kein Geringerer als der britische Mathematiker und Philosoph Alfred N. Whitehead. Die FFT ist ein wunderbares Beispiel dafür.
Das Allerschönste daran: Die FFT ist kein abgeschlossenes Kapitel der Technikgeschichte, sie wird permanent weiterentwickelt. So spielt sie eine entscheidende Rolle in der neuen Welt der Quantencomputer: Sie bildet in den Algorithmen von Peter Shor (Faktorisierung großer Zahlen) und Lov Kumar Grover (Durchsuchen großer Datenmengen) ein wesentliches Element. Herzlichen Glückwunsch zum Geburtstag FFT, mit 60 Jahren stehst Du erst ganz am Anfang Deines Lebens!
Lesen Sie mehr zum Thema
