Neuer Algorithmus: Schneller als die schnelle Fourier-Transformation

Forscher am MIT haben einen Algorithmus für Fourier-Transformationen entwickelt, der in vielen Fällen deutlich schneller sein soll als die schnelle Fourier-Transformation. Das könnte Kompressionsalgorithmen zehnmal schneller machen.

Artikel veröffentlicht am ,
Fourier-Transformation
Fourier-Transformation (Bild: Christine Daniloff/MIT)

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". Die Methode wird in der Signalverarbeitung universell eingesetzt, aber auch bei der Kompression von Bildern und Audiodateien verwendet.

Stellenmarkt
  1. SAP Projektleiter (m/w/d) in der Operative IT/AMS
    Dürr IT Service GmbH, Bietigheim-Bissingen
  2. IT - Initiativbewerbung
    Universitätsklinikum Frankfurt, Frankfurt am Main
Detailsuche

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.

Golem Karrierewelt
  1. Container Technologie: Docker und Kubernetes - Theorie und Praxis: virtueller Drei-Tage-Workshop
    14.-16.12.2022, virtuell
  2. AZ-104 Microsoft Azure Administrator: virtueller Vier-Tage-Workshop
    19.-22.12.2022, virtuell
Weitere IT-Trainings

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 des MIT zu entnehmen, der eigentliche Aufsatz "Nearly Optimal Sparse Fourier Transform" mit den Details wurde noch nicht veröffentlicht.

Bitte aktivieren Sie Javascript.
Oder nutzen Sie das Golem-pur-Angebot
und lesen Golem.de
  • ohne Werbung
  • mit ausgeschaltetem Javascript
  • mit RSS-Volltext-Feed


Lala Satalin... 24. Jan 2012

Sollte nur eine Info über die Bitratenverteilung geben und die Gesamtdateigröße, etc...

WhyLee 24. Jan 2012

Richtig und dazu muß man sagen, daß ein neuer Algorithmus den Vorteil haben kann, da...

WhyLee 24. Jan 2012

Du hast hier vermutlich die Definition von Echtzeit in der Informatik nicht ganz im Blut...

LadyDie 24. Jan 2012

Gemeint war die Ladungsdichte. Mit Streuversuchen (also im Wesentlichen Elektronen mit...



Aktuell auf der Startseite von Golem.de
Tesla-Fabrik
In Grünheide soll "totales Chaos" herrschen

Die Tesla-Fabrik in Grünheide hinkt ihren Produktionszielen noch weit hinterher. Es gibt zu wenig Personal oder die Mitarbeiter kündigen wieder.

Tesla-Fabrik: In Grünheide soll totales Chaos herrschen
Artikel
  1. Elbit Systems Deutschland: Neue Bundeswehr-Funkgeräte lösen Retrogeräte von 1982 ab
    Elbit Systems Deutschland
    Neue Bundeswehr-Funkgeräte lösen Retrogeräte von 1982 ab

    Vor rund einem Jahr hat das Beschaffungsamt der Bundeswehr für 600 Millionen Euro Tausende Funkgeräte aus dem Jahr 1982 nachbauen lassen. Nun werden ganz neue angeschafft.

  2. Europäischer Rat: Einigung über Bargeldobergrenze von 10.000 Euro
    Europäischer Rat
    Einigung über Bargeldobergrenze von 10.000 Euro

    Der Europäische Rat hat sich auf eine Bargeldobergrenze von 10.000 Euro verständigt. Auch Kryptowährungen sollen streng reguliert werden.

  3. Angespielt: Diablo 4 wird brutal, makaber und ein bisschen eklig
    Angespielt
    Diablo 4 wird brutal, makaber und ein bisschen eklig

    Open-World-Freiheiten, dynamische Events und eine geteilte Spielwelt: Golem.de hat Diablo 4 angespielt und mit den Entwicklern gesprochen.
    Von Olaf Bleich

Du willst dich mit Golem.de beruflich verändern oder weiterbilden?
Zum Stellenmarkt
Zur Akademie
Zum Coaching
  • Schnäppchen, Rabatte und Top-Angebote
    Die besten Deals des Tages
    Daily Deals • PS5 bei Amazon bestellbar • Tiefstpreise: Asus RTX 4080 1.689,90€, MSI 28" 4K 579€, Roccat Kone Pro 39,99€, Asus RTX 6950 XT 939€ • Alternate: Acer Gaming-Monitor 27" 159,90€, Razer BlackWidow V2 Mini 129,90€ • 20% Extra-Rabatt bei ebay • Amazon Last Minute Angebote [Werbung]
    •  /