Forum: Digitale Signalverarbeitung / DSP / Machine Learning FFT optimierung (Anfängerfrage & eilig!)


von Dennis Meyer (Gast)


Lesenswert?

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

von Björn (Gast)


Lesenswert?

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

von icke (Gast)


Lesenswert?

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.

von Björn (Gast)


Lesenswert?

Wie gesagt, Brigham beschreibt das Verfahren in seinem Buch.

Gruß

von André (Gast)


Lesenswert?

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).

von a. mittelfinger (Gast)


Lesenswert?

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...

von Thomas Pototschnig (Gast)


Lesenswert?

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

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.