Neuer Algorithmus: Schneller als die schnelle Fourier-Transformation
Die Fourier-Transformation gehört zu den wichtigsten Konzepten der Informatik. Die Methode ermöglicht es, " kontinuierliche, aperiodische Signale in ein kontinuierliches Spektrum zu zerlegen(öffnet im neuen Fenster) " . Die Methode wird in der Signalverarbeitung universell eingesetzt, aber auch bei der Kompression von Bildern und Audiodateien verwendet.
Heute wird meist die schnelle Fourier-Transformation (Fast Fourier Transform, FFT) verwendet, ein Mitte der 1960er Jahre entwickelter Algorithmus, mit dem sich Fourier-Transformationen "on-the-fly" berechnen lassen.
Forscher am MIT haben nun einen Algorithmus vorgestellt, der in vielen Fällen besser funktionieren soll als FFT. Unter bestimmten Umständen soll der neue Algorithmus zehnmal schneller sein als FFT. Er soll vor allem zur Bildkompression nützlich sein. Das bedeutet im Umkehrschluss auch, die Leistungsaufnahme von Systemen lässt sich reduzieren. Das ist relevant beispielsweise für Smartphones, die große Videos komprimieren sollen.
Der neue Algorithmus kann wie FFT zur Verarbeitung digitaler Signale eingesetzt werden. Dabei haben einige Frequenzen eine höhere Bedeutung als andere und manche haben eine so geringe Bedeutung, dass sie getrost vernachlässigt werden können. Deshalb ist die Methode so praktisch zur Kompression von Bildern: Ein Block von 8 x 8 Pixeln kann als Signal mit 64 Segmenten betrachtet werden. Den MIT-Forschern zufolge haben aber empirische Studien gezeigt, dass im Schnitt 57 dieser 64 Frequenzen weggelassen werden können, ohne dass sich die Bildqualität nennenswert verschlechtert.
Fourier-Transformationen mit so wenigen Werten bezeichnet man als "sparse" (spärlich). Der neue Algorithmus ermittelt nun die Bedeutung der wichtigsten Frequenzen in einem Signal. Dabei gilt, je spärlicher das Signal, desto größer fällt die Beschleunigung aus. Und das treffe auf die meisten natürlichen Signale zu, sagte Dina Katabi, die den Algorithmus zusammen mit Piotr Indyk und den beiden Studenten Eric Price und Haitham Hassanieh entwickelt hat.
Einige Details zum neuen Algorithmus sind einer Pressemitteilung(öffnet im neuen Fenster) des MIT zu entnehmen, der eigentliche Aufsatz " Nearly Optimal Sparse Fourier Transform(öffnet im neuen Fenster) " mit den Details wurde noch nicht veröffentlicht.