www.mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Effiziente FFT Implementierungen


Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
kennt jemand von euch spezielle FFT Algorithmen zur Berechnung von 
Blöcken der Grösse 8 bzw. 16.
Danke,
Matze

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
http://spiral.ece.cmu.edu:8080/spiral/index.jsp

oder was meinst du? Du kennst FFTW oder?

Autor: Bernd (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Matthias

Dürfen wir etwas mehr erfahren? Für welche Anwendung? Wenn du z.B. nur 
die Amplitude einer bestimmten Frequenz brauchst, kann diese explizit 
überpüft werden. Aber bei 8 Werten reicht es kaum zur Grundfrequenz. 16 
Werte für eine volle Sinusschwingung sollten es schon sein.

Gruss

Autor: Martin S. (strubi)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

FFTW ist nur gut bei relativ beliebigen dimensionen, das wird hier nicht 
helfen.
Die Antwort findest Du eigentlich recht schnell selber, wenn du dir die 
Symmetrien der Einheitswurzel (e^(2pi*j/N)) anschaust, bei deiner 
geringen Blockgroesse brauchst du also nicht mal Schleifen.
Gibt wohl nun zwei Moeglichkeiten:
a) Dein Problem ist nicht extrem zeitkritisch, die Zeit die du in die 
Optimierung steckst, lohnt sich ev. nicht, also kannst du's gleich 
diskret machen, oder dich fuer Radix4 oder Radix2-Algorithmen 
entscheiden.
b) Es geht extrem auf Zeit, dann steckst du am besten gleich die 
Berechnung in ein FPGA, dann hast du in einem Zyklus (innerhalb einer 
Pipeline, wenn du viele Berechnungen machen musst) dein Ergebnis.

Bei reinen Realdaten kann man nochmal mit einem Trick arbeiten (siehe 
Wikipedia, oder google nach "Radix2 FFT for real data") und abermals 
Zyklen sparen.

Gruss,

- Strubi

Autor: T. H. (pumpkin) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Martin Strubel wrote:
> FFTW ist nur gut bei relativ beliebigen dimensionen, das wird hier nicht
> helfen.

Wie meinen? Belege?

Autor: Martin S. (strubi)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ganz einfach den Source ansehen. Der Overhead ist zu gross fuer eine 
Transformation von nur 8 oder 16 Werten. Dazu kommt: wenn die Sache auf 
nem DSP laufen soll, ist die fftw sowieso meist nicht mehr effizient, 
wenn ueberhaupt benutzbar (meines Wissens kann sie noch keine 
Fixkomma-Arithmetik)
Ganz gut performt die fftw auf i86ern bei Dimensionen, die 
Primfaktor-zerlegbar sind, bei fixen Zweierpotenzen ist man aber auf nem 
DSP mit dedizierten (Assembler-)Algorithmen immer schneller.

Gruss,

- Strubi

Autor: Maximilian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein Optimaler FFT Algorithmus kann nur in Zusammenhang mit der 
Hardware/Sortware gemacht werden. Es ist sehr wichtig zu wissen, ob ein 
Multiplizierer vorhanden ist.

Falls nicht:
16. Punkt FFT durch Radix 4 realisieren, dann fallen nur Addition und 
Subtraktionen an.

Autor: T. H. (pumpkin) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Martin Strubel wrote:
> Ganz einfach den Source ansehen. Der Overhead ist zu gross fuer eine
> Transformation von nur 8 oder 16 Werten.

Sicher, das ist mit Kanonen auf Spatzen. Der Overhead kann aber durchaus 
reduziert werden (z.B. Plan speichern).


> Dazu kommt: wenn die Sache auf nem DSP laufen soll, ist die fftw sowieso
> meist nicht mehr effizient, wenn ueberhaupt benutzbar

Das ist ein anderer Fall. Mir ging es um deine oben gemachte Aussage.


> (meines Wissens kann sie noch keine Fixkomma-Arithmetik)

Jup, nur float, double und long double .

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.