FFT für Anfänger

[Sera (Gast)]

Hallo zusammen,

Ich möchte auch eine FFT in c++ programmieren. Hierbei kommt es mir erst
mal nicht auf die Geschwindigkeit an. Ich habe versucht soviel wie
möglich zu lesen, jedoch beschreiben die Meisten das ganze immer so
kompliziert, das es keiner verstehen kann, daher versuche ich es über
diesen Weg.

Ich möchte für den Anfang ein FFT mit 150 Punkten erstellen.ich habe 
schöne  die Funktionswerte  in einem Array geschrieben.

Kann mir vielleicht jemand anhand dieses kleinen Beispiels vorrechnen 
oder mal erklären
wie ich die FFT  in c++ implementieren oder kennt man ein Classe ,das 
mir  weiterhilft.

bin für  jede Tipps  sehr Dankbar.


Grüsse

Sera

[Achim W. (Gast)]

Hallo,
die FFT ist die schnelle Variante der DFT. Das Ergebnis ist (so glaube 
ich) das gleiche.

DFT:
Du hast Deine Werte in einem Array.
Erzeuge jetzt einfach ein 2. Array und fülle das mit einem Sinus mit zum 
Beispiel 1kHz.

Jetzt gehst Du mit einer Schleife über alle Werte und multiplizierst 
alle Werte aus dem 1. Array mit denen aus dem 2. und bildest die Summe.

Also a[0]*b[0] + a[1]*b[1] + ... + a[150]*b[150]
Das Ergebnis (/150) ist der 1kHz Frequenzanteil.

Allerdings nur der, der in Phase mit dem Sinus ist. Damit die Phase 
keine Rolle spielt, machst Du das gleiche noch mit dem Cosinus und 
bildest den quadratischen Mittelwert aus dem 1kHz Sinusergebnis und dem 
1kHz Cosinusergebnis, also wurzel(s*s + c*c)

Und jetzt das alles wiederholen bei der nächsten Frequenz, zum Beispiel 
1.1kHz ..

[Niklas (Gast)]

Hallo

die FFT ist eine schnelle Berechnung der DFT. Vor allem wenn die Anzahl 
der FFT eine Potenz von 2 ist also N = 2^r.
Bevor du dich an die FFT gibst solltest du daher zuerst die DFT komplett 
verstehen und dich dann an Sachen wie Butterfly, Twiddlefaktoren und 
Bitumkehrung geben. Ansonsten wird das nix mit der FFT

[Aris (Gast)]

Damit hätte man dann die SFT - die slow fourrier analysis.

[FlorenZ (Gast)]

@Achim:
Auch wenn ich die Frage nicht gestellt habe,
vielen Dank für die Antwort.

Ich habe noch nirgends eine verständlichere Erklärung der DFT gelesen.
Die hätte in der Wikipedia durchaus ihre Berechtigung...

Gruß, FlorenZ

[Martin K. (mkmannheim)]

Das ist auf Wiki aber sehr gut erklärt, finde ich. Auch im Netz findet 
man genug Erklärungen.

[Sera (Gast)]

Danke Sehr Achim für dein Erklärung, sorry ich hat Internetproblem.
 Nach deiner Erklärung hab ich mit DFT noch mal beschäftigt und habe die 
Implementierung von DFT wie folgenden vorangegangen:
[c]

for( i=0;i<N;i++){   // N = 1024 : Anzahl der Punkte
  x[i]=f(x);          //  in Array schreibe ich die Funktionswerte
}
for(i=0; i<N;i++){
    a=0;
    b=0;
   for(i=0; i<N;i++){
     a=x[j]*cos((2*pi/N)*i*j);
     b=x[j]*sin((2*pi/N)*i*j);
    a+=a;
    b+=b;
  }
X[i]= sqrt(a*a+b*b);   // DFT Amplitudenwerte von Funktion
}

Kann man mir sagen ob es  richtig und  wie  kann ich  es verbessern 
falls da fehler ist.

PS:

> Das Ergebnis (/150) ist der 1kHz Frequenzanteil.
> Und jetzt das alles wiederholen bei der nächsten Frequenz, zum Beispiel
> 1.1kHz ..
Achim was meinst du hier das habe ich  nicht  verstanden , was du mit 
wiederhlen bei der nächsten Frequenzen meint.


Gruß
Sera

[Achim W. (Gast)]

Ja, fast. Die innere Schleife muss natürlich j sein, nicht i.
Und die Aufsummierung muss anders erfolgen, sonst wird die Summe immer 
wieder zurückgesetzt.

