FFT 512 Punkte

[FFT (Gast)]

Hallo allerseits,

kann mir einer von euch eine grobe Abschätzung der Rechenzeit geben, 
wenn ich eine FFT aus 512 Punkten berechnen will.
Sagen wir mal 10MHz Takt bei einem 16-Bit-er und 12-Bit breiten 
Messwerten.

Was muss man als Faustformel an Rechenzeit erwarten?

mfg

[holger (Gast)]

>Was muss man als Faustformel an Rechenzeit erwarten?

Das was der Prozessor braucht. Je nach dem wie schlecht
die FFT implementiert wird. Sagen wir einfach mal 100ms.

[Anja (Gast)]

http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=2680&dDocName=en023598

Gruß Anja

[Max G. (l0wside)]

Schau mal auf http://www.fftw.org/.

Wenn ich mich recht erinnere, hat eine FFT N*log2 N Operationen, also 
9*512, mithin 4608 Operationen. Wenn jede Operation gesamt 10 Takte 
braucht, bist du bei ca. 45000 Takten, also 4,5 ms.

Die 10 Takte sind aber rein spekulativ, da wirst du selber recherchieren 
müssen.

Max

[FFT (Gast)]

Also bei 256 Stützstellen (= 2^N = 2^8) hätte ich bei der 
Aufwandsabschätzung mit N*2^N = 8*2^8 = 2048 Rechenoperationen.

Bei 10MHz wären das doch etwa 200us, wenn ich 1-Cycle-Operationen hätte, 
oder? Gesetzt der CPU braucht pro Multiplikation und pro Addition 100 
Cycles, dann wären es 20ms, Soweit richtig, und wieviele Cycles sollte 
Man realistisch für eine Addition und eine Multiplikation einplanen?

Dann hätte ich noch ein paar weitere allgemeine Fragen dazu:
Kann eine FFT quasi online gerechnet werden, während neue Messdaten 
eingehen, oder muss die FFT mit jedem neuen Messpunkt aus dem kompletten 
Messdatenvektor neu ermittelt werden?
Ich meine damit, ob es realistisch möglich ist, die FFT aus 512 Punkten 
zu berechnen, und sobald ein neuer Messwert eingeht, die 511 alten 
Messpunkte derart mit dem einen neuen Messpunkt zu kombinieren, dass der 
Rechenaufwand für die aktualisierte FFT nicht mehr so groß wird?

Bei meiner Anwendung werde ich im 20ms-Takt jeweils 5 Messwerte 
AD-Wandeln müssen.
Zwei davon muss ich einer FFT von jeweils 512 Punkten unterziehen. Die 
übrigen Messwerte sollen einen Vektorbetrag bilden, d.h. drei mal 
quadrieren, drei mal Addieren und die Wurzel draus ziehen... und nun 
muss ich dafür eine Aufwandsabschätzung durchführen, um einen sinnvollen 
uC auszuwählen.
Schlussendlich sollen die Daten in regelmäßigen Abständen per Funk ab 
einen Rechner zur Visualisierung übertragen werden.

mfg

[Ralph B. (rberres)]

Einen ganz guten Grundlagenartikel zur FFT Analyse ist mal vor Jahren in 
den UKW Berichten erschienen. Dort wurde auch erklärt, welche 
Operationen
dazu notwendig sind.

Ralph Berres

[oha (Gast)]

Fuer sukzessive Messwerte gaebs dann noch en Goertzel Algorithmus...

[Funker (Gast)]

Wie muss ich mir das Ergebnis dieses Görzel Algorithmus vorstellen, nur 
bestimmte Frequenzkomponenten zu berechnen...?

Mein Signal liegt ohnehin nur im Bereich von unter 5Hz.