Hallo ihr Spezialisten. Ich bin leider am Gebiet der digitalen Signalverarbeitung ziemlich aus der Übung. Daher kann es sein dass ich hier einigen mit einer "zu einfachen" Frage auf die Nerven gehe. Ich habe aber (schwöre bei meiner Ehre) anderndhalb Stunden in Google gesucht ohne eine definitive Antwort zu finden. Sollte daher jemand durch meine "Dummheit" angestachelt sein mich niederzumachen bitte ich trotzdem zunächst den Benutzern mit Bereitschaft zur Hilfeleistung den Vortritt zu lassen. Also ich habe folgende Anforderung: Mein Mikrocontroller hat noch etwa 20kB RAM übrig mit denen muss ich eine 4096-Punkte (real) FFT (kann nicht kleiner sein!) durchführen. Die Quelldatenbreite sind 16bit. Es wäre ok, wenn die Quelldaten verloren gehen, ein in-place-Algorithmus wäre also ok. Rechengeschwindigkeit ist zunächst nachrangig. Leider konnte ich den genauen Speicherbedarf der verschiedenen Implementationen nicht so leicht finden. Zu CMSIS-DSP hab ich in einem Forum was gefunden: https://ez.analog.com/thread/97376-cmsis-dsp-fft-functionality-increases-size-of-the-project-drastically braucht doch recht viel Platz. Kennt jemand eine Bibliothek mit wenig Speicherverbrauch, idealerweise eine wo man schon im vorhinein ausrechnen kann ob sich das ausgeht. Danke im Voraus!
Speichergeizkragen schrieb: > Leider konnte ich den genauen Speicherbedarf der > verschiedenen Implementationen nicht so leicht finden. Naja, zu einer normalen Radix-2-FFT ist vom Platzbedarf für das Programm her nicht viel dazu; das sind nur drei geschachtelte Schleifen. Bitreversing und Umrechnung auf Betrag/Phase geht nochmal extra, ist aber auch nicht viel. Ein Problem könnten die Koeffizienten (Funktionswerte der Winkelfunktionen; "komplexe Einheitswurzeln") werden; entweder braucht man eine Fließkommabibliothek für die Winkelfunktionen, oder man verwendet CORDIC, oder aber man speichert die Werte tabelliert ab. Im besten Falle muss man nur ein Viertel der Koeffizienten speichern; das sind für eine 4096-Punkte-FFT also 1024 Werte.
Hallo Possetitjel . Leider fühle ich mich nicht fähig eine FFT-Funktion selber zu schreiben, zumindest nicht in vertretbarer Zeit. Entsprechend werde ich eher nicht in den Koeffiziententabellen der Bibliotheken optimieren können...
Speichergeizkragen schrieb: > Leider fühle ich mich nicht fähig eine FFT-Funktion > selber zu schreiben, zumindest nicht in vertretbarer > Zeit. Das hatte ich vermutet; das ging mir auch 25 Jahre lang so :) > Entsprechend werde ich eher nicht in den Koeffiziententabellen > der Bibliotheken optimieren können... Naja, "selber schreiben" und "einen Blick in den Quelltext wagen" sind ja zwei verschiedene Dinge. Wenn die Winkelfunktionswerte bei Bedarf immer wieder neu berechnet werden, dann ist das zwar nicht mehr wirklich "fast", aber man braucht überhaupt keine Koeffiziententabelle -- also fällt dafür auch kein Platzbedarf an. Allerdings ist in diesem Falle eine Fließkommabibliothek notwendig, die die Winkelfunktionen kennt. Das wirst Du ja wissen, was Dir in Deiner Sprache zur Verfügung steht.
puh... Du meinst das ist schaffbar in vertretbaren Aufwand in einer Woche sagen wir mit 6h Schlaf und netto 45Minuten Körperhygiene/tag? Mir wärs recht wenns eine für den Speicherverbrauch optimierte Library geben würde, ist etwas verträglicher, auch für meine Umwelt.
Speichergeizkragen schrieb: > braucht doch recht viel Platz. Dann nimm halt den nächstgrößeren µC aus der Familie. Moderne Cortex-M gibts mit reichlich Flash und RAM. Wenn man nicht grade >>10k Stück verkauft, wäre das preiswerter als eine Woche Entwicklungszeit.
Possetitjel schrieb: > Im besten Falle muss man nur ein Viertel der Koeffizienten > speichern; das sind für eine 4096-Punkte-FFT also 1024 > Werte. ... man braucht nur einen Achtel-Kreis. Überlege einmal warum. Gruß Bernd
Moin, die Frage ist nicht dumm, geht nämlich schon in Details die man typischerweise im Studium nicht lernt. Offene Libraries dazu sind mir ausser der fftw und div. DSP-Implementierungen nicht bekannt, ich fürchte, du musst dich in die Materie etwas reingraben. An Tricksereien diesbezüglich fällt mir folgendes ein: - Sliding DFT - Partielle FFT - Realdaten-Packing (Eingangs-Analogdaten ohne Imaginäranteil) - Auf Radix 4 gehen (Preisfrage: Warum geht hier Radix 8 nicht..) Sollten einige Papers (englisch) zu finden sein. Realdaten-Packen geht mit Standard-Libs a la:
1 | /*---------------------------------------------- |
2 | * FFT fuer Realdaten; packt diese in ein |
3 | * komplexes Array |
4 | * n: Anzahl Werte i |
5 | */ |
6 | |
7 | void fftreal(FFT_FLOAT *r, FFT_COMPLEX *c, int n) |
8 | { |
9 | int i; |
10 | |
11 | for (i = 0; i < (n >> 1); i++) |
12 | { |
13 | c[i]->re = *(r++); |
14 | c[i]->im = *(r++); |
15 | } |
16 | |
17 | fftrow(c); |
18 | fftunscramble(c); |
19 | fftrealtran(c, n); |
20 | } |
:
Bearbeitet durch User
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.