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

Neuer Algorithmus: Schneller als die schnelle Fourier-Transformation

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

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.

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.

Anzeige

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



Anzeige

Stellenmarkt
  1. Aarsleff Rohrsanierung GmbH, Röthenbach a.d. Pegnitz (Metropolregion Nürnberg)
  2. SYNLAB Holding Deutschland GmbH, München, Augsburg
  3. CEMA AG, verschiedene Standorte
  4. OEDIV KG, Bielefeld


Anzeige
Hardware-Angebote
  1. (u. a. Ryzen 5 1400 für 150,89€, Ryzen 5 1600 für 198,95€ und Ryzen 7 1700 für 290,99€)
  2. ab 179,99€

Folgen Sie uns
       


  1. Diamond Mega

    Randloses Topsmartphone mit zwei Dual-Kameras für 500 Euro

  2. Adobe

    Deep Fill denkt beim Retuschieren Bildelemente dazu

  3. Elektroautos

    Tesla will Autos in China bauen

  4. Mirai-Nachfolger

    Experten warnen vor "Cyber-Hurrican" durch neues Botnetz

  5. Europol

    EU will "Entschlüsselungsplattform" ausbauen

  6. Krack-Angriff

    AVM liefert erste Updates für Repeater und Powerline

  7. Spieleklassiker

    Mafia digital bei GoG erhältlich

  8. Air-Berlin-Insolvenz

    Bundesbeamte müssen videotelefonieren statt zu fliegen

  9. Fraport

    Autonomer Bus im dichten Verkehr auf dem Flughafen

  10. Mixed Reality

    Microsoft verdoppelt Sichtfeld der Hololens



Haben wir etwas übersehen?

E-Mail an news@golem.de


Anzeige
Essential Phone im Test: Das essenzielle Android-Smartphone hat ein Problem
Essential Phone im Test
Das essenzielle Android-Smartphone hat ein Problem
  1. Teardown Das Essential Phone ist praktisch nicht zu reparieren
  2. Smartphone Essential Phone kommt mit zwei Monaten Verspätung
  3. Andy Rubin Essential gewinnt 300 Millionen US-Dollar Investorengelder

Pixel 2 und Pixel 2 XL im Test: Google fehlt der Mut
Pixel 2 und Pixel 2 XL im Test
Google fehlt der Mut
  1. Pixel Visual Core Googles eigener ISP macht HDR+ schneller
  2. Smartphones Googles Pixel 2 ist in Deutschland besonders teuer
  3. Pixel 2 und Pixel 2 XL im Hands on Googles neue Smartphone-Oberklasse überzeugt

Krack-Angriff: Kein Grund zur Panik
Krack-Angriff
Kein Grund zur Panik
  1. Neue WLAN-Treiber Intel muss WLAN und AMT-Management gegen Krack patchen
  2. Ubiquiti Amplifi und Unifi Erster Consumer-WLAN-Router wird gegen Krack gepatcht
  3. Krack WPA2 ist kaputt, aber nicht gebrochen

  1. Re: 1. Win10 Bluescreen nach Update

    ArcherV | 07:59

  2. Auch hier wieder die Frage:

    david_rieger | 07:56

  3. Re: CS 1.5 !

    LSBorg | 07:55

  4. Re: Wo liegt mein Fehler?

    Dangerzone94 | 07:48

  5. Re: Wir kolonialisieren

    Kabelsalat | 07:47


  1. 07:49

  2. 07:43

  3. 07:12

  4. 14:50

  5. 13:27

  6. 11:25

  7. 17:14

  8. 16:25


  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