Anzeige
Fourier-Transformation
Fourier-Transformation (Bild: Christine Daniloff/MIT)

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.

Anzeige

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.

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


eye home zur Startseite
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...

Der Kaiser! 23. Jan 2012

Kommentieren



Anzeige

  1. IT-Service Designer/in
    Landesbetrieb IT.Niedersachsen, Hannover
  2. Trainee (m/w) IT-Anwendungen
    Süwag Energie AG, Frankfurt am Main
  3. Mitarbeiter/in im Bereich IT Helpdesk für den 1st-Level-Support
    Bosch Communication Center Magdeburg GmbH, Berlin
  4. Datenbankentwickler/in webbasierte Diagnosesysteme
    Robert Bosch GmbH, Plochingen

Detailsuche



Anzeige

Folgen Sie uns
       


  1. Soylent-Flüssignahrung

    Die Freiheit, nicht ans Essen zu denken

  2. Fraunhofer IPMS

    Multispektralkamera benötigt nur ein Objektiv

  3. Transformer 3 (Pro)

    Asus zeigt Detachables mit Kaby Lake

  4. Delock DL-89456

    Netzwerkkarte für 2.5 und 5GbE

  5. Bezahlsystem

    Apple will Pay zügig in Europa ausweiten

  6. Überwachung

    Aufregung um Intermediate-Zertifikat für Bluecoat

  7. Virtual Reality

    Googles Daydream benötigt neues Smartphone

  8. Cortex-A73 Artemis

    ARMs neuer High-End-CPU-Kern für 2017

  9. Tony Fadell

    iPod-Erfinder baut Elektro-Gokarts für Kinder

  10. Riesiges Produktionsgebäude

    Ende Juli wird die Tesla Gigafactory eröffnet



Haben wir etwas übersehen?

E-Mail an news@golem.de


Anzeige
Oracle vs. Google: Wie man Geschworene am besten verwirrt
Oracle vs. Google
Wie man Geschworene am besten verwirrt
  1. Die Woche im Video Die Schoko-Burger-Woche bei Golem.de - mmhhhh!
  2. Java-Rechtsstreit Oracle verliert gegen Google
  3. Oracle vs. Google Wie viel Fair Use steckt in 11.000 Codezeilen?

GPD XD im Test: Zwischen Nintendo 3DS und PS Vita ist noch Platz
GPD XD im Test
Zwischen Nintendo 3DS und PS Vita ist noch Platz
  1. Xbox Scorpio Schneller als Playstation Neo und mit Rift-Unterstützung
  2. Playstation 4 Rennstart für Gran Turismo Sport im November 2016
  3. AMD Drei Konsolen-Chips für 2017 angekündigt

Intels Compute Stick im Test: Der mit dem Lüfter streamt (2)
Intels Compute Stick im Test
Der mit dem Lüfter streamt (2)
  1. Stratix 10 MX Alteras Chips nutzen HBM2 und Intels Interposer-Technik
  2. Apple Store Apple darf keine Geschäfte in Indien eröffnen
  3. HBM2 eSilicon zeigt 14LPP-Design mit High Bandwidth Memory

  1. Was macht der Magen in der freien Zeit

    Dwalinn | 12:31

  2. Re: Der Schwenk auf x86...

    david_rieger | 12:30

  3. Re: Schlafen und aufs Klo gehen ist auch nervig

    Bouncy | 12:30

  4. Werde doch erst einmal erwachsen und teste dann...

    Duke83 | 12:29

  5. Re: Kann mal jemand Herrn Maas aufklären?

    AllDayPiano | 12:29


  1. 12:02

  2. 11:39

  3. 11:28

  4. 11:10

  5. 10:31

  6. 10:27

  7. 08:45

  8. 08:15


  1. Themen
  2. A
  3. B
  4. C
  5. D
  6. E
  7. F
  8. G
  9. H
  10. I
  11. J
  12. K
  13. L
  14. M
  15. N
  16. O
  17. P
  18. Q
  19. R
  20. S
  21. T
  22. U
  23. V
  24. W
  25. X
  26. Y
  27. Z
  28. #
 
    •  / 
    Zum Artikel