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?
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??
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.
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."
> 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!
richtig, fft und dft sind vom ergebnis EXAKT das selbe! die fft ist nur ein schneller algorithmus der dft ... sonst nichts
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.
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).
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
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.