for( i=0;i<N;i++){   // N = 1024 : Anzahl der Punkte
  x[i]=f(x);          //  in Array schreibe ich die Funktionswerte
}

for(i=0; i<N;i++){
    a=0;
    b=0;
    for(j=0; j<N;j ++){ 
        a+=x[j]*cos((2*pi/N)*i*j);
        b+=x[j]*sin((2*pi/N)*i*j);
    }
    X[i]= sqrt(a*a+b*b);   // DFT Amplitudenwerte von Funktion
}

>was du mit wiederhlen bei der nächsten Frequenzen meint.
Damit habe ich genau die äußere Schleife gemeint. Also die zweite der 
drei for-Schleifen mit Index i.

[Mori (Gast)]

ah ok Danke  sehr ;

was  soll ich  da  änderen damit, ich die statt DFT nun FFT 
implementieren.
und  noch eine frage  entspricht  X[0]  das gleiche Anteil von dem 
Signal?

Gruß
Sera

[Achim W. (Gast)]

>und  noch eine frage  entspricht  X[0]  das gleiche Anteil von dem Signal?
genau.

>was  soll ich  da  änderen damit, ich die statt DFT nun FFT implementieren.
Soweit ich das in Erinnerung habe, ist die FFT eine Variante der DFT, 
bei der N immer ein zweier-Potenz ist.
Dadurch kann man den Algorithmus deutlich in der Geschwindigkeit 
optimieren und es sind nicht mehr i*j Schleifendurchgänge notwendig, 
sondern deutlich weniger.

[Mori (Gast)]

ja es muss der anzahl der punkte 2^n sein und da brauchst man nur bis 
2^n/2 werte zu brechnen. aber da  werde ich einfach weiter 
recherchieren.

ist X[0] hier das gleichanteil von den Signal?

[Mori (Gast)]

ah danke habe deine Anwort übersehen

[Balu (Gast)]

Ein Frage: Wenn man über eine komplette Welle drübersummiert, ist das 
Ergebnis doch Null. Oder wird der Effekt genutzt, dass die Wellen 
interferieren? Ich denke mir, dass das Ergennis einfach immer positiv 
sein wird, wenn man eine Welle gleicher Frequenz draufmultipliziert, 
richtig?

Ausserdem: Wieviele Wellen Sinus und Cosinus sind in dem array jeweils 
enthalten?  Es kann ja nur für eine ganzzahlig aufgehen. Ist es eine 
komplette Welle für die höchste Frequenz oder eine für die niedrigste?

Ich denke mir, dass die anderen entsprechend ihrer Frequenz angepasst 
werden und damit viele nicht genau in das Array-Raster passen, was 
wieder leakage erzteugen dürfte, oder?

Wird dieser Effekt durch die Fensterfunktion auf die Eingangsdate 
komplett beseitigt? Oder müssen die Koeefizienten im Sinus Cosinus Array 
auch nochmal gefenstert werden, wie man das bei anderen FIR-Filtern 
macht? Oder wird das dann doppelt gemoppelt?

Dann weiter; Wie stellt man die Stelheit der Frequenzen ein? Macht es 
Sinn, für die längste Welle (die anderen sind ja gemäss Frequenz kürzer) 
nicht nur eine Welle in das Array zu nehmen, sondern mehr als eine? ich 
habe ein wenig herumprobiert und festgestellt, dass die Frequenzen 
selektiver werden und regelrechte Durchsacker entstehen, wenn man die 
Frequenzen durchfährt. ???

Danke für eure Antworten.

[J. S. (engineer)]

Balu schrieb:
> Ausserdem: Wieviele Wellen Sinus und Cosinus sind in dem array jeweils
> enthalten?
Eine, die Grundwelle. Für die anderen Ordnungszahlen die entsprechenden 
Oberwellen.

> Ich denke mir, dass die anderen entsprechend ihrer Frequenz angepasst
> werden und damit viele nicht genau in das Array-Raster passen,
Ja

> was wieder leakage erzteugen dürfte, oder?
Du meinst, weil die Wellen nicht vollständig abschließen? Das ist 
zumindeste bei typischen Auflösungen der FFT unerheblich, weil der 
Beitrag des Restschwanzes minimal ist.

> Wird dieser Effekt durch die Fensterfunktion auf die Eingangsdate
> komplett beseitigt?
Ich würde sagen, das kommt auf die Fensterfunktion an. Je nachdem, wie 
die zum Rand ausläuft, hast Du sicher ein etwas anderes Verhalten.

>regelrechte Durchsacker entstehen
das sollte der oben beschriebene Randeffekt sein.

Welche FFT hast Du verwendet?