Die FFT (Fast Fourier Transform) revolutionierte die digitale Signalverarbeitung und ist sicher eine der wichtigsten Algorithmen des 20. Jahrhunderts. Sie ermöglichte neben dem Messen die effektive Kompression von Signalen und ist daher enorm wichtig für die Verarbeitung von Audio- und Video-Signalen.

 

Schon seit ihrer Entwicklung in den 1960er-Jahren wurde nach besseren Algorithmen gesucht. Letztes Jahr gelang genau das den beiden Forschern Piotr Indyk und Dina Katabi vom MIT. Ihr Algorithmus ist in einigen Fällen mehrere hundert Mal schneller als die FFT. Jetzt aber hat Now Indyk von der Theory of Computation Group des CSAIL (Computer Science and Artificial Intelligence Laboratory) mit seinem Team die Sache auf die Spitze getrieben, indem dazu nur eine minimale Anzal an Samples des Signals notwendig ist.

 

In einem Beitrag zum ACM-SIAM Symposium on Discrete Algorithms demonstrierten Indyk, Michael Kapralov und Eric Price einen Algorithmus, der mit so wenig Samples auskommt, dass man damit der theoretischen Grenze nahe kommt. Dadurch können die Verarbeitungszeiten von Geräten wie Magnetresonanztomografen etc. deutlich verkürzt und unter Umständen sogar die Auflösung gesteigert werden. Weiter würde durch die geringere Anzahl nötiger Samples auch die Aufenthaltsdauer von Patienten sinken, was gleichzeitig Ängste minimiert und die Auslastung dieser teuren medizinischen Diagnoseapparate verbessert.
Auch bei Radioteleskopen wären Optimierungen denkbar, denn man könnte selbst mit weniger Teleskopen Aufnahmen in besserer Qualität generieren. Auch bei Mobilgeräten würde sich durch einen geringeren Rechenaufwand die Akkulaufzeit leicht steigern.

 
Bild: Nach Christine Daniloff, MIT