Gast
#962265
Hallo, kennt jemand von euch spezielle FFT Algorithmen zur Berechnung von Blöcken der Grösse 8 bzw. 16. Danke, Matze
Gast
#962394
http://spiral.ece.cmu.edu:8080/spiral/index.jsp oder was meinst du? Du kennst FFTW oder?
Gast
#962397
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
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
Martin Strubel wrote: > FFTW ist nur gut bei relativ beliebigen dimensionen, das wird hier nicht > helfen. Wie meinen? Belege?
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
Gast
#962933
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.
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 .