FFT optimierung (Anfängerfrage & eilig!)

Dennis Meyer Gast #204581 
Hi,

ich will eine FFT mit Butterfly berechnen. Dazu kann ich nun die n
Eingabedaten in zwei Teile (also n/2) unterteilen und die FFT(n) durch
2 FFT(n/2) berechnen und diese danach zusammensetzen. Das ganze geht
auch öferts nacheinander, bis nur noch 2 Eingabeelemente vorhanden
sind. So weit alles klar!

Wenn ich jetzt allerdings die FFT berechne nutze ich als Eingabedaten
nur Realwerte (benutze die FFT um Polynome zu multiplizieren ->
Realwerte entsprechen koeffizienten. Sollte aber nichts zur Sache tun).
Imaginäranteil der Eingabedaten ist also auf null. Allerdings berechne
ich die FFT mit Einheitswurzeln, welche je Komplexe Zahlen sind.
-> Kann ich nun nicht zwei Transformationen gleichzeitig berechnen,
indem ich die n Eingabewerte der ersten n Daten auf den Realanteil der
Eingabe lege und die zweiten n Eingabedaten auf den Imaginäranteil. Das
sollte doch funktionieren, oder?
Ich berechne ja sowieso schon Komplexe Additionen, da sollte das auch
keine Performance einbußen oder?

Hinweis: Geht nur um die Theorie, keine praxisbezogenen Optimierungen!

Vielen Dank,
Dennis
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Langsamer Modus Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Melden Danke
Björn Gast #204582 
Ja das geht, weiß aber nicht mehr wie es ganau geht. Wenn du die
Möglichkeit hast, dann schau mal in dieses Buch, da wird es
beschrieben:

FFT-Anwendungen
von Elbert O. Brigham
ISBN: 3486215671

Gruß
Björn
Antwort Zitieren Bearbeiten Löschen Melden Danke
icke Gast #204583 
Kann mir spontan nicht vorstellen, daß das geht, das Ergebnis einer fft
ist komplex, auch wenn die Zeitdaten rein real sind.
Oder ich habe deine Absicht nicht verstanden.
Antwort Zitieren Bearbeiten Löschen Melden Danke
André Gast #204585 
Also, Real- und Imaginärteil am Eingang zu nutzen, geht auf jeden Fall
(in diesem Fall sind die gerden Werte der Realteil und die ungeraden
Werte bilden den Imaginärteil), das Ergebnis ist aber neu zu
Rekombinieren, wenn die Transformierte Aussagekraft haben soll. Ich
nehme an, dass eine Rücktransformation erfolgt, die im Ergebnis wieder
nur real ist (genau deswegen funktioniert dieses Verfahren auch, icke).
Antwort Zitieren Bearbeiten Löschen Melden Danke
a. mittelfinger Gast #204586 
Ja, das geht !!! Mal ausm Kopf:
Wenn die Koeffizienten real sind, dann sind die positiven Frequenzen
(also e hoch plus alpha) und die negativen Frequenzen (e hoch minus
alpha) gleich, so dass sich der Imaginärteil auslöscht. D.h bei
komplexen Koeffizienten, bei denen der Imaginärteil eigentlich real
ist, sind die beiden Analysen zum einen als komplexe Summe und zum
anderen als komplexe Differenz übereinandergelagert. Also muß man die
korrespondierenden Frequenzen addieren und subtrahieren, um die beiden
Analysen zu erhalten. Wahrscheinlich muß man beide Analysenwerte noch
halbieren, um die korrekten Gewichte zu erhalten. Außerdem müssen die
jeweils negativen Frequenzen durch einfache Spiegelungen ergänzt
werden, damit bei einer Rücktransformation das Ergebnis wieder real
ist. Also alles zwingend logisch...
Antwort Zitieren Bearbeiten Löschen Melden Danke
Thomas Pototschnig Gast #204587 
Vielleicht reicht dir die Diskrete Cosinus-Transformation.
Da kommen nur reelle Werte raus und sie ist auch recht schnell. Wird in
z.B. in JPEG, MPEG usw benutzt.

Du kriegst halt dann keine Informationen über die Phase - aber wenn man
die nicht braucht ist es egal.

Formeln gibt es wie Sand im Meer - einfach Tante Gugl fragen :-)

Mfg
Thomas
Antwort Zitieren Bearbeiten Löschen Melden Danke
Thread beobachten

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 21 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Dein Name und deine E-Mail-Adresse

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.