www.mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP FFT für Anfänger


Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo

Ich möchte auch mal eine FFT 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 8 Punkten erstellen. (diese kann 
man vielleicht noch leicht verstehen)

Als µC benutze ich einen ATMEGA32 von Atmel. Mit dem integrierten µC 
digitalisiere ich einen Rechteckimpulse, der durch einen 
Funktionsgenerator eingespeist wird. Die 8 digitalisierten Werte 
speicher ich im internen SRAM ab. Nachdem ich nun meine 8 Werte habe, 
kann ich daraus die FFT berechnen.

Meine digitalisierten Werte lauten wie folgt:

x[0]= 0;  x[1]= 0;  x[2] = 50;  x[3] = 50; x[4] =50; x[5] = 50; x[6] = 
0;  x[7] = 0;

auf einigen Seiten habe ich dann gelesen, das zuerst folgene Summen 
gebildet werden

Summe 1 = x[0] + x[4]
Summe 2 = x[1] + x[5]
Summe 3 = x[2] + x[6]
Summe 4 = x[3] + x[7]

Anschließend Subtrahiert man Werte und multipliziert das Ergebnis mit 
der n-te Einheits­wurzel w^n

Differenz1 1 = (x[0] + x[4])*w^1
Differenz1 2 = (x[1] + x[5])*w^2
Differenz1 3 = (x[2] + x[6])*w^3
Differenz1 4 = (x[3] + x[7])*w^4


Jedoch komme ich mit der Einheits­wurzel nicht klar. Zudem weiß ich 
nicht wie es weitergeht.

Kann mir vielleicht jemand anhand dieses kleinen Beispiels vorrechnen 
wie die FFT funktioniert.

Grüsse

Michael

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hast du verstanden wie die DFT (diskrete Fouriertransformation) an sich 
funktioniert?

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nein habe ich nicht. Wenn es eine gute Erklärung gibt dann wäre ich über 
einen Link dankbar.

Ich will doch nur die Umsetzung. Dies kann doch nicht so schwer sein. 
Sind doch nur ein paar Additionen und Multiplikationen

Autor: pumpkin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es ist im Grunde genommen auch nicht schwer.

Was bitte ist die Einheitswurzel? Ich denke damit ist der Twiddle-Faktor 
gemeint. Dieser Twiddle-Faktor ist lediglich ein Zeiger in der komplexen 
Ebene der auf dem Einheitskreis wandert. Stell' dir den Einheitskreis 
vor wie einen Kuchen, der nun aufgeteilt werden soll. Und zwar in N 
gleichgroße Teile. N steht für die Ordnung deiner FFT, in diesem Fall 
ist N=8. Nun schreiben die Techniker aber ungerne immer wieder

  e^(-j*2*PI * k / N) = e^(-j*2*PI / N)^k

sondern kürzen sich das Ganze ab mit

  (W_N)^k  ("W-hoch-k-Index_N")


Im Fall mit N=8 bekommt man also die Twiddle-Faktoren

  W^0 =  1     + j 0
  W^1 =  0.707 + j 0.707
  W^2 =  0     + j 1
  W^3 = -0.707 + j 0.707
  W^4 = -1     + j 0
  W^5 = -0.707 - j 0.707
  W^6 =  0     - j 1
  W^7 =  0.707 - j 0.707
  W^8 = W^0
  W^9 = W^1
   .
   .
   .

Das sind die einzigsten komplexen Faktoren die man hier brauchen wird. 
Zeichne dir das am besten mal auf, dann wird du schnell begreifen wie es 
sich verhält. Zeichne den Einheitskreis auch einmal mit N=16 oder N=4. 
Achte darauf, dass der Zeiger bei 1 + j0 anfängt und mathematisch 
positiv dreht, d.h. gegen den Uhrzeigersinn.

Wenn du das begriffen hast, dann schaue dir ein Butterfly-Plot an um zu 
sehen, wie man eine FFT beispielsweise implementiert.

