Forum: Digitale Signalverarbeitung / DSP / Machine Learning FFT Schlüsselstelle


von Arno M. (Gast)


Lesenswert?

Hallo zusammen,
als Hobbyelektroniker und Autodidakt kämpfe ich zur Zeit  um die 
Hintergründe der Radix 2 FFT vollständig zu verstehen,unter anderem z.B. 
wie der famose Butterfly Algorithmus zustande kommt,.....es will mir 
aber einfach nicht in den Kopf!
Ich habe mich dazu schon gründlich eingelesen:komplexe 
Zahlen,Fouriermatrix,Einheitswurzel,DFT sitzen eigentlich recht gut.Als 
Literatur benütze ich die Bücher von Dspguide.com und "Understanding 
Dsp".Weiss vielleicht jemand Rat wie man an dieser Stelle weiterkommen 
könnte?Danke.
Arno M.

von Null (Gast)


Lesenswert?

Weitergehende Fragen sind :
- Der Unterschied zwischen Fouriertrafo und FFT
- Der Unterschied zwischen einem Linienspektrum und einem 
kontunuierlichen Spektrum
- Der Unterschied zwischen repetitiven Signalen und geplusten Signalen
- Die Eigenfunktionen der Fouriertransformation, dh die Funktionen, die 
auf beiden Seiten der Transformation bis auf eine Multiplikation 
identisch sind
- Die Diracverteilung, resp periodischer Dirac und die FFT

von Thomas S. (Gast)


Lesenswert?

@Arno,
Wie wäre es einfach mal ne Vorlesung dazu zu besuchen ? Bei den ganzen 
Fragen sind schon die Grundlagen nicht ganz unerheblich. Die FFT ist 
doch einfach nur ne Rechenvorschrift, damit die DFT schneller gerechnet 
werden kann, da die Symmetrie der SIN/COS Funktion ausgenutzt wird. 
Evtl. mal den Ansatz machen: Eine 2 oder 4 Punkte DFT zu Fuß 
aufschreiben und siehe da (sic!!!) bei 2 Punkten ist das genau die 
Butterfly-Operation. Später kommen dann noch die Winkeländerungen dazu 
und das war´s auch schon.
@NULL
Die Fouriertransformation (FT) ist zunächste eine kontinuierliche 
Beziehung, die bei der DFT in diskrete Schritte zerlegt wird (also 
abgetastet), daraus ergibt sich das die FT auch ein kontinuierliches 
Spektrum erzeugt , die DFT eben ein diskretes oder Linienspektrum (wie 
der Name ja auch schon sagt). EMpfehlung: Digitale Signalverarbeitung 
von Kammeyer. Sehr gute Einführung für den Praktiker.

von Null (Gast)


Lesenswert?

Periodische Signale haben Linienspektren, jede Krequenzkomponente kriegt 
eine Linie. Wenn nun die Beobachtungsdauer nicht mehr unendlich lange 
ist, so werden aus den Linien schmale peaks, da die Frequenz nun nicht 
mehr beliebig genau bestimmbar ist. Nichtperiodische Signale haben 
kontinuierliche Spektren. Die Eigenfunktionen der Fouriertransformation 
sind die  Gaussfunktionen. Ein Dirac transformiert zu einer Konstanten. 
Ein periodischer Dirac transformiert zu einem periodischen Dirac. Diese 
Weisheiten sollte man gerechner haben und nicht einfach glauben.

Was geschieht mit der Multiplikation unter der FT, was geschieht mit der 
Ableitung unter der FT ?

von Arno M. (Gast)


Lesenswert?

