mikrocontroller.net

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


Autor: Peterle Anonym (Firma: keine) (wanderameise)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht 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?

Autor: bjoern (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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??

Autor: Peterle Anonym (Firma: keine) (wanderameise)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht 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."

Autor: B. F. (unit)
Datum:

Bewertung
0 lesenswert
nicht 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!

Autor: jep (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
richtig, fft und dft sind vom ergebnis EXAKT das selbe!

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

Autor: Bastelbub (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Xeraniad X. (xeraniad)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht 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).

Autor: Baradrist (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht 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 :)

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.