Hallo, ich bin gerade dabei mir von Grund auf eine FFT auf den AVR zu entwickeln und ein Tutorial zu schreiben. Es geht nicht darum einen fertigen Code umzubasteln oder um irgendwelche copy & paste Codes. Mir geht es darum das Verständniss und die Umsetzung darzustellen. Also mal eine ordentliche Beschreibung, mit der man eine FFT auch auf anderen Controllern umsetzen könnte. Alles natürlich in ASM realisiert. Meine Vorstellung sind folgender Aufbau: 1.Theorie 1.1. Mathematischer Hintergrund DFT 1.2. Herleitung FFT aus DFT 1.3 FFT-16 nach RADIX-2 (Butterfly - Graph & Twiddle Faktoren bestimmen) 2.Umsetzung 2.1 Eingangsdaten in 2er-Komplement und Fensterung 2.2 Bit-Reversal-Sort 2.3 Komplexe Berechnung der einzelnen zwischen Stufen 2.4 Betragsrechnung 2.5 Codeoptimierung 2.6 Ausgabe auf Display etc. 3.Erweiterung auf FFT höherer Ordnung 4.Verbesserung der Berechnunggenauigkeit auf 16Bit Wie schaut es generell aus, besteht daran Interesse??? Die Berechnung an sich läuft schon in Excel zum Test. In ASM bin ich schon bis zur Berechnung der 1.Stufe gekommen und das Tutorial steht leider erst bei Punkt 1.3 Gruß Alexander
SUPER Idee!!! :) Kann nur sagen das so ein Tutorial klasse wäre! Gibt ja auch genug nachfragen nach FFT im Forum. Bin mal gespannt auf das Ergebnis!!!
Naja, diese Informationen kriegt man schon n-fach im Internet, auch sehr gute Assembler-Routinen. Wenn es aber um den Lernfaktor geht, kann man's ja immer machen :-) ... Interessant ist das Thema auf alle Fälle!
Ja, darum geht es eigentlich. Im Netz gibt es genügend Sachen, allerdings nur die mathematischen Hintergründe und der fertige Code dazu. Ziel ist es keinen besseren Code zu entwerfen, sondern eine bessere Anleitung mit Herleitung der Teilroutinen :-) Wenn ich morgen die Fensterung dokumentiert habe, stell ich mal den ersten Stand ein.
Kleiner Literaturtipp: Fouriertransformation für Fußgänger (Broschiert) von Tilman Butz (Autor) Das Buch enthält eine wirklich hervorragende Herleitung des FFT Algorithmus! Wenn man die Mathematik dahinter besser versteht klappt auch die Umsetzung viel besser. Vielleicht hilft es ja dein Tutorial noch besser zu machen. Grüße Mandrake
Also ich habe die Doku jetzt auf dem Stand, dass die mathematischen Herleitungen vollständig sind. Ich hoffe sie sind verständlich und zeigen, warum man die Summenformel genau so aufteilt. Anmerkungen erwünscht. Ist der 1.Stand. Arbeite gerade an den nächsten Teil (Fensterung,Eingangsdaten), dort gehts dann mit ASM los.
Ich denk schon, wurde in den meisten Threads schon besprochen. Man könnte am Ende alles mal in C versuchen und die Ergebnisse (Geschwindigkeit)vergleichen. Zudem möchte ich das Prinzip anschließend auf nen FPGA umsetzen und das geht aus ASM viel besser.
> Zudem möchte ich das Prinzip anschließend auf nen FPGA umsetzen und das > geht aus ASM viel besser. Wieso sollte das aus ASM besser gehen?
Für mich persönlich ist ASM besser, da weiß ich was der Prozessor bei jedem Schritt macht und wieviele Takte er dafür braucht. Bin eher so der Hardwaretyp und kann mir VHDL nicht gut aus C saugen.
@ Alexander Liebhold deine erste pdf ist hartes brot aber ich werde stück für stück mich durcharbeiten. ASM find ich auch besser. Bin gespannt auf die nächste pdf c.u Commtel
Hallo Alexander, Idee ist klasse, Anfang sieht gut aus. Warum nicht C und ASM, d.h. zeitkritische Berechnungen und Messungen in ASM eingebettet in einem freundlichen C-Programm. Evtl. auch als Include. Warte auf Rest Gruß Hans
@Comtel Das ist auch der schwierigste Part, aber auch der Wichtigste. Wenn du an dem Punkt der Summenformel für Spektrallinie 2 und 6 angekommen bist (Seite 3), siehst du, dass im Prinzip alles nur geschicktes Ausklammern und Zusammenfassen ist. Ach ja, hab 2 Jahre nix mehr mit FFT gemacht und hatte auch so meine Schwierigkeiten rein zu kommen. Nur Mut, danach wirds wieder einfacher....
@hans wichtig ist, dass das Programm insgesammt schnell läuft, d.h. es ist alles kritisch. Würde erst einmal den Weg mit ASM machen, damit man dass Prinzip dann in C übernehmen kann, sobald alles geht. Kann dann auch gern jemand anderes machen.
Hi, super Idee mit dem Tutorial. Habe von dem theoretischen Kram auch keine Ahnung. Ein Butterfly samt Twiddle Faktoren kann ich aufstellen. Habe das mal für eine 4 Punkt FFT gemacht: x0 + W0/4*x2 + W0/4(x1 + W0/4 * x4) = A0 x0 + W2/4*x2 + W1/4(x1 + W2/4 * x4) = A1 x0 + W0/4*x2 + W2/4(x1 + W0/4 * x4) = A2 x0 + W2/4*x2 + W3/4(x1 + W2/4 * x4) = A3 Jetzt nur mal theoretisch: - Ich rechne meine Twiddle Faktoren wieder um und setze sie ein - Dann kann ich für jede Eingangsfolge x0-x3 mein Ausgang A0-A3 berechnen - Was sagt A0 - A3 aus, sind das schon meine Spektrallinien ? MFG
Um mal mit einem Beispiel zu arbeiten, Eingangsfolge: x0 = 1 x1 = 2 x2 = 0 x3 = -1 Daraus bekomme ich dann mein Ergebnis: A0 = 2 A1 = 1 -j3 A2 = 0 A3 = 1 +j3 Ist das nun schon mein Real-Imag-Teil der Spektrallinie? MFG
Das sind deine komplexen werte. Meist interessiert man sich nicht für die Werte einzeln, sondern fürs Betragsspektrum, dann geht nur die Phase verloren, aber die Amplituden stimmen.
Hmm ... wenn ich also mein Spektruk zeichnen will, brauche ich nur den Realteil zu beachten, oder. Mal eine weitere Frage, diese Summenformeln sind ja immer gleich, will mir die jetzt nicht für eine FFT höherer Ordnung selbst herleiten. Stehen die irgendwo oder gibt es da ein Schema, wie man sich die einfacher herleiten kann?
Nein, den Betrag, und der wird aus |X(j)|=WURZEL(Re(x)^2+Im(x)^2)
gebildet.
Schau dir mal meinen Graphen der FFT 16 an. Dort wirst du einen Verlauf
erkennen können.
Stufe 1: - keine direkten Abhängigkeiten
Stufe 2: - jeder Wert 2^1 wird addiert
- jeder Wert 2^1+1 besitzt Twiddlefaktor mit N=2^2
Stufe 3: - jeder Wert 2^2 wird addiert
- jeder Wert 2^2+1 besitzt Twiddlefaktor mit N=2^3
Stufe 4: - jeder Wert 2^3 wird addiert
- jeder Wert 2^3+1 besitzt Twiddlefaktor mit N=2^4
Na, nun sollte man da doch was sehen.In allen höhren Stufen tuhe ich
immer dasselbe. Ich mein Offset für die Addition und Subtraktion wird
größer, die Position der Twiddlefaktoren verschiebt sich definiert und
die Twiddlefaktoren kann man fortlaufend aschon vorberechnet us dem
Speicher lesen.
Viel Spaß beim Nachvollziehen :-)
Oh, sorry für den Buchstabensalat.... Was noch zu beachten ist, dass alle Werte ab Stufe 2 Komplexe Werte sind. Diese müssen dann in der Form (A+jB)*(C+jD)=(A*C+B*D)+j(A*D+B*C) multipliziert werden!!! Zudem sollte man alle Ergebnisse einer Stufe (nach Addition und Subtraktion) durch 2 Teilen, damit kein Speicherüberlauf auftritt. Zudem kommt bei einer N-wertigen FFT die N-fache Betragsamplitude am ende heraus. D.h. man muss das Ergebniss daher durch N teilen.
Jetzt gibts die neue Version mit Fensterfunktionen und deren Umsetzung in ASM.
Gerade hinzugefügt: Berechnung der ersten Stufe komplett.
Es werden bis jetzt ca. 200us Rechenzeit benötigt
und
alle Ergebnisse liegen Komplex im 2er-Komplement
vor.
P.S. Als Tip, ich würde die erste Stufe erst einmal in Excel
durchspielen, damit man vergleichbare Ergebnisse hat.
Versuche mich auch grad an einer geeigneten FFT. Würde das persönlich aber lieber erst mal am PC simulieren wollen. Wie könnte dafür eine geeignete Testbench aussehen? - Dachte mir, ich lese mir die Werte von der Soundkarte in Matlab/Excel oder noch besser, - ich lese die aktuell abgespielten Musikdaten vom Musikplayer aus z.B WinAmp geht das so ohne weiteres, hat einer ne ahnung ob und wie das geht ? Gruß aus Hamburg
für die, die sich gefragten haben (wie ich) wofür die abkürzung steht. FFT = Fast Fourier Transformation
>für die, die sich gefragten haben (wie ich) wofür die abkürzung steht. >FFT = Fast Fourier Transformation Danke Frau Rieger, jetzt hab ichs verstanden :-D
Hallo, wie sieht das eigentlich mit der Lizenz des Codes aus? Seht er unter der GPL. Ich überlege nämlich ihn einzusetzen und da ist wichtig das zu wissen.
@ Alexander Nun ist das ein grosses Stück Arbeit, das Du da geleistest hast und mir ist gerade nicht recht klar ob jetzt eine Kritik angebracht ist. Wenn nicht ignoriere sie bitte einfach. Deine Ankündigung und die ersten Antworten auf die Ankündigung Deines Vorhabens haben bei mir gewisse Erwartungen geweckt. >1.1. Mathematischer Hintergrund DFT >Wenn es aber um den Lernfaktor geht... >Ja, darum geht es eigentlich. Im Netz gibt es genügend Sachen, >allerdings nur die mathematischen Hintergründe und der fertige Code >dazu. >Ziel ist es keinen besseren Code zu entwerfen, sondern eine bessere >Anleitung mit Herleitung der Teilroutinen Leider sehe ich diese Erwartungen nicht erfüllt. Es mag sein, das ich falsche Erwartungen hatte, aber Tatsache ist, das ich nach lesen Deines pdfs immer noch Fragen habe die Du weder stellst noch beantwortest. Ich weise nochmal darauf hin das ich Dir hier nichts "vorwerfe". Du hast gute Arbeit geleistet denke ich und die ist auch was Wert. Ich denke nur man könnte einiges verbessern. Das Problem bei dem was ich schreibe ist natürlich auch das ich mich nicht wirklich mit der FFT und den Grundlagen auskenne. Ich bitte das zu berücksichtigen. Ich nehme mal zwei Einträge hier im Forum, die klarmachen sollen was ich vermisse. 1. Beitrag "Re: Fourier zu Fuß" 2. Beitrag "Re: Fourier zu Fuß" hier insbesondere das Zitat: ""Fang statt der FFT erstmal mit einer normalen Fourier-Analyse an." Das heisst hier tauchen Fragen auf, die aus Deinem Papier nicht unmittelbar zu klären sind. Wiegesagt, wenn Du das nicht beabsichtigt hast kann ich das akzeptieren, aber dann ist Deine Ankündigung ein wenig irreführend. Auf dem Level, mit dem Du da anfängst gibt es viele Erklärungen. Vielleicht wäre es sinnvoll Dir mal die Fragen hier zur FFT anzuschauen, damit Du noch Anregungen bekommst was man erklären könnte. Ich hoffe Du nimmst mir das nicht übel, aber vielleicht hilft es doch Deine ursprünglichen Ziele wieder etwas mehr in den Fokus zu rücken. Ausserdem habe ich, denke ich, einen sachlichen Fehler entdeckt: In Deinem Papier steht, das das Abtasttheorem aussagt das "mindestens" zwei Abtastwerte vorhanden sein müssen. Das ist so nicht korrekt. Es muss heissen, das "mehr als" zwei Abtastwerte vorhanden sein müssen. Da ich weiss wie das hier manchmal abgeht, möchte ich gleich ankünndigen, das ich zu meiner Äusserung keinen weiteren Kommentar abgebe. Nehmt es als Anregung oder ignoriert es, bitte.
Hey Alex, warum hast Du mit dem Tutorial aufgehört? Das ist gerade das was ich im Moment suche und absolut super gewesen! Hoffe Du machst es noch zu Ende... Gruß
Sorry, war in letzter Zeit ganz schön stark in verschiedene Projekte eingebunden und hatte keine Zeit zum weiterarbeiten. Da die Nachfrage aber hoch ist, werde ich mich wieder rein hängen. Anbei noch eine Veranschaulichung, welche Abhängigkeiten der Butterfly-Graph beinhaltet um das Verfahren auf beliebige 2^n Abtastwerte zu erweitern. Ich werde das Skript so ändern, das ich doch erst mit C-Code anfange, da dieser einfacher zu verstehen und zu lesen ist. (Dieser soll aber nahe dem Assemblerniveau gehalten werden, also keine Gleitkomma o.ä.)Danach kann man eine Assemblerversion starten Bitte Fragen und Ergänzungsvorschläge für das Skript schreiben. Gruß Alexander
Ich habe jetzt das 1.Kapitel erweitert und beschrieben was der Grundgedanke der Fouriert-Transformation ist und wie man anschließend auf die DFT kommt. Gelöscht habe ich den Assembler-Teil, da ich hier mit C starten werde (ein Code mit hunderttausenden LDI und MOV ist nicht mehr gut zu lesen.) Für Vorschläge und Fragen bin ich offen.
Alexander Liebhold schrieb: > Für Vorschläge und Fragen bin ich offen. Aber immer doch: 1.) Wieso eigentlich die Beschränkung auf 8-Bit-Controller? Für die korrekte Durchführung einer FFT ist es an und für sich doch unerheblich, ob die Quantisierung des Ursprungssignals nun mit 8 oder mit 16 Bit erfolgte. Tatsächlich wird man in der Realität nicht ganz selten eine 10-Bit-Quantisierung haben, wenn die Werte eben so vom A/D-Wandler kommen. Nur passen 10 Bits halt so schlecht in ein Byte rein. 2.) In Kapitel 1.1 steht: "Dabei kommt er vom Ansatz her nicht um eine Beschreibung mit komplexen Zahlen herum, da die meisten Spektren auch negative Frequenzen enthalten." Dies finde ich interessant. Wie kann ich denn eine negative Frequenz akustisch erzeugen? Kann man zum Beispiel eine Gitarrensaite so zupfen, dass sie mit minus 800 Hertz schwingt? :-) Klar, die FFT wird ja auch in der Bildverarbeitung etc. eingesetzt. Nur das mit dem "die meisten Spektren" stört mich in dem Zusammenhang, weil es in einem doch recht großen Anwendungsbereich - eben Audio - eher nicht so viel Sinn ergibt. 3.) Wäre es möglich, diesen Thread in das Unterforum DSP zu verschieben? Da würde er meiner persönlichen Meinung nach am besten hinpassen. Naja schrieb: > Ausserdem habe ich, denke ich, einen sachlichen Fehler entdeckt: > In Deinem Papier steht, das das Abtasttheorem aussagt das "mindestens" > zwei Abtastwerte vorhanden sein müssen. Das ist so nicht korrekt. Es > muss heissen, das "mehr als" zwei Abtastwerte vorhanden sein müssen. Das stimmt so nicht, mathematisch gesehen reichen zwei Abtastwerte pro Periode absolut aus. Dass dies technisch so nicht realisierbar ist, weil es keine Filter mit unendlicher Flankensteilheit gibt, stimmt schon. Aber was schert die Mathematik sich um die Technik? ;-)
Mark Brandis schrieb: > Das stimmt so nicht, mathematisch gesehen reichen zwei Abtastwerte pro > Periode absolut aus. Beispiel: 50Hz Sinus gsampelt mit 100Hz... könnte genau die Nulldurchgänge des 50Hz Sinus treffen, dann geht vorne was rein aber hinten kommt nichts mehr raus. Die Samplefrequenz muss grösser 2x der maximalen Signalfrequenz sein, dann stimmts.
Frank schrieb: > Mark Brandis schrieb: >> Das stimmt so nicht, mathematisch gesehen reichen zwei Abtastwerte pro >> Periode absolut aus. > > Beispiel: 50Hz Sinus gsampelt mit 100Hz... könnte genau die > Nulldurchgänge des 50Hz Sinus treffen, dann geht vorne was rein aber > hinten kommt nichts mehr raus. Die Samplefrequenz muss grösser 2x der > maximalen Signalfrequenz sein, dann stimmts. Das Problem hast du bei 200MHz doch auch?
>> Beispiel: 50Hz Sinus gsampelt mit 100Hz... könnte genau die >> Nulldurchgänge des 50Hz Sinus treffen, dann geht vorne was rein aber >> hinten kommt nichts mehr raus. Die Samplefrequenz muss grösser 2x der >> maximalen Signalfrequenz sein, dann stimmts. >Das Problem hast du bei 200MHz doch auch? Wenn ich ein 50 Hz Signal mit 200 Hz sample, erhalte ich z.B. folgende Werte: 0, +1, 0, -1, 0, 1, ... Das ist schon ziemlich aussagekräftig.
@Mark Also das mit der Samplefrequenz stimmt schon. Genau definiert ist es größer gleich 2, wobei bei 2 Abtastwerten diese ungleich der Nulldurchgänge sein muss. In der Praxis muss man natürlich eher einen Faktor 4-8 verwenden. Ich werde es mal noch ändern. Also jedes Spektrum eines kontinuirlichen Signals besitzt negative Frequenzen (außer analytische Signale). Stell dir vor du hast ein 20kHz Audiosignal. Dann hast du ein Band von 0Hz-20kHz und das gespiegelte von -20kHz...0Hz. Klar gibt es das technisch nicht. Aber modulierst du das Signal auf einen 1MHz Träger, so verschiebst du quasi den 0Hz-Ursprung auf 1MHz und was siehst du nun??? Genau!!!! Ein oberes Seitenband (1MHz-1,02MHz) was deinem Band 0...20kHz entspricht und ein unteres Seitenband (0,98MHz-1MHz) was aus den negativen Frequenzen -20kHz-0Hz stammt. Deswegen benötigst du auch immer die doppelte HF-Bandbreite für die Übertragung. (Beim demodulieren kannst du natürlich nur noch das ober Seitenband verwenden.) Das ist natürlich nicht wirklich effektiv, aus diesem Grund verwendet man analytische Signale (das sind Signale mit einem einseitigen Spektrum), die man durch die Hilbert-Transformation erhällt. Da brauch man nämlich nur die einfache HF-Bandbreite. Zu den 8-Bit. Also ich wollte zeigen, das man auch mit ganz einfachen 8-Bit µC für 1,50EURO ne FFT durchführen kann. Das heißt aber nicht, das die Verarbeitung auf 8-Bit beschränkt ist. Eine FFT auf nem DSP oder FPGA umzusetzen ist dann kein Problem, funktioniert ja genau so und dort ist ja genügend Performance vorhanden :-). Also mal schauen, was man aus so nem 8-Bitter raus holen kann. (Auch wenns nur bis 1kHz gehen würde, so kann wenigstens jeder das Prinzip billig und schnell ausprobieren. Hier zählt Lernfaktor nicht Performance. Aber schön wenn hier viele Leute sachlich diskutieren. Werd mich jetzt erst mal an das Problem der Auslöschung und Vorskallierung der Twiddle-Faktoren setzen.
Hi, wird das Tutorial nicht weitergeführt? Schade.... Habe übrigens, da die höheren Radix-Algos vielleicht interessant wären, einen neuen Thread gestartet. Der Autor hier hat eine tolle Arbeit geleistet;-) (Wo bleibt die versprochene Weiterführung??) Shcöne Grüße
Thread beobachten
Seitenaufteilung abschaltenBitte 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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.