FFT für Anfänger

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

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

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

@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

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

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

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.

1

for( i=0;i<N;i++){   // N = 1024 : Anzahl der Punkte

2

  x[i]=f(x);          //  in Array schreibe ich die Funktionswerte

3

}

4

5

for(i=0; i<N;i++){

6

    a=0;

7

    b=0;

8

    for(j=0; j<N;j ++){ 

9

        a+=x[j]*cos((2*pi/N)*i*j);

10

        b+=x[j]*sin((2*pi/N)*i*j);

11

    }

12

    X[i]= sqrt(a*a+b*b);   // DFT Amplitudenwerte von Funktion

13

}

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

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

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

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?

ah danke habe deine Anwort übersehen

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.