Hallo zusammen, bevor ich mich jetzt intensiv in die FFT einlese, habe ich gehofft, dass mir jemand sagen kann, ob das denn auch Sinn macht. Ich habe ein Arry aus 80 unsigned int Werten und möchte eine FFT darüber laufen lassen. Das Problem an der Sache ist, dass ich dafür nur eine begrenzte Zeit und Rechenleistung zur Verfügung habe. Ist es Möglich mit einem 8 Bit Controller innerhalb von 15ms die 80 Werte Auszuwerten? Sagen wir bei einer Taktfrequenz von 4 MHz? An den Werten ließe sich hie und da noch etwas drehen aber vielleicht kann mir ja schon jemand sagen, ob die Idee völliger Unsinn ist oder das Vorhaben realisierbar scheint? Viele Grüße Sebastian
Sebastian schrieb: > ein Arry aus 80 unsigned int Werten Die FFT geht doch nur für 2^n Werte, also entweder 64 oder 128.
Vielleicht ist ja die fft-Routine von ChaN interessant. Auszug aus ffft.S
1 | ;----------------------------------------------------------------------------; |
2 | ; 16bit fixed-point FFT performance with MegaAVRs |
3 | ; (Running at 16MHz/internal SRAM) |
4 | ;
|
5 | ; Points: Input, Execute, Output, Total: Throughput |
6 | ; 64pts: .17ms, 2.0ms, 1.2ms, 3.4ms: 19.0kpps |
7 | ; 128pts: .33ms, 4.6ms, 2.4ms, 7.3ms: 17.5kpps |
8 | ; 256pts: .66ms, 10.4ms, 4.9ms, 15.9ms: 16.1kpps |
9 | ; 512pts: 1.3ms, 23.2ms, 9.7ms, 34.2ms: 14.9kpps |
10 | ; 1024pts: 2.7ms, 51.7ms, 19.4ms, 73.7ms: 13.9kpps |
11 | ;----------------------------------------------------------------------------; |
mfg
Audiofred schrieb: > Wortbreite der Werte, Tiefe der FFT ? Meine int Werte sind 16 Bit breit. Davon nutze ich aber nur 10 Bit (Die Werte kommen aus dem ADC). Was genau ist mit Tiefe gemeint? Udo Schmitt schrieb: > Die FFT geht doch nur für 2^n Werte, also entweder 64 oder 128. Stimmt ja. Das ist aber kein Problem. 64 Werte müssten genügen. 128 Werte gingen aber auch. Die Tabelle liefert doch schon mal einen guten Anhaltspunkt. Sehe ich das richtig, dass ich dann ein Array aus 64 16-Bit Elementen in 3,4ms auswerten kann, wenn ich eine Taktfrequenz von 16 MHz habe?
Bis du dir sicher,. dass du Fourier brauchst? Deine letzte Antwort klingt eher danach ein, zwei Frequenzen rauszufischen. Falls das zutrifft, schau dir mal Goertzel an http://de.wikipedia.org/wiki/Goertzel-Algorithmus
Maxxie schrieb: > Bis du dir sicher,. dass du Fourier brauchst? Deine letzte Antwort > klingt eher danach ein, zwei Frequenzen rauszufischen. Falls das > zutrifft, schau dir mal Goertzel an > http://de.wikipedia.org/wiki/Goertzel-Algorithmus Danke für den Tipp! Das hast du richtig erkannt. Ich möchte genau genommen folgendes: Einer 50 Hz Halbwelle ist ein sehr verrauschtes nicht sinusförmiges Signal überlagert. Die Frequenz dieses Signals variiert stufenlos etwa zwischen 6000 Hz und 2200 Hz. Und eben diese Frequenz möchte ich ermitteln. Ich bin nicht sicher, ob ich den Artikel richtig verstehe aber der Goertzel-Algorithmus müsste hierfür tatsächlich geeignet sein, oder?
Nur bin ich nicht sicher, ob die Stufenlose Frequenz nicht ein Problem ist. Das Beispiel mit dem Telefon läuft ja nur mit diskreten Frequenzen.
Also Wikipedia sagt "Vergleicht man diesen Aufwand mit dem Berechnungsaufwand bei der schnellen Fourier-Transformation ist der Goertzel-Algorithmus immer dann effizienter, wenn weniger als 5/6 log2(N) Spektralkomponenten berechnet werden sollen." Wenn ich es richtig verstehe muss ich für N ja nun die Anzahl meiner Messwerte nehmen und komme auf 5/6 log2(64) = 5. Den Frequenzbereich von 6000 Hz und 2200 Hz muss ich zwar nicht aufs Herz genau ermitteln aber so um die 50 Schritte sollten es schon sein...
Der Goertzel Algorithmus bringt dir leider nur etwas bei fester Frequenz. Wenn du ein Signal über ein Spektrum an Frequenzen suchen musst, ist ein Fourier besser geeignet. In jedem Fall mach dich schlau über die Randbedingungen/Erscheinungen. z.B. Aliasse, Auswirkung der Fensterfunktion, etc.
Sebastian schrieb: > zwar nicht aufs > Herz genau ermitteln aber so um die 50 Schritte sollten es schon sein.. Das bekommst du aber auch nicht mit 64er FFT hin. Dort bekommst du N Schritte von (inklusive) 0 Hz bis Fabtast/2 hin. Also höchstens bei Fabtast = 2*6kHz 40 Schritte. (Da du 2200/6000 "wegwerfen" musst, weil sie dich nicht interessieren)
Sebastian schrieb: > Den Frequenzbereich von 6000 Hz und 2200 Hz muss ich zwar nicht aufs > Herz genau ermitteln aber so um die 50 Schritte sollten es schon sein... Die Frequenzauflösung der FFT bei N Abtastwerten und einer Abtastfrequenz f_abtast ist deltaf = f_abtast*N/2 du willst einen Bereich von 3800Hz mit 50 Schritten auflösen, das macxht auf die maximalen 6000Hz schon 79 Stufen, dann musst du mit >12kHz abtasten und schon brauchst du für die FFT 256 Abtastwerte. du hast dann 128 Frequenzstufen, von denen du 256/2*3800/6000=81 auch berechnen musst.
Danke für eure Antworten. Maxxie schrieb: > In jedem Fall mach dich schlau über die Randbedingungen/Erscheinungen. > z.B. Aliasse, Auswirkung der Fensterfunktion, etc. Ja da habe ich wohl noch einen Haufen Arbeit vor mir. Gibt es eine empfehlenswerte Quelle, die das ganze praxisnah erklärt? Mit der Mathematik auf diesem Niveau tue ich mir bereits sehr schwer und selbst Wikipedia bringt mich hier an meine Grenzen... Maxxie schrieb: > Das bekommst du aber auch nicht mit 64er FFT hin. Dort bekommst du N > Schritte von (inklusive) 0 Hz bis Fabtast/2 hin. Also höchstens bei > Fabtast = 2*6kHz 40 Schritte. (Da du 2200/6000 "wegwerfen" musst, weil > sie dich nicht interessieren) Die Rechnung habe ich immerhin soweit verstanden. Mit 40 Schritten kann ich vermutlich aber auch leben :) Kevin K. schrieb: > deltaf = f_abtast*N/2 Kann es sein, dass es so heißen muss? deltaf = f_abtast/(N*2) außerdem verstehe ich nicht ganz die 2 in dieser Rechnung: > 256/2*3800/6000=81 Wenn ich es so berechne wie Maxxie, komme ich schon bei 128 Abtastwerten auf die 81.
Maxxie schrieb: > Das bekommst du aber auch nicht mit 64er FFT hin. Dort bekommst du N > Schritte von (inklusive) 0 Hz bis Fabtast/2 hin. Also höchstens bei > Fabtast = 2*6kHz 40 Schritte. (Da du 2200/6000 "wegwerfen" musst, weil > sie dich nicht interessieren) Oder kann es sein, dass ich nur N/2 Schritte bekomme? O.o
Also ich habe mir jetzt mal diese Seite durchgelesen http://paulbourke.net/miscellaneous/dft/ und bin nun schon mal etwas schlauer, wenn auch nicht viel. Etwa auf halber Höhe findet sich dieser C Code. http://paulbourke.net/miscellaneous/dft/fft_ms.c Meint ihr der Code taugt was? Wenn ich es richtig verstehe ist der Code für eine Komplexe Zahlenreihe geschrieben aber wenn ich den Imaginären Teil auf 0 setze, kann ich auch mit meiner Messreihe arbeiten? Macht es Sinn, wenn ich mich auf den Code stürze und auf meine Bedürfnisse ummodel? Ich würde den Wert für m, also die Anzahl der Messwerte fest und y entsprechend auf 0 setzen. Oder kann jemand einen besseren Code empfehlen? An diesem Finde ich angenehm, dass ich auch als Anfänger damit arbeiten kann. Er besteht nicht aus gefühlt 1000 Dateien die ich noch irgendwie einbinden muss... Sorry, falls meine Fragen mal wieder bescheuert sind.
Hallo, Sebastian schrieb: > Gibt es eine > empfehlenswerte Quelle, die das ganze praxisnah erklärt? ich finde das Buch "Fouriertransformation für Fußgänger" von Tilman Butz sehr gut geschrieben. Es beginnt bei Fourierreihen und geht über kontinuierliche und diskrete Fouriertransformation, FFT bis hin zu Anwendungen in der digitalen Datenverarbeitung. Der Autor schafft es mathematisch korrekt darzustellen ohne das ganze in einen Beweiswust ausarten zu lassen und gleichzeitig das erklärte auch immer mit konkreten Beispielen anschaulich zu machen. Sebastian schrieb: > Oder kann jemand einen besseren Code empfehlen? Ich hab ihn mir nicht genau angeschaut, die Tatsache, das er aber mit komplexen Zahlen arbeitet lässt darauf schließen, das er nicht sehr gut geeignet ist, da er doppelt soviel Speicher benötigt, wie ein Algorithmus, der rein reell arbeitet. Gruß Kai
Hallo Kai, danke für den Buchtip - klingt genau richtig für mich. Wenn ich noch lange so im Wald stehe, werde ich mir das mal bestellen :) Trotzdem, falls jemand einen gut und verständlich dokumentierten C-Code kennt oder hat, der auf meine Anwendung passt, her damit! ;) Im Internet finden sich zwar haufenweise Beispiele aber die sind oft für komplexe Werte oder für mich leider nicht gut genug beschrieben.
Bitte 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.