Brauche Hilfe beim Verständnis der FFT

[Valentin B. (nitnelav)]

Hallo,
ich möchte meine erste FFT auf einem Mikrocontroller implementieren.
Nun habe ich schon etwas darüber gelesen, also hier mal meine 
Vorstellung davon. Bitte korrigiert mich, wenn ich falsch liege:

 - Ich habe ein Signal. Jedes Signal lässt sich in mehrere Sinuswellen unterschiedlicher Frequenz aufspalten, nur natürlich der Sinus nicht.

 - Eine FFT macht genau das, sie sagt mir, welche Sinus-Frequenzen in einem Signal enthalten sind.

 - Der Unterschied zwischen einer DFT und einer FFT ist, dass die FFT nur einige Punkte abtastet, während die DFT die ganze Kurve verarbeitet.

 - Praktisch habe ich also ein Array von Eingangsdaten(Spannung über Zeit), das von einer Funktion zu einem Array von Ausgangsdaten(Anzahl über 
Frequenz) verarbeitet wird.

Leider bin ich erst in Klasse 11, also bin ich mathematisch noch nicht 
so weit, den Wikipedia-Artikel zu verstehen.
Könnte mir jemand erklären, wie man jetzt auf eine Funktion kommt?
Mit freundlichen Grüßen,
Valentin Buck

[Kai P. (kaitams)]

Hi,

privates Interesse oder schulisches Projekt?!

Also ich denke wenn du nicht gerade ne Lib mit FFT-Funktionalität 
findest wirds aufgrund der fehlenden mathematischen Kenntnisse recht 
mühsam. So kurz erklärt ist es hier nämlich auch nicht. Würde dir 
entsprechende Literatur zur digitalen Signalverarbeitung empfehlen:

Springer - Grundlagen der digitale Signalverarbeitung - Andreas 
Wendemuth

Springer - Digitale Signalverarbeitung 1 - Hans W. Schüßler

Vieweg+Teubner - Signalverarbeitung - Martin Meyer

Vieweg+Teubner - Fouriertransformation für Fußgänger - Tilman Butz


Du kannst ja vielleicht schonmal die Abtastung realisieren, die du für 
die spätere FFT benötigst (wichtig dabei ist das Abtasttheorem).

Gruß Kai

[Alex E. (tecnologic)]

Hi,

was willst du genau wissen? Welchen Algorithmus du verwenden sollst? 
oder was bei der FFT eines Signales herauskommt?

Zum Algorithmus, da gibt es viele, wenn du einen einfach zu 
implementierenden suchst dann findest du den in dem Wiki Artikel unter

"Implementierung als rekursiver Algorithmus"

Zum Verständnis: eine FFT liefert dir die Amplitude der deinem 
Zeitsignal enthaltenen Frequenzen. der Frequenzbereich ergibt sich aus 
der Menge an werten und der Abtast Frequenz. Die Abtastrate muss größer 
sein als die doppelte höchste zumessende Frequenz (Nyquist-Kreterium) 
dh. du kannst auch nur bis zu halben Abtastfrequenz das Spektrum 
abbilden. Die Menge der Werte bestimmt die niedrigste darstellbare 
Frequenz. z.b. bei 1000 Werten mit 1kHz abgetastet kannst das Spektrum 
des Sinales von 1Hz bis 500Hz in 1Hz Schritten abbilden. die oberen 500 
Werte die du noch raus bekommst sind eine Spiegelung der unteren aber 
das musst du noch nicht verstehen das hat was mit der Abtastung zu tun.

Viel Spaß bei Equilizer oder so bauen

MfG

Tec

[Valentin B. (nitnelav)]

Naja, das hier ist alles privat.
Im Grunde genommen wollte ich nur mal mit Frequenzerkennung rumspielen.
Ich hab schon ein paar Sachen mit µCs gemacht, also dachte ich, 
vielleicht kann ich damit zwischen tiefen, mittleren und hohen Tönen 
unterscheiden.

Libs gibts zwar, aber leider verstehe ich die nicht.
Entweder ist die Mathematik zu komplex, oder es ist alles auch noch in 
Assembler (naja, bei µCs eigentlich klar, das ist schneller).

Ich dachte immer, man müsste wirklich nur das Array transformieren und 
der rekursive Quellcode bei Wikipedia sieht ja auch ziemlich einfach 
aus.
Bis auf die Vektorpfeile.
Ich dachte immer, Arrays würden mathematisch durch Matrizen vertreten.

Klar könnte ich das ganze auch analog aufbauen, aber für jede Frequenz 
einen Bandpass, das werden viele Bandpässe. Vor allem bei RC und 
4.Ordnung.

Ich hab auch noch was von FIR-Filtern gehört, und dass die auch 
irgendwie Frequenzen erkennen können (Es würde mir reichen, einige 
Frequenzen unterscheiden zu können).

Gibt es da irgendwas?

Mit freundlichen Grüßen,
Valentin Buck.

[in (Gast)]

dazu gibts nen interessanten artikel
http://www.informatics.sussex.ac.uk/users/adrianth/ices96/paper.html

[Floh (Gast)]

Valentin Buck schrieb:
> Ich dachte immer, man müsste wirklich nur das Array transformieren und
> der rekursive Quellcode bei Wikipedia sieht ja auch ziemlich einfach
> aus.
> Bis auf die Vektorpfeile.
> Ich dachte immer, Arrays würden mathematisch durch Matrizen vertreten.

Du hast Messwerte über die Zeit, also ein eindimensionales Feld/Array 
(Tabelle also). daher bedient man sich Vektoren.

Bei einer FFT im Butterflyschema 
(http://de.wikipedia.org/wiki/Schmetterlingsgraph) lässt sich ein Vektor 
mit Messwerten umrechnen in einen Vektor mit Amplitudenwerten der 
enthaltenen Frequenzen.

FFT ist ja ansich nur eine diskrete Fouriertransformation, die ausnutzt, 
das bei bestimmten Messreihenlängen (besonders gut bei 2er Potenzen) der 
Berechnungsaufwand sinkt.
Die FFT errechnet sich dabei Zwischenwerte, die dann weiter verwendet 
werden und die alten Werte nicht mehr benötigt werden.

Daher lässt sich FFT sehr platzsparend (RAM) implementieren.
:-)

[Valentin B. (nitnelav)]

Ok, jetzt hab ichs kapiert.
Ein Vektor ist ja sozusagen eine Datenliste.
Jetzt verstehe ich auch die Lib (KissFFT).
Danke an alle die mir geholfen haben!
Mit freundlichen Grüßen,
Valentin Buck

[Matthias L. (Gast)]

>Ich hab schon ein paar Sachen mit µCs gemacht, also dachte ich,
>vielleicht kann ich damit zwischen tiefen, mittleren und hohen Tönen
>unterscheiden.

Wenns dir um einzelne Frequenzanteile geht, dann schau dir mal den 
Görtzel-Algorithmus an.

http://de.wikipedia.org/wiki/Goertzel-Algorithmus

[ich (Gast)]

Zum verständnis von FFT find ich die beschreibung von sprut ganz gut:
http://www.sprut.de/electronic/pic/16bit/dsp/fft/fft.htm#nomath
sprut hat eh immer gute sachen ;)