Autor: Tom (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bisschen Grundlagen in komplexer Mathematik wären auch hilfreich.

Ich würde erstmal eine DFT in einer Hochsprache programmieren, um das 
Prinzip verstehen zu lernen. Dann eine FFT, was ja eigentlich nur eine 
Folge von 2-Punkt-DFT ist. Auch in einer Hochsprache, denn da hast du 
mehr Möglichkeite, z.B. float-Variablen. Und dann das Ganze in 
Assembler.

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe schon mal mit der Labview-Demo gearbeitet. Dort möchte ich das 
ganze zuerst ausprobieren, bevor ich es in den µC implementiere. Man 
kann da schöne Signale erzeugen und einfach ein Rauschen draufgeben und 
sich anschließend die FFT anschauen. Der Vorteil ist man kann die 
berechnete FFT von Labview mit der eigenen vergleichen. Sollten ja beide 
identisch sein.

Autor: Tommi Huber (drmota)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael bist du vielleicht der Newbie von 
Beitrag "Probleme mit Aufgabe zu digitale Signalverarbeitung"

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nein bin ich nicht. Ich denke mal Michael heißen wohl sehr viele in 
diesen Forum

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So ich habe mal ein wenig im Internet nach dem Twiddle-Faktor gesucht. 
Jedoch ist mir dann nicht ganz klar wie Du auf die folgenden Ergebnisse 
gekommen bist:

  W^0 =  1     + j 0
  W^1 =  0.707 + j 0.707
  W^2 =  0     + j 1
  W^3 = -0.707 + j 0.707
  W^4 = -1     + j 0
  W^5 = -0.707 - j 0.707
  W^6 =  0     - j 1
  W^7 =  0.707 - j 0.707
  W^8 = W^0
  W^9 = W^1

e^(-j*2*pi*n*k/N) = cos(2*pi*n*k/N) -j sin(2*pi*n*k/N).

W^0 = cos (2*pi*0*0/8) -j sin(2*pi*0*0/8) => cos(0) - j sin(0) => 1
W^1 = cos (2*pi*1*1/8) -j sind(2*pi*1*1/8) => cos(pi/4) -j sin(pi/4) => 
0,0137

Was mache ich denn falsch denn Du kommst ja bei W^1 auf 0.707 + j 0.707

Autor: Alex (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi Newbie,

das für W^0 = 1 + j0 = 1 ist siehst du hoffentlich ein.

Dass cos(pi/4) = 0.707 und sin(pi/4) = 0.707 ist kriegt ein 
Fünftklässler raus, dem man einen Taschenrechner in die Hand drückt.

Wie du es geschafft hast, Real- und Imaginärteil zu 0.0137 zu vermehren 
wird wohl dein Geheimnis bleiben (du weißt was eine komplexe Zahl ist?).

Dass pumpkin die Vorzeichen etwas verdreht hat steht auf einem anderen 
Blatt, er hat sich gegen anstatt mit dem Urzeigersinn auf dem 
Einheitskreis in der komplexen Ebene bewegt.

W^1 = .707 - j.707
...

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe den taschenrechner von Windos verwendet. Vielleicht hat dieser 
sich aber verrechnet, da ich die CPU stark übertaktet habe.

pi/4 = 0,78539816339744830961566084581988

cos(0,785398) ergibt 0,99990
sin(0,785398) ergibt 0,01370

habe leider gerade keinen anderen Taschenrechner zur Hand

Autor: HildeK (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>cos(pi/4) -j sin(pi/4) => 0,0137
Im Taschenrechner RAD als Basis eingeben! Dann kommt das raus, was Alex 
schrieb.
Bei meinem Win-Rechner kommt 0,70710678118654752440084436210485 heraus!

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Oh ich hatte bei Windows nicht auf Rad gestell ^^

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jetzt komme ich auch auf das Ergebnis.

Ich habe noch Probleme mit der Formel e^(-j*2*pi*n*k/N)

j ist klar
pi auch
N = Anzahl der abtastwerte

nur was ist denn k und n? Welchen Bereich hat k und n?

Autor: pumpkin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Dass pumpkin die Vorzeichen etwas verdreht hat steht auf einem anderen
> Blatt, er hat sich gegen anstatt mit dem Urzeigersinn auf dem
> Einheitskreis in der komplexen Ebene bewegt.
>
> W^1 = .707 - j.707
> ...

Konform zu meiner Definition, ich habe es sogar angemerkt. Ich kenne 
keine Literatur in der es anders ist. Stifte also bitte keine unnötige 
Verwirrung.


> Ich habe den taschenrechner von Windos verwendet. Vielleicht hat dieser
> sich aber verrechnet, da ich die CPU stark übertaktet habe.

GAS GAS GAS!

Ich bin raus.

Autor: pumpkin (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Na gut, einen noch.

> nur was ist denn k und n? Welchen Bereich hat k und n?

k und n sind Indizes der DFT. Wenn man die Formel (1) aus dem Anhang 
annimmt, dann steht n für den Frequenzindex und k für den Zeitindex. 
Beides sind ganze Zahlen bzw. beide sind diskret.

Autor: pumpkin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
an Alex:

Entschuldige, jetzt weiss sehe ich erst was du meinst! Das ist mir 
wirklich unangenehm. Korrektur:


  W^0 =  1     + j 0
  W^1 =  0.707 - j 0.707
  W^2 =  0     - j 1
  W^3 = -0.707 - j 0.707
  W^4 = -1     + j 0
  W^5 = -0.707 + j 0.707
  W^6 =  0     + j 1
  W^7 =  0.707 + j 0.707
  W^8 = W^0
  W^9 = W^1
   .
   .
   .

Achte darauf, dass der Zeiger bei 1 + j0 anfängt und mathematisch
positiv dreht, d.h. mit dem Uhrzeigersinn.

Autor: Alex (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mathematisch positiv heißt gegen den Uhrzeigersinn, sorry ;-)

Autor: pumpkin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bin ich jetzt total bescheuert? Wenn ich schon das eine ändere dann muss 
ich auch das andere ändern:

Mathematisch negativ, d.h. im Uhrzeigersinn.

Sonntägliches Kopfkino! Ich halt' lieber den Rand!   ;^)

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Habe ich schon gemerkt. Ich werde das morgen einmal alles durchrechnen 
und posten. Dann habe ich sicher auch noch eine Frage.

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wir sollten hier ein FAQ für FFT einrichten. Mal sehen ob ich es mache.

Autor: Jemand (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Guck mal die gnumeric-Datei da an:
Beitrag "Re: Schnelle FFT in Assembler"
Da hat es jemand ne FFT in Gnumeric nachgebaut. vieleicht hilfts.

Autor: Tobias Weiß (tobis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
also das mit dem drehzeiger ist völlig klar...ganz normaler drehzeiger 
eben.

Doch wie gehts dann weiter???

Butterfly-Plot???

Autor: Jeso (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

hab auch noch so meine Probleme bei der FFT vor allem weil ich den 
mathematischen zusammenhang net so ganz kapier fehlt halt viel Mathe.

Aber jetzt zum Thema versuch grad mal Testweise in Excel den Butterfly 
nachzumachen. Soll dann später mal auf nen AVR oder 8051 umgesetzt 
werden.

Twiddlefaktor hab ich so langsam auch mal kapiert und hab mir sie auch 
ausgerechnet. Gut so weit.
Jetzt hab ich mir ne Eingangsfolge überlegt. Soll en Rechteck werden.
Hab 16 Samples da sind jeweils 2 0 und 2 = 255. Nun stellt sich bei mir 
die Frage wie verrechne ich jetzt den Twiddlefaktor der ja komplex ist 
mit ner rein reelen eingangszahl z.B. die 255. Wenn das jemand 
anschaulich erklären könnte wäre auch von großem nutzen für die 
Umsetzung auf nem AVR.

Wenn ich mir den Butterfly anschaue und ich den dann bei mir die 4 
Stufen ausgerechnet hab dann hab ich am Ende direkt meine Spektren?

Danke für die Antworten.

Autor: Günter -.. (guenter)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Berechnung ist immer komplex. Selbst wenn dein Eingangssignal real 
ist, "wandelst" du es in eine komplex Zahl um.

Also 255 wird 255 +j0 den Wert multiplizierst du jetzt mit dem 
Twiddelfaktor.

Autor: matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein bisschen Googeln würde gut tun.

Fixfertig auf dem Silbertablar:
http://www.codeproject.com/KB/recipes/howtofft.aspx

Autor: JESO (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
0   0   0
1   0   0
2  255  0
3  255  0
4   0  255
5   0  255
6  255 255
7  255 255
8   0   0
9   0   0
10 255  0
11 255  0
12  0  255
13  0  255
14 255 255
15 255 255

So hier hab ich meine Eingangsfolge und danach die Bit Reversal folge 
von meinen 16 Werten.
in der 1. Stufe ist ja der Twiddle Faktor 1 und j 0.
Also addiere ich in Zeile null die Zeile  0 mit Zeile 1 und 
Multipliziere mit Twiddle Faktor Real. und in zeile 1 Subtrahiere ich 
Zeile 0 mit Zeile 1 und multipliziere mit Twiddlefaktor Imaginär. Oder 
hab ich das falsch verstanden. Und in Stufe 2 sind es dann 2 
Twiddlefaktoren und so weiter.

Autor: Roland Bumm (rolandb)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Versuche das ganze vlt nicht an einem Rechteck. Da kommt dann was 
komsiches vlt für dich raus (irgendetwas si oder sinc) förmiges.. Nehme 
erstmal einen Sinus oder Cosinus.


mfg

Autor: Jeso (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Werde es auch noch mit einem anderen Eingangsignal versuchen rechteck 
war erstmal das leichteste. Mir war erstmal nur nicht ganz klar wie ich 
den Butterfly dann rechne vorallem wenn ich nur die Samplewerte habe die 
ja keine Komplexe Zahlen sind. Mal ne dumme Frage wieso soll ich kein 
Rechteck nehmen da sollte doch ein relativ glecihmäßig verteiltes 
Spektrum geben. Werde aber mal en paar sinus werte berechnen.

Autor: Jeso (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Irgendwie hab ich komplexe Zahlen noch nicht ganz verstanden.

Wenn ich jetzt 250 + 5j habe und diese mit Twiddelfaktor 0707 - 0707j 
multipliziere kommt raus:  176,75 - 3,53j stimmt dies.

 (250*0,707) + (5j * -0,707j)

Autor: Günter -.. (guenter)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nein, die Berechnung ist so:
(250 + 5j) * (0707 - 0707j)

= 250 * 0707 - 250 * 0707j + 5j * 0707 - 5j * 0707j

j * j = -1

Das Ergebnis ist dann:
(250*0707 + 5*0707 +j 5*0707 - 250*0707)
Neuer Realwert ist also 250*0707 + 5*0707 und der imaginäre Wert ist 
5*0707 - 250*0707.

Autor: geri (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hallo leute,

frage zum link: http://www.mikrocontroller.net/attachment/28612/dft.JPG

X(n) = sum(x(k) * exp(-j2*Pi*n*k/M), 0<=n<=M-1) ist ja auch schon im 
frequenzbereich periodisch?

bye

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.