Forum: Digitale Signalverarbeitung / DSP / Machine Learning Verständnis FFT-Übung


von Peterle A. (Firma: keine) (wanderameise)


Angehängte Dateien:

Lesenswert?

Gegeben ist eine Folge von diskreten Werten, welche mittels FFT 
transformiert werden sollen.
Mittels DFT ergibt sich ja die Summe aus 11 e-Termen, das habe ich schon 
getan, aber worin besteht nun der Vorteil der FFT, bzw wie wende ich 
diese an?

von bjoern (Gast)


Lesenswert?

hallo, also die fft ist nur ein algorithmus und im prinzip eine dft nur 
etwas ungenauer. wie du die fft anwendest kannst du dir bei wikipedia 
oder in diversen sourcecodes anschauen. sollst du die fft per hand 
ausrechnen??

von Peterle A. (Firma: keine) (wanderameise)


Lesenswert?

ja leider...
also das ganze erstmal in 2 summen unterteieln, jeweils für gerade und 
ungerade N. das führt dann zum butterfly algorithmus.
Das ganze hätte ich gerne mal etwas genauer erklärt, denn es muss ja 
letztendlich einen rechnerischen gewinn ergeben.

von Mark B. (markbrandis)


Lesenswert?

Dann zitiere ich doch mal aus dem Skript von unserem ehemaligen Prof:

"Der Rechenaufwand einer N-Punkte-DFT ist von der Ordnung N^2. Die FFT 
reduziert diesen Aufwand auf die Größenordnung N log2 N. Die Grundidee 
dabei ist, die N Signalwerte in kürzere Stücke zu zerlegen, diese 
einzeln zu transformieren, und danach die Ergebnisse zur DFT 
zusammenzusetzen."

von B. F. (unit)


Lesenswert?

> hallo, also die fft ist nur ein algorithmus und im prinzip eine dft nur
> etwas ungenauer.

Stimmt nicht! Die Genauigkeit der FFT ist dieselbe wie die von der DFT!

von jep (Gast)


Lesenswert?

richtig, fft und dft sind vom ergebnis EXAKT das selbe!

die fft ist nur ein schneller algorithmus der dft ... sonst nichts

von Bastelbub (Gast)


Lesenswert?

Hallo,

ich übe im Moment auch viel mit DFT und FFT für eine anstehende Klausur.

Ich würde dir empfehlen, mit Matlab oder Scilab rumzuexperimentieren. 
Dort siehst du ganz schnell, ob deine Rechnung per Hand richtig ist.

Dann siehst du auch, dass die eine FFT die gleichen Ergebnisse wie eine 
von Hand berechnete DFT liefert.

von Xeraniad X. (xeraniad)


Angehängte Dateien:

Lesenswert?

Guten Tag
Auch wenn der Fred schon etwas länger zurückliegt, wollte ich zwecks 
Dokumentation eine rekursive FFT -Implementation hinzufügen.
Aus dem Histogramm ist die maximale Amplitude bei Frequenz-Index k = 2 
abzulesen. Dies entspricht (leicht verschoben) der negativen cos() 
-Schwingung mit doppelter Grund-Frequenz, womit die ersten 3÷8 der 
gegebenen Abtastwerte beginnen.
Das interpolierende trigonometrische Polynom enthält 17 Terme (bis hin 
zur Nyquist-Frequenz).

von Baradrist (Gast)


Lesenswert?

Auch wenn der Thread wohl nicht mehr so recht gelesen werden sollte und 
die Übung des Thread-Starters vermutlich bereits vergangen ist, möchte 
ich noch etwas hinzufügen (für zukünftige Google-Anfragen zum Thema):

Das Geheimnis hinter einer FFT ist, daß Werte, die die DFT mehrfach 
verwendet, nur einmal berechnet werden. Man versteht dies erst, wenn man 
sich die Formeln der Zerlegungen anschaut. Man beachte die Periodizität 
der komplexen e-Funktion (da sie aus sin und cos zusammengesetzt ist) 
und schon sieht man, welche Terme doppelt/vierfach/etc berechnet werden. 
Es lohnt sich, die Formeln DIREKT aufzuschreiben und ist auch nicht viel 
Aufwand! Wer zu faul dazu sein sollte, diese Seite erklärt alles ganz 
wunderbar:

http://www.librow.com/articles/article-10

Das heißt, die Geschwindigkeit resultiert aus dem Weglassen von 
redundanten Berechnungen. Damit erklärt sich auch, warum DFT und FFT 
exakt gleiche Ergebnisse liefern! Die Berechnung einer FFT "von Hand" 
sollte, so man sie verstanden hat, keine Probleme machen.

Liebe Grüße,

Baradrist

von Mark B. (markbrandis)


Lesenswert?

Baradrist schrieb:
> diese Seite erklärt alles ganz wunderbar:
>
> http://www.librow.com/articles/article-10

Das ist mal eine richtig gute Website! Dankfein :)

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.