Folgende Aufgabe wird gestellt:
Eine 256 Punkt(Eingabelänge 256 Samples im Realteil,Imagteil wird
ausgenullt!!!) FFT mit einer größe von Typ short(16 Bit mit Vorzeichen)
soll so effektiv wie möglich auf einem Atmega32 (16 Mhz Taktung)
implementiert werden. Ich möchte einfach mal wissen, wo hier der max.
Rekord liegt. Ich habe 35 ms für die normale FFT und 52 ms
für die IFFT gebraucht. Wenn das einer von Euch überbieten kann, so
schreibt
bitte einen Beitrag ,wie er es gemacht hat.
Mit einem PIC (8 Bit Busbreite mit 36 Mhz taktung) hat jemand in
140 ms die IFFT geschaft. Andere 16 Bit Controller brauchen im schnitt
bei 16 Mhz 60 ms für die IFFT.
Ich behaupte einfach mal ,das ich mit den Werten 35 und 52 schon Recht
gut liege. Ein kollege hat mir einen Ansatz genannt, wie ich meinen
Algorithmus nocheinmal um 13 ms verbessern könnte. Ob das klappt
,erfahrt Ihr selbstverständlich auch hier.
Ich freue mich über Eure Vorschläge.
Auf Anfrage gebe ich Euch auch meinen FFT Algorithmus optimiert für
die ATMega8 -128 Reihe.
Hallo Thomas
ich arbeite zwar mit nem Pic, mich würde aber trotzdem Dein Algorithmus
interessieren. Ich arbeite an einem mobilen Messsystem, das online eine
FFT machen soll. Soll also möglichst effektiv sein. Ich habe zwar ne
C-Bibliiotek für FFT, die läuft aber nur auf nem PIC30, aber nicht auf
dem PIC18.
Ich würde mich freuen, wenn Du Deinen mir Deinen Code mailen könntest.
-> gunzelg@arcor.de
Danke im Vorraus
Gerhard
hallo thomas
du schreist:
>Eine 256 Punkt(Eingabelänge 256 Samples im Realteil,Imagteil wird>ausgenullt!!!)
was macht das in der praxis für einen sinn wenn der imaginärteil gleich
null ist? und wäre nicht das berechnen der sinus und cosinus werte ein
teil der erheblich zeit brauchen würde?
gruss
tobias
Das kann doch problemlos sein, wenn du rein reelle Daten hast. Eine
zweidimensionale FFT auf einem reellen Bilddatensatz ist z.B. ein
Beispiel. Bei der IFFT darfst du den Im-Teil natürlich nicht
vernachlässigen, das stimmt.
du schreist:
>Eine 256 Punkt(Eingabelänge 256 Samples im Realteil,Imagteil wird>ausgenullt!!!)
was macht das in der praxis für einen sinn wenn der imaginärteil
gleich
null ist?
Wenn man z.B. einen Audiostream hat und diesen in sein Spektrum
zerlegen will ,dann muß man den Imaginärteil sogar ausnullen ,da es in
der Zeitlichen Wellenformdarstellung nur Zeit und Ampiltude gibt.
und wäre nicht das berechnen der sinus und cosinus werte ein
teil der erheblich zeit brauchen würde?
Nein, den Sinus und Cosinus kann man bequem mit Konstantentabellen
machen g
gruss
tobias
Du solltest dich mal nach den modularen Integer FFT's erhundigen. Diese
FFT's arbeiten mit Primzahlen in modularen Ringen und ermöglichen es
somit vollständig auf Fliekommazahlen zu verzichten. Desweiteren sind
diese Abarten der FFT's die effizientesten die man auf Binärrechnern
umsetzen kann. Durch die Anwendung von Integern und Modulararithmetik
habe diese im Gegensatz zu Fließkommaberechnungen ein Fehler von Null,
sie sind also exakte FFTs.
Es gibt nun verschiedene solche FFTs, zB. Nussbaumer oder die Modulare
Fermat FFT von Schönhage und Strassen. Bei all diesen FFTs müssen
modulare Divisionen durchgeführt werden, also im Grunde langsamme
Disvisionen. Aber beide vorhergenannte FFT's arbeiten mit Modularen
Ringen die auf Primzahlen von spezieller Form aufsetzen. Zb. Fermat
Zahlen wie 2^(2^m)+1 oder 2^(2^m)-1. Eine Modulare Division mit solchen
Zahlen involvieren nur Bit-Shifts und Ausgleichsaddtionen bzw.
Subtraktionen. Somit wurde die langsamme Disvision, vergleichbar mit
den vielen Multiplikation bei Fließkomma FFTs, durch enorm schnelle
Operationen ersetzt. Allgemein kann man sagen das modulare Integer FFTs
ca. 5-10 mal schneller sind als die FFTs in komplexen Zahlen basierend
auf Fließkomma/Festkomma Operationen.
Gruß Hagen
Die wesendliche Änderung besteht in dem Programmteil
"Beschleuniger". In der Ursprungsversion wurde der >>15
Befehl verwendet ,quasi ein Rechtsshift um 15 Stellen.
Da es auf einer Atmel MCU keinen effektiven Assemblerbefehl
dazu gibt, macht der C-Compiler nichts anderes ,als alle
15 shifts mit einer Schleife durchzulaufen und diese beinhaltet auch
noch 17 Assenblerzeilen Code!! Ich habe einfach diesen
Shift 15 durch eine einfache Fallunterscheidung ersetzt.
Das braucht jetzt nur noch ca. 20 Assemblerzeilen ist aber mit
einem Durchlauf beendet. Ich beschäftige mich gerade mit den
Registeroptionen des Compilers und versuche nun das Effektiv mit
Assembleroptionen in den Code einzubinden.
//////// Beschleuniger Start
Ich habe ehrlich gesagt nich soviel Ahnung von FFT usw. suche allerdings
schon seit längerem nach einem schnellen FFT Code um einen Low Cost
Spektum Analyser mit einem kleinen Grafik LCD zu bauen. Daher kam
dieser optimierte Code gerade recht.
Für den ersten Test verwende ich einen berechneten Sinus und lade 1024
Werte in das fr Array. fi lade ich mit Nullen. Der Sinus hat einen
Wertebereich von +/-1000.
Nachdem fix_fft gelaufen ist, enthalten alle Werte im Array (0..255)
irgendwas im Bereich -2 bis 1, aber eigentlich müsste irgendwo eine
deutliche Spitze sein...
Einstellungen:
m=8;
inverse=0;
Habe ich was falsch gemacht, oder muss ich noch irgendwas beachten ?
Jenachdem wie die Phase liegt, können die Zielwerte sowol im
Real als auch im Imagteil liegen. Du mußt, um die Lautstärke zu
ermitteln (abs(r[i]) +abs[i[i])) /2 rechnen. Außerdem kann eine solche
FFT nur exakt einen Sinuston finden, wenn er ein vielfaches
von der Niedrigsten Frequenz ist . Ansonsten fallen Werte zwichen
2 Frequenzen und man kann diese eine Frequenz nicht mehr exakt
bestimmen. Abhilfe dafür schafft z.b. Zero-Padding.
Aber bei einem einzigem Ton müßtest du trotzdem über 1-2
Frequnzen eine deutliche Spitze herausbekommen. Der Fehler leigt
vermutlich woanders. Du mußt natürlich als ArrayLänge 8 und nicht 256
angeben. Villeicht hat du in deiner Sinusfunktion einen fehler.
Um das zu testen nimm einfach mal Sinwave[0..n]. Oder wenn f Sinuston <
f Grundfrequenz ist, dann krigt man natürlich auch kein ergebnis.
Hab jetzt den Fehler behoben (und darüber auch noch den ti=tr-v)
Die Sinuskurve ist auf jedenfall richtig im Array:
fr[i]=1000*sin(i/2);
Das kann ich auch im Debugger nachprüfen.
Die Werte am Ende der FFT (mit zusammengefassten i und r Werten) liegen
dann bei 0-6...
Ich habe mal die Werte am Ende der FFT in den Anhang gepackt.
@Steril
Damit wird ein Signal in die darin enthaltenen einzelnen Frequenzen und
die entsprechende Stärke zerlegt. Speichert man nur die stärksten
Frequenzen, hat man einen mp3 Encoder.
Allerdings kann man mit FFT noch viel mehr machen wie z.B. Primzahlen
berechnen oder sehr, sehr große Zahlen multiplizieren (frag mich aber
bitte nicht wie...)
Eiegntlich ist FFT (Fast Fourier Transformation) nur eine Spezialform
von DFT (Discrete Fourier Transformation)
sieht bei mir ähnlich aus
fi und fr jeweils länge 256
fi setze ich vorher komplett auf 0 fr enthält audio-samples (hab sowohl
musik als auch reinen sinus probiert)
m=8 und inverse=0
die ergebnisse liegen bei 0 bis 3
ich setze vor beginn der fft einen io-pin auf high und hintehrer wieder
auf low. laut oszilloskop dauert also die komplette fft mit 256 punkten
knappe 20ms, kommt mir etwas wenig vor (taktrate 18,432MHz)
Gute Idee mit dem Pin....
Muss ich bei mir auch mal machen.
Ich habe das Programm allerdings nicht auf einem AVR sondern auf einem
16bit Controller M16C mit 24MHz laufen.
hallo thomas
ich habe gerade ein bischen gegoogelt und folgende seite gefunden.
http://www.jjj.de/fft/fftpage.html
dort hat es ein txt file zum downloaden int fft.c, siehe anhang.
ich weiss jetzt halt auch nicht ob das deine homepage ist. wenn ja hut
ab, und gratulation zu der programmierung deiner fft. der code scheint
mit deinem ziemlich identisch zu sein.
nur wegen dem optimierungswettberb
gruss tobias
jup die seite hab ich auch gefunden und mit der int_fft.c nen bissel
rumgespielt
es passiert mehr wie bei obigem code aber so ganz richtig ist das auch
noch nich
Ich habe eine FFT Routine für QBASIC, aus einem simplen mp3 En/dekoder
Programm. Diese geht einwandfrei, nur in C gehts nichtmehr. In QBASIC
habe ich schon oft damit ein Oszilloskop mit Frequenzmessung
programmiert. Ebenso ein Empfänger für den Bereich 100-1MHz. Da konnte
ich mit einer einfachen Antenne, NE592 Videoopamp und einem TDA8703
über 100 MW Sender erkennen...
ich hab eine funktionierende FFT Funktion in C die auf dem AVR läuft nur
benutzt die leider fließkommaoperationen und ist entsprechend langsam
und invertieren kann sie auch nicht das brauch ich aber auch nicht
tobias hofer wrote.....
dort hat es ein txt file zum downloaden int fft.c, siehe anhang.
ich weiss jetzt halt auch nicht ob das deine homepage ist. wenn ja hut
ab, und gratulation zu der programmierung deiner fft. der code scheint
mit deinem ziemlich identisch zu sein.
die int_fft.c Ursprungsversion stammt nicht von mir , sondern ich habe
sie nur etwas abgeändert ,damit sie speziell auf Atmel Controllern
schneller läuft.
so also hab jetzt den originalen sourcecode ohne die optimierungen
genommen und siehe da es funktioniert - wenn auch nich ganz so schnell
50ms bei 18,432MHz mit 256 Punkten.
außerdem hab ich die Sinus-Tabelle ins Flash getan das ist exakt
genauso schnell und sparrt 2kb RAM...
außerdem sollten die werte des eingangssignals den wertebereich des
datentyps halbwegs gut ausnutzen also +/- dürfte wohl etwas wenig sein
Bei mir gehts immer noch nicht...
Ich kann zwar eine Spitze erkennen, die sich auch verschiebt wenn ich
die Frequenz ändere, aber da sind noch mehr SPitzen, dort wo keine
hingehören....
Hallo,
jetzt grab ich den alten Thread wieder aus ;)
Ich verwende auch gerade diese FFT. Ich verstehe nicht was die m=8 bei
dem Funktionsaufruf der FFT bewirkt. Kann mir einer weiterhelfen?
Grüße Andreas
noch ne Frage :)
was für Werte erhält man denn wenn man ein Feld mit 256 Stellen nimmt
und diese von 0 - 255 füllt. sprich feld[20]=20,feld[21]=21 usw.
Oder besser gefragt, wie könnte man die FFT gut testen? Mit konstanten
Zahlen? Was erhalte ich hinter her?
Oh je so viel Fragen ;)
Grüße Andreas
Weißt du überhaupt, was eine FFT ist?
http://www.dspguide.com/
Ich halte es für verkehrt, zu versuchen mit einer Sache
rumzuexperimentieren, wenn ich nicht einmal ihre Grundlagen verstanden
habe.
Hallo Alex,
ich möchte ein Sprachsignal in den Frequenzbereich transformieren um
Untersuchungen in bestimmten Frequenzen vorzunehmen und möchte dafür
die FFT verwenden.
Als Input in diesem Fall wäre, da der A/D Wandler mir ja nur int Werte
liefert, wäre der Realteil (fr[] länge 256) die Daten vom A/D Wandler
und der Imaginärteil 0 (fi[] länge 256) und die FFT vorwärts mit 0.
Aber das m leuchtet mir nicht ein....
Naja ich les mal weiter...
Gruß Andreas
Um die "Spitzen", die "nicht reinpassen" herauszubekommen, kann man
(wenn dir fft richtig funktioniert) noch ein sogenanntes "Windowing"
durchführen. Dabei wird einfach gesagt das Signal ein und ausgeblendet.
Damit werden die Signalsprünge am Anfang und Ende der Datenreihe
geglättet und somit diese hochfrequengen Anteile unterdrückt, die sonst
Aliasing Effekte erzeugen ("Spitzen, die nicht reinpassen").
Wen es interessiert googelt mal nach windowing fft, hanning window,
hamming window oder blackman window. Die Verschieden Arten wirken sich
auf Amplitudentreue oder Phasentreue aus.
Wäre auch interessant hier mal ne schnelle Lösung für nen MC zu haben
;)
@Andreas Siebel
jo das sieht man schön wenn man z.B einen Sinus abtastet und der nicht
100% innerhalb der Window Zeit (tw) liegt. Dann bekommt man noch ne
schöne si(x)-Funktion auf die Maximalwerte der eigentlichen Frequenz
des Sinussignals gelegt. Da wären wir schon wieder beim Thema
Faltung....
> Autor: Benedikt> Datum: 04.08.2004 07:42> Bei mir gehts immer noch nicht...> Ich kann zwar eine Spitze erkennen, die sich auch verschiebt wenn
ich
> die Frequenz ändere, aber da sind noch mehr SPitzen, dort wo keine> hingehören....
Wenn Du ne Sinuswelle reinjagst, die aufm ersten und letzten Sample
einen Nulldurchgang hat und es werden keine "fremden" Frequenzen
angezeigt, dann liegt's wahrscheinlich am Window.
"Es gibt nun verschiedene solche FFTs, zB. Nussbaumer oder die
Modulare
Fermat FFT von Schönhage und Strassen. Allgemein kann man sagen das
modulare Integer FFTs ca. 5-10 mal schneller sind als die FFTs in
komplexen Zahlen basierend auf Fließkomma/Festkomma Operationen."
Kann mir jemand mit einer Quelle helfen, wo diese Algorithmen
beschrieben sind?
vielen dank.
