Hallo allerseits, ich beschäftige mich im zuge meines "Lichtorgel-Pimpens" etwas mit FFT am AVR. Hier scheint die Version von Elm Chan ja weit verbreitet zu sein: http://elm-chan.org/works/akilcd/report_e.html die ist größtenteils in Assembler, und ich tu mir schwer die zu verstehen... Frage 1: Der Code stammt aus dem Jahr 2005, scheint aber immer noch gut zu funktionieren (und deshalb weit verbreitet zu sein). In den letzten 10 Jahren dürfte sich aber am Compiler-Sektor doch einiges getan haben, sodass eine reine Assembler-Implementierung nicht mehr den riesigen Vorsprung vor einer klugen C-Implementierung haben sollte. Kann man das so sagen? Wenn ja, gibt es eine sinnvolle C-Implementierung für AVR (ATmega328)? Mir gehts weniger darum die auch einzusetzen, sondern mehr ums Verstehen (Windowing im Preprocessing hab ich begriffen, bit reversal im Postprocessing auch, in der Mitte haperts etwas bei den butterfliegen...) Frage 2: wie ist denn das mit der "Trennschärfe" der Bänder? Wenn ich das richtig verstanden habe, haben die Bänder ja immer die doppelte Frequenz, also z.B. 100 - 200 - 400 - 800 Hz. Was passiert bei einem Signal von 300 Hz? Frage 3: Wenn ich nur wenige Bänder haben will (Lichtorgel, da reichen eigentlich 3, wenn ausbaubar vielleicht 6 oder 8) ist da FFT überhaupt die richtige Herangehensweise? Das "Referenzprojekt" 6-kanal-Lichtorgel am AVR nutzt auch die ElmCHan-FFT, um nachher erst wieder (mühsam) die Bänder zusammenzufassen. ist das nicht "Rechenzeit verschütten"? Danke euch, Michi
:
Verschoben durch Admin
Das hier scheint etwas in C zu sein http://www.element14.com/community/groups/development-tools/blog/2011/01/11/real-time-audio-spectrum-analyzer-using-a-pic-8-bit-microcontroller auch hier http://hackaday.com/2011/01/08/pic-spectrum-analyzer-uses-fast-fourier-transform-routine/ Wenn der Code in C ist, sollte der Unterschied zwischen PIC und AVR keine so große Rolle spielen MfG Klaus
> Frage 1: [...] eine reine Assembler-Implementierung nicht mehr den riesigen > Vorsprung vor einer klugen C-Implementierung haben sollte. Kann man das > so sagen? Wenn ja, gibt es eine sinnvolle C-Implementierung für AVR > (ATmega328)? Teilweise sind da Bitfuseleien, die in Assembler einfacher effizient zu implementieren sind. Probiers halt aus. > Mir gehts weniger darum die auch einzusetzen, sondern mehr ums Verstehen Wenn's ums Verstehen geht, nimm ne Floatingpoint FFT auf'm PC. Die Fixed-Point-Implementation auf einer 8-Bit-CPU schlägt sich mehr mit den Limitierungen der CPU rum als mit dem Algorithmus an sich. > Frage 2: [...] Wenn ich das richtig verstanden habe, haben die Bänder ja > immer die doppelte Frequenz, also z.B. 100 - 200 - 400 - 800 Hz. Nein, das ganzzahlige Vielfache der Grundfrequenz: 100, 200, 300, ... Und es sind "Bänder", die sich auch etwas überlappen. > Frage 3: Wenn ich nur wenige Bänder haben will (Lichtorgel, da reichen > eigentlich 3, wenn ausbaubar vielleicht 6 oder 8) ist da FFT überhaupt > die richtige Herangehensweise? Eine FFT hat eine Laufzeit von O(n*log(n)), ein FIR-Filter O(n). Rein theoretisch sind FIRs schneller, solange du nur maximal log(n) Stück brauchst (bei 128-FFT also 7 FIR). Allerdings ist das O(1) bei der FFT größer als bei dem FIR, so dass du wohl noch einige FIRs drauf legen kannst. Dazu kommt, dass du bei wenigen diskreten FIRs wohl nicht alle mit 128 Samples laufen lässt. > Das "Referenzprojekt" 6-kanal-Lichtorgel > am AVR nutzt auch die ElmCHan-FFT, um nachher erst wieder (mühsam) die > Bänder zusammenzufassen. ist das nicht "Rechenzeit verschütten"? Was machst du denn mit der nichtverbrauchten Rechenzeit? Ne Busyloop? Es gibt kein "Geld zurück" für nicht verbrauchte Rechenzeit. Wenn eine Lösung mit FFT einfacher und trotz des Rechenaufwands schnell genug ist, was spricht dagegen?
Michael Reinelt schrieb: > die ist > größtenteils in Assembler, und ich tu mir schwer die zu verstehen... Keine Arme->keine Kekse. Lerne einfach Assembler. AVR-Assembler ist wirklich einfach, an einem WE vollständig erlernbar (natürlich nicht die perfekte Nutzung, nur die vollständige Sprachkenntnis). Ganz im Gegensatz zu C. Das benötigst du Wochen allein bis zur vollständigen Sprachkenntnis... Wobei ich sowieso davon ausgehe, daß du (wie die meisten) von C sowieso nicht mehr begriffen hast, als nötig ist, um den geklauten Code anderer Leute zum Laufen zu bringen und irgendwie zusammenzuleimen... > Frage 1: Der Code stammt aus dem Jahr 2005, scheint aber immer noch gut > zu funktionieren (und deshalb weit verbreitet zu sein). In den letzten > 10 Jahren dürfte sich aber am Compiler-Sektor doch einiges getan haben, Nicht wirklich. Mit Assembler kann man immer noch um etwas bis sehr viel schneller sein als mit C. Hängt von der Aufgabe ab. Es gibt aber nach wie vor keine (und wird es auch niemals geben) eine Aufgabe, bei der eine Umsetzung in C schneller ist als eine von kompetenten Leuten geschriebene Asm-Routine. D.h.: Jeder C-Versuch kann bestenfalls so gut ausfallen wie die optimale Asm-Routine, aber niemals besser. Tendenziell ist also Asm IMMER im Vorteil. Und weil das so ist, lohnt es auch immer, Asm zu lernen... > Frage 2: wie ist denn das mit der "Trennschärfe" der Bänder? Wenn ich > das richtig verstanden habe, haben die Bänder ja immer die doppelte > Frequenz Das hast du definitiv nicht richtig verstanden. Ganz sprach-unabhängig... > Frage 3: Wenn ich nur wenige Bänder haben will (Lichtorgel, da reichen > eigentlich 3, wenn ausbaubar vielleicht 6 oder 8) ist da FFT überhaupt > die richtige Herangehensweise? Nein, da würde man wohl sinnvollerweise auf Goertzel setzen. Auch wieder sprachunabhängig. Allerdings: auch hier wird wieder nur in Assembler der optimale Gortzel entstehen können, C-Umsetzungen werden mehr oder weniger langsamer sein... Das liegt daran, daß Goertzel (wie auch FFT) zwar schon relativ simpel ist, aber noch nicht simpel genug, daß ein C-Compiler ihn aus eigener Kraft wirklich optimal umsetzen könnte... Das gilt selbst dann noch, wenn der C-Programmierer unendlich viel Zeit dafür einsetzt, seinen Compiler in die richtige Richtung zu tricksen. Mal abgesehen davon, daß genau das NICHT Sinn der Sache bei der Verwendung einer (und sei es auch nur Möchtegern-) Hochsprache ist oder sein kann...
c-hater schrieb: > Wobei ich sowieso davon ausgehe, daß du (wie die meisten) von C sowieso > nicht mehr begriffen hast, als nötig ist, um den geklauten Code anderer > Leute zum Laufen zu bringen und irgendwie zusammenzuleimen... Starke Worte, die mich aber nur ein Lächeln kosten...
Hallo Michael, ich habe aus Anlass Deiner Frage meine C-source einer FFT mit integern mal rausgesucht und angehängt. Der Code arbeitet mit int16_t Eingangsdaten und deckt FFTs der Länge 2^5=32 bis 2^10=1024 ab. Die Routine macht 'autoscaling': Sie merkt, wenn der 16Bit Zahlenbereich droht überzulaufen und skaliert dann entsprechend, die resultierende Skalierung wird rapportiert. Dieser Code funktioniert, der steckt in vielen laufenden Geräten, ich hab aber die Geschwindigkeit vergessen, liegt im ms-Bereich. Ich habe die Source aus einem C-Projekt rausgeschnitten, kann sein, das ich was vergessen habe, ich habs' auch nicht auf Übersetzbarkeit getestet. Gern gebe ich auch mehr Unterstützung, der Code ist mir ans Herz gewachsen, die Variablennamen habe ich als jugendlicer Programmierer vor vielen, vielen Jahren vergeben. Cheers Detlef
Erfolg! Meine FFT läuft! ich bin mal grundsätzlich extrem begeistert von dem Ding, auch von der Genauigkeit. Ich speise das Ding mit meinem Funktionsgenerator, und anhand der Amplituden der jeweils benachbarten Bänder kann man die Mittenfrequenz ziemlich genau einstellen, indem man solange verstellt bis die Amplitude der Seitenbänder identisch sind. Und die empfindlichkeit liegt bei 6 kHz immer noch bei 1-2 Hz! Aber - ich habe "leichte" Verständnisprobleme mit der Interpretation des Ergebnisvektors, vor allem des ersten Wertes. Am leichtesten erkläre ich das mal an einem Beispiel: Ich sample mit 14.423kHz (die krumme zahl ergibt sich aus 12 MHz, Prescaler 64 und 13 Cycles im free-running mode des ATmega) meine FFT hat 64 Slots, das Ergebnis theoretisch auch, wobei die oberen 32 uninteressant sind (spiegelung der unteren 32) Ich würde also Frequenzbänder im Abstand 14423/64 = 225 Hz erwarten. Die sehe ich auch, aber genau um einen Slot nach oben verschoben: Wenn ich genau 225 Hz einspeise, habe ich ein maximum im Slot 1, Slot 0 "zappelt", Slot 2 zeigt grob die Hälfte von Slot 1, alle weiteren sind auf 0, also ander geschrieben: x - 40 - 20 - 0 - 0 (x steht fürs zappeln) Wenn ich genau 450 Hz einspeise, erhalte ich 0 - 20 - 40 - 20 - 0 675 Hz: 0 - 0 - 20 - 40 - 20 - 0 das höchste Band 32 (also [31] wegen start 0) hat das maximum bei 6975 Hz, erwarten täte ich 7200 Hz irgendwie ist das alles um eins nach rechts verschoben... ich habe auch "meine" FFT mit der Originalversion vom Elm Chan verglichen, die zeigt das exakt gleiche Ergebnis. Erwarte ich falsch, und das passt eh alles, oder ist hier ein Wurm drinnen? das Zappeln des untersten Bandes könnte ich mir noch durch das Windowing erklären... Kann mich jemand bei der Denkfehleranalyse unterstützen?
Enrico Koeck schrieb: > Das unterste Band ist Null Herz (Gleichanteil), nicht vergessen. Hmmm, sowas hatte ich schon vermutet... aber die Bänder haben ja immer eine "breite", geht dann das unterste Band von 0 Hz bis ??? Irgendow hatte ich heute eine Seite an der Hand, da wurde erklärt, dass alle Bänder bis auf das erste und letzte eine bestimmte breite haben, nur eben das erste und letzte eine andere... ich find das nicht mehr.
Na das Nullte müsste dann von -225Hz - +225Hz gehen, wenn ich mich nicht täusche. Und doppelte Höhe wie in echt haben (weil reell). Zumindest der Gleichanteil.
Ha! ich glaub ich habs... Gleichanteil dürfte ja eigentlich keiner drinnen sein, außer wenn die Frequenz zu tief ist sodass keine komplette Schwingung mehr Platz hat. Aber - durch das Windowing wird eine Verschobene Sinus-Schwingung (also eine die grad nicht bei 0 beginnt) vorne und hinten bedämpft, damit ergibt sich ein Gleichanteil, er auch mit der phase der Sinus-Schwingung mitgeht. Das erklärt genau das "Zappeln" des untersten Bandes... => unterstes band ignorieren, und gut ist. Danke!
Genau. Zu bedenken ist aber auch, dass dir eventuell tiefe Frequenzen durch die Lappen gehen können, was ja besonders bei einer Lichorgel auch zu unerwünschten ergebnissen führen könnte (flackert nicht zum Bass mit).
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.