Hallo,
zunächst danke
@Thomas S.
die Idee eine DFT "zu Fuß" zu schreiben habe ich auch schon 
gehabt.Wollte aber z.B. verstehen woher die Subtraktionen in der FFT 
stammen (DFT=nur Additionen).
Habe aber inzwischen im Netz ein Beispiel gefunden mit Matrizen und 
relative Unterteilung in geraden u. ungeraden Untermatrizen,wobei dann 
die bekannten Butterfly-Grafiken eine grafische Umsetzung dieser 
Matrizen-operationen sein müssten.Mein Ziel wäre es,als Übung-ohne 
fremde Hilfe-,eine ((kleine!)  FFT in einem Avr zu implementieren um die 
Beträge dann auf ein Lcd darzustellen....

ciao
Arno M.

von Matthias B. (duesentrieb_610)


Lesenswert?

Hi there,

natürlich ist es ne gute Idee, sich mal ne Vorlesung (oder auch zwei 
oder drei...) zum Thema zu Gemüte zu führen. Sollte das nicht gehen, 
hilft es vielleicht, sich die "Numerical Recipes" näher anzuschauen, die 
es (der Verlag hat es autorisiert! :) ) auch online gibt. Im Falle C 
kuxu hirr: http://www.nrbook.com/a/bookcpdf.php
und hier speziell das Kapitel 12.
Die beste Einführung in das Thema ist m.E. allerdings das 
Unter-hundert-Seiten-Büchlein "A Students Guide to Fourier Transforms" 
von J.F. James. Ich blätterte es auf ner Messe durch, las den Beginn(*), 
kaufte das Teil und habe es nie bereut.
Ich denke, wenn Du Dir beide Werke anschaffst, bist Du gut gerüstet.

Viel Erfolg!



* Er lautete
"Showing a fourier transform to a physics or engineering student 
generally produces the same reaction as showing a crucifix to count 
dracula.
This need not be so."

von Null (Gast)


Lesenswert?

>* Er lautete
>"Showing a fourier transform to a physics or engineering student
>generally produces the same reaction as showing a crucifix to count
>dracula. This need not be so."

Das stimmt so nicht. Als Physikstudent kommt die Fouriertransformation 
etwa im ersten Semester, und sehr ausfuehrlich. Wie Du sagst, es lohnt 
sich einen genaueren Blick drauf zu werfen. Es ist nicht so schwierig. 
Es ist auch ein Augenoeffner. Viele Anwendungen drum herum sind 
eigentlich hokus pokus, und macht's trotzdem. Und es geht trotzdem. Zb 
lebt die Fouriertransformation im Schwartzraum, wo alle Funktionen gegen 
unendlich schneller verschwinden als jedes Polynom. Dh, ein konstanter 
Sinus ist nicht dabei. Seine Fouriertransformierte, der Dirac, ist ja 
auch keine Funktion. Desgleichen duerfte man Diracs auch nicht 
transformieren.

Es stimmt, dass Ingenierstudenten die Fouriertransformation scheuen. Sie 
wurde aber auch nicht wirklich erklaert. Der Stoffplan und das Vorwissen 
scheinen das nicht zuzulassen.

von Null (Gast)


Lesenswert?

Was ich nich vergass : Das ganze Physikstudium lebt von der 
Fouriertransformation. Wenn man die nicht gepackt hat, kann man eh nach 
Hause gehen. Der Impulsraum als Dualitaet zu Ortsraum ist zentral fuer 
die Festkoerperphysik, Phononen-, Photonen- Kopplungen ans Gitter, 
zentral fuer das Verstaendnis des Hamiltonian fuer die Quantenmechanik.

von Christoph db1uq K. (christoph_kessler)


Lesenswert?

Amazon.de wollte es nicht finden, aber amazon.com hats:
A Student's Guide to Fourier Transforms (Paperback)
by J. F. James (Author) Paperback: 142 pages Publisher: Cambridge 
University Press; 2 edition (December 29, 2006) Language: English 
ISBN-10: 0521004284 ISBN-13: 978-0521004282 List Price: $30.00

von Matthias B. (duesentrieb_610)


Lesenswert?

Null wrote:
> Was ich nich vergass : Das ganze Physikstudium lebt von der
> Fouriertransformation. Wenn man die nicht gepackt hat, kann man eh nach
> Hause gehen. Der Impulsraum als Dualitaet zu Ortsraum ist zentral fuer
> die Festkoerperphysik, Phononen-, Photonen- Kopplungen ans Gitter,
> zentral fuer das Verstaendnis des Hamiltonian fuer die Quantenmechanik.

Bingo - just meine Diplomarbeit (Festkörperphysik) bewog mich damals, 
das Teil mitzunehmen, hauptsächlich wegen der Kapitel über 
Autokorrelationsfuktionen, PSDs und dergleichen.
Aber auch die ganze Faltungsalgebra geht ohne Fourier (resp. Hankel) 
nicht, und das Thema Faltung verfolgt einen in der Praxis auf Schritt 
und Tritt - auch, wenn man weder Quantenmechanik noch Festkörperei 
betreibt.


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.