Neuer Algorithmus Schnellere Fourier-Transformation

Fourier Transformation
Fourier Transformation

Wissenschaftler vom MIT (Massachusetts Institute of Technology) haben einen neuen Algorithmus entwickelt, mit dem sich die Fourier-Transformation schneller bewerkstelligen lässt. Damit könnten zum Beispiel Videodateien stärker als bisher komprimiert weiter.

Die Fourier-Transformation ist eine der Grundlagen für die Informationstechnik. Mit ihr können komplexe Signale als eine Kombination von sinusförmigen Einzelsignalen zerlegt werden. Umgekehrt wird sie auch benutzt, um Bild- und Tonsignale zu komprimieren, Differentialgleichungen zu lösen oder Börsentrends zu analysieren.

Ein großer Schritt nach vorn war die Entwicklung eines Algorithmus mit dem Namen „Fast Fourier Transformation“ (FFT) Mitte der 60er Jahre, mit der solche Analysen mit großer Geschwindigkeit vollzogen werden konnten. Seither suchte man nach Möglichkeiten, dies noch weiter zu beschleunigen – Schnelligkeit kann z.B. an der Börse große Gewinne versprechen.

Eine Gruppe von Forschern am MIT haben jetzt einen Weg gefunden, unter bestimmten Umständen sogar eine zehnfache Beschleunigung möglich zu machen. Als erstes könnten in der Elektronik davon Smartphones profitieren: Große Videofiles ließen sich so weit komprimieren, dass die Übertragung schneller abläuft und damit die Batterie weniger belastet oder auch das monatliche Abonnement auf bestimmte Übertragungsmengen schont.

Auch der neu entwickelte Algorithmus arbeitet mit digitalen Signalen. Diese sind ja „Proben“ aus dem ursprünglich analogen Signal. In einem ersten Schritt werden aus der Vielzahl der überlagerten Signale nur die Wichtigen herausgefiltert. In einem zweiten Schritt entnehmen die MIT-Forscher nur eine bestimmte Menge dieser Signale (d.h. nicht alle umgewandelten Proben) und interpretieren diese als „gewichtete Summe“ einer entsprechenden Zahl von überlagerten Frequenzen. Das lässt sich vertreten, weil viele der digitalen Proben keine besonders große Gewichtung haben. Die Wissenschaftler haben nämlich herausgefunden, dass von 64 entnommenen Proben (ein Block von 8x8 Punkten) 57 Proben vernachlässigt werden können, ohne dass es zu einem spürbaren Verlust in der Bild- oder Tonqualität kommt.