Effiziente FFT Implementierungen

[Matthias (Gast)]

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

[Gast (Gast)]

http://spiral.ece.cmu.edu:8080/spiral/index.jsp

oder was meinst du? Du kennst FFTW oder?

[Bernd (Gast)]

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

[Martin S. (strubi)]

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

[T. H. (pumpkin)]

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

Wie meinen? Belege?

[Martin S. (strubi)]

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

[Maximilian (Gast)]

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.

[T. H. (pumpkin)]

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 .